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
inference 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
approach to be viable in practice is the e ciency 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 [
A very important di erence 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 di erently (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 [
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-LitecRore and DL-LitehRorn, from AC0 to LogSpace. (The inequality constraints do not a ect the complexity.) In the presence of functionality constraints, dropping the UNA increases the combined complexity of satis ability for DL-LitecFore and DL-LitekFrom from NLogSpace to P, and the data complexity of query answering (or instance checking) for DL-LitecFore and DL-LitehForn from AC0 to P. With arbitrary number restrictions the price is even higher: e.g., the data complexity of query answering (or instance checking) for DL-LitecNore 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 rst-order rewritability of (positive existential) queries, and so cannot use the standard database query engines in a straightforward manner. Since the OWL 2 pro les are de ned as syntactic restrictions without changing the basic semantic assumptions, it was chosen not to include in the OWL 2 QL pro le 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,
the logics of the form DL-Lite(RF) and DL-Lite(RN ) with restricted interaction
between number restrictions and role inclusions (similar to that in DL-LiteA
[
DL-Lite Logics We begin by de ning the description logic DL-LitebRo;oNl , 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-LitebRo;oNl contains object names a0; a1; : : : , concept names A0; A1; : : : , and role names P0; P1; : : : . Complex roles R and concepts C are de ned as follows:
R B C ::= ::= ::=
Pi ? B j j j
Pi ; Ai :C j j
q R; C1 u C2; where q is a positive integer. The concepts of the form B are called basic.
A DL-LitebRo;oNl TBox, T , is a nite set of concept and role inclusions of the form C1 v C2 and R1 v R2, respectively. An ABox, A, is a nite set of assertions of the form Ak(ai); :Ak(ai), Pk(ai; aj ); :Pk(ai; aj ). Taken together, T and A constitute the DL-LitebRo;oNl 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 role (K) the set fPk; Pk j Pk 2 role(K)g, 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 2 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 2
I j ]fy 2
I j (x; y) 2 RI g q : A KB K = (T ; A) is satis able if there is an interpretation I satisfying all the members of T and A, in which case we write I j= 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= ajI 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-LitebRo;oNl . A DL-LitebRo;oNl 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 k (by de nition, 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: As B1 v :B2 is equivalent to B1uB2 v ?, core TBoxes can be regarded as sitting in the intersection of Krom and Horn TBoxes. The fragments of DL-LitebRo;oNl with Krom, Horn and core TBoxes are denoted by DL-LitekRr;oNm, DL-LitehRo;rNn and DL-LitecRo;rNe , respectively.
For 2 fcore; krom; horn; boolg, 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., 9R ::= 1 R) and only those 2 R that occur in concept inclusions of the form 2 R v ? (known as global functionality constraints ). 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 9R), and DL-Lite (without number restrictions di erent from 9R).
As shown in [
For a TBox T , let vT be the re exive and transitive closure of the relation (R; R0); (inv(R); inv(R0)) j R v R0 2 T . Say that R0 is a proper sub-role of R in T if R0 vT R and R0 6vT R.
Consider now the language DL-Lite(bRooNl ) obtained from DL-LitebRo;oNl by imposing 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 positive occurrences of quali ed number restrictions q R:C in TBoxes T provided that the following condition is satis ed: (exists) if q R:C occurs in T then T does not contain negative occurrences of q0 R or q0 inv(R), for q0 2.
Moreover, we can also allow in DL-Lite(bRooNl ) role disjointness, re exivity, irre exivity, symmetry and asymmetry constraints. The languages DL-Lite(hRorNn ), DL-Lite(kRroNm) and DL-Lite(cRorNe ) are de ned as the corresponding fragments of DL-Lite(bRooNl ) (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 de ne the languages DL-Lite(RF) as sub-languages of DL-Lite(RN ) in which only number restrictions of the form 9R, 9R:C and functionality constraints 2 R v ? are allowed|provided, of course, that they satisfy (inter) and (exists); in particular, 9R: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: satis ability, instance checking and query answering. The KB satis ability 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 j= C(a), that is, aI 2 CI , for every model I of K. Instance checking and satis ability are (AC0-) reducible to the complement of each other.
Finally, we remind the reader that a positive existential query q is any rstorder formula constructed by means of ^, _ and 9y 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. Languages
Combined complexity
Data complexity Instance checking
Query answering
P P [Th.4] P [Cor.1] coNP [Th.2] coNP
[Th.1]
coNP [
[Th.5] coNP
P coNP coNP coNP coNP DL-Lite[cojrRe ]
DL-Lite[cForje(=RhFor)n]
DL-Lite[cNorje=horn
(RN )] DL-Lite[kNrojm( R=bNoo)l]
Satis ability
NLogSpace
NLogSpace [
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 j= q(a), if I j= q(a) whenever I j= K. The query answering problem is to decide, given a tuple a, whether K j= q(a). Note that instance checking is a special case of query answering.
The complexity results obtained in this paper for the three reasoning problems 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
Satis ability: Combined and Data Complexity
As shown in [
Logics of the form DL-LiteR, for 2 fcore; krom; horn; boolg, without
equality constraints do not feel whether the UNA is adopted or not: for combined
complexity, satis ability is NLogSpace-complete for DL-LitecRore and DL-LitekRrom,
P-complete for DL-LitehRorn and NP-complete for DL-LitebRool [
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 satis ability and instance checking problems for DL-Lite and DL-LiteR, with 2 fcore; krom, horn; boolg, 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 j= K i I j= K0, for every interpretation I.
Proof. Let G = (V; E) be the symmetric graph with
V = ob(A);
E = (ai; aj ) j ai
aj 2 A or aj
ai 2 A ;
and [ai] the set of all vertices of G that are reachable from ai. De ne A0 by
removing all the equality constraints from A and replacing every ai with aj 2 [ai] with
minimal j. Note that this minimal j can be computed in LogSpace: just
enumerate 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
undirected graphs is SLogSpace-complete and that SLogSpace = LogSpace [
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.
In this section, we show that the interaction between number restrictions and
the possibility of identifying objects in the ABox results in a higher
complexity. Indeed, it turns out that, for both combined complexity and data
complexity, the satis ability problem for the logics DL-LiteN and DL-Lite(RN ),
2 fcore; krom; horn; boolg, without the UNA is NP-complete. This is quite
di erent from the case when the UNA is adopted, where satis ability is in AC0
for any of the logics DL-Lite(RN ) for data complexity, and is tractable for the
logics DL-Lite(hRorNn ), DL-Lite(kRroNm) and DL-Lite(cRorNe ) under combined
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 [
ak;1 _ ak;2 _ ak;3 ; 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-LitecNore, we need object names aik, for 1 k n, 1 i m, and ck and tk, for 1 k n, role names S and P , and concept names A1; A2; A3. Let A' be the ABox containing the following assertions: 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-LitecNore 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 i (T ; A') is satis able 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; zk j 1 k n [ xik j a(ai) = f; 1 { ckI = yk and (tk)I = zk, for 1 k n,
( k { (aik)I = zxki;; iiff aa((aaii)) == ft;; for 1 i m, 1 i k m; 1 k
n , n, { SI = ((ai1)I ; (ai2)I ); : : : ; ((ain 1)I ; (ain)I ); ((ain)I ; (ai1)I ) j 1 { P I = (ckI ; (tk)I ) j 1 k n [ (ckI ; (akk;j)I ) j 1 k n; 1 i j m , 3 .
It is readily checked that I j= (T ; A').
(() Suppose I j= K. De ne an assignment a by taking a(ai) = t i (ai1)I = (t1)I . Our aim is to show that a(ak;j) = t for exactly one j 2 f1; 2; 3g, for each k, 1 k n. We have P I (ckI ; (akk;j)I ) for all j = 1; 2; 3. Moreover, (akk;i)I 6= (akk;j)I for i 6= j. As ckI 2 ( 3 P )I and P I (ckI ; (tk)I ), we then must have (akk;j )I = (tk)I for some unique j 2 f1; 2; 3g. It follows from functionality of S that, for each 1 k n, we have (a1k;j )I = (t1)I for exactly one j 2 f1; 2; 3g. tu
The next theorem establishes a matching upper bound: Theorem 3. Without the UNA, satis ability 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 2 fcore; krom; horn; bool g. Proof. The upper bound can proved using the following non-deterministic algorithm. Given a DL-Lite(bRooNl ) 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 2 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 satis ability checking algorithm for DL-LitebNool to decide whether the KB K0 = (T ; A0) is consistent under the UNA.
Clearly, if the algorithm returns `yes,' then I0 j= K0, for some I0 respecting the UNA, and we can construct a model I of K (not necessarily respecting the UNA) by extending I0 with the following interpretation of object names: aI = aiI0 , whenever ai is the representative of a= (I coincides with I0 on all other symbols). Conversely, if I j= K then we take the equivalence relation de ned by ai aj i aiI = ajI . Let I0 be constructed from I by removing the interpretations of all object names that are not representatives of the equivalence classes for . It follows that I0 respects the UNA and is a model of K0, so the algorithm returns `yes.' tu 3.2
DL-Lite(RF): Functionality Constraints
Let us consider now DL-Lite(bRooFl) 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
satis ability problem for the logics of the form DL-LiteF and DL-Lite(RF),
2 fcore; krom; horn; boolg, is P-complete for data complexity (under the UNA,
it is in AC0 [
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. Lemma 2. For every DL-Lite(bRooFl) KB K = (T ; A) with equality and inequality constraints, one can construct in polynomial time in jAj a DL-Lite(bRooFl) KB K0 = (T ; A0) such that A0 contains neither equalities nor inequalities, and K is satis able without the UNA i K0 is satis able 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 rst identifying aj with ak, for each aj ak 2 A, and removing the equality from A, and then exhaustively applying the following procedure to A: { if 2 R v ? 2 T , R1 vT R, R2 vT R, and R1(ai; aj ); R2(ai; ak) 2 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
satis able, 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 satis able i K0 is satis able. So it su ces to show
that K0 is satis able without the UNA i it is satis able 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 [
The reduction above cannot be done better than in P, as shown by the next theorem.
Theorem 4. Without the UNA, satis ability of DL-LitecFore KBs (even without 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 ^ k=1 ' = ak;1 ^ ak;2 ! ak;3 ^ p ^ al;0 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 `' j= ai?' in the language of DL-LitecFore we need object names aik, 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(ai1; ai2); : : : ; S(ain 1; ain); S(ain; ai1); for 1 i P (akk;1; fk); P (akk;2; gk); Q(gk; akk;3); Q(fk; akk;1); m; for 1 T (t; al1;0); for 1 l p; k
n; and the TBox T asserts that all of the roles are functional: 2 P v ?; 2 Q v ?; 2 S v ? and 2 T v ?: Clearly, K = (T ; A) is a DL-LitecFore KB and T does not depend on '. We claim that ' j= aj i K0 = (T ; A [ f:T (t; aj1)g) is not satis able without the UNA. It su ces to prove that ' j= aj i I j= T (t; aj1) in every model I of K.
()) Let I j= K and suppose ' j= aj . Then we can derive aj from ' using the following inference rules: { ' j= al;0 for each l, 1 l p; { if ' j= ak;1 and ' j= ak;2, for some k, 1 k n, then ' j= 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, ' j= ak;1, ' j= ak;2, for some k, 1 k n, and that I j= T (t; a1k;1) ^ T (t; a1k;2). Since T is functional, we have (a1k;1)I = (a1k;2)I . Since S is functional, (akk;01)I = (akk0;2)I , for all k0, 1 k0 n, and in particular, for k0 = 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, (akk0;3)I = (akk0;1)I , for all k0, 1 k0 n, and in particular, for k0 = 1. Thus, I j= T (t; aj1).
(() Suppose that ' 6j= aj . Then there is an assignment a such that a(') = t and a(aj ) = f. Construct an interpretation I by taking {
I = xik j a(ai) = f; 1 k
n; 1 (xik; if a(ai) = f;
for 1 { (aik)I =
zk; if a(ai) = t; { tI = w, T I = (w; z1) , { SI = ((ai1)I ; (ai2)I ); : : : ; ((ain 1)I ; (ain)I ); ((ain)I ; (ai1)I ) j 1
(vk; if a(ak;2) = f; { fkI = uk and
gkI = { P I = ((akk;1)I ; fkI ); ((akk;2)I ; gkI ) j 1 { QI = (gkI ; (akk;3)I ); (fkI ; (akk;1)I ) j 1 uk; if a(ak;2) = t; k k
for 1 n , n .
It is readily checked that I j= K and I 6j= T (t; aj1). i k m [ zk; uk; vk j 1 n and 1 i k
k m, n, n [ w , i m , tu
The above result strengthens the NLogSpace lower bound for instance
checking in DL-LitecFore given in [
Corollary 1. Without the UNA, the satis ability problems for DL-LiteF and DL-Lite(RF) KBs, 2 fcore; krom; horng, with equalities and inequalities are P-complete for both combined complexity and data complexity.
Without the UNA, satis ability of DL-LitebFool and DL-Lite(bRooFl) KBs with equalities and inequalities is NP-complete for combined complexity and P-complete for data complexity. 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. tu 4
Query Answering: Data Complexity
The P and coNP upper bounds for data complexity of query answering in
DL-LitehRo;rFn and DL-LitebRo;oNl without the UNA follow immediately from the
results for Horn-SHIQ [
Proof. ()) Suppose that K j
0 = q(a) and I is a model of K respecting the UNA.
In view of satis ability of K0, we have I j= K0, and thus I j= q(a).
(() Take any I0 with I0 j= K0. We construct an interpretation J 0 respecting the UNA as follows. Let J 0 be the disjoint union of I0 and ob(A). De ne a function h : J 0 ! I0 by taking h(a) = aI0 , for each a 2 ob(A), and h(w) = w, for each w 2 I0 , and let aJ 0 = a; AJ 0 = u j h(u) 2 AI0
and P J 0 = (u; v) j (h(x); h(v)) 2 P I0 ; for all object, concept and role names a, A, P . Clearly, J 0 respects the UNA and J 0 j= 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 j= q(a), we must then have J 0 j= q(a), and since h is a homomorphism, I0 j= q(a). Therefore, K0 j= q(a) in models without the UNA, as required. tu
The remaining part of the proof of the theorem is exactly as in [2, Theorem 7.1], as now we may assume that K is a DL-LitehRorn KB containing neither inequality nor role constraints.
tu