Disjunctive Datalog
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
A disjunctive Datalog program is a collection of rules. A Template:Dfni is a clause of the form:[2]
- [math]\displaystyle{ a_1 \vee \dots \vee a_n \leftarrow b_1 \wedge \dots \wedge b_m \quad 1 \leq n, 0 \leq m }[/math]
where [math]\displaystyle{ b_1 }[/math], ..., [math]\displaystyle{ b_m }[/math] may be negated, and may include (in)equality constraints.
Semantics
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
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
The DLV (DataLog with Disjunction, where the logical disjunction symbol V is used) system implements the disjunctive stable model semantics.[4]
See also
Sources
Notes
- ↑ Kaminski, Mark; Nenov, Yavor; Grau, Bernardo Cuenca (2014-06-21). "Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 28 (1). doi:10.1609/aaai.v28i1.8854. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/8854.
- ↑ Eiter, Gottlob & Mannila 1997, p. 370.
- ↑ 3.0 3.1 Eiter, Gottlob & Mannila 1997.
- ↑ 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, ISBN 978-3-642-24205-2, http://dx.doi.org/10.1007/978-3-642-24206-9_17, retrieved 2023-08-04
References
- Eiter, Thomas; Gottlob, Georg; Mannila, Heikki (1997-09-01). "Disjunctive datalog". ACM Transactions on Database Systems 22 (3): 364–418. doi:10.1145/261124.261126. ISSN 0362-5915. https://doi.org/10.1145/261124.261126.
 |  |
