Introduction
Description logics (DLs) have recently been used to provide access to large
amounts of data through a high-level conceptual interface, which is of relevance
in several application contexts, notably data integration and ontology-based data
access. Besides the traditional reasoning services of knowledge base satis ability
and instance checking, a further important service in that context is that of
answering complex database-like queries by fully taking into account the axioms
in the TBox and the data stored in the ABox. The key property for such an
approach to be viable in practice is the e ciency of query evaluation, in
particular for conjunctive queries and, more generally, for positive existential queries
(this class of queries includes unions of conjunctive queries) [
Successive work [
Combined complexity DL-Lite(cRorNe)
Satis ability NLogSpace
P [Th.1] NLogSpace
[Th.1] NP [Th.1]
Data complexity Instance checking
Query answering in AC0 in AC0 in AC0 in AC0 [Th.2]
in AC0 in AC0
[Th.3]
coNP [
DL-LitebNool which allows full Booleans as concept constructs. (Note that these
results hold only under the unique name assumption. DL-Lite logics without
this assumption are investigated in [
One aim of this paper is to extend DL-LitehNorn, DL-LitebNool and their
fragments with a number of new constructs without spoiling their
computational properties. The resulting logic is called DL-Lite(hRorNn). Another aim is to
present explicit (exponential) FO rewritings of positive existential queries over
DL-Lite(hRorNn) KBs. The constructs we add to our logics are as follows: (i) role
inclusions, (ii) quali ed number restrictions, and (iii) role disjointness,
symmetry, asymmetry, re exivity, and irre exivity constraints. Needless to say that
when adding (i) and (ii), we have to restrict the interaction of these constructs
with number restrictions (otherwise, even the logic DL-LitecRo;rFe with extremely
primitive concept inclusions, but with unrestricted role inclusions and global
functionality constraints is ExpTime-complete for combined complexity and
Pcomplete for data complexity [
The complexity results obtained in this paper are summarized in Table 1. 2
DL-Lite(bRooNl ) and its fragments We start by de ning the description logic DL-Lite(bRooNl ), the most expressive of our logics, which subsumes, in particular, all members of the DL-Lite family [6{8].
The language of DL-Lite(bRooNl ) contains object names a0; a1; : : : , concept names A0; A1; : : : , and role names P0; P1; : : : . Complex concepts C and roles R are de ned as follows:
B C ::= ::= ? j Ai j B j :C j q R; q R:C j C1 u C2;
R ::=
Pi j Pi ; where q is a positive integer. The concepts of the form B will be called basic. A DL-Lite(bRooNl ) TBox, T , is a nite set of concept inclusions (CIs, for short), role inclusions, and role constraints of the form:
C1 v C2;
R1 v R2;
Dis(R1; R2);
Irr(Pk); and
Ref(Pk):
We write inv(R) for Pk if R = Pk, and for Pk if R = Pk . Denote by vT the
re exive and transitive closure of f(R; R0); (inv(R); inv(R0)) j R v R0 2 T g. Say
tfohlalotwRi n0gissaynptraocpteirc scuobn-driotlieonosf oRn iDnLT-LiifteR(bRo0oNvl)TTBoxes T (cf. DL-LiteA [
It follows that no TBox can contain both a functionality constraint 2 R v ? and an occurrence of q R:C, for some q 1 and some role R.
An ABox, A, is a nite set of assertions of the form: Ak(ai), Pk(ai; aj ) and :Pk(ai; aj ). Taken together, T and A constitute the DL-Lite(bRooNl ) knowledge base (KB, for short) K = (T ; A).
As usual in description logic, an interpretation, I = ( I ; I ), consists of
a nonempty domain I and an interpretation function I that assigns to each
object name ai an element aiI 2 I , to each concept name Ai a subset AiI I ,
and to each role name Pi a binary relation PiI I I . In this paper, we
adopt the unique name assumption (UNA): aiI 6= ajI , for all i 6= j, and refer the
reader to [
The role and concept constructs are interpreted in I in the standard way. We will also use standard abbreviations such as > = :?, 9R = ( 1 R) and q R = :( q + 1 R). The satisfaction relation j= is also standard; we only mention here that I j= Dis(R1; R2) i R1I \ R2I = ; (R1 and R2 are disjoint ), I j= Irr(Pk) i (x; x) 2= PkI for all x 2 I (Pk is irre exive), I j= Ref(Pk) i (x; x) 2 PkI for all x 2 I (Pk is re exive). Note that symmetric and asymmetric role constraints can be regarded as syntactic sugar in this language: Sym(Pk) and Asym(Pk) can be equivalently replaced with Pk v Pk and Dis(Pk; Pk ), respectively (extending a TBox with Pk v Pk cannot violate (inter) as Pk is not a proper sub-role of Pk). A KB K = (T ; A) is said to be satis able (or consistent ) if there is an interpretation, I, satisfying all the members of T and A. In this case we write I j= K (as well as I j= T and I j= A) and say that I is a model of K.
It is to be emphasized that such constructs as role constraints and quali ed number restrictions are used in conceptual modeling and also belong to the OWL 2 proposal; moreover, as we show, adding them does not a ect the computational complexity of our logics.
Similarly to classical logic, we adopt the following de nitions: a TBox T is :B1 v B2; { a DL-Lite(hRorNn) TBox if its CIs are of the form B1 u u Bk v B (the Bi and B are basic concepts and, by de nition, the empty conjunction is >); { a DL-Lite(kRroNm) TBox2 if its CIs are of the form B1 v B2; B1 v :B2 or 1 An occurrence of a concept on the right-hand (resp., left-hand) side of a concept inclusion is called negative if it is in the scope of an odd (resp., even) number of negations :; otherwise the occurrence is called positive. 2 The Krom fragment of rst-order logic consists of all formulas in prenex normal form whose quanti er-free part is a conjunction of binary clauses. { a DL-Lite(cRorNe) TBox if its CIs are of the form B1 v B2 or B1 v :B2. As B1 v :B2 is equivalent to B1 u B2 v ?, core TBoxes can be regarded as both Krom and Horn TBoxes. We note here that a concept C occurring in T in some q R:C can be a conjunction of any concepts allowed on the right-hand side of concept inclusions in the respective language. 3
DL-Lite in the Light of First-Order Logic Our main aim in this section is to prove the upper combined complexity bounds for reasoning in DL-Lite(bRooNl ) and its fragments and develop the technical tools we need to investigate the data complexity of query answering in DL-Lite(hRorNn).
For a DL-Lite(bRooNl ) KB K = (T ; A), denote by role (K) the set of role names occurring in K and their inverses and by ob(A) the set of object names occurring in A. Let QTR be the set of natural numbers containing 1 and all the numerical parameters q such that q R or q R:C occurs in T . Note that jQTR j 2 if T contains a functionality constraint for R. Our main result in this section is: Theorem 1. (i) Satis ability of DL-Lite(bRooNl ) KBs is NP-complete; (ii) satis ability of DL-Lite(hRorNn) KBs is P-complete; and (iii) satis ability of DL-Lite(kRroNm) and DL-Lite(cRorNe) KBs is NLogSpace-complete.
Let us consider rst the sub-language of DL-Lite(bRooNl ) without quali ed number restrictions and role constraints, which will be required for purely technical reasons; we denote it by DL-Lite(bRooNl ). In Section 4, we will also use DL-Lite(hRorNn).
Let K = (T ; A) be a DL-Lite(bRooNl ) KB and let Id be a distinguished role name, which will be used to simulate the identity relation required for encoding the role constraints. We assume that either K does not contain Id at all or satis es the following conditions: (Id1) Id(ai; aj ) 2 A i i = j, for all ai; aj 2 ob(A), (Id2) > v 9Id; Id v Id T , and QITd = QITd = f1g, (Id3) Id is only allowed in role inclusions of the form Id if this is not the case we can always introduce the mQisRs0inwghneunmevbeerrsRinvQTR0 , e.g., We assume, without loss of generality, that QTR T R0 (for by adding ? v q R0 to the TBox). T
We present now a reduction of the satis ability problem for DL-Lite(bRooNl ) KBs to satis ability of rst-order formulas with one variable, or QL1-formulas. With every object name ai 2 ob(A) we associate the individual constant ai of QL1 and with every concept name Ai the unary predicate Ai(x) from the signature of QL1. For each role R 2 role (K), we introduce jQTR j-many fresh unary predicates EqR(x); for q 2 QR . The intended meaning of these predicates
T is as follows: for a role name Pk, E1Pk(x) and E1Pk (x) represent the domain and range of Pk, respectively; more generally, for each q 2 QR , EqPk(x) and T EqPk (x) represent the sets of points with at least q distinct Pk-successors and at v Id and Id v R. least q distinct Pk-predecessors, respectively. We write inv(EqR)(x) for EqPk (x) if R = Pk, and for EqPk(x) if R = Pk . Additionally, for every pair of roles Pk; Pk 2 role (K), we take two fresh individual constants dpk and dpk of QL1, which will serve as `representatives' of the points from the domain and range of Pk, respectively (provided that it is not empty). Denote the set of all those dpk and dpk by dr(K) and write inv(dr) for dpk if R = Pk, and for dpk if R = Pk . By induction on the construction of concept C we de ne the QL1-formula C : ? = ?; (Ai) (:C) = Ai(x); = :C (x); ( q R)
= EqR(x); (C1 u C2) = C1 (x) ^ C2 (x): For every role R 2 role (K), we need two QL1-formulas: "R(x) =
R(x) =
E1R(x) ! inv(E1R)(inv(dr)); ^
Eq0 R(x) ! EqR(x) : q;q02QR; q0>q
T q0>q00>q for no q002QTR i ^ Formula "R(x) says that if the domain of R is not empty then its range is not empty either: it contains the constant inv(dr), the `representative' of the domain of inv(R). The meaning of R(x) should be obvious. For a KB K, we de ne h Kze = 8x T
R(x) ^
^ R2role (K) "R(x) ^ R(x) ^
Aze ; where T R(x) =
C1 (x) ! C2 (x) C1vC22T ^ ^
Ak(ai)2A Aze =
Ak(ai) ^ ^
EqRe;a R(a) R(a;a0)2CleT (A) ^
^ ^ RvR02T or q2QTR inv(R)vinv(R0)2T
EqR(x) ! EqR0(x) ; ^ (:Pk(ai; aj ))?e ; :Pk(ai;aj)2A CleT (A) = fR0(ai; aj ) j R(ai; aj ) 2 A; R vT R0g,3 qRe;a is the maximum number in QR such that there are qR;a many distinct ai with R(a; ai) 2 Cle (A), and e
T T (:Pk(ai; aj ))?e = ? if Pk(ai; aj ) 2 Cle ( ) and > otherwise. Note that the size
T A
of Kze is linear in the size of K, no matter whether the numerical parameters are
coded in unary or in binary. The following lemma is an analogue of [3, Theorem 1]
(for the proof see [
KB K is satis able i the QL1-sentence Kze is
It should be clear that the translation ze can be computed in NLogSpace for
combined complexity. Indeed, this is trivial for the rst conjunct of Kze . To
compute Aze , we rst need to be able to check, given a role R and a pair of
objects ai, aj , whether R(ai; aj ) 2 CleT (A) and second, given R(a; a0) 2 CleT (A), to
3 We slightly abuse notation and write R(ai; aj) 2 A to indicate that Pk(ai; aj) 2 A
if R = Pk, or Pk(aj; ai) 2 A if R = Pk .
compute qRe;a. The R(ai; aj ) 2 CleT (A) test can be done by a non-deterministic
algorithm using space logarithmic in jrole (K)j (see, e.g., the NLogSpace
die
rected graph reachability problem [
T e T reached. The resulting qR;a is the maximum number in QR not exceeding q. T
As follows from the proof of Lemma 1, for a DL-Lite(bRooNl ) KB K = (T ; A), every model M of Kze induces a model IM of K with the following properties: (abox) For all ai; aj 2 ob(A), (aiIM ; ajIM ) 2 RIM i R(ai; aj ) 2 CleT (A). (uniq) The object names a 2 ob(A) induce a partitioning of IM into disjoint labeled trees Ta = (Ta; Ea; `a) with nodes Ta, edges Ea, root aIM , and a labeling function `a : Ea ! role (K) n fId; Id g. (cp) There is a function cp : IM ! ob(A) [ dr(K) such that cp(aIM ) = a for a 2 ob(A), and cp(w) = dr, for role R such that w0 2 Ta, (w0; w) 2 Ea and `a(w0; w) = inv(R), for some a 2 ob(A). (iso) For each R 2 role (K), all labeled subtrees generated by w 2 IM with cp(w) = dr are isomorphic. (con) For all basic concepts B in K and w 2 IM , w 2 BIM i M j= B [cp(w)]. (role) For every role name Pk, including Id,
P IM = (aiIM ; ajIM ) j R(ai; aj ) 2 A; R vT Pk k [ (w; w) j Id vT Pk [ (w; w0) 2 Ea j a 2 ob(A); `a(w; w0) = R; R vT Pk : of DL-Lite(bRooNl ) Such a model will be called an untangled model of K (the untangled model of K induced by M, to be more precise). It should be pointed out that there are two main distinguishing features of untangled models for DL-Lite(bRooNl ) KBs: (i) there are at most job(A)j + jrole (K)j di erent types of points in them, and (ii) although two points may be connected by a set of roles , one can always select R 2 such that is an upward closure of fRg under vT , provided that one of the points is not from ob(A).
The following lemma reduces satis ability of DL-Lite(bRooNl ) KBs to satis ability
KBs (for the proof see [4, Lemma 5.17]): Lemma 2. For every DL-Lite(bRooNl ) KB K0 = (T 0; A0), one can construct (in linear time and logarithmic space) a DL-Lite(bRooNl ) KB K = (T ; A) such that { every untangled model IM of K is a model of K0, provided that there are no R1(ai; aj ); R2(ai; aj ) 2 Cle ( ) with Dis(R1; R2) 2 T 0, and
T A
there is no R(ai; ai) 2 Cle (A) with Irr(R) 2 T 0;
{ every model I0 of K0 gives risTe to a model I of K based on the same domain
as I0 and such that I agrees with I0 on all symbols from K0.
1
formTuhleao, rfeomra1DfoLl-lLowitse(bfRorooNl m)KLBem,amuansiv2earsnadl H1,otrhneQoLbs1e-rfovramtiounlat,hfoart aKDzeLi-sLaitQe(hRLorNn-)
KB, and a universal Krom QL1-formula, for a DL-Lite(kRroNm) KB, and the
complexity results for the respective fragments of QL1 [
For the data complexity the following result is proved in [4, Section 6]: Theorem 2. The satis ability and instance checking problems for DL-Lite(bRooNl ) KBs are in AC0 for data complexity. 4
FO Rewritability of Query Answering In this section we study the data complexity of query answering over DL-Lite(hRorNn) KBs. We assume that all concept and role names of a KB occur in its TBox and write role (T ) and dr(T ) instead of role (K) and dr(K), respectively. Denote by Bcon(T ) the set of basic concepts occurring in T (i.e., concepts of the form A and q R, for a concept name A occurring in T , R 2 role (T ) and q 2 QTR).
A positive existential query q(x) is a rst-order formula '(x) constructed by means of conjunction, disjunction and existential quanti cation from atoms of the from A(t1) and P (t1; t2), where t1; t2 are terms taken from the list of variables y0; y1; : : : and object names a0; a1; : : : . The free variables of ' are called distinguished variables of q. An assignment a in I is a function associating with each variable y an element a(y) of I . We write aiI;a = aiI and yI;a = a(y). For K = (T ; A), say that a tuple a of object names from A is a certain answer to q(x) w.r.t. K, and write K j= q(a), if I j= q(a) whenever I j= K. The query answering problem is, given K, a query q(x) and a ob(A), decide whether K j= q(a). Our main result in this section is the following: Theorem 3. The positive existential query answering problem for DL-Lite(hRorNn) KBs is in AC0 for data complexity.
Proof. Suppose that we are given a consistent DL-Lite(hRorNn) KB K0 = (T 0; A0) and a positive existential query in prenex form q(x) = 9y '(x; y), y = y1; : : : ; yk, in the signature of K0. Consider the DL-Lite(hRorNn) KB K = (T ; A) provided by Lemma 2. The untangled models of K produce exactly the same answers as K0: Lemma 3. For every tuple a of object names in K0, we have K0 j= q(a) i I j= q(a) for all untangled models I of K.
Next we show that, as Kze is a universal Horn sentence, it is enough to
consider just one special untangled model I0 of K. Let M0 be the minimal
Herbrand model of Kze . We remind the reader (see, e.g., [
Kze j= B (c); for all c 2 and B 2 Bcon(T ): Denote by I0 the untangled model of K induced by M0 and its domain by By Lemma 1 with (con) and (cp),
i 2 BI0 i aI0
K j= B(ai);
for all ai 2 ob(A) and B 2 Bcon(T ): For each R 2 role (T ), by Lemma 1, if RI0 6= ; then M0 j= (9R) [dr] and thus, (T [ f9R v ?g; A) is not satis able, whence RI 6= ;, for all models I of K. Moreover, if RI0 6= ; then w 2 BI0 i
K j= 9R v B; for all w 2
I0 with cp(w) = dr;
(2) where cp : I0 !
is the function provided by (cp).
Lemma 4. If I0 j= q(a) then I j= q(a) for all untangled models I of K. Proof. Suppose I j= K. As q(a) is a positive existential sentence, it is enough to construct a homomorphism h : I0 ! I. By (uniq), I0 is partitioned into trees Ta, for a 2 ob(A). De ne the depth of w 2 I0 to be the length of the path in the respective tree from its root to w. Denote by Wm the set of points of depth m; in particular, W0 = faI0 j a 2 ob(A)g. We construct h as the union of homomorphisms hm : Wm ! I, m 0, such that hm+1(w) = hm(w), for all w 2 Wm. For the basis of induction, set h0(aiI0 ) = aiI , for ai 2 ob(A); h0 is a homomorphism by (1) and (abox). For the induction step, suppose hm has been de ned. If v 2 Wm, set hm+1(v) = hm(v). Otherwise, v 2 Wm+1 n Wm. By (uniq), there is a unique u 2 Wm with (u; v) 2 Ea, for some a 2 ob(A). Let `a(u; v) = S. By (cp), cp(v) = inv(ds) and, by (role), u 2 (9S)I0 . As hm is a homomorphism, hm(u) 2 (9S)I , whence there is w 2 I with (hm(u); w) 2 SI . Set hm+1(v) = w. As (9inv(S))I0 6= ;, cp(v) = inv(ds) and w 2 (9inv(S))I , by (2), if v 2 BI0 then w 2 BI , for all B 2 Bcon(T ). It remains to show that (w; v) 2 RI0 implies (hm+1(w); hm+1(v)) 2 RI . By (role), we have (w; v) 2 RI0 , for w 2 Wm+1 and v 2 Wm+1 n Wm, just in two cases: either w 2 Wm+1 n Wm, and then w = v with Id vT R, or w 2 Wm, and then w = u with S vT R. In the former case, (hm+1(v); hm+1(v)) 2 IdI RI . In the latter case, (u; v) 2 SI0 ; hence (hm+1(u); hm+1(v)) 2 SI RI . tu
Our next lemma shows that to check whether I0 j= q(a) it su ces to consider only the set of points Wm0 of depth m0 in I , for some m0 that does not depend on jAj (see [4, Lemma 7.4] for the proof): Lemma 5. Let m0 = k + jrole (T )j. If I0 j= 9y '(a; y) then there is an assignment a0 in Wm0 (i.e., a0(yi) 2 Wm0 for all i) such that I0 j=a0 '(a; y).
To complete the proof of Theorem 3, we encode the problem `K j= q(a)?' as a model checking problem for rst-order formulas. We x a signature that contains a unary predicate Ak(x) for each concept name Ak and a binary predicate Pk(x; y) for each role name Pk, and then represent the ABox A of K as a rst-order model AA with domain ob(A): for each ai; aj 2 ob(A), AA j= Ak[ai] i
Ak(ai) 2 A and
AA j= Pk[ai; aj] i
Pk(ai; aj) 2 A: Now we de ne a rst-order formula 'T ;q(x) in the above signature such that (i) 'T ;q(x) depends on T and q but not on A, and (ii) AA j= 'T ;q(a) i I0 j= q(a).
To simplify the presentation, we denote by e(T ) the extension of T with: { q0 R v q R, for all R 2 role (T ) and q; q0 2 QTR with q0 > q, and { q R v q R0, for all q 2 QTR and R v R0 2 T or inv(R) v inv(R0) 2 T . It follows from the de nition of ze and Lemma 1 that, for a Horn concept inclusion C v B, we have T j= C v B i (C (x) ! B (x)) is a logical consequence of f(Ci (x) ! Bi (x)) j Ci v Bi 2 e(T )g.
We begin by de ning formulas B(x), B 2 Bcon(T ), that describe the types of the elements of ob(A) in the model I0 in the following sense (cf. (1)): AA j= These formulas are de ned as the ` xed-points' of sequences of formulas with one free variable, where B0(x); B1(x); : : : if B = A; if B =
q R; for i 1; 8 >A(x); B0(x) = <
9y1 : : : 9yq h > : Bi(x) =
B0(x)
^ 1 i<j q _
(yi 6= yj ) ^ _
Bi11(x) ^ B1u uBkvB2e(T )
^ 1 i q
RT (x; yi)i; ^
Bik1(x) ; and RT (x; y) = WPkvT R Pk(x; y) _ W R Pk(y; x). Clearly, if there is an i such that, for all B 2 Bcon(T ), Bi(x) Pk vBi+T1(x), i.e., every Bi(x) is equivalent to Bi+1(x) in rst-order logic, then Bi(x) Bj(x) for all B 2 Bcon(T ), j i. TheNmexintimweu mintsruocdhuicedoseesntneontceexsceBed;drN, f=orjBBco2n(BTco)jn, (sTo )waensdetdrB2(xd)r=(T ),BNt(hxa)t. describe the types of the elements of dr(T ) in I0 in the following sense (cf. (2)): AA j=
B;dr i w 2 BI0 ; for each (some) w 2
I0 with cp(w) = dr: (4) These sentences are de ned similarly to the B(x): namely, for each B 2 Bcon(T ) and dr 2 dr(T ), we consider a sequence B0;dr; B1;dr; : : : by taking B;dr = 0B;dr; 0
Bi;dr = iB;dr _ _ Bi11;dr ^
B1u uBkvB2e(T ) where iB;dr = ?, for all B 6= 9R and i 0, and
i 1 ^ Bk;dr ; for i 1; 0 9R;dr = 9x 9inv(R)(x) and i 9R;dr =
_ ds2dr(T ) i 1 9inv(R);ds; for i 1: We have Bi;dr Bi+;d1r for some i M = N jrole (T )j. So, let B;dr = BM;dr.
Now we consider the directed graph GT = (VT ; ET ), where VT is the set of all equivalence classes [R], [R] = fR0 j R vT R0; R0 vT Rg, such that 9R is not empty in some model of T , and ET is the set of all pairs ([Ri]; [Rj ]) such that (path) T j= 9inv(Ri) v q Rj and either inv(Ri) 6vT Rj or q 2, and Rj has no proper sub-role satisfying (path). We have ([Ri]; [Rj ]) 2 ET i , for any ABox A0, whenever the minimal untangled model I0 of (T ; A0) contains a copy w of inv(dri0), for Ri0 2 [Ri], then w is connected to a copy of inv(drj0 ), for Rj0 2 [Rj ], by all relations S with Rj vT S. Let T ;m0 be the set of all paths in GT of length m0 (as in Lemma 5):
T ;m0 = " [ ([R1]; : : : ; [Rn]) j 1 n
m0 & ([Rj ]; [Rj+1]) 2 ET ; for j < n : For ; 0 2 T ;m0 and R 2 role (T ), we write !R 0 if (i) = 0 and Id vT R or (ii) :[S] = 0 or (iii) = 0:[inv(S)], for some S with S vT R.
Let Tk ;m0 be the set of all k-tuples of the form = ( 1; : : : ; k), i 2 T ;m0 . Intuitively, when evaluating the query 9y '(x; y) over I0, each bound, or nondistinguished, variable yi is mapped to a point w in Wm0 . However, the rstorder model AA does not contain the points from Wm0 n W0, and to represent them, we use the following `trick.' By (uniq), every point w in Wm0 is uniquely determined by the pair (a; ), where aI0 is the root of the tree Ta containing w, and is the sequence of labels `a(u; v) on the path from aI0 to w. It follows from the unraveling procedure and (path) that 2 T ;m0 . So, in the formula 'T ;q we are about to de ne we assume that the yi range over W0 and represent the rst component of the pairs (a; ), whereas the second component is encoded in the ith member of (these yi should not be confused with the yi in the original query q, which range over all of Wm0 ). In order to treat arbitrary terms t occurring in '(x; y) in a uniform way, we set t = ", if t = a 2 ob(A) or t = xi, and t = i, if t = yi (the distinguished variables xi and the object names a are mapped to W0 and do not require the second component of the pairs).
Given an assignment a0 in Wm0 we denote by split(a0) the pair (a; ), where a is an assignment in AA and = ( 1; : : : ; k) 2 Tk ;m0 are such that { for each distinguished variable xi, a(xi) = a with aI0 = a0(xi); { for each bound variable yi, a(yi) = a and i = ([R1]; : : : ; [Rn]), n m0, with aI0 being the root of the tree containing a0(yi) and R1; : : : ; Rn being the sequence of labels `a(u; v) on the path from aI0 to a0(yi).
Not every pair (a; ), however, corresponds to an assignment in Wm0 because some paths in may not exist in our I0: GT represents possible paths in all models for the xed TBox T and varying ABox. As follows from the unraveling pr=oce([dRu]r;e:,: :a),pioinathians nWomt0ennouWg0h Rco-rwreitsnpeosnsdess itnoAa: A2Aoj=b(A:) 0aqnRd[a] ^2 qTR;m[a0],, for some q 2 QTR. Thus, for every (a; ) with = ( 1; : : : ; k), there is an assignment a0 in Wm0 with split(a0) = (a; ) i AA j=a (y), where (y) = ^
_ 1 i k q2QTRi i6=" : 0 q Ri (yi) ^ q Ri (yi) and each Ri, for 1 i k with i 6= ", is such that i = ([Ri]; : : : ).
We de ne now, for every 2 Tk ;m0 , concept name A and role name R,
A (t) = R (t1; t2) = ( A(t);
if t = "; A;inv(ds); if t = 0:[S]; for some 0 2 T ;m0 ; (t1 = t2); >:?; 8RT (t1; t2); if t1 = t2 = "; > < if t1 !R t2 and either t1 6= " or t2 6= "; otherwise: We claim that, for each assignment a0 in Wm0 , (a; ) = split(a0) and term t,
I0 j=a0 A(t) i I0 j=a0 R(t1; t2) i
AA j=a A (t); AA j=a R (t1; t2); for all concept names A; for all roles R: (5) (6) For A(a), A(xi) or A(yi) with i = " the claim follows from (3). For A(yi) with i = 0:[S], by (cp), we have cp(a(yi)) = inv(dr), for some R 2 [S]; the claim then follows from (4). For R(yi1 ; yi2 ) with i1 = i2 = ", the claim follows from (abox). Let us consider the case of R(yi1 ; yi2 ) with i2 6= ": we have a0(yi2 ) 2= W0 and thus, by (role), I0 j=a0 R(yi1 ; yi2 ) i { a0(yi1 ), a0(yi2 ) are in the same tree Ta, for a 2 ob(A), i.e., AA j=a (yi1 = yi2 ), { and either (a0(yi1 ); a0(yi2 )) 2 Ea and then `a(a0(yi1 ); a0(yi2 )) = S for some S vT R, or (a0(yi2 ); a0(yi1 )) 2 Ea and then `a(a0(yi2 ); a0(yi1 )) = S for some inv(S) vT R, or a0(yi1 ) = a0(yi2 ) and then Id vT R, i.e., i1 !R i2 . Other cases are similar and left to the reader.
Finally, let ' (x; y) be the result of attaching the superscript of ' and to each atom _ 2 Tk ;m0 'T ;q(x) = 9y ' (x; y) ^ (y) : As follows from (5){(6), for every assignment a0 in Wm0 , we have I0 j=a0 '(x; y) i AA j=a ' (x; y) for (a; ) = split(a0). For the converse direction notice that, if AA j=a (y) then there is an assignment a0 in Wm0 with split(a0) = (a; ).
Clearly, AA j= 'T ;q(a) i I0 j= q(a), for every tuple a. We also note that, for every pair of tuples a and b of object names in ob(A), ' (a; b) is a positive existential sentence with inequalities, and so domain-independent.4 It is also easily seen that, for each b, (b) is domain-independent. It follows from the minimality of I0 that 'T ;q(a) is domain-independent, for each tuple a of object names in ob(A).
Finally, we note that the resulting query contains mk (k+m) disjuncts, where m = jrole (T )j and k is the number of bound variables in q. tu
We also remark that although extending the DL-Lite(RN) languages with
transitive roles does not change the combined complexity of reasoning, it does
change the data complexity: instance checking and satis ability in DL-Lite(RN),
for 2 fcore; krom; horn; boolg, are NLogSpace-complete (rather than in AC0)
and query answering over DL-Lite(hRorNn) and DL-Lite(cRorNe) KBs is
NLogSpacecomplete for data complexity (see Section 5.4 of [