Combined FO Rewritability for Conjunctive Query Answering in DL-Lite

Abstract

Standard description logic (DL) reasoning services such as satis ability and subsumption mainly aim to support TBox design. When the design has been completed and the TBox is used in an actual application, it is usually combined with instance data stored in an ABox, and therefore query answering becomes the most important reasoning service. In this context, conjunctive queries (CQs) have become very popular, and a rich literature on the subject has emerged in recent years; see, e.g., [5, 9, 12{14, 19, 22]. Unfortunately, CQ answering in expressive DLs of the ALC and SHIQ families is often computationally harder than satis ability and subsumption [11, 15], while in typical applications it is also much more time critical. To address this problem, it has been proposed to use standard relational database management systems (RDBMS) for DL query processing [7]. Indeed, the DL-Lite family of DLs was designed to allow CQ answering using standard RDBMSs while still capturing as much basic expressivity of ontology languages as possible [2, 3, 6{9, 20]. The basic idea behind CQ answering in DL-Lite is to store the ABox as a relational instance in the RDBMS and to rewrite the query to account for the implicit information represented in the TBox, of which the RDBMS is unaware. The foundation of this approach is captured formally by the notion of FO rewritability [8].1 Recently, an alternative approach to using RDBMSs for CQ answering in DLs has been proposed by generalizing FO rewritability to combined FO rewritability [17, 18]. In this new approach, the TBox is incorporated mainly into the ABox rather than into the query, though limited query rewriting is still necessary. Formally, a DL enjoys combined FO rewritability if, given a knowledge base (T ; A) and a CQ q, it is possible to e ectively rewrite (i) the ABox A and the TBox T into a nite FO structure M (independently of q) and (ii) q and (possibly) T into an FO query qy (independently of A) in such a way that query answers are preserved|i.e., the answers to qy over M are the same as the certain answers to q over (T ; A). Important members of the

Introduction

1 The term used in [ 8 ] is FO reducibility, but we prefer `rewritability' to avoid confusion with the complexity class FO from descriptive complexity.

E L family of DLs, which is incomparable in expressive power to the DL-Lite family, enjoy combined FO rewritability [17, 18]. In fact, this was originally the main motivation for introducing the more general notion of rewritability: while a DL can only enjoy FO rewritability if its data complexity for CQ answering is in LogSpace [ 8, 9 ] (actually, in AC0 [ 3 ]), PTime DLs such as those in the E L family can allow combined FO rewritability.

However, even for DLs such as DL-Lite in which the data complexity of CQ answering is in AC0, the novel approach to CQ answering can be useful. On the one hand, this approach presupposes authority over the data to implement ABox rewriting, which makes it unsuitable for applications in which only a query interface is provided such as virtual data integration. On the other hand, though, the increased exibility obtained by allowing to rewrite both the query and the ABox can be expected to enable more e cient query execution. In this context, it is interesting to note that the query rewriting for DL-Lite of the original approach [ 8, 9 ] involves an exponential blowup in the size of the query (the rewritten query is a union of (jT j jqj)jqj many CQs of length jqj), whereas the approach for E L [17, 18] does not involve such a blowup.

In this paper, we apply the novel approach to CQ answering pursued in [17, 18] to the DL-Lite family of DLs. More precisely, we concentrate on the DL-LitehNorn [ 2, 3 ] (which properly contains DL-LiteF;u of [ 8 ]) and show that it is possible to rewrite (i) every DL-LitehNorn TBox T and ABox A (independently of a given CQ q) to a nite FO structure of size O(jT j jAj) and (ii) every CQ q (independently of both T and A) into an FO query qy such that the answers are preserved. The proof is much less trivial than one might expect since, compared to E L, the presence of inverse roles in DL-Lite complicates matters considerably. This also results, in general, in the rewritten query qy to be of size 2O(jqj) and thus exponential in the size of q (which is commonly small), but independent of the size of T (which is often large). However, we identify a large and natural class of queries where the size of qy is only O(jqj2).

We perform an initial experimental evaluation of our approach and compare its performance to the approach of [ 8, 9 ] implemented in the QuOnto system [ 1, 21 ]. Summarized, the evaluation con rms the intuition that our combined approach should typically lead to smaller query execution times. In particular, the QuOnto rewriting often signi cantly blows up queries that use concepts with many subsumees, which typically leads to long query execution times. The execution times in our own approach are typically small if we stay within the identi ed query class that admits polynomial rewriting. On the negative side, the ABox rewriting can take long and should either be implemented o ine or using (yet to be developed) incremental techniques. 2

DL-LitehNorn The DL-Lite family of DLs was originally introduced in [7{9]. We consider DL-LitehNorn, the most expressive dialect of DL-Lite that does not include role inclusions and for which query answering is in AC0 for data complexity; for relations to other logics in the DL-Lite family see [ 3, 2 ]. Let NI, NC, and NR be countably in nite sets of individual names, concept names, and role names. Roles R and concepts C of DL-LitehNorn are de ned as follows, where P 2 NR, A 2 NC and m > 0:

R ::= P j P and

C ::= > j ? j A j m R: As usual, we write 9R for 1 R and identify (R ) with R. A DL-LitehNorn TBox is a nite set of concept inclusions (CIs) of the form C1 u u Cn v C; where C1; : : : ; Cn and C are concepts. For example, the CIs 2 R v ? and A u B v ? say that the role R is functional and that concepts A and B are disjoint, respectively. An ABox is a nite set of concept assertions A(a) and role assertions R(a; b), where A is a concept name, R a role and a; b 2 NI. We use Ind(A) to denote the set of individual names occurring in A. A DL-LitehNorn knowledge base (KB) is a pair (T ; A) with T a TBox and A an ABox. The semantics of the DL-LitehNorn constructs is de ned in the standard way [ 4 ], with the unique names assumption for ABox individuals. For I an interpretation, C1, C2 concepts, R a role, and a; b individual names, we use the notation I j= C1 v C2, I j= C1(a), and I j= R(a; b) with the usual meaning. A KB K = (T ; A) is consistent if there is an interpretation I with I j= for all 2 T [ A. In this case, we write I j= K and say that I is a model of K.

Let NV be a countably in nite set of variables. Taken together, the sets NV and NI form the set NT of terms. A rst-order (FO) query is a rst-order formula q = '(v) in the signature NC [ NR with terms from NT, where the concept and role names are treated as unary and binary predicates, respectively, and the sequence v = v1; : : : ; vk of variables from NV contains all the free variables of '. The free variables are called the answer variables of q, and q is k-ary if it has k answer variables. A conjunctive query (CQ, for short) is a rst-order query of the form q = 9u (u; v), where is a conjunction of concept atoms A(t) and role atoms P (t; t0) with t; t0 2 NT. The variables in u are called the quanti ed variables of q. We denote by var(q) the set of all variables in u and v, by qvar(q) the set of quanti ed variables, by avar(q) the set of answer variables, and by term(q) the set of terms in q.

For I an interpretation, q = '(v) a k-ary FO query, and a1; : : : ; ak 2 NI, we write I j= q[a1; : : : ; ak] if I satis es q with vi assigned to aiI , 1 i k. A certain answer for a k-ary CQ q and a KB K is a tuple (a1; : : : ; ak) such that a1; : : : ; ak occur in K and I j= q[a1; : : : ; ak] for each model I of K. We use cert(q; K) to denote the set of all certain answers for q and K. This de nes the query answering problem studied in this paper: given a DL-LitehNorn KB K and a CQ q, compute cert(q; K). 3

ABox Rewriting / Canonical Interpretations

The ABox rewriting part of our approach consists of expanding the ABox A to a canonical interpretation IK for the KB K = (T ; A). The ABox A can be viewed as a `fragment' of IK, i.e., every ABox individual is an element of IK , but there are also additional elements that witness existential and number restrictions. Expanding A to IK involves adding these additional elements, connecting them to the ABox individuals and other additional elements by means of roles, and adding extra concept memberships for the ABox individuals.

Let K = (T ; A) be a DL-LitehNorn knowledge base. For a role R, let domA(R) = fa 2 Ind(A) j 9b 2 Ind(A) R(a; b) 2 Ag: We call a role R generating w.r.t. K if there are a 2 Ind(A) and R1; : : : ; Rn such that Rn = R, K j= 9R1(a), a 62 domA(R1), and T j= 9Ri v 9Ri+1 for 1 i < n. In other words, R is generating w.r.t. K if every model I of K must contain a d 2 I with an incoming R-arrow but there is an I where no such d is identi ed by an individual in the ABox. The canonical interpretation IK for K is de ned now as follows:

IK = Ind(A) [ fxR j R is generating w.r.t. Kg; AIK = fa 2 Ind(A) j K j= A(a)g [ fxR 2 I j K j= 9R v Ag; P IK = f(a; b) 2 Ind(A) Ind(A) j P (a; b) 2 Ag [ f(a; xP ) j K j= 9P (a) and a 2= domA(P )g [ f(xP ; a) j K j= 9P (a) and a 2= domA(P )g [ f(xS; xP ) j K j= 9S f(xP ; xS) j K j= 9S v 9P and P 6= S g [ v 9P and P 6= Sg; aIK = a: In the above de nition, P ranges over role names, while R and S range over role names and their inverses. We do not discuss in detail how IK can be constructed in the context of database systems here; for a similar construction see [17]. Note that IK is nite by de nition, and that IK n Ind(A) can typically be expected to be relatively small.

Example 1. Consider the KB K = (T ; A) with

T = fA1 v A; A2 v A; 9P A = fA1(a); A2(b); S(a; b)g: v 9S; 9S v 9R; A v 9P g;

Then the canonical interpretation IK is as follows:

IK = fa; b; xP ; xS; xRg; AIK = fa; bg;

AIK = fag; 1

AIK = fbg; 2 P IK = f(a; xP ); (b; xP )g; SIK = f(a; b); (xP ; xS)g; RIK = f(b; xR); (xS; xR)g: We note that IK is not always a model of K. Indeed, this cannot be expected since DL-LitehNorn does not enjoy the nite model property whereas IK needs to be nite to be stored as a relational instance. As a concrete example, consider K = (T ; A) with T = fA v 9P; 2 P v ?g and A = fA(a); A(b)g. Then xP 2 ( 2 P )IK , and so IK 6j= K. From the perspective of query answering, this is not a problem. What is more problematic is that IK does not give the right answers to queries, i.e., it is not the case that IK j= q[a] i K j= q[a] for all k-ary CQs q and k-tuples a Ind(A). In contrast, the `unravelling' of IK into an (in nite) interpretation UK as introduced in the following does give the right answers to queries.

A path in IK is a nite sequence axR1 xRn , for n 0, where { a 2 Ind(A); { (aIK ; xR1 ) 2 R1IK ; { (xRi ; xRi+1 ) 2 RiIK , for 1 { Ri+1 6= Ri , for 1 i < n.

i < n; We denote by paths(IK) the set of all paths in IK and by tail(p) the last element in p 2 paths(IK). Then UK is de ned as follows:

UK aUK AUK P UK = paths(IK); = a for all a 2 Ind(A); = fp j tail(p) 2 AIK g; = f(a; b) j a; b 2 Ind(A) ^ P (a; b) 2 Ag [ f(s; s xP ) j s xP 2 UK g [ f(s xP ; s) j s xP 2

UK g; where ` ' denotes concatenation. Just like IK, UK is in general not a model of K. A simple example is given by T = fA v 2 P g and A = fA(a)g, where we have UK 6j= A v 2P because a is P -related only to xP in UK. Nevertheless, UK gives the right answers to all conjunctive queries. A proof of the following theorem can be found in the full version of this paper [16].

Theorem 1. For every satis able DL-LitehNorn KB K, every k-ary conjunctive query q, and every k-tuple a Ind(A), K j= q[a] i UK j= q[a]: In the next section, we show how to rewrite the query q such that the answers to q in UK (which is in nite and cannot be stored in a database) are identical to the answers to the rewritten query in IK, thus paving the way to using IK as a database instance for query answering. In the rewriting, we exploit several structural properties of IK and UK that follow immediately from the de nitions. Of particular interest are the following two properties: (p1) If (d; e); (d; e0) 2 RIK with e 6= e0, then d 2 Ind(A) or d = xR . (p2) If (d; e); (d; e0) 2 RUK with e 6= e0, then d 2 Ind(A).

We also use an additional concept name aux with the interpretations auxIK =

IK n Ind(A) and auxUK = UK n Ind(A). Thus, aux distinguishes the elements of IK used to satisfy existential restrictions and number restrictions from those that correspond to individual names. 4

Query Rewriting

We present a procedure that rewrites a k-ary CQ q into an FO query qy such that IK j= qy[a] i UK j= q[a], for all KBs K = (T ; A) and all k-tuples a Ind(A). Using Theorem 1 we obtain the intended answers to K and q by using an RDBMS to execute qy over IK stored as a relational instance.

Our construction of qy proceeds in two steps. First, we consider only queries q satisfying a syntactic condition of being free of bad spikes. For queries of this sort, we construct a rewriting q of size O(jqj2). In the second step, we show how an unrestricted query q can be transformed into a query qy that is a disjunction of queries free of bad spikes and such that the answers to q and qy coincide on interpretations UK. The size of qy is 2O(jqj). Applying the rst step to each disjunct, we thus obtain a rewriting of q of size 2O(jqj)2 . We note that the rst step is quite useful by itself as it establishes queries free of bad spikes as a large and natural class of queries that can be rewritten with only a polynomial blowup. 4.1

Polynomial Rewriting

To simplify the notation, we sometimes identify a CQ with the set of its atoms and do not distinguish atoms P (u; v) and P (v; u) in queries. To prepare for the rewriting of arbitrary queries, which uses the rewriting presented here as a sub-procedure, we allow the input query q to contain atoms :aux(v). Note that this is a purely technical issue and in applications aux(v) can be completely hidden from the user.

De nition 1. Let q be a conjunctive query. A subquery qc = fR0(t0; t1); R1(t1; t2); : : : ; Rn 1(tn 1; tn)g q is said to be a cycle if t0 = tn, ti 6= tj for 0 i < j < n, and R0 6= R1 if n = 2.

For n 3 each 5-tuple (ti; Ri; ti+n1; Ri+n1; ti+n2) with i < n and Ri = Ri+n1 is called a spike in qc, where +n denotes addition modulo n. The spike is bad w.r.t. q if ti+n1 is a quanti ed variable and :aux(ti+n1) 2= q. Now we call qc free of bad spikes if no spike in qc is bad w.r.t. q, and q is free of bad spikes if every cycle qc q is.

The condition that R0 6= R1 for n = 2 in the de nition of cycles ensures that the query fP (u; v)g, which is identi ed with fP (u; v); P (v; u)g, is not regarded as a cycle. Fix a query q = 9u ' that is free of bad spikes. De ne inductively sets Id(qi) by taking Id(q0) = f(t; t; ;) j t 2 term(q)g and, for i > 0,

Id(qi+1) = Id(qi) [ f(t1; t2; fRg) j 9(s1; s2; R) 2 Id(qi) 9R(t1; s1); R(t2; s2) 2 q (R 2= R)g [ f(t1; t2; R1 [ R2)) j 9s (t1; s; R1) 2 Id(qi) ^ (s; t2; R2) 2 Id(qi)g: Set Idq = Si 0 Id(qi) and let Cyc(q) be the set of quanti ed variables v occurring on some cycle in q. We de ne the rewriting of q as q = 9u (' ^ '1 ^ '2); where '1 '2 = = ^

^ v2avar(q)[Cyc(q) R(t;s);R(t0;s0)2q; (s;s0;R)2Idq;R 2=R

:aux(v); (s = xR) ! (t = t0) : The main result of this paper is the following theorem whose rather non-trivial proof can be found in [16]: Theorem 2. Let q = 9u ' be a k-ary CQ free of bad spikes. Then, for every knowledge base K and every k-tuple a Ind(A), IK j= q [a] i UK j= q[a]: Together, Theorems 1 and 2 show that the rewritten query q is as required. Clearly, the size of q is O(jqj2). We now give an intuitive explanation of this rewriting whose general purpose is to allow only matches in IK that can be `reproduced' in UK.

The conjunct '1 of q ensures that answer variables and variables in cycles are matched to ABox individuals. The former is required independently of whether we use UK or IK and just re ects the fact that query answers can contain ABox individuals only. The latter is more interesting. First, it is readily seen that no variable in a cycle can be matched to an element of auxUK if the cycle is free of bad spikes and thus, completeness is not compromised. To see why variables in cycles must be matched to ABox individuals to ensure soundness, consider the query q0 = 9v1; v2; v3(P1(v1; v2) ^ P2(v2; v3) ^ P3(v3; v1)). As q0 is a cycle, q0 = 9v1v2v3(P1(v1; v2)^P2(v2; v3)^P3(v3; v1)^:aux(v1)^:aux(v2)^:aux(v3)); where the :aux(vi) are introduced since the vi are in a cycle. To see that without this rewriting we would not get correct answers, consider K0 = (T0; A0) with T0 = fA v 9P1; 9P1 v 9P2; 9P2 v 9P3; 9P3 v 9P1g; A0 = fA(a)g: Then K 6j= q0 and thus UK 6j= q0, but IK j= q0. On the other hand, IK 6j= q0 .

To explain the conjunct '2, consider q1 = 9u (P (v; u) ^ P (w; u)). Then we have (v; w; fP g) 2 Id(q11) and, therefore,

q1 = 9u (P (v; u) ^ P (w; u) ^ :aux(v) ^ :aux(w) ^ (u = xP ! v = w)); where :aux(v) ^ :aux(w) is introduced by '1 since v and w are answer variables and the last conjunct is introduced by '2. Completeness is not compromised because, by (p2), no non-ABox element can be in a relation RUK to two distinct elements and u = xP implies that u is matched with a non-ABox element. To see that the last conjunct is necessary to ensure soundness, consider K1 = (T1; A1), for T1 = fA v 9P g and A1 = fA(a); A(b)g. Then K1 6j= q1[a; b] and thus UK1 6j= q1[a; b], but IK1 j= q1[a; b]. On the other hand, IK1 6j= q1 [a; b]. The use of the pre-condition u = xP instead of aux(u) for identifying v and w is one of the main di erences to the rewriting for EL in [17]. It re ects property (p1) of IK. 4.2

Exponential Rewriting

We now show how an unrestricted query q can be transformed into a query qy that is a disjunction of queries free of bad spikes and such that the answers to q and qy coincide on the interpretations UK.

Given a spike S = (t0; R0; t1; R1; t2), its center variable v(S) is t1 (which must, by de nition, be a quanti ed variable). We rewrite q = 9u ' into a disjunction of the form qy = _ 9u ('i ^ i ^ i); i (y) where 1. each 'i is a substitution instance of ' (obtained from ' by replacing terms); 2. each i is a conjunction of atoms aux(t);

3. each i is a conjunction of negated atoms :aux(t);

4. for each 'i and each spike S in a cycle in 'i, either v(S) is not quanti ed or :aux(v(S)) is a conjunct of i.

The last condition guarantees that each disjunct is free of bad spikes. Indeed, each disjunct is of the form discussed in the previous section and, using Theorem 2, we can apply the rewriting from the previous section to each disjunct of qy and get a rewriting for q that can be passed to an RDBMS for execution. Theorem 3. For every k-ary CQ q, one can construct an FO query qy of the form (y) such that, for every knowledge base K and k-tuple a Ind(A), we have UK j= q[a] i UK j= qy[a]: We now discuss the construction of qy in detail. The rewriting is iterative in the following sense: a single step rewriting obtains a formula of the form qy, but for which Condition 4 may not yet be satis ed. Hence we reapply the rewriting to the disjuncts of the obtained formula until Condition 4 is satis ed. For this reason, we assume that the input query q = 9u ' to the rewriting may contain atoms :aux(v). Let S(q) be the set of bad spikes S in cycles in q and let = fv(S) j S 2 S(q)g. For every subset U of , de ne an equivalence relation U on term(q) as the re exive and transitive closure of

f(t0; t1) j (t0; R; t; R0; t1) 2 S(q); t 2 U g: Intuitively, U is a `guess' identifying those variables in that are mapped to elements of auxUK , whereas all variables in n U are mapped to elements of IK that are identi ed by individual names. Having this guess allows us to eliminate bad spikes by (i) adding atoms :aux(v) for all v 2 n U and (ii) identifying all terms t; t0 with t U t0 as these have to be mapped to the same element in matches of q in UK by property (p2) from Section 3.

qU = 9u 'U ^ ^ aux(t ) ^ t2U

^ t2( nU) :aux(t ) ; where t is a representative of the U -equivalence class from ' by replacing every t in it with t . of t and 'U results Lemma 1. For every k-ary CQ q, every KB K, and every k-tuple a we have UK j= q[a] i UK j= WU qU [a]: Ind(A), Clearly, all bad spikes in q are eliminated during the construction of qU . However, as mentioned above, this elimination can introduce new bad spikes. So we apply the rewriting to the disjuncts of qU and repeat this process until we end up with a query satisfying Condition 4 above. This procedure must terminate since at least two terms are identi ed at each step. The outcome is the desired rewriting qy of q. It is not hard to see that it is of size 2O(jqj). 5

Experiments

We evaluate the performance of our combined FO rewriting technique by comparing it (i) with unrewritten queries over the original ABox, which does not yield correct results but provides an `ultimate lower bound' in the sense that queries cannot be expected to be executed any faster; and (ii) with the non-combined FO query rewriting introduced in [ 8, 9 ] and implemented in the QuOnto system [ 1, 21 ].

The experiments employ two DL-Lite ontologies formulated in DL-Litecore , the common fragment of DL-LitehNorn and the logic underlying QuOnto. The rst ontology, called Galen-Lite, is the DL-Litecore approximation of the wellknown medical ontology Galen: it consists of exactly those DL-Litecore concept inclusions (in the vocabulary of Galen) that are logical consequences of Galen. Galen-Lite contains 2734 concept names, 207 roles, and 4890 axioms. The second ontology is called Core; it is a DL-Litecore representation of (a fragment of) a supply-chain management system used by the bookstore chain Ottakar's, now rebranded as Waterstone's. Core contains 84 concept names, 77 roles, and 381 axioms. Galen-Lite de nes a complex concept hierarchy, but there are only few axioms that involve roles. This leads to canonical interpretations whose anonymous (i.e., non-ABox) part is relatively small. Core, in contrast, comprises more interesting statements about roles, which gives a richer anonymous part in canonical interpretations. Core's concept hierarchy, however, is not as sophisticated as the one of Galen-Lite. Both ontologies can be found at http://www.dcs.bbk.ac.uk/~roman/query-rewriting/.

In the experiments for the combined FO rewriting technique, we use the following representation of IK. As relational database systems are not optimized to handle a large number of relatively small relations, one for each concept and role name in the ontology, only two relations have been used to represent IK: acbox(conceptid,indid) and arbox(roleid,domain-indid,range-indid); where conceptid and roleid are numerical identi ers for concept names and roles names, indid, domain-indid, and range-indid are numerical identi ers for individuals, acbox represents concept memberships, and arbox role memberships. B+tree indices were created on the attribute pairs {conceptid,indid}, {roleid,domain-indid} and {roleid,range-indid}. We distinguish ABox individuals from anonymous ones by positive and negative ids, and thus need not store aux as a relation. As an example for this representation, take the query `q = A(x) ^ :aux(x)' which, with respect to the Core ontology (that merely provides the concept identi er for A), translates to the SQL statement select indid from acbox where conceptid=31 and indid > 0: Data sets (ABox instances) for our experiments were generated randomly. The data was stored and the test queries were executed on PostgreSQL version 8.3.7 running on a SUN Fire-280R server with two UltraSPARC III 1.2GHz CPUs, 4GB memory and 1TB storage under Solaris 5.10.

Figures 1 and 2 summarize the running times for each of the test queries and varying ABox size. For each ABox, we report the number of individuals (Ind, in thousands), the numbers of concept assertions (CAs, in millions) and role assertions (RAs, in millions) in the original ABox and in the rewritten ABox (i.e, the canonical interpretation). For each query, we show the following execution times in the columns UN, RW and QO: UN: the unmodi ed query over the original ABox; RW: the query rewritten as in Section 4 over the canonical interpretation from

Section 3; QO: the query produced by QuOnto (over the original ABox).

The queries referred to in the gure are as follows, where the symbols A; B; R, etc., stand for concept and role names in Core and Galen-Lite: coreQ1(x) = 9yz A(x); B(y); R(x; y); R(x; z); C(z) coreQ2(x) = 9yz R(x; y); S(x; z) coreQ3(x) = 9yz A(x); R(x; y); S(x; z) coreQ4(x) = 9xyzw R(x; y); R(z; y); R(x; w); R(z; w) galenQ1(x) = 9y A(x); R(x; y); B(y) galenQ2(x) = 9y A0(x); R0(x; y); B0(y) galenQ3(x) = 9yz A(x); B(y); R(x; y); R(x; z); C(z) galenQ4(x) = 9xyzw R(x; y); R(z; y); R(x; w); R(z; w) Thus, the only di erence between, say, coreQ1 and galenQ3 is that the abstract symbols have been replaced by distinct concept and role names. Note that coreQ4 and galenQ4 contain bad spikes, whereas all other queries are free of them. These queries show only a sample of the queries that we have tested, but the results are representative.

To evaluate the results, we rst compare the query processing times for the unmodi ed query over the original ABox (UN) with the times for our combined FO rewriting technique (RW). The gures show that RW is almost always less than 10 times longer than UN, in many case much less than 5 times longer. In terms of absolute numbers, RW queries are all answered within one minute, and usually even within a few seconds (just like UN queries). This applies even to the queries coreQ4 and galenQ4, for which an exponential rewriting is required. Finally, we observe that the performance of the combined FO rewriting approach is similar for Core and Galen-Lite, and thus does not seem to strongly depend on the structure of the TBox. We nd these results extremely encouraging: while our approach results in a considerable increase in the ABox size and rewriting the ABox may take some time (up to an hour using standard RDBMSs, which are not optimized for this task), the actual query execution is usually not signi cantly slower than the `ultimate lower bound'.

We now compare UN/RW with the QuOnto approach, which results in query execution times that are much less favorable for both Core and Galen. To explain this discrepancy, recall that the RW approach rewrites the query independently of the TBox, whereas QuOnto rewriting does depend on the TBox. To see a basic example of this dependence, consider q(x) = A(x) and T = fA1 v A; A2 v Ag, where the QuOnto rewriting is q0(x) = A(x) _ A1(x) _ A2(x), i.e., there is one disjunct for each subsumee of the concept A in the query. Galen-Lite is a TBox in which many concepts have a lot of subsumees. For example, the concepts A and B in galenQ2 have 39 and 11 (direct and indirect) subsumees, which results in 429 subqueries; galenQ3 even generates 3072 subqueries.

Other sources of query expansion in QuOnto stem from mandatory role participation assertions and the possibility of query folding due to multiple occurrences of the same role. Like many ontologies originating from ER design, the Core TBox contains such constraints. For the queries coreQ1, coreQ2, and coreQ3, this results in 180, 310, and 2100 disjuncts in the rewritten query, respectively. We note that the weak performance of QuOnto on coreQ1 and coreQ3 over the Core TBox can, in part, be traced to poor query optimizer choices. On queries with very many disjuncts, the probability of the optimizer choosing a bad strategy for at least one of the disjuncts is rather high, and the resulting execution time will dominate the execution time of the overall query. 6

Conclusion

We introduce a novel approach to CQ answering over DL-LitehNorn TBoxes using relational database systems. Our experimental evaluation suggests that, in applications where the user has authority over the data and can implement ABox rewriting, this approach may be preferable to the TBox-based rewriting [ 8, 9 ]. The work presented in this paper is only a rst step: future work includes an adaptation of our approach to variants of DL-Lite with role hierarchies, extending the class of CQs for which a polynomial rewriting is possible, nding a more careful exponential rewriting step, and developing incremental approaches to ABox rewriting. It might also be interesting to combine the ideas underlying query rewriting in QuOnto with ABox rewriting to improve query execution times in the QuOnto approach. 16. C. Lutz, R. Kontchakov, D. Toman, F. Wolter, and M. Zakharyaschev. Combined FO rewritability for conjunctive query answering in DL-Lite. Available at http: //www.informatik.uni-bremen.de/~clu/, 2009. 17. C. Lutz, D. Toman, and F. Wolter. Conjunctive query answering in EL using a database system. In Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008), 2008. 18. C. Lutz, D. Toman, and F. Wolter. Conjunctive Query Answering in the Description Logic EL using a Relational Database System. In Proc. of the 21th Int. Joint Conf. on Arti cial Intelligence (IJCAI 2009), page in press, 2009. 19. M. Ortiz, D. Calvanese, and T. Eiter. Data complexity of query answering in expressive description logics via tableaux. J. of Automated Reasoning, 41(1):61{ 98, 2008. 20. A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati.

Linking data to ontologies. J. on Data Semantics, X:133{173, 2008. 21. A. Poggi, M. Rodriguez, and M. Ruzzi. Ontology-based database access with DIG-Mastro and the OBDA Plugin for Protege. In Kendall Clark and Peter F. Patel-Schneider, editors, Proc. of the 4th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 DC), 2008. 22. H. Perez-Urbina, B. Motik, and I. Horrocks. Rewriting Conjunctive Queries over Description Logic Knowledge Bases. In Proc. of the 3rd Int. Workshop on Semantics in Data and Knowledge Bases (SDKB 2008), number 4925 in LNCS, pages 199{214, Springer, 2008.

References

1. A. Acciarri , D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , M. Palmieri , and R. Rosati . QuOnto: Querying ontologies . In Proc. of the 20th Nat. Conf. on Arti cial Intelligence (AAAI 2005 ), pages 1670 { 1671 , 2005 .

2. A. Artale , D. Calvanese , R. Kontchakov , and M. Zakharyaschev . DL-Lite in the light of rst-order logic . In Proc. of the 22nd Nat. Conf. on Arti cial Intelligence (AAAI 2007 ), pages 361 { 366 , 2007 .

3. A. Artale , D. Calvanese , R. Kontchakov , and M. Zakharyaschev . The DL-Lite family and relations . Technical Report BBKCS-09-03 , SCSIS, Birkbeck College, London, 2009 (available at http://www.dcs.bbk.ac.uk/research/techreps/2009/ bbkcs-09-03.pdf).

4. F. Baader , D. Calvanese , D. McGuinness , D. Nardi , and P. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2003 .

5. D. Calvanese , G. De Giacomo, and M. Lenzerini . On the decidability of query containment under constraints . In PODS'98 , pages 149 { 158 , New York, NY, USA, 1998 . ACM.

6. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , A. Poggi , R. Rosati , and M. Ruzzi . Data integration through DL-LiteA ontologies . In K.- D. Schewe and B. Thalheim, editors, Revised Selected Papers of the 3rd Int. Workshop on Semantics in Data and Knowledge Bases (SDKB 2008 ), volume 4925 of Lecture Notes in Computer Science, pages 26 { 47 . Springer, 2008 .

7. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . DL-Lite: Tractable description logics for ontologies . In Proc. of the 20th Nat. Conf. on Arti cial Intelligence (AAAI 2005 ), pages 602 { 607 , 2005 .

8. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Data complexity of query answering in description logics . In Proc. of the 10th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2006 ), pages 260 { 270 , 2006 .

9. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Tractable reasoning and e cient query answering in description logics: The DL-Lite family . J. of Automated Reasoning , 39 ( 3 ): 385 { 429 , 2007 .

10. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Inconsistency tolerance in P2P data integration: An epistemic logic approach . Information Systems , 33 ( 4 ): 360 { 384 , 2008 .

11. T. Eiter , C. Lutz , M. Ortiz , and M. Simkus . Query answering in description logics with transitive roles . In Proceedings of the 21st International Joint Conference on Arti cial Intelligence IJCAI09 . AAAI Press, 2009 .

12. B. Glimm , I. Horrocks, C. Lutz , and U. Sattler . Conjunctive query answering for the description logic SHIQ . In Proc. of the 20th Int. Joint Conf. on Arti cial Intelligence (IJCAI 2007 ), pages 399 { 404 , 2007 .

13. B. Glimm , I. Horrocks , and U. Sattler . Conjunctive query answering for description logics with transitive roles . In Proceedings of the 2006 Description Logic Workshop (DL 2006 ). CEUR Workshop Proceedings , 2006 .

14. I. Horrocks and S. Tessaris . A conjunctive query language for description logic ABoxes . In In AAAI/IAAI, pages 399 { 404 , 2000 .

15. C. Lutz. The complexity of conjunctive query answering in expressive description logics . In A. Armando, P. Baumgartner , and G. Dowek, editors, Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR2008) , number 5195 in LNAI , pages 179 { 193 . Springer, 2008 .