Tractable Queries for Lightweight Description Logics

1 Introduction

Conjunctive queries (CQs) form a natural and important class of relational databases queries. In the description logic (DL) research community, there has been increasing interest in the problem of retrieving the answers to a CQ while taking into account the knowledge specified by a DL ontology [Calvanese et al., 2007; Lutz et al., 2009]. The use of an ontology typically leads to an increase in the complexity of CQ answering 1 compared to the relational database setting. Indeed, for the so-called expressive DLs, CQ answering is co-NP hard in data complexity (that is, when the ontology and query are considered fixed, and the complexity is measured in the size of the data only), in contrast to the AC0 upper bound for standard databases. In combined complexity (that is, when the complexity is measured in terms of the combined sizes of the query, ontology, and data), rather than NP-complete, the problem is at least ExpTime-hard, and often requires doubleexponential time (cf. the survey [Ortiz and Simkus, 2012]). Since such high complexity is prohibitive for data-rich applications, most work in the area focuses on ontologies formulated in lightweight DLs of the DL-Lite [Calvanese et al.,

1 When talking about the complexity of CQ answering, we mean the complexity of the query output tuple problem, that is, to decide whether a given tuple is in the answer of a CQ.

Magdalena Ortiz Mantas ˇSimkus Guohui Xiao

Institute of Information Systems Vienna University of Technology, Austria

2007] and EL [Baader et al., 2005] families, which enjoy better computational properties. Indeed, CQ answering for DL-Lite knowledge bases has the same data and combined complexity as for plain databases, whereas for EL, CQ answering is P-complete in data complexity, but remains NPcomplete in combined complexity.

A classic result in database theory states that CQ answering becomes feasible in polynomial time when restricted to the class of acyclic CQs [Yannakakis, 1981]. Later investigations lead to the identification of more general structural properties, such as bounded treewidth, query width, or hypertree width [Chekuri and Rajaraman, 1997; Gottlob et al., 1999], which guarantee tractable CQ answering. Since the NP-hardness in combined complexity of CQ answering in DLs is a direct consequence of the analogous result for relational databases, it seems natural to ask whether these tractability results also transfer to the DL setting. This would be very desirable since it is likely that most of the queries that will actually occur in applications are acyclic. While there are no collections of real-world CQs that can be used to support this claim in the DL setting, one can find some compelling evidence by looking at the closely related setting of SPARQL queries over RDF data, where it has been reported that acyclic queries (in fact, acyclic conjunctive graph patterns) comprise more than 99% of the queries in a log of around three million queries posed to the DBpedia endpoint [Picalausa and Vansummeren, 2011]. Unfortunately, lifting positive results from databases to the DL setting is often not possible, even when one considers lightweight DLs. For instance, for the logic DL-LiteR, which underlies the QL profile of the OWL 2 standard [OWL Working Group, 2009], CQ answering was recently shown to be NP-hard already for acyclic queries [Kikot et al., 2011].

In this paper, we show that for plain DL-Lite (without role hierarchies) and for EL, the picture is brighter. Specifically, all polynomial-time upper bounds for classes of CQs known from relational databases carry over to DL-Lite. In the case of the EL family, we get polynomiality even for ELH, thus showing that role hierarchies alone are not the culprit for the loss of tractability. Although this general tractability result relies on known properties of the logics, to our knowledge, it has not been pointed out before. The proof involves a polynomial reduction from the problem of answering a given 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, which may be undesirable in many settings. Hence, we also propose an alternative polynomial-time algorithm for acyclic CQs, based on a rewriting into datalog. We have implemented a simple prototype of the approach, and it shows promising results for answering large acyclic CQs.

2 Preliminaries

Description Logics We briefly recall the syntax and semantics of DL-LiteR [Calvanese et al., 2007], ELH [Baader et al., 2005], and their sublogics DL-Lite and EL. Let NC, NR, and NI be countably infinite sets of concept names, role names, and individuals, respectively, and let NR = NR∪{r- | r ∈ NR} be the set of (complex) roles. For R ∈ NR, R- denotes r- if R = r ∈ NR, and r if R = r-.

An ABox is a finite set of assertions of the forms A(b) and r(b, c) with A ∈ NC, r ∈ NR, and b, c ∈ NI. A TBox is a finite set of axioms, whose form depends on the particular DL. In DL-Lite, TBox axioms are concept inclusions of the form C1 ⊑ C2, with C1 = B1 and C2 = (¬)B2 for B1,B2 of the form A ∈ NC or ∃R with R ∈ NR. DLLiteR TBoxes may also contain role inclusions of the form R1 ⊑ (¬)R2 with R1,R2 ∈ NR. In EL, TBoxes consist of concept inclusions C1 ⊑ C2, but in this case C1,C2 may be complex concepts constructed according to the syntax C := ⊤ | A | C ⊓ C | ∃r.C. ELH TBoxes additionally allow role inclusions of the form r1 ⊑ r2, similarly to DLLiteR, but with r1, r2 ∈ NR. A DL knowledge base (KB) K = (T , A) consists of a TBox T and ABox A.

The semantics of DL KBs is defined in terms of (DL) interpretations I = (∆I , ·I ), where the domain ∆I is a non-empty set, and the interpretation function ·I maps each a ∈ NI to an object aI ∈ ∆I , each A ∈ NC to a set AI ⊆ ∆I , and each r ∈ NR to a binary relation rI ⊆ ∆I × ∆I . The function ·I is extended to complex concepts and roles in the usual way, see [Calvanese et al., 2007; Baader et al., 2005] for details. We say that I satisfies an axiom P1 ⊑ P2 if P I 1 ⊆ P I 2 ), and it satisfies an assertion A(a) (resp. r(a, b)) if aI ∈ AI (resp. (aI , bI ) ∈ rI ). Finally, I is a model of a KB K = (T , A) if it satisfies every axiom in T and assertion in A. K is consistent if it admits some model. We use Ind(A) for the individuals occurring in A. We let IA be the interpretation with ∆I = Ind(A) and such that (i) c ∈ AI iff A(c) ∈ A, and (ii) (c, d) ∈ rI iff r(c, d) ∈ A.

Queries We recall non-recursive datalog queries and the more restricted conjunctive queries, cf. [Levy and Rousset, 1998]. Let NV and ND be countably infinite sets of variables and datalog relations, respectively. Each σ ∈ ND has an associated non-negative integer arity. Atoms are expressions of the form p(⃗x), where ⃗x ∈ (NV)n , and (i) p ∈ NC and n = 1, (ii) p ∈ NR and n = 2, or (iii) p ∈ ND and n is the arity of p. Atoms of the form (i) and (ii) are called DL-atoms.

A rule ρ is an expression of the form h(⃗x) ← β1, . . . , βm, where h(⃗x), β1, . . . , βm are atoms, h is a datalog relation, and every variable of ⃗x occurs in body(ρ) = {β1, . . . , βm}. Abusing notation, we write β ∈ ρ instead of β ∈ body(ρ). The variables in head(ρ) are called the answer variables of ρ.

Given a set of rules P, we let Dep(P) = (V,E) be the directed graph such that: (a) V is the set of all datalog relations occurring in P , and (b) (p1, p2) ∈ E whenever there is a rule ρ ∈ P such that p1 is the relation in head(ρ) and p2 occurs in body(ρ). A non-recursive datalog query is a pair Q = (P, q), where P is a set of rules such that Dep(P) has no cycle, and q is a datalog relation. The arity of Q is the arity of q.

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) ∈ ρ, we write I |=π A(x) if π(x) ∈ AI , and for a role atom R(x1, x2) ∈ ρ, we write I |=π R(x1, x2) if (π(x1), π(x2)) ∈ RI . We call π a match for ρ in I if I |=π β for all DL-atoms β ∈ ρ.

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) ∈ ρ, π(⃗y) is an answer to (P, p) in I. We use ans(Q, I) to denote the set of answers to Q in I. We denote by cert(Q,K) the set of certain answers to Q = (P, q) over a KB K, defined as cert(Q,K) = {⃗a ∈ (NI)n | (⃗a)I ∈ ans(Q, I) for any model I of K}, where n is the arity of Q.

A conjunctive query (CQ) is a non-recursive datalog query of the form ({ρ}, q), such that body(ρ) contains only DLatoms. Since the particular relation q is irrelevant, we will use single rules (or rule bodies) to denote CQs.

In this paper, we focus on the decision problem known as the query output tuple (QOT) problem, which takes as input a query Q, a KB (T ,A), and a tuple of individuals ⃗a, and consists in deciding whether ⃗a ∈ cert(Q, (T , A)). Whenever we talk about the complexity of query answering, we mean the computational 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-LiteR or ELH KB (T ,A) possesses a canonical model IT ,A. For DL-LiteR, the domain ∆T ,A of IT ,A consists of all words aR1 . . .Rn (n ≥ 0) such that a ∈ Ind(A), Ri ∈ NR, and:

- for 1 ≤ i < n, T |= ∃Ri ⊑ ∃Ri+1 and Ri ̸= Ri+1. We say that w′ ∈ ∆T ,A is a child of w ∈ ∆T ,A if w′ = wR for some R. The interpretation function is defined as follows:

The construction of IT ,A for ELH KBs is similar, please refer to [Lutz et al., 2009] for details. Note that for both DLLiteR and ELH KBs, 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, yielding:

Fact 1. Let K be a consistent DL-Lite or ELH KB, and let IK be its canonical model. Then cert(Q,K) = ans(Q, IK) for every non-recursive datalog query Q.

3 General Tractability Result

In this section, we observe that for both DL-Lite and ELH, the answers to a CQ ρ over a consistent KB K = (T , A) coincide with the answers to ρ over an interpretation IT ,A,ρ that can be constructed in polynomial time from K and ρ. Since IT ,A,ρ can be viewed as a relational database, we obtain that any class of CQs that is tractable for plain databases is also tractable for KBs formulated in these DLs.

To establish this result, we rely on the following wellknown property of query matches in DL-Lite and ELH (cf. [Kikot et al., 2012; Lutz et al., 2009]):

Lemma 2. Consider a consistent DL-Lite or ELH KB (T ,A), a CQ ρ, and an object w in the anonymous part of IT ,A. Then all query matches π for ρ that coincide on the set of variables {x | π(x) = w} coincide also on the sets of variables that are matched to the children of w.

It follows from Lemma 2 that if there is a query atom R(x, y) such that π(y) is a child of π(x) in the anonymous part, then it is uniquely determined which other query variables have to be matched inside the tree rooted at π(x), and how these variables are ordered into a tree. We can exploit this property to construct the desired IT ,A,ρ in two steps as follows:

1. First, we generate from ρ a polynomial number of treeshaped queries, which correspond to the different ways that a subquery of ρ can be mapped inside a tree in the anonymous part of IT ,A. Each query is generated by selecting an atom R(x, y) ∈ ρ and considering what happens if x and y were to be mapped respectively to a node w and one of its children in the anonymous part. By repeatedly applying Lemma 2, we can determine which other variables must be matched inside the tree rooted at w, and how the resulting subquery collapses into a tree.
2. Only the fragments of the anonymous part of the canonical model into which one of these tree-shaped queries can be homomorphically embedded can participate in query matches. Hence, by appropriately augmenting the core with instantiations of these tree-shaped queries, we obtain an interpretation IT ,A,ρ that is sufficient for retrieving all query answers. Specifically, we attach to each individual a a copy of each tree-shaped query for which there is a match rooted at a. To handle the case of (parts of) queries whose matches may be detached from the core, we also instantiate a disconnected copy of each tree-shaped query which can be mapped inside the anonymous part of IT ,A.

Construction for DL-Lite The following notion of tree witness for DL-Lite was defined in [Kontchakov et al., 2010]. Let ρ be a CQ and let R(x, y) be such that either R(x, y) ∈ ρ or R-(y, x) ∈ ρ. A tree witness for R(x, y) in ρ is a partial map f from the variables in ρ to words over the alphabet NR such that its domain is minimal (w.r.t. set-theoretic inclusion) and the following conditions hold:

We remark that each tree witness f naturally corresponds to a tree-shaped CQ obtained by restricting the original CQ ρ to the variables in the domain of f and unifying variables z, z′ with f(z) = f(z′ ). By definition, there is at most one tree witness for each R(x, y), which we denote by fR(x,y). We say that 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 ̸= Ri and T |= ∃Ri-1 ⊑ ∃Ri. Existence and validity of tree witnesses can be tested in polynomial time.

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). Moreover, we may assume that if π(x) is minimal (that is, there is no π(x′ ) which is a prefix of π(x)), then π(x) is within distance |T | of the ABox. Hence, the matches for ρ in IT ,A coincide with the matches of ρ in the structure IT ,A,ρ 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) and T , A |= ∃R(a).
• (b) the objects biw such that bi is a fresh object chosen for a valid tree witness fR(x,y), w occurs in the range of fR(x,y), and there is an individual a ∈ Ind(A) and chain of roles R1, . . . ,Rn of length at most |T | such that T , A |= ∃R1(a), Rn = R, and for each 1 < i ≤ n, Ri-1 ̸= Ri and T |= ∃Ri-1 ⊑ ∃Ri.

To extend the interpretations of concept and role names to these new objects, we let wR ∈ AIT ,A,ρ whenever T |= ∃R- ⊑A, and (w, wR) ∈ RIT ,A,ρ for each new wR.

We remark that the existence of a role chain and individual having the properties stated in (b) can be decided in polynomial time by initializing a set Reach with all roles S such that T ,A |= ∃S(a) for some a ∈ Ind(A), and then adding U to Reach whenever there is V ∈ Reach such that T |= V - ⊑ U. 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 [Calvanese et al., 2007], it follows that IT ,A,ρ can be constructed in polynomial time.

Construction for ELH In what follows, it will prove convenient to use conjunction as a role constructor: if r1, r2 ∈ NR are role names, then their conjunction r1 ⊓ r2 is a role whose interpretation is (r1 ⊓r2)I = r1 I ∩r2 I . We denote by ELH⊓ the extension of ELH with role conjunction.

We introduce a notion of tree witness for ELH, inspired by the fork elimination procedure from [Lutz, 2008]. Let ρ be a CQ and α = r(x, y) ∈ ρ. We begin by defining a set Dα and equivalence relation ∼α over Dα by initializing Dα to {x, y}, and then applying the following rules until convergence:

Note that Dα and ∼α are uniquely defined and can be computed in linear time in the size of ρ. We let ρα be the query obtained by restricting ρ to the variables in Dα, then replacing each variable z by its equivalence class [z] under ∼α. We define a directed graph Gα whose nodes are the equivalence classes in ∼α and whose edges are the atoms in ρα. If Gα contains no (directed) cycles, then we define the tree witness for α = r(x, y) in ρ as the map f : Dα → (2NR ×2NC )∗ with:

To every tree witness f, we can naturally associate an ELH⊓ concept concf(ε) as follows: if f(z) = w is a leaf, then concf(w) = ⊤, and if f(z) = w has children w1, . . .wn with wi = wMiNi, then concf(w) = dni=1 ∃(dr∈Mi r).(dA∈Ni A⊓ concf(wi)). It follows from results in [Rudolph et al., 2008] that it can be checked in polynomial time whether T , A |= concf (ε). Using a reachability construction similar to the one for DL-Lite, we can also test in polynomial time whether concf (ε) is non-empty in IT ,A.

We are now ready to define the interpretation IT ,A,ρ. Its domain is the set of words in NI · (2NC × 2NR )∗ that contains each individual occurring in A, each aw such that w is in the domain of a tree witness f for which (T ,A) |= concf (ε)(a) holds, and each bi · w such that fi is a tree witness with concf(ε)IT ,A ̸= ∅ (for bi a fresh symbol selected for fi). Concept and role names are interpreted as follows:

and each individual a is interpreted as itself (aIT ,A,ρ = a).

The following theorem resumes the key properties of the interpretations IT ,A,ρ just described.

Theorem 3. Let ρ be a CQ, let (T ,A) be a consistent DL-Lite or ELH knowledge base, and let IT ,A,ρ be the interpretation defined previously. The following statements hold:

1. IT ,A,ρ can be built in polynomial time in ρ, T and A.
2. For every tuple ⃗a of individuals, ⃗a ∈ ans(ρ, IT ,A) iff ⃗a ∈ ans(ρ, IT ,A,ρ).

In light of Theorem 3 and Fact 1, to determine whether ⃗a ∈ cert(ρ, (T ,A)), it is sufficient to test the consistency of (T ,A) and then, if (T ,A) is consistent, to decide whether ⃗a ∈ 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 the desired result:

Corollary 4. Let Q be a class of CQs for which the query output tuple problem over relational databases is decidable in polynomial time. Then the query output tuple problem for Q is also tractable for KBs formulated in DL-Lite and ELH.

The construction of IT ,A,ρ above is easily extended to DLLiteR using the notion of tree witnesses proposed in [Kikot et al., 2012]. However, the construction is no longer polynomial since there can be exponentially many tree witnesses for a single atom R(x, y) in ρ [Kikot et al., 2011], and so we do not obtain an analogue of Theorem 3. Indeed, it follows from results by Kikot et al. 2011 that the tuple output problem for tree-shaped CQs is NP-complete for DL-LiteR KBs.

Therefore, to obtain tractability results to DL-LiteR, one must impose some syntactic restriction on T and ρ that ensures a polynomial bound on the number of tree witnesses, e.g. the absence of twisty roles proposed in [Kikot et al., 2012].

4 Answering Acyclic Queries

The expansion technique presented in Section 3 allows us to convert any polynomial-time algorithm for evaluating a tractable class of CQs over relational databases into a polynomial-time algorithm for evaluating the same class of queries over DL-Lite and ELH 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 non-recursive datalog programs. We present the approach for DL-Lite KBs, but discuss at the end of the section how the approach can be adapted to DL-LiteR and ELH.

We begin with some preliminaries. 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 x′ if ρ contains a (body) atom r(x, x′ ) or r(x′ , x). A CQ ρ is acyclic if G(ρ) is acyclic, and rooted if every connected component of G(ρ) has at least one answer variable. We consider a slight generalization of acyclicity: we say that a CQ ρ is acyclic modulo answer variables (a-acyclic for short) if the graph G-(ρ) obtained by deleting from G(ρ) each edge (x, x′ ), where x, x′ are answer variables is acyclic.

Our rewriting procedure works on queries which are both rooted and a-acyclic (we will discuss later how to handle the non-rooted case). To every rooted a-acyclic CQ ρ, we associate the set of connected components {T1, . . . , Tn} of G-(ρ). Because ρ is rooted, every Ti is a connected acyclic graph containing at least one vertex which is an answer variable. We select an arbitrary answer 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. For a variable x of ρ, we denote by ⃗xρ the tuple (y1, . . . , yk), where y1, . . . , yk are the answer variables that are descendants of x.

Rewriting procedure for rooted queries Consider a rooted a-acyclic CQ ρ = q(⃗x) ← α and a DL-Lite TBox T , and let X be the set of answer variables which are roots in ρ (see previously). We rewrite the query ρ into the non-recursive datalog program rewT (ρ) = (P, q) defined as follows. In addition to q, the program uses the following datalog relations: (i) (|⃗xρ|+1)-ary relations qx, q′x for every variable x of ρ, and (ii) unary relations qA and q∃R for every A ∈ NC and R ∈ NR occurring in ρ. We now describe the rules in P. There is a single top-level rule defining q:

For every variable x in ρ, with Y = {y1, . . . , yn} the set of children of x in ρ, we have the following rule

and for every y ∈ Y , we also have

and for all y ∈ Y satisfying the following conditions:

• (i) there is an atom R(x, y) ∈ ρ or R-(y, x) ∈ ρ and the tree witness fR(x,y) exists and is valid
• (ii) for every u in domain of fR(x,y) with fR(x,y)(u) = wS and A(u) ∈ ρ, we have T |= ∃S- ⊑ A
• (iii) the set Z = {z | fR(x,y)(z) = ε ∧ z ̸= x} contains all
• answer variables in the domain of fR(x,y)

we additionally have the rule

Finally, for every B ∈ NC ∪ {∃R | R ∈ NR} with qB a datalog relation in P , we have the rules

Intuitively, the relation qx corresponds to the query ρ|x whose answer variables are {x} ∪ ⃗xρ and whose body is obtained by restricting the body of ρ to the atoms whose arguments among x and its descendants; whereas the relation q′y corresponds to the query ρ|xy (with y a child of x) obtained by adding to ρ|y 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 root variables and each of the queries ρ|x associated with a root variable x of ρ. Then rule (2) states that to make ρ|x hold at an individual, we must satisfy the concept atoms for x and the query ρ|xy for each child y of x. Rules (3) and (4) provide two ways of satisfying ρ|xy. 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 ρ|y 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 answer variables cannot be mapped inside the anonymous part, we need condition (iii), which checks that every answer 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 ρ|xy can be satisfied by making ∃R 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 ρ|xy (i.e. the query obtained by removing the atoms mapped inside the anonymous part). The latter corresponds precisely to the union of the queries ρ|z 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 ∃R w.r.t. T .

We establish the correctness of our rewriting procedure.

Theorem 5. Let ρ be a rooted a-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(ρ|x,K) = ans((P, qx), IA). This can be proven by induction on the number of variables in ρ|x, utilizing Fact 1 and properties of tree witnesses.

The next theorem shows that our rewriting procedure provides a polynomial-time algorithm for evaluating rooted aacyclic conjunctive queries.

Theorem 6. Given a rooted a-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 ⃗a ∈ ans(rewT (ρ), IA) can be tested in polynomial time in the size of Q 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. [Dantsin et al., 2001]).

Handling non-rooted queries. We now return to the case of non-rooted a-acyclic CQs, and show that such queries can be answered via a reduction to the rooted query case. Given an a-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 ρ, such that β contains no answer variable.
3. If β has a match fully in the anonymous part of IT ,A, then drop β from ρ 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 ∅.

For testing whether β satisfies the condition in step 3, it suffices to consider the tree witnesses f of the subquery β whose domain are all the variables in β. For each such witness f, we need to test: (i) validity of f, (ii) whether T |= ∃R- ⊑A for all x with f(x) of the form wR and all atoms A(x) in β, and (iii) whether there exists a chain of roles R1, . . . ,Rn that is implied by the knowledge base and that reaches the first role in f, as in item (b) of the construction of IT ,A,ρ for DL-Lite. Since all these steps are feasible in polynomial time, we obtain a polynomial-time procedure for solving the QOT problem for arbitrary a-acyclic CQs over DL-Lite KBs.

Adapting the rewriting for DL-LiteR and ELH We now discuss how to modify the rewriting to handle DL-LiteR and ELH KBs. First, since both DLs support role inclusions, we must replace atoms r(x, y) by atoms qr(x, y), and add the corresponding rules qr(x, y) ← S(x, y) with T |= S ⊑ r.

Then the algorithm can be directly employed for DL-LiteR, but using the notion of tree witness in [Kikot et al., 2012]. Similarly as in Section 3, the algorithm may not be polynomial since there can be exponentially many tree witnesses.

For ELH, apart from handling role inclusions as above, rule (4) must be modified to use the ELH version of tree witnesses. In particular, instead of an atom q∃R(x), we use qCf (x), where Cf is the concept induced by the tree witness f for r(x, y). Note that there are only linearly many tree witnesses, hence only linearly many new relations qCf . Assuming that the ELHTBox is in normal form (cf. [Baader et al., 2005]), we only need to consider atomic concepts A which entail C, yielding a linear number of rules of the form qCf (x) ← qA(x). Finally, we must modify the rules in (5) defining the relations qA to capture entailment in ELH, which may require the use of recursive datalog rules (see e.g. [Eiter et al., 2012]). Importantly, these rules have at most two variables each, and so they do not impact the polynomial upper bound argument. Thus, by using this modified rewriting, and handling non-rooted CQs in a similar way to DL-Lite, we obtain a polynomial-time algorithm for deciding the QOT problem for a-acyclic CQs over ELH KBs.

5 Preliminary Evaluation

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 non-recursive 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 [Stocker and Smith, 2008] for loading the data.

To test our prototype, we used the university ontology LUBM∃20 described in [Lutz et al., 2012], which adds concept inclusions with additional concept names, and with existential concepts on the right-hand side, to the original LUBM ontology [Guo et al., 2005]. We considered three acyclic queries from the benchmark in [Lutz et al., 2012] (q2, q4, and q5), which are rather small (at most 4 atoms), and created four additional large acyclic queries, with 13 to 34 atoms, and 7 to 17 variables. The new queries are also significantly larger than the ones in the REQUIEM test suite (≤ 7 atoms). The importance of handling such larger queries in practice has been previously argued in [Rosati and Almatelli, 2010].

We compared our rewriting procedure with REQUIEM [P´erez-Urbina et al., 2009] and IQAROS [Venetis et al., 2012] which, like most of the existing query rewriting systems for the DL-Lite family, generate unions of CQs rather that nonrecursive datalog programs. For the four large queries, both REQUIEM and IQAROS did not terminate (within ten minutes). Even for the small q4 and q5, the generated rewritings were too large to be posed directly to an off-the-shelf RDBMS: REQUIEM generated tens of thousands of queries for both, and IQAROS almost 15 thousand for q4, and almost one thousand for q5. By contrast, for our approach, the rewriting times were negligible for all queries (under half a second) and the produced rewritings have less than 30 rules, disregarding the rules (5) of the algorithm (since the latter are independent of the query, we computed them separately and stored them using a database view per concept/role name).

We also tested the feasibility of evaluating our rewritings over large ABoxes. For this, we used the modified LUBM data generator [Lutz et al., 2012] (with 5% incompleteness). Each university has approximately 17k individuals, 28K concept assertions, and 47K role assertions. We carried out our experiments on ABoxes with 20 - 200 universities, resulting in very large ABoxes (up to ca. 1.5 GB on disk). The results reported in Table 1 show that the algorithm scales well.

Finally, we note that a performance comparison with PRESTO [Rosati and Almatelli, 2010], which also outputs non-recursive datalog programs, was not possible because this system is not publicly available. However, we can observe that its underlying algorithm may produce exponentialsize rewritings for acyclic CQs, as witnessed by the family of queries q(x) ← r(x, y) ∧ ∧0≤i≤n p(y, zi) ∧ p(ui, zi) coupled with the empty TBox. Intuitively, the PRESTO algorithm generates a separate rule for every possible way of selecting a collection of variables from {u1, . . . , un} and identifying them with y. This exponential blow-up suggests that our positive results are not merely an artifact of the datalog representation, but derive also from our use of acyclicity.

6 FutureWork

We plan to generalize our rewriting technique to larger tractable classes of CQs, like bounded treewidth CQs. Another direction is to identify suitable restrictions for more expressive DLs that allow for tractable answering of acyclic queries. Our proof-of-concept implementation raises hopes that efficient evaluation of large acyclic queries is feasible, but many challenges must still be addressed. 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 [Rodriguez-Muro and Calvanese, 2012] for handling the rules of type (5) appears particularly promising.

Acknowledgements The authors were supported by a Universit´e Paris-Sud Attractivit´e starting grant and ANR project PAGODA ANR-12-JS02-007-01 (Bienvenu), FWF project T515-N23 (Ortiz), FWF project P25518-N23 and WWTF project ICT12-015 (ˇSimkus), Vienna PhD School of informatics and EU project Optique FP7-318338 (Xiao).