We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a WFS for the recent Datalog family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog with negation under the equalityfriendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of E L and of members of the DL-Lite family, as well as corresponding complexity results for query answering.
The recent Datalog family of ontology languages [
The Datalog languages bridge an apparent gap in expressive power between
database query languages and DLs as ontology languages, extending the well-known
Datalog language in order to embed DLs. They also allow for transferring important
concepts and proof techniques from database theory to DLs. For example, it was so far
not clear how to enrich tractable DLs by the feature of nonmonotonic negation. By the
results of [
In this paper, we concentrate on the important problem of defining a WFS for (unrestricted) normal Datalog , i.e., Datalog with existentially quantified variables in rule heads and negations in rule bodies. This new semantics is called the equality-friendly WFS (EFWFS), since it has the crucial advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA.
Since (unrestricted) normal Datalog generalizes positive Datalog , consistency checking and query answering in it is in general undecidable. However, it turns out that the guarded fragment of normal Datalog can be translated to guarded fixed point logic, which is a well-studied decidable formalism. Through this translation, we thus obtain the decidability of consistency checking and query answering in guarded normal Datalog . Furthermore, we obtain upper complexity bounds, which are then also shown to be tight. Guarded Datalog covers in particular the DLs E L and DL-LiteR (which is underlying the OWL 2 QL profile). Therefore, our decidability results and upper complexity bounds carry over to these DLs. The following example illustrates how the WFS can be extended to such DLs.
Example 2 (Holidays) Consider an ABox containing the three holiday destinations Dest(d1), Dest(d2), and Dest(d3). Suppose that any destination that offers the opportunity to swim needs either direct access to the beach (Beach(x)) or a bus connection to some beach (BeachBus(x; y)). That is, at destinations where swimming is possible, we want to make sure that never both not Beach and not 9BeachBus hold. This can be achieved by the following two rules:
(1) (2) Observe also that not Swimming(d) would immediately imply the facts not Beach(d) and not 9BeachBus(d), since it would make it impossible that either of the two axioms could be applied to derive new facts about d.
The following example shows a case where not making the UNA is more appropriate than making it under the WFS.
Example 3 (Company) Suppose we are given certain facts about employees and their employers. The following two concept membership axioms state that John and Sam are employees: Employee(John), Employee(Sam). To these axioms, we add a concept inclusion axiom that maintains that every employee must have an employer: Employee v 9:hasEmployer. Finally, we would like to test whether or not John and Sam work in the same company, which is expressed by the query 9x(hasEmployer(John; x) u not hasEmployer(Sam; x)). Then, under the UNA, equality between all individuals (including new ones) is minimized, and we evaluate the query to true, which is not the case without UNA, where different Skolem terms may be interpreted by the same object. 2
Databases and Queries. We assume (i) an infinite universe of (data) constants D (which constitute the “normal” domain of a database), and (ii) an infinite set of variables V (used in queries and constraints). We denote by X sequences of variables X1; : : : ; Xk with k > 0. We assume a relational schema R, which is a finite set of relation names (or predicate symbols, or simply predicates). A term t is a constant or variable. An atomic formula (or atom) a has the form P(t1; :::; tn), where P is an n-ary predicate, and t1; :::; tn are terms. A conjunction of atoms is often identified with the set of all its atoms.
A database (instance) D for a relational schema R is a (possibly infinite) set of atoms with predicates from R and arguments from D . A conjunctive query (CQ) over R has the form Q(X) = 9Y F (X; Y), where F (X; Y) is a conjunction of atoms with the variables X and Y, and eventually constants. Note that F (X; Y) may also contain equalities but no inequalities. A Boolean CQ (BCQ) over R is a CQ of the form Q(). We often write a BCQ as the set of all its atoms, having constants and variables as arguments, and omitting the quantifiers. Answers to CQs and BCQs are defined via homomorphisms, which are mappings m : D [ V ! D [ V such that (i) c 2 D implies m (c) = c, and (ii) m is naturally extended to atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ Q(X) = 9Y F (X; Y) over a database D, denoted Q(D), is the set of all tuples t over D for which there exists a homomorphism m : X [ Y ! D such that m (F (X; Y)) D and m (X) = t. The answer to a BCQ Q() over a database D is Yes, denoted D j= Q, iff Q(D) 6= 0/ .
Tuple-Generating Dependencies (TGDs). Tuple-generating dependencies (TGDs) describe constraints on databases in the form of generalized Datalog rules with existentially quantified conjunctions of atoms in rule heads; their syntax and semantics are as follows. Given a relational schema R, a tuple-generating dependency (TGD) s is a firstorder formula of the form 8X8Y F (X; Y) ! 9ZY (X; Z), where F (X; Y) and Y (X; Z) are conjunctions of atoms over R, called the body and the head of s , respectively. Such s is satisfied in a database D for R iff, whenever there is a homomorphism h that maps the atoms of F (X; Y) to atoms of D, there is an extension h0 of h that maps the atoms of Y (X; Z) to atoms of D. Since TGDs can be reduced to TGDs with only single atoms in their heads, in the sequel, every TGD has w.l.o.g. a single atom in its head. A TGD s is guarded iff it contains an atom in its body that contains all universally quantified variables of s . The leftmost such atom is the guard of s .
Query answering under TGDs, i.e., the evaluation of CQs and BCQs on databases
under a set of TGDs is defined as follows. For a database D for R, and a set of TGDs
S on R, the set of models of D and S , denoted mods(D; S ), is the set of all (possibly
infinite) databases B such that (i) D B and (ii) every s 2 S is satisfied in B. The set
of answers for a CQ Q to D and S , denoted ans(Q; D; S ), is the set of all tuples a
such that a 2 Q(B) for all B 2 mods(D; S ). The answer for a BCQ Q to D and S is
Yes, denoted D [ S j= Q, iff ans(Q; D; S ) 6= 0/ . Note that query answering under general
TGDs is undecidable [
Negative Constraints. Another crucial ingredient of Datalog for ontological modeling are negative constraints (or simply constraints), which are first-order formulas of the form 8XF (X) ! ?, where F (X) is a conjunction of atoms (not necessarily guarded), called its body. We usually omit the universal quantifiers, and we implicitly assume that all sets of constraints are finite here.
Normal TGDs and BCQs. Normal TGDs are TGDs that may also contain (default-) negated atoms in their bodies: Given a relational schema R, a normal TGD (NTGD) s has the form 8X8Y F (X; Y) ! 9ZY (X; Z), where F (X; Y) is a conjunction of atoms and negated atoms over R, and Y (X; Z) is a conjunction of atoms over R. We usually omit the universal quantifiers. As for standard TGDs, w.l.o.g., Y (X; Z) is a singleton atom. We say s is satisfied in a database D for R iff, whenever there is a homomorphism h for all the variables and constants in the body of s that maps (i) positive literals of F (X; Y) to atoms of D and (ii) no negated atom of F (X; Y) to an atom of D, then there is an extension h0 of h that maps the head atom to an atom of D. We call s guarded iff it contains a positive body atom that contains all universally quantified variables of s . W.l.o.g., constants in the body of guarded s occur only in guards.
We next add negation to BCQs. A normal Boolean conjunctive query (NBCQ) Q is an existentially closed conjunction of atoms and negated atoms 9X p1(X) ^ ^ pm(X) ^ :pm+1(X) ^ ^ :pm+n(X); where m > 1, n > 0, and the variables of the pi’s are among X. Q is covered if for every negative atom a in Q there is a positive atom in Q containing every argument in a. In the sequel, w.l.o.g., NBCQs contain no constants. 3
In this section, we first recall the well-founded semantics (WFS) of normal programs. As a central new contribution, we then introduce a WFS of normal Datalog programs without the UNA.
WFS of Normal Programs. The WFS [
We first give some preliminary definitions. A function-free normal program is a finite set of rules r of the form b1; : : : ; bn; :bn+1; : : : ; :bn+m ! a , where a; b1; : : : ; bn+m are atoms and m; n > 0. We call a the head of r, denoted H(r), while the conjunction b1; : : : ; bn; :bn+1; : : : ; :bn+m constitutes its body. Let B(r) = B+(r) [ B (r), where B+(r) = fb1; : : : ; bng, and B (r) = fbn+1; : : : ; bn+mg. The program is ground if it contains no variables. Let P be a function-free ground normal program. The Herbrand base of P, denoted HBP, is the set of all atoms that can be constructed from the predicate symbols and the constants appearing in P. For all S HBP, we let ::S = f::a j a 2 Sg. We denote by LitP = HBP [ ::HBP the set of all literals with predicate symbols and constants from P. A (three-valued) interpretation relative to P is any set I LitP that is consistent (i.e., there is no atom a 2 HBP with fa; :ag I).
The WFS has many different equivalent definitions (see also [
TP(I) = fH(r) j r 2 P; B+(r)[::B (r) Ig; WP(I) = TP(I) [ ::UP(I): Since WP is monotonic, it has a least fixed point, denoted lfp(WP), which is the wellfounded semantics (WFS) of P, denoted WFS(P). Intuitively, starting with I = 0/ , rules are applied to obtain new positive and negated facts (via TP(I) resp. ::UP(I)). This is repeated until no longer possible.
EFWFS of Normal Datalog Programs. We relate normal Datalog programs to sets of function-free ground normal programs, and define their equality-friendly WFS (EFWFS) as the set of well-founded models of the associated normal programs.
The basic idea is as follows. If we do not make the UNA, different constants in a normal Datalog program P may represent the same value. Thus, P may turn out to be any of the programs P0 obtained from P by identifying constants. Furthermore, in every such program P0, existential quantifiers may introduce one or more value, which, since we do not make the UNA, does not have to be “fresh”, but can be any constant. Hence, without the UNA, the meaning of P may be captured by the set of all normal programs P00 obtained from P by identifying values, and replacing TGDs in P by arbitrary instances, at least one for each possible variable assignment for its body. It is then natural to consider the well-founded models of all those programs P00 as the semantics of P.
More precisely, an instance of a normal TGD F (X; Y) ! 9ZY (X; Z) is a rule of the form F (a; b) ! Y (a; c); where a; b; c are tuples of constants. Let P = D [ S be a normal Datalog program, where D is a database and S a set of normal TGDs. An instance I of P is a normal program consisting of all facts in D, and instances of TGDs in S such that for all TGDs F (X; Y) ! 9ZY (X; Z) in S , and all interpretations a; b for X; Y, there is at least one c such that F (a; b) ! Y (a; c) is in I . Let I (P) be the set of all instances of P, and dom(P) the set of all constants in P. For any m : dom(P) ! D , let Pm be the program obtained from P by replacing all constants c with m(c). Then, the equality-friendly well-founded semantics of P, denoted EFWFS(P), is the set fWFS(P00) j m : dom(P) ! D ; P00 2 I (Pm )g. Query-answering for an NBCQ Q is now defined by saying that Q evaluates to Yes in EFWFS(P) iff Q evaluates to Yes in all elements of EFWFS(P). Here, an NBCQ Q evaluates to Yes in a three-valued interpretation I iff there is a homomorphism that maps all elements of Q+ into atoms in I and all elements of Q into negated atoms in I.
Obviously, A(0) is in the EFWFS of P. Furthermore, because of the second rule, every possible well-founded model of P contains R(0; c1; c2). But we cannot assume c2 6= 0. If c2 = 0, all possible applications of the third rule are blocked, and thus :S(0) would be derived (the last rule may then still add another atom R(d1; d2; 0), but this does not affect the overall result). Otherwise, in case c2 6= 0, the third rule would yield S(0), because clearly we have :A(c2). Therefore, neither S(0) nor its negation is in EFWFS(P) and the only atoms that are always in EFWFS(P) are A(0) and R(0; c1; c2) for some constants c1 and c2 (so, the query 9X1; X2 (R(0; X1; X2)) would evaluate to true). The picture changes, if we add the constraint R(X1; X2; X3); R(X3; X2; X1) !?. Then, c2 generated by the second rule must be different from 0, and so we always obtain S(0), and we get :R(d1; d2; 0), for all d1; d2, by the last rule. 4
The EFWFS can be characterized in terms of guarded fixed point logic. This characterization turns out to be more convenient for reasoning about the EFWFS of guarded normal Datalog programs.
Guarded fixed point logic (GFP), introduced by Grädel and Walukiewicz [
Let R be a relational schema. The set of formulas of GFP over R is built from atomic formulas over R (including equality atoms) using Boolean combinations, and the following two additional formula formation rules:
I. If a is an atomic formula over R containing the variables in X, and y is a GFP formula over R whose free variables occur in a, then 9X (a ^ y) and 8X (a ! y) are GFP formulas over R. The formula a is called guard.
II. Let R be a k-ary predicate, X a k-tuple of variables, and y(R; X) a GFP formula
over R [ fRg whose free variables occur in X, and where R appears only positively
(in the scope of an even number of negation symbols) and not in guards. Then,
[lfpR;X y](X) and [gfpR;X y](X) are GFP formulas over R with free variables X.
As for the semantics of the formulas in II, given a database D for R, y defines an
operator F : P(dom(D)k) ! P(dom(D)k) with F(S) := fa j D j= y(S; a)g. This operator
is monotone and thus has a least fixed point lfp(F) and a greatest fixed point gfp(F).
Then, D j= [lfpR;X y](a) iff a 2 lfp(F), and D j= [gfpR;X y](a) iff a 2 gfp(F).
Example 5 ([
We are now ready to describe the translation of guarded normal Datalog into GFP. Let P = D [ S be a fixed guarded normal Datalog program, where D is a database, and S is a set of guarded NTGDs. Without loss of generality, we assume that P contains only a single predicate R;4 let k be its arity. We construct a GFP sentence efwfs(P) whose models closely correspond to the databases in EFWFS(P). The key is to “existentially quantify” all the instances of NTGDs that we use to compute the WFS, and to mimic the fixed-point definition of the WFS using those instances.
Technically, we represent instances of an NTGD s 2 S using a 2k-ary predicate Ss . If R(U) is the guard of s , and R(V) is its head, then a tuple (a; b) in Ss encodes the instance of s obtained by substituting a and b for U and V, respectively. For example, if s is the NTGD R(X ;Y; 0); :R(X ; 1; 1) ! 9Z R(Z; X ; 2), then the atom Ss ((a; b; 0); (c; a; 2)) represents the instance R(a; b; 0); :R(a; 1; 1) ! R(c; a; 2) of s .
We also use k-ary predicates T , C, T , F, and R, where T is intended to encode a superset of all true atoms; C holds all permutations of tuples in T ; T and F respectively hold the set of all true atoms and the set of all false atoms (the latter relativized to C); and R corresponds to the predicate R of the initial database D. It is not hard to construct GFP sentences that enforce the desired interpretation of the predicates Ss , T , C, and R. Based on those GFP sentences, it is then possible to construct GFP sentences yT and yF that enforce the desired interpretations of T and F. The sentence yT basically does nothing else than defining the (set of all positive literals of the) least fixed point of WP0 , where P0 consists of all instances of NTGDs in S represented by the tuples in the predicates Ss , while yF defines the greatest fixed point of a certain operator, yielding the greatest unfounded set UP0 (T ) (relativized to C).
For an NBCQ Q over fRg, let Q be the BCQ obtained by replacing every positive literal R(X) in Q with T (X), and every negative literal :R(X) in Q with F(X). Lemma 6 For all covered NBCQs Q over the schema of P, we have EFWFS(P) j= Q iff efwfs(P) j= Q . 5
We now take a look at the complexity of answering covered NBCQs over guarded normal Datalog programs P = D [ S . More precisely, we consider the combined complexity, measured in terms of the overall input, including P and the query.
In Section 4, we characterized the EFWFS of guarded normal Datalog programs
via a translation into guarded fixed point logic GFP. From the fact that satisfiability for
GFP sentences is in 2-EXPTIME (and in EXPTIME in case of bounded arities) [
We remark that Theorem 7 carries over to unions of covered NBCQs, that is, queries Q of the form Win=1 Qi, where each Qi is a covered NBCQ. 6
WFS for OWL 2 QL
All the DLs of the DL-Lite family in [
The following definition extends DL-LiteR 5 (underlying the OWL 2 QL profile) and
DL-LiteR;u [
R(a; b) are concept and role membership axioms, respectively.
A DL-LiteR;u;not knowledge base (T ; A ) is a DL-LiteR;not knowledge base iff all inclusion axioms in T contain precisely one positive atom on the left-hand side.
Finally, we define E L not as the extension of E L that allows formulas of the form notC for atomic concepts C = A and for concepts C = 9R:B to occur in top-level conjunctions on the left-hand side of TBox-axioms.
The semantics of DL-LiteR;not (resp., DL-LiteR;u;not) is defined by translating a given
DL-LiteR;not (resp., DL-LiteR;u;not) knowledge base KB into a normal Datalog
program PKB and by computing the well-founded semantics of PKB. The details of the
translation of DL-LiteR;not (resp., DL-LiteR;u;not) into Datalog are an extension of
the translation of DL-LiteR (resp., DL-LiteR;u) given in [
Suppose next that we are additionally given a database with holiday destinations Dest(d1), Dest(d2), and Dest(d3), which we want to be different, i.e., we assume that differentFrom(d1; d2), differentFrom(d2; d3), and differentFrom(d1; d3). We want to formalize the idea that any destination where one can swim should have a beach or a bus to a location with a beach — otherwise one has to take delight in walking. This can be achieved by considering the rules (1) and (2) along with the additional rule
Furthermore, we may assume that at any place where one is not confined to only walking, one can also swim:
Consider the following further facts: WalkingOnly(d1) and BeachBus(d2; d3). Clearly, WalkingOnly(d1) implies that Swimming(d1) cannot be derived — because rule (4), the only rule that can derive Swimming(d1), requires the negation of WalkingOnly(d1) to be true. Thus, the WFS of the knowledge base includes not Swimming(d1). This is in contrast to what would happen if we interpreted not as “classical” negation: in the latter case, we could not derive anything from WalkingOnly(d1), as axiom (4) would trivially be satisfied for d1. Other facts that are derived for d1 are not Beach(d1) and not 9BeachBus(d1) (= not R(x; y) for any y), because the fact not Swimming(d1) implies that rules (1) and (2) cannot be used to derive Beach(d1) or 9BeachBus(d1) (note that we use the fact that d1 has to be different from d2 and d3, because of our ABox assumptions). Concerning the destination d2, the WFS contains the following atoms: not Beach(d2), not WalkingOnly(d2), and Swimming(d2).
The complexity of answering covered NBCQs for any of our DL-Litenot logics and for E L not can now be determined using Theorem 7. Note that Theorem 10 also yields immediate bounds for the complexity of standard DL problems such as instance and satisfiability checking.
Theorem 10 Let L be any of DL-LiteR;u;not, DL-LiteR;not or E L not. Then, given a knowledge base KB = (T ; A ) and an acyclic (resp., general) covered NBCQ Q, deciding whether Q is true under the EFWFS of KB is in EXPTIME (resp., 2-EXPTIME) for combined complexity. (3) (4)
There is already a substantial amount of work on combining rules and ontologies. The
main direction of research so far has been to combine rules and ontologies into
dlprograms consisting of a knowledge base together with a set of rules. This combination
can be carried out in a loose or tight fashion. Representatives of the former are in
particular the dl-programs in [
We achieve the combination of rules and ontologies by a reduction from
description logics to logic programming formalisms. Obviously our work is based on the earlier
work on Datalog . Based on the same idea of translating ontologies into logic
programming rules and hence closely related to our work are [
We have defined the equality-friendly WFS for Datalog with existentially quantified variables in rule heads and negations in rule bodies. Via a translation of its guarded fragment to guarded fixed point logic, we have then proved the decidability in the guarded case, and obtained complexity results for this case. These are important contributions in their own right. In addition, since the approach does not make the UNA, it can be readily used to extend DLs by nonmonotonic negation under the WFS, as illustrated along several DLs, including DL-LiteR , underlying the important OWL 2 QL profile.
Interesting topics for future research include to investigate the data complexity of guarded normal Datalog and to explore how the approach can be extended by keys and to other ontology languages, including OWL 2 EL and OWL 2 RL. Acknowledgments. This work was supported by the EPSRC grant EP/H051511/1 “ExODA: Integrating Description Logics and Database Technologies for Expressive Ontology-Based Data Access”, by the European Research Council under the EU’s 7th Framework Programme (FP7/2007-2013)/ERC grant 246858 (DIADEM), by the European Commission under the EU’s FP7 grant 238975 (SEALS), and by a Yahoo! Research Fellowship. Georg Gottlob is a James Martin Senior Fellow, and also gratefully acknowledges a Royal Society Wolfson Research Merit Award. The work was carried out in the context of the James Martin Institute for the Future of Computing.