DL-Lite without UNA A. Artale,1 D. Calvanese,1 R. Kontchakov,2 and M. Zakharyaschev2 1 2 KRDB Research Centre School of Comp. Science and Inf. Sys. Free University of Bozen-Bolzano Birkbeck College I-39100 Bolzano, Italy London WC1E 7HX, UK lastname @inf.unibz.it {roman,michael}@dcs.bbk.ac.uk 1 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 to both data integration and ontology-based data access. The fundamental infer- ence service in this case is answering queries by taking into account the axioms in the TBox and the data stored in the ABox. The key property for such an ap- proach to be viable in practice is the efficiency of query evaluation. To address these needs a series of description logics has been proposed and investigated in [6–8, 16] (the so-called DL-Lite family) and in [1, 2]. The significance of the DL-Lite logics is testified by the fact that they form the basis of OWL 2 QL, one of the three profiles of the web ontology language OWL 2.1 According to the current version of the official W3C profiles document, the purpose of OWL 2 QL is to be the language of choice for applications that use very large amounts of data and where query answering is the most important reasoning task. A very important difference between description logics and OWL is the status of the unique name assumption (UNA), which is commonly made in DL but not adopted in OWL. Instead, the OWL syntax provides explicit means for stating which object names are supposed to denote the same individual and which of them should be interpreted differently (in OWL, these constructs are called sameAs and differentFrom). Until recently, it had been assumed that the DL-Lite logics are interpreted under the UNA. The role of the UNA (for DL-LiteA ) is discussed in [4, 5], where it is shown that if the UNA is dropped, instance checking becomes NLogSpace- hard for data complexity. The aim of this paper is to investigate in depth the impact of dropping the UNA on both the combined and data complexity of rea- soning in the DL-Lite family and extensions, classified according to the following features: (1) the presence or absence of role inclusion assertions; (2) the form of the allowed concept inclusions, where we consider four classes core, Krom, Horn, and Bool exhibiting different computational properties; (3) the form of the allowed numeric constraints, ranging from none, to global functionality constraints only, and to arbitrary number restrictions. 1 http://www.w3.org/TR/owl2-profiles/ In a nutshell, the obtained results can be summarized as follows. Without any kind of number restrictions, the above logics do not ‘feel’ the UNA. However, equality between object names increases the data complexity for core and Horn logics, DL-LiteR R 0 core and DL-Litehorn , from AC to LogSpace. (The inequality constraints do not affect the complexity.) In the presence of functionality con- straints, dropping the UNA increases the combined complexity of satisfiability for DL-LiteF F core and DL-Litekrom from NLogSpace to P, and the data complex- ity of query answering (or instance checking) for DL-LiteF F core and DL-Litehorn 0 from AC to P. With arbitrary number restrictions the price is even higher: e.g., the data complexity of query answering (or instance checking) for DL-LiteN core increases from AC0 to coNP if the UNA is not adopted. Needless to say that in all these cases we loose the important property of first-order rewritability of (positive existential) queries, and so cannot use the standard database query engines in a straightforward manner. Since the OWL 2 profiles are defined as syntactic restrictions without changing the basic semantic assumptions, it was chosen not to include in the OWL 2 QL profile any construct that interferes with the UNA and which, in the absence of the UNA, would cause higher complexity. That is why OWL 2 QL does not include any form of number restrictions and the sameAs constructor. As for the matching upper complexity bounds, we show that, without UNA, (RF ) the logics of the form DL-Liteα and DL-Lite(RN α ) with restricted interaction between number restrictions and role inclusions (similar to that in DL-LiteA [16]) behave precisely in the same way as DL-LiteF N α and DL-Liteα , respectively. R,F (If this interaction is not restricted then even the logic DL-Litecore is ExpTime- hard for combined complexity and P-hard for data complexity [13].) 2 DL-Lite Logics R,N We begin by defining the description logic DL-Litebool , which can be regarded as the supremum of the original DL-Lite family [6–8] in the lattice of description logics. The language of DL-LiteR,N bool contains object names a0 , a1 , . . . , concept names A0 , A1 , . . . , and role names P0 , P1 , . . . . Complex roles R and concepts C are defined as follows: R ::= Pi | Pi− , B ::= ⊥ | Ai | ≥ q R, C ::= B | ¬C | C1 u C2 , where q is a positive integer. The concepts of the form B are called basic. A DL-LiteR,N bool TBox, T , is a finite set of concept and role inclusions of the form C1 v C2 and R1 v R2 , respectively. An ABox, A, is a finite set of assertions of the form Ak (ai ), ¬Ak (ai ), Pk (ai , aj ), ¬Pk (ai , aj ). Taken together, R,N T and A constitute the DL-Litebool knowledge base (KB) K = (T , A). In the following, we denote by role(K) the set of role names occurring in T and A, by 2 role± (K) the set {Pk , Pk− | Pk ∈ role(K)}, and by ob(A) the set of object names in A. For a role R, we set inv(R) = Pk− if R = Pk , and inv(R) = Pk if R = Pk− . As usual, an interpretation, I = (∆I , ·I ), consists of a domain ∆I 6= ∅ and an interpretation function ·I that assigns to each ai an element aIi ∈ ∆I , to Ai a subset AIi ⊆ ∆I of the domain, and to each Pi a binary relation PiI ⊆ ∆I × ∆I . The interpretation of the concept constructs, the concept and role inclusions, and the ABox assertions is also standard. For example, (≥ q R)I = x ∈ ∆I | ]{y ∈ ∆I | (x, y) ∈ RI } ≥ q .  A KB K = (T , A) is satisfiable if there is an interpretation I satisfying all the members of T and A, in which case we write I |= K and say that I is a model of K. The unique name assumption (UNA) is the following requirement imposed on interpretations I: aIi 6= aIj for all i 6= j. As was mentioned in the introduction, in this paper we do not make this assumption. The languages we consider here are obtained by imposing various syntactic restrictions on DL-LiteR,N R,N bool . A DL-Litebool TBox T is called a Krom TBox if its concept inclusions are of the form B1 v B2 , B1 v ¬B2 or ¬B1 v B2 (Krom) (here and below all the Bi and B are basic concepts). T is called a Horn TBox if its concept inclusions are of the form l Bk v B (Horn) k (by definition, the empty conjunction is just >). Finally, T is a core TBox if its concept inclusions are restricted to B1 v B2 or B1 v ¬B2 . (core) As B1 v ¬B2 is equivalent to B1 uB2 v ⊥, core TBoxes can be regarded as sitting R,N in the intersection of Krom and Horn TBoxes. The fragments of DL-Litebool R,N R,N with Krom, Horn and core TBoxes are denoted by DL-Litekrom , DL-Litehorn and DL-LiteR,Ncore , respectively. For α ∈ {core, krom, horn, bool}, we denote by DL-LiteR,F α the fragment of DL-LiteR,N α in which, out of all number restrictions ≥ q R, we are allowed to use existential concepts (i.e., ∃R ::= ≥ 1 R) and only those ≥ 2 R that occur in concept inclusions of the form ≥ 2 R v ⊥ (known as global functionality con- straints). If no number restrictions ≥ q R with q ≥ 2 are allowed, then we obtain the fragments denoted by DL-LiteR α . And if role inclusions are excluded from the language then the resulting fragments are denoted by DL-LiteN α (with arbitrary number restrictions), DL-LiteF α (with functionality constraints and existential concepts ∃R), and DL-Liteα (without number restrictions different from ∃R). As shown in [13], the logics DL-LiteR,F R,N core , DL-Litecore and their extensions turn out to be computationally rather costly, with satisfiability being ExpTime- hard for combined complexity and instance checking P-hard or even NP-hard 3 for data complexity. On the other hand, for the purpose of conceptual modeling one may need both concept and role inclusions. A compromise can be found by artificially limiting the interplay between role inclusions and number restrictions in a way similar to the logic DL-LiteA [16]. ∗  For0 a TBox T , let v0 T be the reflexive and transitive closure of the relation (R, R ), (inv(R), inv(R )) | R v R0 ∈ T . Say that R0 is a proper sub-role of R in T if R0 v∗T R and R0 6v∗T R. Consider now the language DL-Litebool obtained from DL-LiteR,N (RN ) bool by im- posing the following syntactic restriction on its TBoxes T : (inter) if R has a proper sub-role in T then T contains no negative occurrences 2 of number restrictions ≥ q R or ≥ q inv(R) with q ≥ 2. Without spoiling its computational properties, we can allow in this language pos- itive occurrences of qualified number restrictions ≥ q R.C in TBoxes T provided that the following condition is satisfied: (exists) if ≥ q R.C occurs in T then T does not contain negative occurrences of ≥ q 0 R or ≥ q 0 inv(R), for q 0 ≥ 2. (RN ) Moreover, we can also allow in DL-Litebool role disjointness, reflexivity, ir- (RN ) reflexivity, symmetry and asymmetry constraints. The languages DL-Litehorn , (RN ) DL-Litekrom and DL-Lite(RN core ) are defined as the corresponding fragments of (RN ) DL-Litebool (we only note that a concept C occurring in some ≥ q R.C can be any concept allowed on the right-hand side of concept inclusions in the respective language or a conjunction thereof). We also define the languages DL-Lite(RF α ) as sub-languages of DL-Lite(RN α ) in which only number restrictions of the form ∃R, ∃R.C and functionality con- straints ≥ 2 R v ⊥ are allowed—provided, of course, that they satisfy (inter) and (exists); in particular, ∃R.C is not allowed if R is functional. Finally, if the UNA is not adopted, it is standard to include in the language equality and inequality constraints of the form ai ≈ aj and ai 6≈ aj (which are supposed to belong to the ABox part of a KB) with their obvious semantics. We will concentrate on three fundamental reasoning tasks for the logics L of the resulting family: satisfiability, instance checking and query answering. The KB satisfiability problem is to check, given an L-KB K, whether there is a model of K. The instance checking problem is to decide, given an object name a, an L-concept C and an L-KB K = (T , A), whether K |= C(a), that is, aI ∈ C I , for every model I of K. Instance checking and satisfiability are (AC0 -) reducible to the complement of each other. Finally, we remind the reader that a positive existential query q is any first- order formula constructed by means of ∧, ∨ and ∃y starting from atoms of the form A(t) and P (t1 , t2 ), where A is a concept name, P a role name, and t, t1 , t2 2 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. 4 Complexity Languages Combined complexity Data complexity Satisfiability Instance checking Query answering [ |R] a) DL-Litecore NLogSpace LogSpace LogSpace a) [ |R] a) DL-Litekrom NLogSpace [2] LogSpace coNP [18] [ |R] a) DL-Litehorn P [2] LogSpace LogSpace a) ≤ [Th.5] [ |R] DL-Litebool NP [2] LogSpace a) ≤ [Th.1] coNP [F |(RF )] DL-Litecore/horn P ≤ [Cor.1] ≥ [Th.4] P ≥ [Th.4] P [F |(RF )] DL-Litekrom P ≤ [Cor.1] P coNP [F |(RF )] DL-Litebool NP P ≤ [Cor.1] coNP [N |(RN )] DL-Litecore/horn NP ≥ [Th.2] coNP ≥ [Th.2] coNP [N |(RN )] DL-Litekrom/bool NP ≤ [Th.3] coNP coNP a) in AC0 for KBs without equality constraints. Table 1. Tight complexity results for DL-Lite logics without the UNA. [β |β ] DL-Liteα 1 2 means DL-Liteβα1 or DL-Liteβα2 DL-Liteβcore/horn means DL-Liteβcore or DL-Liteβhorn (likewise for DL-Liteβkrom/bool ) are terms taken from the list of variables y0 , y1 , . . . and the list of object names a0 , a1 , . . . . The free variables of q are called distinguished variables; we write q(x1 , . . . , xn ) for a query with distinguished variables x1 , . . . , xn . Given a query q(x) with x = x1 , . . . , xn and an n-tuple a of object names, we write q(a) for the result of replacing every occurrence of xi in q(x) with the ith member of a. Queries containing no distinguished variables will be called ground. The satisfaction relation I |=a q(a) between an interpretation I and a query q under an assignment a for the variables yi in ∆I is defined in the usual way (e.g., I |=a ∃yi ϕ iff I |=b ϕ, for some assignment b in ∆I that may differ from a only on yi ). For a ground query q(a), the relation |=a does not depend on a, and so we write I |= q(a) instead of I |=a q(a). The answer to such a query is either ‘yes’ or ‘no.’ For a KB K = (T , A), we say that a tuple a of object names from A is a certain answer to q(x) w.r.t. K and write K |= q(a), if I |= q(a) whenever I |= K. The query answering problem is to decide, given a tuple a, whether K |= q(a). Note that instance checking is a special case of query answering. The complexity results obtained in this paper for the three reasoning prob- lems and both combined and data complexity are summarized in Table 1. Some of them will be proved in the remaining part of the paper. 3 Satisfiability: Combined and Data Complexity As shown in [2], under the UNA, the satisfiability problem for combined com- plexity is NLogSpace-complete for the logics of the form DL-Lite(RNcore ) and 5 (RN ) (RN ) (RN ) DL-Litekrom , P-complete for DL-Litehorn and NP-complete for DL-Litebool . For data complexity, satisfiability (as well as instance checking) is in AC0 for all of the above logics and their fragments. Logics of the form DL-LiteR α , for α ∈ {core, krom, horn, bool}, without equal- ity constraints do not feel whether the UNA is adopted or not: for combined com- plexity, satisfiability is NLogSpace-complete for DL-LiteR R core and DL-Litekrom , R R P-complete for DL-Litehorn and NP-complete for DL-Litebool [2]. However, for data complexity, dropping the UNA results in a slightly higher complexity because of the equality constraints. More precisely, we have: Theorem 1. Without the UNA and with equality constraints, the satisfiability and instance checking problems for DL-Liteα and DL-LiteR α , with α ∈ {core, krom, horn, bool}, are LogSpace-complete for data complexity. The proof of this theorem is based on the following reduction: Lemma 1. For every KB K = (T , A), one can construct in LogSpace in the size of A a KB K0 = (T , A0 ) without equality constraints such that I |= K iff I |= K0 , for every interpretation I. Proof. Let G = (V, E) be the symmetric graph with  V = ob(A), E = (ai , aj ) | ai ≈ aj ∈ A or aj ≈ ai ∈ A , and [ai ] the set of all vertices of G that are reachable from ai . Define A0 by remov- ing all the equality constraints from A and replacing every ai with aj ∈ [ai ] with minimal j. Note that this minimal j can be computed in LogSpace: just enumer- ate the object names aj w.r.t. the order of their indices j and check whether the current aj is reachable from ai in G. It remains to recall that reachability in undi- rected graphs is SLogSpace-complete and that SLogSpace = LogSpace [17]. In view of the reduction in the proof of Lemma 1 and the fact that AC0 is a proper subclass of LogSpace, the upper bound in Theorem 1 cannot be lowered to AC0 . However, the AC0 data complexity can be regained if we refrain from using the equality constraints; see Section 4. Let us consider now the logics of the form DL-Lite(RN α ) and DL-Lite(RF α ) , together with their fragments. 3.1 DL-Lite(RN α ) : Arbitrary Number Restrictions In this section, we show that the interaction between number restrictions and the possibility of identifying objects in the ABox results in a higher complex- ity. Indeed, it turns out that, for both combined complexity and data com- plexity, the satisfiability problem for the logics DL-LiteN α and DL-Liteα (RN ) , α ∈ {core, krom, horn, bool}, without the UNA is NP-complete. This is quite different from the case when the UNA is adopted, where satisfiability is in AC0 for any of the logics DL-Lite(RN α ) for data complexity, and is tractable for the (RN ) (RN ) logics DL-Litehorn , DL-Litekrom and DL-Lite(RN core ) under combined complex- ity [2]. 6 Theorem 2. Without the UNA, satisfiability of DL-LiteN core KBs (even with- out equality and inequality constraints) is NP-hard for both combined and data complexity. Proof. The proof is by reduction of the following variant of the 3SAT problem— called monotone one-in-three 3SAT —which is known to be NP-complete [10]: given a positive 3CNF formula n ^  ϕ = ak,1 ∨ ak,2 ∨ ak,3 , k=1 where each ak,j is one of the propositional variables a1 , . . . , am , decide whether there is an assignment for the variables aj such that exactly one variable is true in each of the clauses in ϕ. To encode this problem in the language of DL-LiteN k core , we need object names ai , for 1 ≤ k ≤ n, 1 ≤ i ≤ m, and ck and t , k for 1 ≤ k ≤ n, role names S and P , and concept names A1 , A2 , A3 . Let Aϕ be the ABox containing the following assertions: S(a1i , a2i ), . . . , S(an−1 i , ani ), S(ani , a1i ), for 1 ≤ i ≤ m, 1 2 n−1 n n 1 S(t , t ), . . . , S(t , t ), S(t , t ), k P (ck , t ), for 1 ≤ k ≤ n, P (ck , akk,j ), Aj (akk,j ), for 1 ≤ k ≤ n, 1 ≤ j ≤ 3, and let T be the TBox with the axioms: A1 v ¬A2 , A2 v ¬A3 , A3 v ¬A1 , ≥ 2 S v ⊥, ≥ 4 P v ⊥. Clearly, (T , Aϕ ) is a DL-LiteN core KB and T does not depend on ϕ (so that we cover both combined and data complexity). We claim that the answer to the monotone one-in-three 3SAT problem is positive iff (T , Aϕ ) is satisfiable without the UNA. (⇒) Let a be an assignment satisfying the requirements of the problem. Take some ai0 with a(ai0 ) = t (clearly, such an i0 exists, for otherwise a(ϕ) = f) and construct an interpretation I = (∆I , ·I ) by taking: – ∆I = yk , z k | 1 ≤ k ≤ n ∪ xki | a(ai ) = f, 1 ≤ i ≤ m, 1 ≤ k ≤ n ,   – cIk = yk and k I k ( (t ) = z , for 1 ≤ k ≤ n, xki , if a(ai ) = f, – (aki )I = for 1 ≤ i ≤ m, 1 ≤ k ≤ n, z k , if a(ai ) = t, – S I = ((a1i )I , (a2i )I ), . . . , ((ain−1 )I, (ani )I ), ((ani )I , (a1i )I ) | 1 ≤ i ≤ m ,  – P I = (cIk , (tk )I ) | 1 ≤ k ≤ n ∪ (cIk , (akk,j )I ) | 1 ≤ k ≤ n, 1 ≤ j ≤ 3 . It is readily checked that I |= (T , Aϕ ). (⇐) Suppose I |= K. Define an assignment a by taking a(ai ) = t iff (a1i )I = 1 I (t ) . Our aim is to show that a(ak,j ) = t for exactly one j ∈ {1, 2, 3}, for each k, 1 ≤ k ≤ n. We have P I (cIk , (akk,j )I ) for all j = 1, 2, 3. Moreover, (akk,i )I 6= (akk,j )I 7 for i 6= j. As cIk ∈ (≤ 3 P )I and P I (cIk , (tk )I ), we then must have (akk,j )I = (tk )I for some unique j ∈ {1, 2, 3}. It follows from functionality of S that, for each 1 ≤ k ≤ n, we have (a1k,j )I = (t1 )I for exactly one j ∈ {1, 2, 3}. t u The next theorem establishes a matching upper bound: Theorem 3. Without the UNA, satisfiability of DL-LiteN α and DL-Liteα (RN ) KBs with equality and inequality constraints is NP-complete for both combined complexity and data complexity and any α ∈ {core, krom, horn, bool }. Proof. The upper bound can proved using the following non-deterministic algo- (RN ) rithm. Given a DL-Litebool KB K = (T , A), we – guess an equivalence relation ∼ over ob(A); – select in each equivalence class ai /∼ a representative, say ai , and replace every occurrence of ai0 ∈ ai /∼ in A with ai ; – fail if the equalities and inequalities are violated in the resulting ABox—i.e., if it contains ai 6≈ ai or ai ≈ aj , for i 6= j; – otherwise, remove the equality and inequality constraints from the ABox and denote the result by A0 ; – use an NP satisfiability checking algorithm for DL-LiteN bool to decide whether the KB K0 = (T , A0 ) is consistent under the UNA. Clearly, if the algorithm returns ‘yes,’ then I 0 |= K0 , for some I 0 respecting the UNA, and we can construct a model I of K (not necessarily respecting the UNA) by extending I 0 with the following interpretation of object names: 0 aI = aIi , whenever ai is the representative of a/∼ (I coincides with I 0 on all other symbols). Conversely, if I |= K then we take the equivalence relation ∼ defined by ai ∼ aj iff aIi = aIj . Let I 0 be constructed from I by removing the interpretations of all object names that are not representatives of the equivalence classes for ∼. It follows that I 0 respects the UNA and is a model of K0 , so the algorithm returns ‘yes.’ tu 3.2 DL-Lite(RF α ) : Functionality Constraints (RF ) Let us consider now DL-Litebool and its fragments. In the absence of the UNA, the necessity to identify pairs of objects due to functionality constraints also causes an increase in complexity. However, this increase is less dramatic as the procedure of identifying objects is deterministic: without the UNA, the satisfiability problem for the logics of the form DL-LiteF α and DL-Liteα (RF ) , α ∈ {core, krom, horn, bool}, is P-complete for data complexity (under the UNA, it is in AC0 [2]). For the combined complexity, satisfiability in DL-LiteFα and DL-Lite(RF α ) , α ∈ {core, krom}, becomes P-complete rather than NLogSpace- complete as it is under the UNA (and remains the same for α ∈ {horn, bool}). The following lemma shows that for all these logics reasoning without the UNA can be reduced in polynomial time in the size of the ABox to reasoning under the UNA. 8 (RF ) Lemma 2. For every DL-Litebool KB K = (T , A) with equality and inequality (RF ) constraints, one can construct in polynomial time in |A| a DL-Litebool KB K0 = (T , A0 ) such that A0 contains neither equalities nor inequalities, and K is satisfiable without the UNA iff K0 is satisfiable under the UNA. Proof. In what follows by identifying aj with ak in A we mean replacing each occurrence of ak in A with aj . We construct A0 by first identifying aj with ak , for each aj ≈ ak ∈ A, and removing the equality from A, and then exhaustively applying the following procedure to A: – if ≥ 2 R v ⊥ ∈ T , R1 v∗T R, R2 v∗T R, and R1 (ai , aj ), R2 (ai , ak ) ∈ A, for distinct aj and ak , then identify aj with ak . If the resulting ABox contains ai 6≈ ai , for some ai , then, clearly, K is not satisfiable, so we add A(ai ) and ¬A(ai ) to the ABox, for some concept name A. Finally, we remove all inequalities from the ABox and denote the result by A0 . It should be clear that A0 is computed from A in polynomial time and that, without the UNA, K is satisfiable iff K0 is satisfiable. So it suffices to show that K0 is satisfiable without the UNA iff it is satisfiable under the UNA. The implication (⇐) is trivial. To prove (⇒), observe that every model I for K0 not respecting the UNA can be transformed into a model I of K0 respecting the UNA by starting from the set of all object names, which are interpreted as distinct domain elements, and applying the unraveling procedure to cure the defects in the interpretation (for details see Lemmas 8.4 and 5.14 in [2]). t u The reduction above cannot be done better than in P, as shown by the next theorem. Theorem 4. Without the UNA, satisfiability of DL-LiteF core KBs (even with- out equality and inequality constraints) is P-hard for both combined and data complexity. Proof. The proof is by reduction of the entailment problem for Horn-CNF, which is known to be P-complete (see, e.g., [3, Exercise 2.2.4]). Let n ^ p ^  ϕ = ak,1 ∧ ak,2 → ak,3 ∧ al,0 k=1 l=1 be a Horn-CNF formula, where each ak,j and each al,0 is one of the propositional variables a1 , . . . , am and ak,1 , ak,2 , ak,3 are all distinct, for each k, 1 ≤ k ≤ n. To encode the P-complete problem ‘ϕ |= ai ?’ in the language of DL-LiteF core we need object names aki , for 1 ≤ k ≤ n, 1 ≤ i ≤ m, fk and gk , for 1 ≤ k ≤ n and t and role names P , Q, S and T . The ABox A contains the following assertions S(a1i , a2i ), . . . , S(ain−1 , ani ), S(ani , a1i ), for 1 ≤ i ≤ m, P (akk,1 , fk ), P (akk,2 , gk ), Q(gk , akk,3 ), Q(fk , akk,1 ), for 1 ≤ k ≤ n, T (t, a1l,0 ), for 1 ≤ l ≤ p, 9 and the TBox T asserts that all of the roles are functional: ≥ 2 P v ⊥, ≥ 2 Q v ⊥, ≥ 2S v ⊥ and ≥ 2 T v ⊥. Clearly, K = (T , A) is a DL-LiteF core KB and T does not depend on ϕ. We claim that ϕ |= aj iff K0 = (T , A ∪ {¬T (t, a1j )}) is not satisfiable without the UNA. It suffices to prove that ϕ |= aj iff I |= T (t, a1j ) in every model I of K. (⇒) Let I |= K and suppose ϕ |= aj . Then we can derive aj from ϕ using the following inference rules: – ϕ |= al,0 for each l, 1 ≤ l ≤ p; – if ϕ |= ak,1 and ϕ |= ak,2 , for some k, 1 ≤ k ≤ n, then ϕ |= ak,3 . We show the claim by induction on the length of the derivation of aj from ϕ. The basis of induction is trivial. So assume that aj = ak,3 , ϕ |= ak,1 , ϕ |= ak,2 , for some k, 1 ≤ k ≤ n, and that I |= T (t, a1k,1 ) ∧ T (t, a1k,2 ). Since T is functional, 0 0 we have (a1k,1 )I = (a1k,2 )I . Since S is functional, (akk,1 )I = (akk,2 )I , for all k 0 , 1 ≤ k 0 ≤ n, and in particular, for k 0 = k. Then, since P is functional, fkI = gkI , from which, by functionality of Q, (akk,3 )I = (akk,1 )I . Finally, since S is functional, 0 0 (akk,3 )I = (akk,1 )I , for all k 0 , 1 ≤ k 0 ≤ n, and in particular, for k 0 = 1. Thus, I |= T (t, a1j ). (⇐) Suppose that ϕ 6|= aj . Then there is an assignment a such that a(ϕ) = t and a(aj ) = f. Construct an interpretation I by taking – ∆I = xki | a(ai ) = f, 1 ≤ k ≤ n, 1 ≤ i ≤   m ∪  k ( z , uk , v k | 1 ≤ k ≤ n ∪ w , k xi , if a(ai ) = f, – (aki )I = for 1 ≤ k ≤ n and 1 ≤ i ≤ m, z k , if a(ai ) = t, – tI = w, T I = (w, z 1 ) ,  – S I = ((a1i )I , (a2i )I ), .( . . , ((ain−1 )I , (ani )I ), ((ani )I , (a1i )I ) | 1 ≤ i ≤ m ,  vk , if a(ak,2 ) = f, – fkI = uk and gkI = for 1 ≤ k ≤ n, uk , if a(ak,2 ) = t, – P I = ((akk,1 )I , fkI ), ((akk,2 )I , gkI ) | 1 ≤ k ≤ n ,  – QI = (gkI , (akk,3 )I ), (fkI , (akk,1 )I ) | 1 ≤ k ≤ n .  It is readily checked that I |= K and I 6|= T (t, a1j ). t u The above result strengthens the NLogSpace lower bound for instance checking in DL-LiteF core given in [5]. Corollary 1. Without the UNA, the satisfiability problems for DL-LiteF α and DL-Lite(RF α ) KBs, α ∈ {core, krom, horn}, with equalities and inequalities are P-complete for both combined complexity and data complexity. (RF ) Without the UNA, satisfiability of DL-LiteF bool and DL-Litebool KBs with equalities and inequalities is NP-complete for combined complexity and P-com- plete for data complexity. 10 Proof. The upper bounds follow from Lemma 2 and the corresponding upper bounds for the UNA case. The NP lower bound for combined complexity is obvious and the P lower bounds follow from Theorem 4. t u 4 Query Answering: Data Complexity The P and coNP upper bounds for data complexity of query answering in DL-LiteR,F R,N horn and DL-Litebool without the UNA follow immediately from the results for Horn-SHIQ [12, 9] and SHIQ [14, 15, 11], respectively. We show now that the maximal DL-Lite logic for which query answering remains in AC0 without the UNA is the logic DL-LiteR horn extended with role constraints as specified in the following theorem: Theorem 5. Without the UNA, the positive existential query answering prob- lem for DL-LiteRhorn KBs with disjointness, (a)symmetry, (ir )reflexivity role con- straints and inequalities (but without equalities) is in AC0 for data complexity. It is LogSpace-complete for data complexity and KBs with equality constraints. Proof. The proof follows the lines of the proof of [2, Theorem 7.1] given for the UNA case and uses the observation that models without the UNA produce no more answers than their unravelled counterparts. More precisely, let K0 = (T 0 , A0 ) be a consistent DL-LiteR horn KB, and q(x) a positive existential query. Then [2, Lemma 5.17] provides a DL-LiteR horn KB K that has no role constraints but may still have inequality constraints. The following lemma shows that one can simply ignore the inequality constraints in K0 and thus reduces the query answering problem without the UNA to query answering under the UNA: Lemma 3. For every tuple a of object names in K0 , we have K0 |= q(a) (in models without the UNA) iff I |= q(a) for all models I of K respecting the UNA. Proof. (⇒) Suppose that K0 |= q(a) and I is a model of K respecting the UNA. In view of satisfiability of K0 , we have I |= K0 , and thus I |= q(a). (⇐) Take any I 0 with I 0 |= K0 . We construct an interpretation J 0 respecting 0 0 the UNA as follows. Let ∆J be the disjoint union of ∆I and ob(A). Define a J0 I0 I0 function h : ∆ → ∆ by taking h(a) = a , for each a ∈ ob(A), and h(w) = w, 0 for each w ∈ ∆I , and let 0 0 0 0 0 aJ = a, AJ = u | h(u) ∈ AI and P J = (u, v) | (h(x), h(v)) ∈ P I ,   for all object, concept and role names a, A, P . Clearly, J 0 respects the UNA and J 0 |= K0 . It also follows that h is a homomorphism. By [2, Lemma 5.17], there is a model I of K with the same domain as J 0 that coincides with J 0 on all symbols in K0 . As I |= q(a), we must then have J 0 |= q(a), and since h is a homomorphism, I 0 |= q(a). Therefore, K0 |= q(a) in models without the UNA, as required. t u The remaining part of the proof of the theorem is exactly as in [2, Theo- rem 7.1], as now we may assume that K is a DL-LiteR horn KB containing neither inequality nor role constraints. t u 11 References 1. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. DL-Lite in the light of first-order logic. In Proc. of the 22nd Nat. Conf. on Artificial Intelligence (AAAI 2007), pages 361–366, 2007. 2. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. The DL-Lite family and relations. Technical Report BBKCS-09-03, School of Computer Science and Information Systems, Birbeck College, London, 2009. Available at http:// www.dcs.bbk.ac.uk/research/techreps/2009/bbkcs-09-03.pdf. 3. E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Perspec- tives in Mathematical Logic. Springer, 1997. 4. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, and R. Rosati. Mastro-i: Efficient integration of relational data through DL ontologies. In Proc. of the 2007 Description Logic Workshop (DL 2007), volume 250 of CEUR Elec- tronic Workshop Proceedings, http://ceur-ws.org/, pages 227–234, 2007. 5. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, R. Rosati, and M. Ruzzi. Data integration through DL-Lite A ontologies. In 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. 6. 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 Artificial Intelligence (AAAI 2005), pages 602–607, 2005. 7. 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. 8. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning, 39(3):385–429, 2007. 9. T. Eiter, G. Gottlob, M. Ortiz, and M. Šimkus. Query answering in the description logic Horn-SHIQ. In Proc. of the 11th Eur. Conference on Logics in Artificial Intelligence (JELIA 2008), pages 166–179, 2008. 10. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. 11. 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 Artificial Intelligence (IJCAI 2007), pages 399–404, 2007. 12. U. Hustadt, B. Motik, and U. Sattler. Data complexity of reasoning in very expres- sive description logics. In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), pages 466–471, 2005. 13. R. Kontchakov and M. Zakharyaschev. DL-Lite and role inclusions. In Proc. of the 3rd Asian Semantic Web Conf. (ASWC 2008), volume 5367 of Lecture Notes in Computer Science, pages 16–30. Springer, 2008. 14. M. Ortiz, D. Calvanese, and T. Eiter. Characterizing data complexity for con- junctive query answering in expressive description logics. In Proc. of the 21st Nat. Conf. on Artificial Intelligence (AAAI 2006), pages 275–280, 2006. 15. 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. 12 16. 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. 17. O. Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008. 18. A. Schaerf. On the complexity of the instance checking problem in concept lan- guages with existential quantification. J. of Intelligent Information Systems, 2:265– 278, 1993. 13