We present a family of expressive extensions of Datalog, called Datalog , as a new paradigm for query answering over ontologies. The Datalog family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. In particular, we show that query answering under so-called guarded Datalog is PTIME-complete in data complexity, and that query answering under so-called linear Datalog is in AC0 in data complexity. We also show how negative constraints and a general class of key constraints can be added to Datalog while keeping ontology querying tractable. We then show that linear Datalog , enriched with a special class of key constraints, generalizes the well-known DL-Lite family of tractable description logics. Furthermore, the Datalog family is of interest in its own right and can, moreover, be used in various contexts such as data integration and data exchange. This work is a short version of [8].
Ontologies play a key role in the Semantic Web [
This paper proposes and studies variants of Datalog that are suited for efficient
ontological reasoning, and, in particular, for tractable ontology-based query answering.
We introduce the Datalog family of Datalog variants, which extend plain Datalog
by the possibility of existential quantification in rule heads, and by a number of other
features, and, at the same time, restrict the rule syntax in order to achieve tractability.
In the Datalog family, rules are a restricted form of tuple-generating dependencies
(TGDs) and equality-generating dependencies (EGDs). More specifically, in guarded
Datalog , rules are guarded TGDs (GTGDs), i.e., TGDs with a single atom in the body
that contains all universally quantified variables; in linear Datalog , rules are linear
TGDs (LTGDs), i.e., TGDs that have a single atom in the body. We characterize the
data complexity of query answering for both the above sublanguages of Datalog . We
show that query answering is PTIME-complete and in AC0 (which is the complexity of
evaluating fixed first-order formulas over a database or finite structure), when the query
and the set of GTGDs and LTGDs are fixed, respectively. We then enrich Datalog by
adding negative constraints, which are Horn clauses with a (not necessarily guarded)
conjunction of atoms in their body and the truth constant false, denoted ?, in the head.
We show that the introduction of such constraints does not increase the complexity
of query answering in Datalog . As a further extension, we add non-conflicting keys,
which are special EGDs that do not interact with TGDs, and thus also do not increase
the complexity of query answering in Datalog . We deal only with keys, since this
suffices to capture the most common tractable ontology languages in the literature. The
class of non-conflicting keys is a generalization of the one in [
Further results. We have several other results that, for space reasons, we do not include
here. We refer the reader to [
We briefly recall some basics on databases, queries, TGDs, and the chase. Databases and Queries. We assume (i) an infinite universe of data constants (which constitute the “normal” domain of a database), (ii) an infinite set of (labeled) nulls N (used as “fresh” Skolem terms, which are placeholders for unknown values, and can thus be seen as variables), and (iii) an infinite set of variables X (used in dependencies and queries). Different constants represent different values (unique name assumption), while different nulls may represent the same value. We assume a lexicographic order on [ N , with every symbol in N following all symbols in . 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 predicates). A term t is a constant, null, or variable. An atomic formula (or atom) a has the form P (t1; :::; tn), where P is n-ary predicate, and t1; :::; tn are terms. We denote by dom(a) the set of all its arguments. These notations naturally extend to sets and conjunctions of atoms. Conjunctions of atoms are often identified with the sets of their atoms. A database (instance) D for R is a (possibly infinite) set of atoms with predicates from R and arguments from [ N . Such D is ground iff it contains only atoms with arguments from . A conjunctive query (CQ) over R has the form Q(X) = 9Y (X; Y), where (X; Y) is a conjunction of atoms with the variables X and Y. A Boolean CQ (BCQ) over R is a CQ of the form Q(). Answers to CQs and BCQs are defined via homomorphisms, which are mappings : [ N [ X ! [ N [ X such that (i) c 2 implies (c) = c, (ii) c 2 N implies (c) 2 [ N , and (iii) is naturally extended to atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ Q(X) = 9Y (X; Y) over a database D, denoted Q(D), is the set of all tuples t over for which there exists a homomorphism : X [ Y ! [ N such that ( (X; Y)) D and (X) = t. The answer to a BCQ Q() over D is Yes, denoted D j= Q, iff Q(D) 6= ?.
TGDs. Given a relational schema R, a tuple-generating dependency (TGD) is a
firstorder formula of the form 8X8Y (X; Y) ! 9Z (X; Z), where (X; Y) and (X;
Z) are conjunctions of atoms over R, called the body and the head of , respectively.
We usually omit the universal quantifiers in TGDs. Such is satisfied in a database D
for R iff, whenever there is a homomorphism h that maps the atoms of (X; Y) to
atoms of D, there exists an extension h0 of h that maps the atoms of (X; Z) to atoms
of D. All sets of TGDs are finite here. The notion of query answering under TGDs is
defined as follows. For a set of TGDs on R, and a database D for R, the set of models
of D given , denoted mods( ; D), is the set of all databases B such that B j= D [ .
The set of answers to a CQ Q on D given , denoted ans(Q; ; D), is the set of all
tuples a such that a 2 Q(B) for all B 2 mods( ; D). The answer to a BCQ Q over D
given is Yes, denoted D [ j= Q, iff ans(Q; ; D) 6= ?. Note that query answering
under general TGDs is undecidable [
TGD CHASE RULE. Consider a database D for a relational schema R, and a TGD on R of the form (X; Y) ! 9Z (X; Z). Then, is applicable to D if there exists a homomorphism h that maps the atoms of (X; Y) to atoms of D. Let be applicable, and h1 be a homomorphism that extends h as follows: for each Xi 2 X, h1(Xi) = h(Xi); for each Zj 2 Z, h1(Zj ) = zj , where zj is a “fresh” null, i.e., zj 2 N , zj does not occur in D, and zj lexicographically follows all other nulls already introduced. The application of adds to D the atom h1( (X; Z)) if not already in D.
The important notion of the (derivation) level of an atom in a TGD chase is defined
as follows. Let D be the initial database from which the chase is constructed. Then:
(1) The atoms in D have level 0. (2) Let a TGD (X; Y) ! 9Z (X; Z) be applied at
some point in the construction of the chase, and let h and h1 be as in the TGD chase rule.
If the atom with highest level among those in h1( (X; Y)) has level k, then the added
atom h1( (X; Z)) has level k + 1. The chase algorithm for and D consists of an
exhaustive application of the TGD chase rule in a breadth-first (level-saturating) fashion,
which leads as result to a (possibly infinite) chase for and D, denoted chase( ; D).
The chase of level up to k > 0 for and D, denoted chasek( ; D), is the set of all
atoms in chase( ; D) of level at most k. The (possibly infinite) chase relative to TGDs
is a universal model, i.e., for every B 2 mods( ; D), there exists a homomorphism that
maps chase( ; D) onto B [
We now introduce guarded Datalog as a class of special TGDs that show computational data tractability, while being at the same time expressive enough to model ontologies. BCQs relative to such TGDs can be evaluated on a finite part of the chase of constant size in the data complexity.
A TGD is guarded iff it contains an atom in its body that contains all universally quantified variables of . The leftmost such atom is the guard atom (or guard) of . The non-guard atoms in the body of are the side atoms of .
Example 3.1. The TGD r(X; Y ); s(Y; X; Z) ! 9W s(Z; X; W ) is guarded (via the guard s(Y; X; Z)), while the TGD r(X; Y ); r(Y; Z) ! r(X; Z) is not guarded.
Sets of guarded TGDs (with single-atom heads) are theories in the guarded fragment
of first-order logic [
Given a finite set S [ N , two sets of atoms A1 and r1(a; b) r2(b) aAb2iajerectSio-niso m:oAr1ph[icdo(omr (isAo1m)o!rphAi2c [if dSom=(?A)2i)ffstuhcehretheaxtis(tis) 1 2 and 1 are homomorphisms, and (ii) (c) = c = 1(c) r1(z1; a) r2(a) for all c 2 S. Two atoms a1 and a2 are S-isomorphic (or isomorphic if S = ?) iff fa1g and fa2g are S-isomorphic. The 1 2 notion of S-isomorphism (or isomorphism if S = ?) is nat- r1(z2; z1) r2(z1) urally extended to more complex structures, such as pairs of two subtrees (V1; E1) and (V2; E2) of the guarded chase for- 1 2 est, and two pairs (b1; S1) and (b2; S2), where b1 and b2 are . . . r2(z2) atoms, and S1 and S2 are sets of atoms. The following lemma Fig. 1. Guarded chase shows that if two atoms have S-isomorphic types, then their forest in Example 3.2. subtrees are also S-isomorphic.
The next lemma provides an upper bound for the number of all non-T -isomorphic pairs consisting of an atom and a type.
and a 2 chase( ; D). Let P be a set of pairs (b; S), each consisting of an atom b and a type S of atoms c with arguments from a and new nulls. If jP j > , then P contains at least two dom(a)-isomorphic pairs. = (2w)w 2(2w)w jRj ,
Using the above two lemmas, we are now ready to prove that the atoms in the type of an atom a in the guarded chase forest cannot be generated at a depth of the guarded chase forest that exceeds the depth of the atom a by a value that depends only on the TGDs. Here, the guarded depth of an atom a in the guarded chase forest for and D, denoted depth(a), is the length of the path from D to a in the forest. Note that this is generally different from the derivation level.
depth(b) 6 depth(a) + k, where k depends only on . and D, and b 2 type(a). Then, Proof. Let k = (2w)w 2(2w)w jRj , where w is the maximal arity of a predicate in R. Suppose depth(b) > depth(a) + k for one atom b in the type of a. That is, the path P in the guarded chase forest leading to b has a length greater than k from the depth of a. Suppose first b contains no nulls. By Lemma 3.2, there are two isomorphic atoms h and h0 (in this order) on P with isomorphic types (see Fig. 3). By Lemma 3.1, the subtree of h is isomorphic to the subtree of h0. But then b is also in the subtree of h, on a path Q that is at least one edge shorter than P , which contradicts the assumption that P is the path leading to b. Suppose next the set of nulls N in b is nonempty, and consider the common predecessor c of a and b of largest depth. By Lemma 3.2, there are two N -isomorphic atoms h and h0 (in this order) on P with N -isomorphic types (see Fig. 3). Since b is in the type of a, it cannot contain new nulls compared to a.
level 0 Since c is the common predecessor h c of a and b of largest depth, b also cannot contain new nulls compared to c, and h0 a h thus compared to h and h0. So, b is in the a h0 types of both h and h0. By Lemma 3.1, b the subtree of h is N -isomorphic to the b subtree of h0. But then b is also in the subtree of h, on a path Q that is at least (a) (b) one edge shorter than P , which contradicts the assumption that P is the path Fig. 2. Construction in Lemma 3.3’s proof. leading to b. In summary, all atoms in the type of a can be obtained on paths of length at most k. 2
We next show that BCQs can be evaluated using only a finite, initial portion of the guarded chase forest, whose size is determined by the TGDs only. Here, the guarded chase of level up to k > 0 for and D, denoted g-chasek( ; D), is the set of all atoms in the forest of depth at most k.
into chase( ; D), then there exists a homomorphism that maps Q into g-chasek( ; D), where k depends only on Q and R.
The following definition captures a general property, where also the whole derivation of the query atoms are contained in the finite, initial portion of the guarded chase forest, whose size is determined by the TGDs only.
every database D for R and for every BCQ Q, whenever there exists a homomorphism that maps Q into chase( ; D), then there exists a homomorphism of this kind such that all ancestors of (Q) in the chase graph for and D are contained in gchase g ( ; D), where g depends only on Q and R.
It is not difficult to prove, based on Lemmas 3.3 and 3.4, that guarded TGDs enjoy
the BGDP. Hence, BCQ answering under guarded TGDs is in PTIME in data complexity,
since by the existence of the homomorphism in Lemma 3.4 and in Definition 3.1,
we obtain Q(g-chase g ( ; D)) = Q(chase( ; D)) = ans(Q; ; D). The following
theorem summarizes these and other results from [
TGDs on R, and Q a BCQ Q over R. Then, deciding D [ j= Q is PTIME-complete in data complexity. It can be done in linear time in data complexity for atomic Q. 4
We now introduce linear Datalog as a variant of guarded Datalog , where we prove
that query answering is even FO-rewritable (and thus in AC0) in the data complexity.
Nonetheless, linear Datalog is still expressive enough for representing ontologies [
We first define the bounded derivation-depth property, which is strictly stronger than the bounded guard-depth property.
iff, for every database D for R and for every BCQ Q over R, whenever D [ j= Q, then chase d ( ; D) j= Q, where d depends only on Q and R.
Clearly, in the case of linear TGDs, for every a 2 chase( ; D), the subtree of a is determined only by a, instead of type(a) (cf. Lemma 3.1). Therefore, for a single atom, its depth coincides with the number of applications of the TGD chase rule that are necessary to generate it. By this observation, as an immediate consequence of the fact that guarded TGDs enjoy the BGDP, we obtain that linear TGDs have the bounded derivation-depth property. The next result shows that queries relative to TGDs with the bounded derivation-depth property are FO-rewritable.
As an immediate consequence of the fact that linear TGDs enjoy the BDDP and of Theorem 4.1, we have that BCQs are FO-rewritable in the linear case.
In this section, we extend Datalog with negative constraints and EGDs, which are both important when representing ontologies.
of the form 8X (X) ! ?, where (X) is a (not necessarily guarded) conjunction of atoms. It is often also written as 8X 0(X) ! :p(X), where 0(X) is obtained from (X) by removing the atom p(X). We usually omit the universal quantifiers. Example 5.1. If the unary predicates c and c0 represent two classes, we may use the constraint c(X); c0(X) ! ? to assert that the two classes have no common instances. Similarly, if additionally the binary predicate r represents a relationship, we may use c(X); r(X; Y ) ! ? to enforce that no member of the class c participates to r.
Query answering on a database D under TGDs T and constraints C can be done effortlessly by additionally checking that every constraint = (X) ! ? 2 C is satisfied in D given T , each of which can be done by checking that the BCQ Q = (X) evaluates to false in D given T . We write D [ T j= C iff every 2 C is false in D given T . We thus obtain immediately the following result. Here, a BCQ Q is true in D given T and C , denoted D [ T [ C j= Q, iff (i) D [ T j= Q or (ii) D [ T 6j= C (as usual in DLs).
straints on R, respectively, D be a database for R, and Q be a BCQ on R. Then, D [ T [ C j= Q iff (i) D [ T j= Q or (ii) D [ T j= Q for some 2 C .
The next theorem shows that constraints do not increase the data and combined complexity of answering BCQs in the guarded and linear case. It follows from Theorem 5.1, by which the additional effort of deciding D [ T j= C can be done by answering j C j BCQs Q without constraints, where each query Q has a size of k k 6 k C k, and in the data complexity, j C j and k k are constants. Here, j C j denotes the cardinality of C , while k C k denotes the input size of C . This additional effort does not increase the complexity of answering BCQs without constraints.
straints on R, respectively, D be a database for R, and Q be a BCQ. Then, deciding D [ T [ C j= Q in the guarded (resp., linear) case has the same data and the same combined complexity as deciding D [ T j= Q in the guarded (resp., linear) case.
a first-order formula of the form 8X (X) ! Xi = Xj , where (X), called the body of , is a conjunction of atoms, and Xi and Xj are variables from X. We call Xi = Xj the head of . Such is satisfied in a database D for R iff, whenever there exists a homomorphism h such that h( (X; Y)) D, it holds that h(Xi) = h(Xj ). Example 5.2. The EGD r(X; Y ); r(X; Y 0) ! Y = Y 0 expresses that the second argument of the binary predicate r functionally depends on the first argument of r.
The chase is naturally extended to databases under EGDs in addition to TGDs: The chase of a database D in the presence of two sets T and E of TGDs and EGDs, respectively, denoted chase( T [ E ; D), is computed by iteratively applying (1) a single TGD once, according to the order specified above, and (2) the EGDs, as long as applicable (i.e., until a fixpoint is reached), where EGDs are applied as follows:
EGD CHASE RULE. Consider a database D for a relational schema R, and an EGD on R of the form (X) ! Xi = Xj . Such an EGD is applicable to D iff there exists a homomorphism : (X) ! D such that (Xi) and (Xj ) are different and not both constants. If (Xi) and (Xj ) are different constants, then there is a hard violation of , and the chase fails. Otherwise, the result of the application of to D is the database h(D) obtained from D by replacing every occurrence of a non-constant element e 2 f (Xi); (Xj )g in D by the other element e0 (if e and e0 are both nulls, then e precedes e0 in the lexicographic order).
While adding negative constraints is computationally effortless, adding EGDs is
more problematic. The interaction of TGDs and EGDs leads to undecidability of query
answering even in simple cases, such that of functional and inclusion dependencies [
We now first concentrate on the semantic notion of separability for EGDs, which
formulates a controlled interaction between EGDs and TGDs (and negative constraints),
such that the EGDs do not increase the complexity of answering BCQs. We then provide
a sufficient syntactic condition for the separability of EGDs, where we transfer a result
by [
Definition 5.1. Let R be a relational schema, and T and E be sets of TGDs and EGDs on R, respectively. Then, E is separable from T iff for every database D for R, the following conditions (i) and (ii) are both satisfied: (i) If there is a hard violation of an EGD in chase( T [ E ; D), then there is also a hard violation of some EGD of E , when this EGD is directly applied to D. (ii) If there is no chase failure, then for every BCQ Q, chase( T [ E ; D) j= Q iff chase( T ; D) j= Q.
The following result shows that adding separable EGDs to TGDs and constraints does not increase the data and combined complexity of answering BCQs in the guarded and linear case. It follows immediately from the fact that the separability implies that chase failure can be directly evaluated on D. For fixed (resp., variable) E , this can be done by evaluating a first-order formula on D (resp., in polynomial time in the size of D and E ), which clearly does not increase the data (resp., combined) complexity of answering BCQs in the three cases.
straints on R, respectively, and D be a database for R. Let E be a set of EGDs that is separable from T , and Q be a BCQ. Then, deciding D [ T [ C [ E j= Q in the guarded (resp., linear) case has the same data complexity and also the same combined complexity as deciding D [ T j= Q in the guarded (resp., linear) case.
We next provide a sufficient syntactic condition for the separability of EGDs. We
focus on key dependencies (KDs, or simply keys): a key on a predicate r specifies a set
K of key attribute positions of r; it is satisfied in a database D if no two atoms in D of
the form r(t) have the same values in all positions in K. Clearly, KDs are special types
of EGDs. The EGD chase rule in case of a KD applies to pairs of tuples that violate
the KD. For example, a KD asserting that the key attribute of a ternary predicate r is
the first one is applicable to the instance D = fr(a; b; z3); r(a; z2; z1)g (where the zi’s
are nulls), and its application yields the new instance fr(a; b; z1)g. The following
definition generalizes the notion of “non-key-conflicting” dependency relative to a set of
keys, introduced in [
2 Definition 5.2. Let be a key, and be a TGD of the form (X; Y) ! 9Z r(X; Z). Then, is non-conflicting (NC) with iff either (i) the key does not apply to the predicate r in the head of or (ii) the positions of in r are not a proper subset of the X-positions in r in the head of , and every existentially quantified variable in appears only once in the head of . We say is non-conflicting (NC) with a set of TGDs
T iff is NC with every 2 T . We say a set of keys K is non-conflicting (NC) with T iff every K is NC with T .
Example 5.3. Consider the four keys 1, 2, 3, and 4 defined by the key attribute sets
K1 = fr[
The following theorem shows that the NC property between keys and TGDs implies
their separability. This generalizes a useful result of [
respectively, such that K is NC with T . Then,
We conclude this section by stating that in the NC case, keys do not increase the data and the combined complexity of answering BCQs under guarded (resp., linear) TGDs and constraints. This result is immediate by Theorems 5.4 and 5.3.
straints on R, respectively, and D be a database for R. Let E be a set of EGDs that is NC with T , and Q be a BCQ. Then, deciding D [ T [ C [ E j= Q in the guarded (resp., linear) case has the same data complexity and also the same combined complexity as deciding D [ T j= Q in the guarded (resp., linear) case. 6
In [
A = fScientist; Article; ConPaper; JouPaperg;
RA = fhasAuthor; hasFirstAuthor; isAuthorOfg; I = fi1; i2g: The following are concept inclusion axioms, which informally express that (i) conference and journal papers are articles, (ii) conference papers are not journal papers, (iii) every scientist has a publication, (iv) isAuthorOf relates scientists and articles:
The following role inclusion and functionality axioms express that (v) isAuthorOf is the inverse of hasAuthor, and (vi) hasFirstAuthor is a functional binary relationship: isAuthorOf v hasAuthor; hasAuthor v isAuthorOf; (funct hasFirstAuthor): Finally, the concept and role membership axioms Scientist(i1), isAuthorOf(i1; i2), and Article(i2) express that the individual i1 is a scientist who authors the article i2.
Then, the concept inclusion axioms are translated to the following TGDs and constraints (where we identify atomic concepts and roles with their predicates):
The role inclusion and functionality axioms are translated to these TGDs and EGDs: isAuthorOf(Y; X) ! hasAuthor(X; Y ); hasAuthor(Y; X) ! isAuthorOf(X; Y ); hasFirstAuthor(X; Y ); hasFirstAuthor(X; Y 0) ! Y = Y 0: Finally, the three concept and role membership axioms are translated to the three database atoms Scientist(i1), isAuthorOf(i1; i2), and Article(i2), respectively (where we also identify individuals with their constants). Acknowledgments. The work of A. Cal`ı and G. Gottlob was supported by the EPSRC grant Number EP/E010865/1 “Schema Mappings and Automated Services for Data Integration”. G. Gottlob, whose work was partially carried out at the Oxford-Man Institute of Quantitative Finance, gratefully acknowledges support from the Royal Society as the holder of a Royal Society-Wolfson Research Merit Award. T. Lukasiewicz’s work was supported by the German Research Foundation under the Heisenberg Programme.