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.

Syntax

edit

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.

Semantics

edit

There are at least three ways to define the semantics of disjunctive Datalog:[3]

  • Minimal model semantics
  • Perfect model semantics
  • Disjunctive stable model semantics, which generalizes the stable model semantics

Expressivity

edit

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.

Implementations

edit

The DLV (DataLog with Disjunction, where the logical disjunction symbol V is used) system implements the disjunctive stable model semantics.[4]

See also

edit

Sources

edit

Notes

edit
  1. ^ Kaminski, Mark; Nenov, Yavor; Grau, Bernardo Cuenca (2014-06-21). "Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence. 28 (1). arXiv:1404.3141. doi:10.1609/aaai.v28i1.8854. ISSN 2374-3468. S2CID 17098158.
  2. ^ Eiter, Gottlob & Mannila 1997, p. 370.
  3. ^ a b Eiter, Gottlob & Mannila 1997.
  4. ^ Alviano, Mario; Faber, Wolfgang; Leone, Nicola; Perri, Simona; Pfeifer, Gerald; Terracina, Giorgio (2011), "The Disjunctive Datalog System DLV", Datalog Reloaded, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 282–301, doi:10.1007/978-3-642-24206-9_17, ISBN 978-3-642-24205-2, retrieved 2023-08-04

References

edit