Misplaced Pages

Disjunctive Datalog

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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. DLV is an implementation of disjunctive Datalog.

Syntax

A disjunctive Datalog program is a collection of rules. A rule is a clause of the form:

a 1 ∨ ⋯ ∨ a n ← b 1 ∧ ⋯ ∧ b m 1 ≤ n , 0 ≤ m {\displaystyle a_{1}\vee \dots \vee a_{n}\leftarrow b_{1}\wedge \dots \wedge b_{m}\quad 1\leq n,0\leq m}

where b 1 {\displaystyle b_{1}} , ..., b m {\displaystyle b_{m}} may be negated, and may include (in)equality constraints.

Semantics

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:

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

Expressivity

This section needs expansion with: 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. These problems are only expressible in Datalog if the polynomial hierarchy collapses.

Implementations

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

See also

Sources

Notes

  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. ^ 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

Category:
Disjunctive Datalog Add topic