It is a classic result in database theory that conjunctive query (CQ) answering, which is NP-complete in general, is feasible in polynomial time when restricted to acyclic queries. Subsequent results identified more general structural properties of CQs (like bounded treewidth) which ensure tractable query evaluation. In this paper, we lift these tractability results to knowledge bases formulated in the core dialect of DL-Lite. The proof exploits known properties of query matches in this logic and involves a query-dependent modification of the data. To obtain a more practical approach, we next propose a concrete polynomial-time algorithm for answering acyclic CQs based upon a rewriting into datalog. We also show how the algorithm can be extended to a larger class of (nearly acyclic) CQs. A preliminary evaluation of our proof-of-concept implementation suggests the interest of our approach for handling large acyclic CQs.
Description logics of the DL-Lite family [
The NP-hardness of CQ answering in relational databases motivated the search for
classes of CQs which admit efficient evaluation. A well-known result in database theory
shows that CQ answering becomes feasible in polynomial time when restricted to the
class of acyclic CQs [
In this paper, we show that for plain DL-Lite (without role hierarchies) the picture is brighter: all polynomial-time upper bounds for classes of CQs known from relational databases carry over to DL-Lite. Although this general tractability result relies on known properties of the logic, to our knowledge, it has not been pointed out before. The proof reduces the problem of answering a CQ over a knowledge base K to answering the same CQ over a database that results from a polynomial expansion of the dataset in K. The algorithm arising from this reduction has a disadvantage: it involves a query-dependent expansion of the data. For this reason, we propose an alternative algorithm based on a rewriting into non-recursive datalog, which runs in polynomial time for acyclic CQs. We also show how this approach can be extended to a larger family of CQs that are almost acyclic. We have implemented a simple prototype of the rewriting algorithm, and it shows promising results for answering large acyclic CQs.
The general tractability result and rewriting algorithm for acyclic CQs are presented
in [
Description Logics We briefly recall the syntax and semantics of DL-Lite and its
extension DL-LiteR [
An ABox is a finite set of assertions of the forms A(b) and r(b; c) with A 2 NC, r 2 NR, and b; c 2 NI. A TBox is a finite set of axioms, which in DL-Lite are concept inclusions of the form B1 v (:)B2, with B1; B2 of the form A 2 NC or 9R with R 2 NR. In DL-LiteR, TBoxes may additionally contain role inclusions of the form R1 v (:)R2 with R1; R2 2 NR. A knowledge base (KB) K = (T ; A) consists of a TBox T and ABox A.
The semantics of KBs is defined in terms of (DL) interpretations I = ( I ; I ) in
the usual way, see [
I = Ind(A) such that (i) c 2 AI iff A(c) 2 A, and (ii) (c; d) 2 rI iff r(c; d) 2 A.
Queries We first recall non-recursive datalog queries [
Given a rule and a DL interpretation I, an assignment is a function that maps every variable of to an object in I . For a concept atom A(x) 2 , we write I j= A(x) if (x) 2 AI , and for a role atom r(x1; x2) 2 , we write I j= r(x1; x2) if ( (x1); (x2)) 2 rI . We call a match for in I if I j= for all DL-atoms 2 . A tuple t is an answer to a query Q = (P; h) in an interpretation I if there exists a rule = h(x) in P and a match for in I such that (i) t = (x) and (ii) for each non-DL-atom p(y) 2 , (y) is an answer to (P; p) in I. We use ans(Q; I) to denote the set of answers to Q in I. The set cert(Q; K) of certain answers to an n-ary query Q over a KB K is defined as fa 2 (NI)n j aI 2 ans(Q; I) for any model I of Kg.
A union of conjunctive queries (UCQ) is a non-recursive datalog query Q = (P; q) such that every rule in P has head relation q and has only DL-atoms in its body. A conjunctive query (CQ) is a UCQ of the form (f g; q). We typically represent a UCQ as a set of CQs, and often use single rules (or rule bodies) to denote CQs.
The query output tuple (QOT) problem takes as input a query Q, a KB (T ; A), and a tuple of individuals a, and consists in deciding whether a 2 cert(Q; (T ; A)). Whenever we talk about the complexity of query answering, we mean the complexity of the QOT problem. We focus on combined complexity, which is measured in terms of the size of the whole input (a, Q, T , A).
Canonical Models Every consistent DL-Lite KB (T ; A) possesses a canonical model IT ;A. Its domain T ;A consists of all words aR1 : : : Rn (n 0) such that: (i) a 2 Ind(A) and Ri 2 NR, (ii) if n 1, then T ; A j= 9R1(a), and (iii) for 1 i < n, Ri 6= Ri+1 and T j= 9Ri v 9Ri+1. We call w0 2 T ;A a child of w 2 T ;A if w0 = wR for some R. The interpretation function is defined as follows: aIT ;A = a for all a 2 Ind(A) AIT ;A = fa 2 Ind(A) j T ; A j= A(a)g [ faR1 : : : Rn j n 1 and T j= 9Rn v Ag rIT ;A = f(a; b) j r(a; b) 2 Ag [ f(w1; w2) j w2 = w1rg [ f(w2; w1) j w2 = w1r g Note that IT ;A is composed of a core, which is obtained by restricting IT ;A to the objects in Ind(A), and an anonymous part consisting of (possibly infinite) trees rooted at objects in the core. It is well-known that IT ;A can be homomorphically mapped into any model of T and A, which yields: Fact 1 Let K be a consistent DL-Lite KB, and let IK be its canonical model. Then cert(Q; K) = ans(Q; IK) for every non-recursive datalog query Q.
In this section, we observe that the answers to a CQ over a consistent DL-Lite KB K = (T ; A) coincide with the answers to in an interpretation IT ;A; that can be constructed in polynomial time from K and . As a consequence, we obtain that any class of CQs that is tractable for plain databases is also tractable for DL-Lite KBs.
To establish this result, we rely on the notion of tree witness introduced in [
It follows from the definition that there can be at most one tree witness for each R(x; y), which we denote by fR(x;y). Notice that each tree witness f for a CQ naturally induces a tree-shaped CQ, denoted f , obtained by restricting to the variables in the domain of f and unifying variables z; z0 with f (z) = f (z0).
Definition 2. A tree witness fR(x;y) is valid w.r.t. T if for every word R1 : : : Rn in the range of fR(x;y), and every 1
i < n, we have Ri 1 6= Ri and T j= 9Ri 1 v 9Ri.
The notion of validity essentially mimics condition (iii) in the definition of IT ;A, thereby ensuring that whenever a tree witness fR(x;y) is valid and there is an element of the form wR in the anonymous part of IT ;A, then the element w is the root of a tree that contains ww0 for every w0 in the range of fR(x;y). Moreover, the image of any match for in IT ;A restricted to the elements in the anonymous part always corresponds to a union of such trees. Hence, if a match for in IT ;A maps x and y to objects w and wR respectively, then there is a tree witness fR(x;y) for R(x; y) in which is valid w.r.t. T and such that (z) = wfR(x;y)(z) for each variable z in the domain of fR(x;y). This means that by taking the range of all the valid tree witnesses, we can obtain all the tree-shaped structures that can potentially participate in matches for subqueries of . By appropriately augmenting the core with these structures, we obtain an interpretation IT ;A; that is sufficient for retrieving all query answers. Formally, we have: Definition 3. Let IT ;A; be the structure obtained by adding to the core: (a) the objects aw such that w occurs in the range of a valid tree witness fR(x;y),
T ; A j= 9R(a), and (b) the objects xSw where x is a variable in and S; w satisfy: (i) there is an individual a 2 Ind(A) and a chain of (possibly inverse) roles R1; : : : ; Rn of length at most jT j such that Rn = S, T ; A j= 9R1(a), and for each 1 < i n, Ri 1 6= Ri, and T j= 9Ri 1 v 9Ri, (ii) there exists a variable y and valid tree witness fR(x;y) with S 6= R and
T j= 9S v 9R whose range contains w.
Note that x is not an object of the domain of IT ;A; .
To extend the interpretations of concept and role names to these new objects, we let wR 2 AIT ;A; whenever T j= 9R v A, and (w; wR) 2 RIT ;A; for new w; wR.
Item (a) of Definition 3 attaches to each individual a a copy of the tree structure associated with tree witness f whenever the query qf has a match rooted at a. Item (b) handles the situation in which there is match for a connected component 0 of the query which maps all variables to objects in the anonymous part, in which case the set f (y) j y is variable in 0g form a tree. By letting x be the variable in 0 mapped closest to the ABox, and S be its incoming arc, the new objects xSw introduced in (b) induce the same tree structure, allowing the match for 0 to be reproduced in IT ;A; . Theorem 1. Let be a CQ, let (T ; A) be a consistent DL-Lite knowledge base, and let IT ;A; be the interpretation defined above. The following statements hold: 1. For every tuple a of individuals, a 2 ans( ; IT ;A) iff a 2 ans( ; IT ;A; ). 2. IT ;A; can be built in polynomial time in , T and A.
Proof (sketch). The “if” direction of statement 1 is immediate since IT ;A; corresponds
to a subinterpretation of IT ;A. For the “only if” direction, we must show how every
match for in IT ;A can be reproduced in IT ;A; . This is straightforward for
connected components of which contain an answer variable since we can directly use .
The remaining connected components are mapped into one of the tree-shaped structures
from item (b) of Definition 3. For statement 2, existence and validity of tree witnesses
can be tested in polynomial time. The existence of a role chain and individual having
the properties stated in (b) can be decided by initializing a set Reach with all roles S
such that T ; A j= 9S(a) for some a 2 Ind(A), and adding U to Reach whenever there
is V 2 Reach such that T j= 9V v 9U . Since there are only polynomially many
objects of the forms aw and bw as above, and instance checking and TBox reasoning
are tractable for DL-Lite KBs [
In light of Theorem 1 and Fact 1, to determine whether a 2 cert( ; (T ; A)), it is sufficient to test the consistency of (T ; A) and then, if (T ; A) is consistent, to decide whether a 2 ans( ; IT ;A; ). If we view IT ;A; as a plain relational database, the latter check is just a special case of the QOT problem. Hence, we obtain: Corollary 1. Let Q be a class of CQs for which the query output tuple problem over plain relational structures is decidable in polynomial time. Then the query output tuple problem for Q is also tractable for KBs formulated in DL-Lite.
The construction of IT ;A; above is easily extended to DL-LiteR using the
definitions of canonical models and tree witnesses from [
The expansion technique presented in Section 3 allows us to convert any polynomialtime algorithm for evaluating a class of CQs over plain databases into a polynomial-time algorithm for evaluating the same class of queries over DL-Lite KBs. However, the resulting algorithm would involve building the structure IT ;A; for each input query , which is clearly undesirable. We now present our main contribution: a polynomial-time procedure for evaluating acyclic CQs which is based upon rewriting CQs into nonrecursive datalog programs.
We begin with some preliminaries. To prepare for the extension to nearly acyclic queries in the next section, we will allow CQs to use a special concept name core, whose purpose is to force some variables to be mapped to the core. Semantically, this is achieved by defining cert( ; K) as the set of tuples a such that in every model I of K, there is a match for the CQ obtained by removing all core atoms from , such that maps the answer variables to a and maps every variable x with core(x) 2 to an element aI (with a an individual in K). Note that for CQs with no core atoms, this definition coincides with the earlier one. We say that a variable x is a core variable in if it is an answer variable, or contains the atom core(x) or an atom of the form r(x; x).
As usual, the query graph G( ) of a CQ is defined as the undirected graph whose nodes are the variables of , and that has an edge between x and x0 if contains a (body) atom r(x; x0) or r(x0; x). A CQ is acyclic if G( ) is acyclic, and rooted if every connected component of G( ) has at least one core variable. We consider a slight generalization of acyclicity: we say that a CQ is acyclic modulo core variables (cacyclic for short) if the graph G ( ) is acyclic, where G ( ) is obtained by deleting from G( ) each edge (x; x0) where x and x0 are core variables.
Our rewriting procedure works on queries which are both rooted and c-acyclic (we will discuss later how to handle the non-rooted case). To every rooted c-acyclic CQ , we associate the set of connected components fT1; : : : ; Tng of G ( ). Because is rooted, every Ti is a connected acyclic graph containing at least one vertex which is a core variable. We select an arbitrary core variable xi for each Ti and designate it as the root of Ti, allowing us to view Ti as a tree. Then, given a pair of variables x; y of , we say y is a child of x if y is a child of x in the (unique) tree Ti that contains x, and define descendant as the transitive closure of child.
Rewriting procedure for rooted queries Consider a rooted c-acyclic CQ = q(v) and a DL-Lite TBox T . Let X and Xr denote respectively the set of core variables and the set of root variables (recall that Xr X). For a variable x of , we denote by x the tuple hy1; : : : ; yki consisting of the answer variables of that are descendants of x. We rewrite the query into the non-recursive datalog program rewT ( ) = (P; q) defined as follows. In addition to concepts and roles, and the relation q, the program uses the following datalog relations: (i) (jx j + 1)-ary relations qx; qx0 for every variable x of , and (ii) unary relations qA and q9R for every A 2 NC and R 2 NR occurring in . We now describe the rules in P . There is a single top-level rule defining q: q(v) ^ qx(x; x ) ^ x2Xr
^ xi;xj2X^r(xi;xj)2 r(xi; xj ) For every variable x in , with Y = fy1; : : : ; yng the set of children of x in , we have qx(x; x )
^ A(x)2 ;A6=core qA(x) ^ ^ qy0(x; y ) and for all y 2 Y satisfying the following conditions: (i) there is an atom R(x; y) 2 or R (y; x) 2 and the tree witness fR(x;y) exists and is valid (ii) for every u in the domain of fR(x;y) with fR(x;y)(u) = wS and A(u) 2 , we have
T j= 9S v A (iii) the set Z = fz j fR(x;y)(z) = " ^ z 6= xg contains all core variables in the domain qy0(x; y) q9R(x) ^ ^ qz(x; z ) z2Z Finally, for every B 2 NC [ f9R j R 2 NRg with qB a datalog relation in P , we have and for every y 2 Y , we also have qy0(x; y )
^ r(x;y)2
^ s(y;x)2 r(x; y) ^
s(y; x) ^ qy(y; y ) qB(x) qB(x) qB(x)
A(x) s(x; y) s(y; x) for all A 2 NC such that T j= A v B for all s 2 NR such that T j= 9s v B for all s 2 NR such that T j= 9s v B Notice that the special concept core does not appear in the program rewT ( ).
Intuitively, the relation qx corresponds to the query jx whose answer variables are fxg [ x and whose body is obtained by restricting the body of to the atoms whose arguments among x and its descendants; the relation qy0 corresponds to the query jxy (with y a child of x) obtained by adding to jy the role atoms linking x and y. Rule (1) stipulates that a tuple is in the answer to if it makes true all of the role atoms linking two core variables and each of the queries jx associated with a root variable x of . Then rule (2) states that to make jx hold at an individual, we must satisfy the concept atoms for x and the query jxy for each child y of x. Rules (3) and (4) provide two ways of satisfying jxy. The first way, captured by rule (3), is to map y to an ABox individual, in which case the role atoms between x and y must occur in the ABox, and the query jy must hold at this individual. The second possibility, treated by rule (4), is that y is mapped to an element of the anonymous part of IT ;A which is a child of x. For this to occur, several conditions must be verified. First, if y is an R-successor of x, then the tree witness fR(x;y) must exist and be valid w.r.t. T . Second, we must ensure that all concept atoms concerning variables that are mapped inside the anonymous part by fR(x;y) are satisfied (this is checked in item (ii)). Finally, since core variables cannot be mapped inside the anonymous part, we need condition (iii), which checks that every core variable z in the domain of fR(x;y) is such that fR(x;y)(z) = ". If all of these conditions are met, then rule (4) states that the query jxy can be satisfied by making 9R hold at x (thereby guaranteeing the existence of the required paths in the anonymous part of IT ;A) and by satisfying the remainder of the query jxy (i.e. the query obtained (3) (4) (5) by removing the atoms mapped inside the anonymous part). The latter corresponds to the union of the queries jz where z is a descendant of x with fR(x;y)(z) = " . Finally, the rules in (5) provide the standard rewriting of concepts A and 9R w.r.t. T .
We establish the correctness of our rewriting procedure.
Theorem 2. Let be a rooted c-acyclic CQ and K = (T ; A) a DL-Lite KB. Then cert( ; K) = ans(rewT ( ); IA).
Proof (idea). The key step in the proof is showing that for every variable x in , cert( jx; K) = ans((rewT ( ); qx); IA). This can be proved by induction on the number of variables in jx, utilizing Proposition 1 and properties of tree witnesses.
The next theorem shows that our rewriting procedure provides a polynomial-time algorithm for evaluating rooted c-acyclic conjunctive queries.
Theorem 3. Given a rooted c-acyclic CQ and a DL-Lite KB (T ; A), the program
rewT ( ) can be computed in polynomial time in the size of and T , and deciding if
a 2 ans(rewT ( ); IA) can be done in polynomial time in the size of rewT ( ) and A.
Proof. For the first point, we observe that the number of relations in rewT ( ) is linear
in the number of atoms in and that each relation is defined using linearly many rules
in the size of and T . We also note that testing the conditions for rules of type (4) can
be done in polynomial time in the size of and T (cf. Section 3). The second statement
is true because once the answer variables in rewT ( ) have been instantiated with the
individuals in a, we have a non-recursive datalog program (with constants) where every
rule contains at most two variables. It is known that datalog programs of this form can
be evaluated in polynomial time (cf. [
Handling non-rooted queries. We now show that non-rooted c-acyclic CQs can be answered via a reduction to the rooted query case. Given an c-acyclic CQ over a KB K = (T ; A), the set cert( ; K) can be computed using the following steps: 1. If is rooted, then return cert( ; K). 2. Choose a maximally connected component of that contains no core variable. 3. If has a match fully in the anonymous part of IT ;A, drop it and go to step 1. 4. If there is a variable x in such that the rooted query g(x) has a non-empty answer over K, then drop from and go to step 1. Otherwise, return ;. It is not hard to show that the condition in step 3 holds just in the case that there exists a variable x and a role S 2 NR which is reachable in the canonical model (cf. Definition 3 b.i) such that there is a valid tree witness f for S(z; x) in S;x = [fS(z; x)g (z fresh) such that: (i) if f (y) = , then y = z, and (ii) T j= 9R v A whenever f (y) = wR and A(y) 2 . It follows that step 3 can be carried out in polynomial time, and thus we obtain a polynomial-time procedure for arbitrary c-acyclic CQs.
Answering UCQs Given a union of c-acyclic CQs Q = (P; q), we can decide whether
a 2 cert(Q; K) by testing whether a 2 cert( ; K) for some c-acyclic CQ 2 P .
Since there are only linearly many 2 P , and each check a 2 cert( ; K) takes only
polynomial time, we obtain a polynomial procedure for unions of c-acyclic CQs.
Answering acyclic queries in DL-LiteR To support role inclusions, we can replace
atoms r(x; y) by atoms qr(x; y), and add the corresponding rules qr(x; y) S(x; y)
with T j= S v r. Using the notion of tree witness in [
We show how the rewriting algorithm from the previous section can be generalized to queries which are “nearly” acyclic. Formally, we call a conjunctive query k-acyclic if deleting k atoms from leads to a c-acyclic query3. Our goal is to show that, when k is bounded by a constant, any k-acyclic query can be rewritten in polynomial time into a union of c-acyclic CQs which is equivalent for the purposes of query answering.
We start by showing the following: Proposition 1. Assume is a k-acyclic CQ. Then we can obtain a UCQ Q such that: 1. each 0 2 Q is (k 1)-acyclic, 2. cert(Q; K) = cert( ; K) for any DL-Lite KB K, and 3. jQj 3.
If k is bounded by a constant c, we can obtain Q in polynomial time in the size of . Proof. Let be a -minimal set of atoms from such that n is c-acyclic. Observe that the minimality of implies that contains only role atoms. Pick an atom = R(x; y) in . The CQs in Q capture the three possible ways for a match to map R(x; y) into the canonical model of K: (a) both (x); (y) are in the core, (b) (y) is a child of (x), and (c) (x) is a child of (y). To capture (a), we consider the query c obtained by adding to the atoms core(x) and core(y). For case (b), we compute from the query # by marking the variables that must map into the anonymous part. We start by marking the variable y in , and then exhaustively apply the following rule: Suppose has an atom R1(x1; x2) or R1 (x2; x1) such that x2 is marked. Suppose also has an atom R2(x2; x3) or R2 (x3; x2) such that x3 6= x and x3 is not marked. If R2 = R1 , then replace in the variable x3 by x1. If R2 6= R1 , then mark x3.
The query ", which deals with case (c), is obtained from by marking x, and then applying exhaustively the above rule modified by replacing “x3 6= x” with “x3 6= y”. We call d (d 2 f#; "g) proper if the set of marked variables in d induces a treeshaped query, and no core variable is marked. We let Q = f cg [ f d j d 2 f#; "g; d is properg. It is not too difficult to show cert(Q; K) = cert( ; K) for any KB K.
Let denote the query obtained by deleting from ; clearly is (k 1)-acyclic.
To see that c is (k 1)-acyclic, observe that c = [ fcore(x); R(x; y); core(y)g,
so G ( c n 0) = G ( n 0) for any 0 (recall that G is obtained from the query
graph by deleting edges between core variables). Thus, since is (k 1)-acyclic,
c must also be (k 1)-acyclic. Next take a proper query d, with d 2 f#; "g, and
3 We remark that k-acyclicity is inspired by the notion of bounded feedback edge sets often
considered in parameterized complexity, cf. [
Provided is known, Q can be obtained in polynomial time in the size of . If k is bounded by a constant, then can also be identified in polynomial time because the set can be computed by considering all (polynomially many) subsets of at most k atoms.
Repeated applications of Proposition 1 yield the desired polynomial reduction to c-acyclic UCQs: Corollary 2. For any k-acyclic query there is a UCQ Q such that: 1. each 0 2 Q is c-acyclic, 2. cert(Q; K) = cert( ; K) for any DL-Lite KB K, and 3. jQj 3k.
If k is bounded by a constant, Q can be computed in polynomial time in the size of .
Since c-acyclic UCQs can be answered in polynomial time using the rewriting technique from Section 4, we obtain a polynomial-time procedure for k-acyclic CQs. 6
We developed a prototype rewriting system that takes as input a rooted acyclic CQ
and a DL-LiteR TBox T , and outputs an SQL statement expressing the resulting
nonrecursive datalog program rewT ( ) (using common table expressions). We evaluated
the result over ABoxes stored in a relational database, using the PostgreSQL database
system, and Owlgres [
To test our prototype, we used the LUBM290 ontology described in [
We compared our rewriting procedure with REQUIEM [
We also tested the feasibility of evaluating our rewritings over large ABoxes. For
this, we used the modified LUBM data generator [
Finally, we note that a performance comparison with PRESTO [
We plan to generalize our rewriting technique to larger tractable classes of CQs, like
bounded treewidth CQs, and also to try to identify suitable restrictions for more
expressive DLs that allow for tractable query answering. Our proof-of-concept
implementation raises hopes that efficient evaluation of large (nearly) acyclic queries is feasible,
but many challenges remain. For example, we observe that breaking down the queries
into small rules as is done by our rewriting may lead to a loss of structure that could be
used by database management systems for optimized evaluation. There are many other
aspects, not directly related to the rewriting technique, that must also be taken into
account to achieve practicable query answering, such as exploring more efficient forms of
representing data in ABoxes, using different kinds of indexes, and considering different
translations of our programs into SQL. Using semantic indexes [
Acknowledgements This work was supported by a Universite´ Paris-Sud Attractivite´ grant and ANR project PAGODA ANR-12-JS02-007-01 (Bienvenu), FWF project T515N23 (Ortiz), FWF project P25518-N23 and WWTF project ICT12-015 ( Sˇimkus), Vienna PhD School of informatics and EU project Optique FP7-318338 (Xiao). 4 In fact, the exponential blowup occurs even without the atoms Bi(ui), but some quite obvious modifications to the algorithm would resolve the issue. With these atoms present, it appears non-trivial changes to the algorithm would be required.