Disjunctive Datalog is an extension of the logic programming language Datalog that allows disjunctions in the heads of rules.
Disjunctive Datalog has been applied in the context of reasoning about ontologies in the semantic web.
A disjunctive Datalog program is a collection of rules.
There are at least three ways to define the semantics of disjunctive Datalog:[3] 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.