Disjunctive Datalog is an extension of the logic programming language Datalog that allows disjunctions in the heads of rules. This extension enables disjunctive Datalog to express several NP-hard problems that are not known to be expressable in plain Datalog. Disjunctive Datalog has been applied in the context of reasoning about ontologies in the semantic web. [1] DLV is an implementation of disjunctive Datalog.
A disjunctive Datalog program is a collection of rules. A rule is a clause of the form: [2]
where , ..., may be negated, and may include (in)equality constraints.
![]() | This section needs expansion. You can help by adding to it. (March 2023) |
There are at least three ways to define the semantics of disjunctive Datalog: [3]
![]() | This section needs expansionwith: examples of programs expressing these problems. You can help by adding to it. (March 2023) |
Disjunctive Datalog can express several NP-complete and NP-hard problems, including the travelling salesman problem, graph coloring, maximum clique problem, and minimal vertex cover. [3] These problems are only expressible in Datalog if the polynomial hierarchy collapses.
The DLV (DataLog with Disjunction, where the logical disjunction symbol V is used) system implements the disjunctive stable model semantics. [4]