We consider the setting of ontological database access, where an Abox is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a T -box formulated in DLLite or Linear Datalog . It is well-known that ( ; q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of and q. This gives rise to the interesting question of whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate ( ; q) into a polynomially sized equivalent nonrecursive Datalog program P .
? Future improvements and extended versions of this paper will be published in arXive-CORR
at http://arxiv.org/abs/1106.3767
setting where ontological constraints are formulated in terms of tuple-generating
dependencies (tgds), and we make heavy use of the well-known chase procedure [
Consider a set of tgds and a database D over a joint signature R. Let q be a Boolean conjunctive query (BCQ) issued against (D; ). We would like to transform q into a nonrecursive Datalog query P such that (D; ) j= q iff D j= P . We assume here that P has a special propositional goal goal, and D j= P means that goal is derivable from P when evaluated over D. Let us define an important property of classes of tgds. Definition 1. Polynomial witness property (PWP). The PWP holds for a class C of tgds if there exists a polynomial such that, for every finite set C of tgds and each BCQ q, the following holds: for each database D, whenever (D; ) j= q, then there is a sequence of at most (j j; jqj) chase steps whose atoms already entail q.
Our main technical result, which is more formally stated in Section 3, is as follows. Theorem 1. Let be a set of tgds from a class C enjoying the PWP. Then each BCQ q can be rewritten in polynomial time into a nonrecursive Datalog program P of size polynomial in the joint size of q and , such that for every database D, (D; ) j= q if and only if D j= P . Moreover, the arity of P is max(a + 2; 9), where a is the maximum arity of any predicate symbol occurring in , in case a sufficiently large linear order can be accessed in the database, or otherwise by O(max(a + 2; 9) log m), where m is the joint size of q and .
Other Results. From this result, and from already established facts, a good number
of further rewritabliity results for other formalisms can be derived. In particular, we can
show that conjunctive queries based on other classes of tgds or description logics can
be efficiently translated into nonrecursive Datalog. Among these formalisms are: linear
tgds, originally defined in [
Structure of the Paper. The rest of the paper is structured as follows. In Section 2 we state a few preliminaries and simplifying assumptions. In Section 3, we explain the idea of the proof of the main result. Section 4, contains the other results following from the main result. A brief overview of related work concludes the paper in Section 5. 2
We assume the reader to be familiar with the terminology of relational databases and
the concepts of conjunctive query (CQ) and Boolean conjunctive query (BCQ). For
simplicity, we restrict our attention to Boolean conjunctive queries q. However, our
results can easily be reformulated for queries with output, see the extended version of
this paper [
Given a relational schema R, a tuple-generating dependency (tgd) is a first-order
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 , denoted body ( )
and head ( ), respectively. We usually omit the universal quantifiers in tgds. Such is
satisfied in a database D for R iff, whenever there exists 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. We assume in the rest
of the paper that every tgd has exactly one atom and at most one existentially quantified
variable in its head. A set of tgds is in normal form if the head of each tgd consists
of a single atom. It was shown in [4, Lemma 10] that every set of TGDs can be
transformed into a set 0 in normal form of size at most quadratic in j j, such that
and 0 are equivalent with respect to query answering. The normal form transformation
shown in [
For a database D for R, and a set of tgds on R, the set of models of D and , denoted mods(D; ), is the set of all (possibly infinite) databases B such that (i) D B and (ii) every 2 is satisfied in B. The set of answers for a CQ q to D and , 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 for a BCQ q to D and is yes iff the empty tuple is in ans(q; D; ), also denoted as D [ j= q.
Note that, in general, query answering under tgds is undecidable [
The chase procedure [
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 to D, 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 value (i.e., a Skolem constant) different from all nulls already introduced. The application of on D adds to D the atom h1( (X; Z)) if not already in D (which is possible when Z is empty).
The chase algorithm for a database D and a set of tgds 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 D and . Each atom from the database D is assigned a derivation level. Atoms in D have derivation level 0. If an atom has not already derivation level i but can be obtained by a single application of a tgd via the chase rule from atoms having derivation level i, then its derivation level is i + 1. The set of all atoms of derivation level k is denoted by chasek(D; ). The chase of D relative to , denoted chase(D; ), is then the limit of chasek(D; ) for k ! 1.
The (possibly infinite) chase relative to tgds is a universal model, i.e., there exists
a homomorphism from chase(D; ) onto every B 2 mods(D; ) [
A chase sequence of length n based on D and is a sequence of n atoms such that each atom is either from D or can be derived via a single application of some rule in from previous atoms in the sequence. If S is such a chase sequence and q a conjunctive query, we write S j= q if there is a homomorphism from q to the set of atoms of S.
We assume that every database has two constants, 0 and 1, that are available via the unary predicates Zero and One, respectively. Moreover, each database has a binary predicate Neq such that Neq(a; b) is true precisely if a and b are distinct values.
We finally define N -numerical databases. Let D be a database whose domain does not contain any natural numbers. We define DN as the extension of D by adding the natural numbers 0; 1; : : : ; N to its domain, a unary relation Num that contains exactly the numbers 1; : : : ; N , binary order relations Succ and < on 0; 1; : : : ; N , expressing the natural successor and “<” orders on N , respectively. 3 We refer to DN as the N -numerical extension of D, and, a so extended database as N -numerical database. We denote the total domain of a numerical database DN by domN (D) and the nonnumerical domain (still) by dom(D). Standard databases can always be considered to be N -numerical, for some large N by the standard type integer, with the < predicate (and even arithmetic operations). A number maxint corresponding to N can be defined. 3
Theorem 1. Let C be a class of tgds in normal form, enjoying the polynomial witness property and let be the polynomial bounding the number of chase steps (with (n1; n2) max(n1; n2), for all naturals n1; n2). For each set C of tgds and each Boolean CQ q, one can compute in polynomial time a nonrecursive Datalog program P of polynomial size in j j and jqj, such that, for every database D it holds D; j= q if and only if D j= P . Furthermore: (a) For N -numerical databases D, where N (j j; jqj), the arity of P is max(a + 2; 9), where a is the maximum arity of any predicate symbol occurring in ; (b) otherwise (for non-numerical databases), the arity of P is O(max(a + 2; 9) log (j j; jqj)), where a is as above.
We note that N is polynomially bounded in j j and jqj by the polynomial that
only depends on C. The rest of this section explains the basic ideas of the proof of this
result. A more detailed proof is given in [
High-level idea of the proof. We first describe the high level idea of the construction of the Datalog program P . It checks whether there is a chase sequence S = t1; : : : ; tN with respect to D and and a homomorphism h from q to (the set of atoms of) S. To this end, P consists of one large rule rgoal of polynomial size in N and some shorter rules that define auxiliary relations and will be explained below.
The aim of rgoal is to guess the chase sequence S and the homomorphism q at the same time. We recall that N does not depend on the size of D but only on j j and jqj and thus rgoal can well be as long as the chase sequence and q together. One of the advantages of this approach is that we only have to deal with those null values that are actually relevant for answering the query. Thus, at most N null values need to be represented. 3 Of course, if dom(D) already contains some natural numbers we can add a fresh copy of f0; 1; : : : ; N g instead.
One might try to obtain rgoal by just taking one atom Ai for each tuple ti of S and one atom for each atom of q and somehow test that they are consistent. However, it is not clear how consistency could possibly be checked in a purely conjunctive fashion.4 There are two ways in which disjunctive reasoning is needed. First, it is not a priori clear on which previous tuples, tuple ti will depend. Second, it is not a priori clear to which tuples of S the atoms of q can be mapped.
To overcome these challenges we use the following basic ideas. (1) We represent the tuples of S (and the required tuples of D) in a symbolic fashion, utilizing the numerical domain. (2) We let P compute auxiliary predicates that allow us to express disjunctive relationships between the tuples in S.
Example 1. We illustrate the proof idea with a very simple running example, shown in Figure 1.
(a) : 1: R1(X; Y ) ! 9Z R4(X; Y; Z) 2: R2(Y; Z) ! 9X R4(X; Y; Z) 3: R3(X; Z) ! 9Y R4(X; Y; Z) 4: R4(X1; Y1; Z1); R4(X2; Y2; Z2) ! R5(X1; Z2) (b) q : R5(X; Y ); R3(Y; X) (c) D :
R1 a b c d
R2 e g
R3 g a g h
A possible chase sequence in this example is shown in Figure 2(a). The mapping X 7! a and Y 7! g, maps R5(X; Y ) to t5 and R3(Y; X) to t6, thus satisfying q. (a) – t1: R1(a; b) – t2: R4(a; b; ?2) – t3: R2(e; g) – t4: R4(?4; e; g) – t5: R5(a; g) – t6: R3(g; a) (b) – t1: R1(a; b; a) – t2: R4(a; b; ?2) – t3: R2(e; g; e) – t4: R4(?4; e; g) – t5: R5(a; g; a) – t6: R3(g; a; g) i ri fi xi1 xi2 xi3 si ci1 ci2 1 1 0 a b a 0 0 0 2 4 1 a b 2 1 1 1 (c) 3 2 0 e g e 0 0 0 4 4 1 4 e g 2 3 3 5 5 1 a g a 4 2 4 6 3 0 g a g 0 0 0
Notation and conventions. Let C be a class of tgds enjoying the PWP, let be a set of tgds from C, and let q be a BCQ. Let R1; : : : Rm be the predicate symbols occurring in or in q. We denote the number of tgds in by `. 4 Furthermore, of course, there are no relations to which the atoms Ai could possible be matched.
Let N := (j j; jqj) where is as in Definition 1, thus N is polynomial in j j and jqj. By definition of N , if (D; ) j= q, then q can be witnessed by a chase sequence of length N . Our assumption that (n1; n2) max(n1; n2), for every n1; n2, guarantees that N is larger than (i) the number of predicate symbols occurring in , (ii) the cardinality jqj of the query, and (iii) the number of rules in .
For the sake of a simpler presentation, we assume that all relations in have the same arity a and all rules use the same number k of tuples in their body. The latter can be easily achieved by repeating tuples, the former by filling up shorter tuples by repeating the first tuple entry. Furthermore, we only consider chase sequences of length N . Shorter sequences can be extended by adding tuples from D.
Example 2. Example 1 thus translates as illustrated in Figure 3. The (extended) chase sequence is shown in Figure 2 (b). The query q is now satisfied by the mapping X 7! a, Y 7! g, U 7! g, V 7! a, thus mapping R5(X; Y; X) to t5 and R3(Y; X; Y ) to t6. (a) : 1: R1(X; Y; X); R1(X; Y; X) ! 9Z R4(X; Y; Z) (b) q : R5(X; Y; U ); R3(Y; X; V ) 2: R2(Y; Z; Y ); R2(Y; Z; Y ) ! 9X R4(X; Y; Z) (c) D : 3: R3(X; Z; X); R3(X; Z; X) ! 9Y R4(X; Y; Z) R1 R2 R3 4: R4(X1; Y1; Z1); R4(X2; Y2; Z2) ! a b a e g e g a g
R5(X1; Z2; X1) c d c g h g
Proof idea (continued). On an abstract level, the atoms that make up the final rule rgoal of P can be divided into three groups serving three different purposes. That is, rgoal can be considered as a conjunction rtuples ^ rchase ^ rquery. Each group is “supported” by a sub-program of P that defines relations that are used in rgoal, and we refer to these three subprograms as Ptuples, Pchase and Pquery, respectively.
– The purpose of rtuples is basically to lay the ground for the other two. It consists of
N atoms that allow to guess the symbolic encoding of a sequence S = t1; : : : ; tN . – The atoms of rchase are designed to verify that S is an actual chase sequence with respect to D. – Finally, rquery checks that there is a homomorphism from q to S.
Ptuples and rtuples. The symbolic representation of the tuples ti of the chase sequence S uses numerical values to encode null values, predicate symbols Ri (by i), tgds j 2 (by j) and the number of a tuple ti in the sequence (that is: i).
In particular, the symbolic encoding uses the following numerical parameters.5 – ri to indicate the relation Rri to which the tuple belongs; – fi to indicate whether ti is from D (fi = 0 ) or yielded by the chase ( fi = 1);
– Furthermore, xi1; : : : ; xia represent the attribute values of ti as follows. If the jth attribute of ti is a value from dom(D) then xij is intended to be that value, otherwise it is a null represented by a numeric value.
Since each rule of has at most one existential quantifier in its head, at each chase step, at most one new null value can be introduced. Thus, we can unambiguously represent the null value (possibly) introduced in the j-th step of the chase by the number j.
The remaining parameters si and ci1; : : : ; cik are used to encode information about the tgd and the tuples (atoms) in S that are used to generate the current tuple. More precisely, si is intended to be the number of the applied tgd si and ci1; : : : ; cik are the tuple numbers of the k tuples that are used to yield ti. In the example, e.g., t5 is obtained by applying 4 to t2 and t4. The encoding of our running example can be found in Figure 2 (c).
We use a new relational symbol T of arity a + k + 4 not present in the schema of D for the representation of the tuples from S. Thus, rtuples is just: T (1; r1; f1; x11; : : : ; x1a; s1; c11; : : : ; c1k); : : :;
T (N; rN ; fN ; xN1; : : : ; xNa; sN ; cN1; : : : ; cNk).
The sub-program Ptuples is intended to “fill” T with suitable tuples. Basically, T contains all encodings of tuples in D (with fi = 0) and all syntactically meaningful tuples corresponding to possible chase steps (with fi = 1).
Pchase and rchase. The following kinds of conditions have to be checked to ensure that the tuples “guessed” by rtuples constitute a chase sequence. (1) For every i, the relation Rri of a tuple ti has to match the head of its rule si .
– In the example, e.g., r4 has to be 4 as the head of 2 is an R4-atom. (2) Likewise, for each i and j the relation number of tuple tcij has to be the relation number of the j-th atom of si .
– In the example, e.g., r2 must be 4, as c5;1 = 2 and the first atom of s5 = 4 is an R4-atom. (3) If the head of si contains an existentially quantified variable, the new null value is represented by the numerical value i.
– This is illustrated by t4 in the example: the first position of the head of rule 2 has an existentially quantified variable and thus x4;1 = 4. (4) If a variable occurs at two different positions in si then the corresponding positions in the tuples used to produce ti carry the same value. (5) If a variable in the body of si also occurs in the head of si then the values of the corresponding positions in the body tuple and in ti are equal.
– Z2 occurs in position 3 of the second atom of the body of 4 and in position 2 of its head. Therefore, x4;3 and x5;2 have to coincide (where the 4 is determined by c5;2.
It turns out that all these tests can be done by rchase, given some relations that are precomputed by Pchase. More precisely, we let Pchase specify a 4-ary predicate IfThen(X1; X2; U1; U2) that is intended to contain all tuples fulfilling the condition: if X1 = X2 then U1 = U2. Similar predicates are defined for conditions with two and three conjuncts in the IF-part. Their definition by Datalog rules is straightforward.
Pquery and rquery. Finally, we explain how it can be checked that there is a homomorphism from q to S. We explain the issue through the little example query R3(x; y) ^ R4(y; z). To evaluate this query, rquery makes use of two additional variables q1 and q2, one for each atom of q. The intention is that these variables bind to the numbers of the tuples that the atoms are mapped to. We have to make sure two kinds of conditions. First, the tuples need to have the right relation symbol and second, they have to obey value equalities induced by the variables of q that occur more than once.
The first kind of conditions is checked by adding atoms IfThen(q1; i; ri; 3) and IfThen(q2; i; ri; 4) to rquery, for every i N . The second condition is checked similarly. As we do not need any further auxiliary predicates, Pquery is empty.
This completes the description of P . Note that P is nonrecursive, and has polynomial size in the size of q and . Furthermore, the arity of P is as required. This proves part (a) of Theorem 1.
In order to prove part (b), we must get rid of the numeric domain (except for 0 and 1). This is actually very easy. We just replace each numeric value by a logarithmic number of bits (coded by our 0 and 1 domain elements), and extend the predicate arities accordingly. As a matter of fact, this requires an increase of arity by a factor of log N = O(log jqj). This concludes our explanation of the proof ideas underlying Theorem 1.
Remark 1. Note that the evaluation complexity of the Datalog program obtained
for case (b) is not significantly higher than the evaluation complexity of the program P
constructed for case (a). For example, in the most relevant case of bounded arities, both
programs can be evaluated in NPTIME combined complexity over a database D. In
fact, it is well-known that the combined complexity of a Datalog program of bounded
arity is in NPTIME (see [
Remark 2. It is easy to generalize this result to the setting where q is actually a union of conjunctive queries (UCQ). 4
We wish to mention some interesting consequences of Theorem 1 that follow easily from the above result after combining it with various other known results. 4.1
A linear tgd [
By Theorem 1, we then conclude:
Theorem 2. Conjunctive queries under linear tgds of bounded arity are polynomially
rewritable as nonrecursive Datalog programs in the same fashion as for Theorem 1. So
are sets of inclusion dependencies of bounded arity.
A pioneering and highly significant contribution towards tractable ontological reasoning
was the introduction of the DL-Lite family of description logics (DLs) by Calvanese et
al. [
A DL-lite theory (or TBox) = ( ; +) consists of a set of negative constraints
such as key and disjointness constraints, and of a set + of positive constraints
that resemble tgds. As shown in [
Sticky tgds [
Several techniques for query-rewriting have been developed. An early algorithm,
introduced in [
The size of the computed rewriting increases exponentially w.r.t. the number of atoms
in the given query. This is mainly due to the fact that unifications are derived in a
“blind” way from every unifiable pair of atoms, even if the generated rule is
superfluous. An alternative resolution-based rewriting technique was proposed by Pere´z-Urbina
et al. [
Of more interest to the present work are rewritings into nonrecursive Datalog.
In [
Acknowledgment G. Gottlob’s Work was funded by the EPSRC Grant EP/H051511/1 ExODA: Integrating Description Logics and Database Technologies for Expressive Ontology-Based Data Access. We thank the anonymous referees, as well as Roman Kontchakov, Carsten Lutz, and Michael Zakharyaschev for useful comments on an earlier version of this paper.