Edinburgh Research Explorer
Datalog+/-: Questions and Answers
Citation for published version:
Gottlob, G, Lukasiewicz, T & Pieris, A 2014, Datalog+/-: Questions and Answers. in Principles of Knowledge
Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna,
Austria, July 20-24, 2014. pp. 682-685. <http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/7965>
Link:
Link to publication record in Edinburgh Research Explorer
Document Version:
Publisher's PDF, also known as Version of record
Published In:
Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International
Conference, KR 2014, Vienna, Austria, July 20-24, 2014
General rights
Copyright for the publications made accessible via the Edinburgh Research Explorer is retained by the author(s)
and / or other copyright owners and it is a condition of accessing these publications that users recognise and
abide by the legal requirements associated with these rights.
Take down policy
The University of Edinburgh has made every reasonable effort to ensure that Edinburgh Research Explorer
content complies with UK legislation. If you believe that the public display of this file breaches copyright please
contact openaccess@ed.ac.uk providing details, and we will remove access to the work immediately and
investigate your claim.
Download date: 08. Dec. 2021
, Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning
Datalog+/–: Questions and Answers
Georg Gottlob and Thomas Lukasiewicz and Andreas Pieris
Department of Computer Science, University of Oxford, UK
firstname.lastname@cs.ox.ac.uk
• What is Datalog± and what are its advantages? answer is, accordingly, true or false. Other relevant reason-
Datalog± is a rule-based formalism that combines the ad- ing tasks are instance checking, query containment and con-
vantages of logic programming in Datalog with features for sistency (or satisfiability) checking. These latter tasks are,
expressing ontological knowledge and advanced data mod- however, easily reduced to Boolean query answering.
eling constraints. Datalog± provides a uniform framework
• Which are the main decidable Datalog± languages?
for query answering and reasoning with incomplete data.
It generalizes disparate other KR formalisms such as plain There are so far three main paradigms which extend plain
Datalog, description logics (DLs), in particular, DL-Lite and Datalog with existential quantifiers in rule heads, and also
EL, F-Logic Lite, highly relevant fragments of UML class guarantee the decidability of query answering:
diagrams, data-exchange formalisms, graph query languages Weakly-acyclic Datalog± , based on weakly acyclic tgds
such as SPARQL, and so on. Datalog± is a conceptually introduced in the context of data exchange (Fagin et al.
very simple and clear cut formalism that extends plain Dat- 2005), guarantees the existence of a finite universal model,
alog with features such as existential quantifiers, equalities, which in turn implies the decidability of query answering.
and the falsum (⊥) in rule heads and, at the same time, re- The rules {σ2 , σ3 , σ4 } given above form a weakly-acyclic
stricts the rule syntax so as to achieve decidability and, when set of Datalog± rules. Extensions of weak-acyclicity have
required, tractability. Its closeness to logic programming al- been studied, e.g., in (Marnette 2009; Grau et al. 2013).
lowed us to enrich it by non-monotonic negation under the Guarded Datalog± ensures the existence of treelike uni-
stratified, well-founded, and stable model semantics. versal models, which in turn implies the decidability of
query answering (Calı̀, Gottlob, and Kifer 2013). A rule
• How do Datalog± rules look like? is guarded if it has an atom which contains all the body-
A self-explanatory set of Datalog± rules follows: variables; e.g., the rules {σ1 , σ2 , σ4 }. An important subclass
of guarded Datalog± is linear Datalog± , where rules have
σ1 : emp(X) → ∃Y hasMgr (X, Y ), emp(Y ), only one body-atom, e.g., the rules {σ1 , σ4 }. Extensions of
σ2 : hasMgr (X, Y ), emp(X) → emp(Y ), guardedness have been studied in (Baget et al. 2011).
σ3 : emp(X), emp(Y ) → colleagueOf (X, Y ), Sticky Datalog± guarantees the termination of back-
σ4 : emp(X) → ∃Y worksIn(X, Y ), dept(Y ). ward resolution, and thus the decidability of query answer-
Such rules are also known as tuple-generating dependencies ing (Calı̀, Gottlob, and Pieris 2012). The key idea underlying
(tgds). All variables that are not existentially quantified are stickiness is that the body-variables which are in a join al-
assumed to be universally quantified. We just omit the uni- ways are propagated (or “stick”) to the inferred atoms; e.g.,
versal quantifiers in front of such rules. As will be pointed the set of rules {σ1 , σ3 , σ4 }. The main goal of stickiness
out later, Datalog± rules may also contain equalities and the was the definition of a language that allows for joins in rule-
falsum symbol (⊥) in their heads. bodies, which are not always expressible via guarded rules.
Interestingly, the consolidation of the above paradigms
• Which reasoning tasks are considered with Datalog± ? leads to more expressive decidable formalisms. Notable ex-
The main reasoning task is query answering under the so- amples are glut-guardedness (Krötzsch and Rudolph 2011),
called certain-answers semantics. If Q(X) is a conjunctive obtained by combining weak-acyclicity and guardedness,
query (CQ) or a union of conjunctive queries (UCQ) with weak-stickiness (Calı̀, Gottlob, and Pieris 2012), obtained
free variables X, D a database over a domain (universe) by joining weak-acyclicity and stickiness, and tameness, ob-
∆ whose tuples are interpreted in the usual way as ground tained by combining guardedness and stickiness (Gottlob,
facts, and Σ a Datalog± program (a.k.a. Datalog± ontology), Manna, and Pieris 2013). Another important language is shy
then the answer to Q consists of all those tuples a of ∆- Datalog± (Leone et al. 2012).
elements such that D ∪ Σ |= Q(a). For Boolean queries, the
• What about equalities and the falsum (⊥) in rule heads?
Copyright c 2014, Association for the Advancement of Artificial Weakly-acyclic Datalog± can be safely combined with ar-
Intelligence (www.aaai.org). All rights reserved. bitrary equality rules, a.k.a. equality-generating dependen-
682
