Disjunctive Datalog#Implementations

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.{{Cite journal |last1=Kaminski |first1=Mark |last2=Nenov |first2=Yavor |last3=Grau |first3=Bernardo Cuenca |date=2014-06-21 |title=Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning |url=https://ojs.aaai.org/index.php/AAAI/article/view/8854 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |language=en |volume=28 |issue=1 |doi=10.1609/aaai.v28i1.8854 |s2cid=17098158 |issn=2374-3468|arxiv=1404.3141 }} DLV is an implementation of disjunctive Datalog.

Syntax

A disjunctive Datalog program is a collection of rules. A {{dfni|rule}} is a clause of the form:{{sfn|Eiter|Gottlob|Mannila|1997|p=370}}

: $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$ , ..., $b_m$ may be negated, and may include (in)equality constraints.

Semantics

There are at least three ways to define the semantics of disjunctive Datalog:{{sfn|Eiter|Gottlob|Mannila|1997}}

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

Expressivity

{{expand section|date=March 2023|with=examples of programs expressing these problems}}

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.{{sfn|Eiter|Gottlob|Mannila|1997}} 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.{{Citation |last1=Alviano |first1=Mario |title=The Disjunctive Datalog System DLV |date=2011 |url=http://dx.doi.org/10.1007/978-3-642-24206-9_17 |work=Datalog Reloaded |pages=282–301 |access-date=2023-08-04 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |isbn=978-3-642-24205-2 |last2=Faber |first2=Wolfgang |last3=Leone |first3=Nicola |last4=Perri |first4=Simona |last5=Pfeifer |first5=Gerald |last6=Terracina |first6=Giorgio|doi=10.1007/978-3-642-24206-9_17 }}

Sources

= Notes =

= References =

{{Cite journal |last1=Eiter |first1=Thomas |last2=Gottlob |first2=Georg |last3=Mannila |first3=Heikki |date=1997-09-01 |title=Disjunctive datalog |journal=ACM Transactions on Database Systems |volume=22 |issue=3 |pages=364–418 |doi=10.1145/261124.261126 |s2cid=8755376 |issn=0362-5915|doi-access=free }}

Category:Logic programming languages