The DL-Lite family of description logics has recently been proposed and investigated in [5{7] and later extended in [1, 8, 3]. The relevance of the DL-Lite family is witnessed by the fact that it forms the basis of OWL 2 QL, one of the three pro les of OWL 2 (http://www.w3.org/TR/owl2-pro les/). According to the o cial W3C pro les document, the purpose of OWL 2 QL is to be the language of choice for applications that use very large amounts of data. This paper extends the DL-Lite languages of [3] by relaxing the restriction on the interaction between cardinality constraints (N ) and role inclusions (or hierarchies, H). We also introduce a new family of languages, DL-LiteHN A, 2 fcore; krom; horn; boolg, extending DL-Lite with attributes (A). The notion of attributes, borrowed from conceptual modeling formalisms, introduces a distinction between (abstract) objects and application domain values, and consequently, between concepts (sets of objects) and datatypes (sets of values), and between roles (relating objects to objects) and attributes (relating objects to values). The advantage of the presented languages over DL-LiteA [8] is that the range restrictions for attributes can be local (and not only global as in DL-LiteA). Indeed, DL-LiteHN A has a possibility to express concept inclusion axioms of the form C v 8U:T , for an attribute U and its datatype T . In this way, we allow re-use of the very same attribute associated to di erent concepts with di erent range restrictions. For example, we can say that employees' salary is of type Integer, researchers' salary is in the range 35,000{70,000 (enumeration type) and professors' salary in the range 55,000{100,000|while both researchers and professors are employees. Note that local attributes are strictly more expressive than global ones. For example, concept disjointness (or unsatis ability) can be inferred just from datatype disjointness for the same (existentially quali ed) attribute. Since DL-Lite languages have been proved useful in capturing conceptual data models [8, 4, 2], the extension with attributes, as presented here, will generalize their use even further. We aim at establishing computational complexity of knowledge base satis ability in these new DLs. In particular we prove the following results:
Introduction
1. We can relax the restrictions presented in [
The Description Logic DL-LitebHooNl A The language of DL-LitebHoNolA contains object names a0; a1; : : :, value names v1; v2; : : :, concept names A0; A1; : : :, role names P0; P1; : : :, attribute names U0; U1; : : :, and datatype names T0; T1; : : :. Complex roles R and concepts C are de ned below:
R ::= Pi j Pi ; B ::= > j ? j Ai j q R j C ::= B j :C j C1 u C2; q Ui where q is a positive integer. The concepts of the form B are called basic concepts.
A DL-LitebHoNolA TBox, T , is a nite set of concept, role, attribute and datatype inclusion axioms of the form:
C1 v C2;
C v 8U: T;
R1 v R2;
U v U 0;
T v T 0;
T u T 0 v ?; and an ABox, A, is a nite set of assertions of the form:
Ak(ai); :Ak(ai);
Pk(ai; aj ); :Pk(ai; aj );
Uk(ai; vj ) and
Tk(vj ): We standardly abbreviate 1 R and 1 U by 9R and 9U , respectively. Absence of an attribute (i.e., C v 8U: ?) can be expressed as C u 9U v ?.
Together, a TBox T and an ABox A constitute the DL-LitebHoNolA knowledge base (KB) K = (T ; A). In the following, we denote by role(K) and att (K) the sets of role and attribute names occurring in K, respectively; role (K) denotes the set fPk; Pk j Pk 2 role(K)g.
Semantics. As usual in description logic, an interpretation, I = ( I ; I ), consists of a nonempty domain I and an interpretation function I . The interpretation domain I is the union of two non-empty disjoint sets: the domain of objects IO and the domain of values IV . We assume that all interpretations agree on the semantics assigned to each datatype Ti, as well as on each constant vi. In particular, TiI = val(Ti) IV is the set of values of datatype Ti, and each vi is interpreted as one speci c value, denoted val(vi), i.e., viI = val(vi) 2 val(Ti). Furthermore, I assigns to each object name ai an element aiI 2 IO, to each concept name Ak a subset AkI IO of the domain of objects, to each role name Pk a binary relation PkI IO IO over the domain of objects, and to each attribute name Uk a binary relation UkI IO IV . We adopt here the unique name assumption (UNA): aiI 6= ajI ; for all i 6= j: The role and concept constructs are interpreted in I in the standard way: (Pk )I = f(y; x) 2
I O
IO j (x; y) 2 PkI g; >I = ?I = ;; ( q R)I = ( q U )I = (8U: T )I = (:C)I =
I ; O x 2 x 2 x 2
IO n CI ; (C1 u C2)I = C1I \ C2I ;
IO j ]fy j (x; y) 2 RI g IO j ]fv j (x; v) 2 U I g q ; q ; IO j 8v: (x; v) 2 U I ! v 2 T I ; (attribute value restriction) (inverse role) (domain of objects) (the empty set) (at least q R-successors) (at least q U -attributes) (not in C) (both in C1 and in C2) where ]X is the cardinality of X. The satisfaction relation j= is also standard:
I j= C1 v C2 i I j= T1 u T2 v ?
I j= T1 v T2 i
i
I j= Ak(ai) i I j= :Ak(ai) i
C1I T I 1
C2I ;
T2I ; T1I \ T2I = ;; aiI 2 AkI ; aiI 2= AkI ;
I j= R1 v R2 i
I j= U1 v U2 i
I j= Pk(ai; aj ) i I j= :Pk(ai; aj ) i
I j= Uk(ai; vj ) i
I j= Tk(vj ) i
R1I
R2I ; U1I U2I ; (aiI ; ajI ) 2 PkI ; (aiI ; ajI ) 2= P I
k (aiI ; vjI ) 2 UkI ; vjI 2 TkI : 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 (of T and A). 2.1
Fragments of DL-LitebHooNl A We consider various syntactical restrictions on the language of DL-LitebHoNolA along two axes: (i) the Boolean operators (bool ) on concepts, (ii) the role and attribute inclusions (H). Similarly to classical logic, we adopt the following definitions. A TBox T will be called a Krom TBox 1 if its concept inclusions are restricted to:
B1 v B2;
B1 v :B2 and :B1 v B2; (Krom) (here and below all the Bi and B are basic concepts). T will be called a Horn TBox if its concept inclusions are restricted to: l Bk v B: k Finally, we call T a core TBox if its concept inclusions are restricted to: B1 v B2 and
B1 u B2 v ?: 1 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. (Horn) (core) As B1 v :B2 is equivalent to B1 u B2 v ?, core TBoxes can be regarded as sitting in the intersection of Krom and Horn TBoxes. In this paper we study the following logics, for 2 fcore; krom; horn; boolg: DL-LitekHroNmA; DL-LitehHoNrnA; DL-LitecHorNe A are the fragments of DL-LitebHoNolA with Krom, Horn, and core TBoxes, respectively; DL-LiteHN is the fragment of DL-LiteHN A without attributes and datatypes; DL-LiteN A is the fragment of DL-LiteHN A without role and attribute inclusions.
As shown in [
The language DL-Lite(HN ) [
De nition 1. Given a TBox T and a role R 2 role (T ), we de ne the following parameters: ubound (R; T ) = min f1g [ fq 1 j q 2 and q R occurs negatively in T g ; lbound (R; T ) = max f0g [ fq j
q R occurs positively in T g ;
rank (R; T ) = max lbound (R; T ); PR02dsubT (R) rank (R0; T ) ;
rank (R; A) = max f0g[fn j Ri(a; ai) 2 A; Ri vT R; for distinct a1; : : : ; ang :
Consider the languages obtained from DL-LiteHN by imposing one of the
following two restrictions:
(inter1) for every R 2 role (T ), if R has a proper sub-role in T then
ubound (R; T ) rank (R; T );
(inter2) for every R 2 role (T ), if R has a proper sub-role in T then
ubound (R; T ) rank (R; T ) + maxf1; rank (R; A)g.
language (inter) [
NLogSpace [Th.1]
PTime [Th.1] NP [Th.2] NLogSpace [Th.1]
NP [Th.1] NLogSpace [Th.3]
PTime [Th.3] NP [Th.2] NP [Th.4]
NP [Th.3] NA
NA non-restrict.
These new restrictions are in some way weaker than (inter) and, for example, allow for the specialization of functional roles: KB K = (T ; A) with T = f 2 R v ?; R1 v R2; R2 v Rg, and A = fR(a; b); R1(a1; b1); R2(a2; b2)g does not satisfy (inter), but it satis es both (inter1) and (inter2). Finally, the above restrictions can also be applied to sub-attributes in the languages DL-LiteHN A. Table 1 summarizes the obtained complexity results (with numerical parameters q coded in binary). 3
Reasoning in DL-LiteHN In this section, we investigate the complexity of deciding KB satis ability in languages DL-LiteHN under the restrictions (inter1) and (inter2), respectively.
We adapt the proof presented in [
( q R) = EqR(x); (C1 u C2) = C1 (x) ^ C2 (x): The QL1 sentence encoding the knowledge base K is de ned as follows: Kze = 8x T (x) ^ T R(x) ^
R(x) ^
R(x)
^ Aze : ^
R2role (K) T (x) = T R(x) =
^ C1vC22T ^
^ RvT R0 q2QTR
C1 (x) ! C2 (x) ;
EqR(x) ! EqR0(x) ; Formulas T (x), the R(x), for R 2 role (K), and T R(x) encode the TBox T : ^ R(x) = Eq0 R(x) ! EqR(x) ; q;q02QTR; q0>q where QR contains 1, all q such that
T Sentence Aze encodes the ABox A:
Aze = ^ Ak(ai) ^ ^ :Ak(ai) ^
Ak(ai)2A :Ak(ai)2A q R occurs in T and all QR0 , for R0 vT R.
T ^
EqRe;a R(a) ^ a;a02ob(A) R0vT R; R0(a;a0)2A
?; :Pk(ai;aj)2A R(ai;aj)2A; RvT Pk ^ where qRe;a is the maximum number in QR such that there are qRe;a many distinct T ai with Ri(a; ai) 2 A and Ri vT R. For each R 2 role (K), we also need the following formula expressing the fact that the range of R is not empty whenever its domain is non-empty:
R(x) = E1R(x) ! inv (E1R(dr)); where inv (E1R(dr)) is E1Pk (dpk ) if R = Pk and E1Pk(dpk) if R = Pk . Lemma 1. A DL-LitebHoNol knowledge base under restriction (inter2) is satis able i the QL1-sentence Kze is satis able.
Proof. (Sketch) The only challenging direction is ((). To prove it, we adapt the
proofs of Theorem 5.2 and Lemma 5.14 in [
I j M j= Ak[cp(w)]g; where cp(w) is the element d 2 D of which w is a copy.
The interpretation for each role Pk, is de ned inductively as PkI = Sm1=0 Pkm, where Pkm Wm Wm, along with the construction of I . The initial interpretation for each role name Pk is de ned as follows:
Pk0 = f(aiM; ajM) 2 W0
W0 j R(ai; aj) 2 A and R vT Pkg: For every R 2 role (K), the required R-rank r(R; d) of d 2 D is de ned by taking r(R; d) = max f0g [ fq 2 QTR j M j= EqR[d]g . The actual R-rank rm(R; w) of a point w 2 I at step m is rm(R; w) = (]fw0 2 Wm+1 j (w; w0) 2 Pkm+1g; if R = Pk;
]fw0 2 Wm+1 j (w0; w) 2 Pkm+1g; if R = Pk :
Assume that Wm and Pkm, m 0, have been already de ned. Let Wm+1 = ; and
Pkm+1 = ;, for each role name Pk. If we had rm(R; w) = r(R; cp(w)), for each role
R and w 2 Wm, then the interpretation we need would be constructed. However,
the actual rank of some points could still be smaller than the required rank. We
cure these defects by adding R-successors for them. Note that the `curing' process
for a given w and R, not only increases the actual R-rank of w, but also all its
R0-ranks, for all R vT R0. At this point we adapt the construction in [
In each equivalence class [R] = fS j S T Rg we select a single role, a representative. Let G = (RepT ; E) be a directed graph such that RepT is the set of representatives and (R; R0) 2 E i R is a proper sub-role of R0. Clearly, G is a directed acyclic graph and so, by a topological sort, one can assign to each representative a unique number smaller than the number of all its descendants in G. We use the ascending total order induced on G when choosing an element Pk in RepT , and extend in that way Wm and Pkm to Wm+1 and Pkm+1, respectively. ( km) Let w 2 km; q = r(Pk; cp(w)) rm(Pk; w), d = cp(w). There is q0 q > 0 with M j= Eq0 Pk[d]. Then, M j= E1Pk[d] and M j= E1Pk [dpk ]. In this case we take q fresh copies w10; : : : ; wq0 of dpk , add them to Wm+1 and for each 1 i q, set cp(wi0) = dpk , add the pairs (w; wi0) to each Pjm+1 with Pk vT Pj and the pairs (wi0; w) to each Pjm+1 with Pk vT Pj (note that by adding pairs to Pjm+1 we change its the actual rank); ( km ) This rule is the mirror image of ( km): Pk and dpk are replaced with Pk and dpk, respectively.
We need to show that, for all w 2
I and all q R in T , (a1) if (a2) if q R occurs positively in T then M j= EqR[cp(w)] implies w 2 ( q R)I ; q R occurs negatively in T then w2( q R)I implies M j= EqR[cp(w)]. Consider rst w 2 W0. It should be clear that actual R-rank of w r0(R; w)
rank(R; A) + PR02dsubT (R) rank(R0; T ) and so, by (inter2), the total number of R-successors before we cure the defects does not exceed ubound(R; T ). If ubound(R; T ) = 1 then there are no negative occurrences of q R with q 2 and, although may have rm(R; w) r(R; cp(w)) after curing the defects of R, both (a1) and (a2) hold. Otherwise, we have ubound(R; T ) + 1 2 QTR and so, by (inter2), max QR > rank(R; T ) + T rank(R; A), whence r0(R; w) < max QR. So, as r(R; cp(w)) lbound(R; T ) and lbound(R; T ) < ubound(R; T ) < max QTR, after curing the defect, we will have
T rm(R; w) = r(R; cp(w)), for all m > 0, and both (a1) and (a2) hold. The case with w 2 Wm0 n Wm0 1, for m0 > 0 is similar, only now rm0 (R; w)
1 + PR02dsubT (R) rank(R0; T ):
Finally, we show that I j= ' for each ' 2 K. For ' = Ak(ai), ' = :Ak(ai) the claim is by the de nition of AI . For ' = :Pk(ai; aj ), we have (ai; aj ) 2 P I k k i (ai; aj ) 2 Pk0 i R(ai; aj ) 2 A and R vT Pk. By induction on the structure of concepts and (a1) and (a2), one can show that I j= C1 v C2 whenever M j= 8x(C1 (x) ! C2 (x)), for each ' = C1 v C2. Finally, I j= ' holds by de nition in case ' = R1 v R2 2 T .
Theorem 1. Under restriction (inter2), checking KB satis ability is NPcomplete in DL-LitebHoNol , PTime-complete in DL-LitehHoNrn and NLogSpacecomplete in both DL-LitekHrNom and DL-LitecHoNre.
We now consider the case where the restriction (inter1) is imposed on the interaction between sub-roles and number restrictions. In presence of an ABox, (inter2) restricts the number of R-successors in the ABox, which appears to be a strong constraint on the instances of the ABox. On the other hand, the less restrictive condition (inter1), which does not impose any bound on R-successors in the ABox, does not come for free, as shown by the following theorem: Theorem 2. Under restriction (inter1), checking KB satis ability is NP-hard even in DL-LitecHoNre.
Proof. We show that graph 3-colorability can be reduced to KB satis ability. Let G = (V; E) be a graph with vertices V and edges E and fr; g; bg be three colors. Consider the following KB K = (T ; A) with role names vi and w and object names o; r; g; b and the xi, for each vertex vi 2 V :
T =f
f9vi u 9vj v ? j (vi; vj ) 2 Eg; A =fB1(o); w(o; r); w(o; g); w(o; b)g [ fw(o; xi); B2(xi) j vi 2 V g: (jV j + 4) w v ?g [ fvi v w; B1 v 9vi; B2 u 9vi v ? j vi 2 V g [ It can be shown that K is satis able i G is 3-colorable. 4
Reasoning with Attributes In this section we study the e ect of extending DL-Lite with attributes. In particular, we show that for the Bool, Horn and core cases the addition of attributes does not change the complexity of KB satis ability.
Theorem 3. KB satis ability is NP-complete in DL-LitebNooAl , PTime-complete in DL-LitehNoArn and NLogSpace-complete in DL-LitecNoAre.
Under restriction (inter2), checking KB satis ability is NP-complete in DL-LitebHoNolA, PTime-complete in DL-LitehHoNrnA and NLogSpace-complete in DL-LitecHoNreA.
Proof. (Sketch) We encode a DL-LiteHN A KB K = (T ; A) in a QL1 sentence Kza in a way similar to the translation used in Lemma 1. Denote by val (A) the set of all value names that occur in A. Similarly to roles, we de ne the sets QU T of natural numbers for all occurrences of q U (including sub-attributes). We need a unary predicate EqU (x), for each attribute name U and q 2 QU , denoting T the set of objects with at least q values of attribute U . We also need, for each attribute name U and each datatype T , a unary predicates U T (x), denoting all objects that may have attribute U values only of datatype T . Following this intuition, we extend by the following two statements: ( q U ) = EqU (x) and (8U:T ) = U T (x): The QL1 sentence encoding the KB K is de ned as follows: Kza =
Kze ^ 8x T U (x) ^
U (x) ^ U1 (x) ^ U2 (x) ^
2
Aza ^ Aza ; ^
U2att(K) where Kze is as before, T U (x), U (x) and Aza are similar to T R(x), R(x) and Aze , but rephrased for attributes and their inclusions. The new types of ABox assertions require the following formula:
2 Aza = ^
^ Uk(ai;vj)2A datatype T
U T (ai) ! T vj ^
^ T (vj)2A
T vj ; where T vj is a propositional variable for each datatype T and each vj 2 val (A). The two additional formulas, U1 (x) and U2 (x), capturing datatype inclusions and disjointness constraints are:
U1 (x) U2 (x) = =
^ T vT 02T
^ T uT 0v?2T
U T (x) ! U T 0(x) ;
U T (x) ^ U T 0(x) ^ E1U (x) ! ? ^
^ T v ^ T 0v ! ? v2val(A) : We would like to note here that the formula U2 (x) for disjoint datatypes demonstrates a subtle interaction between attribute range constraints 8U:T and minimal cardinality constraints 9U .
We show that K is satis able i the QL1-sentence Kza is satis able. For ((), let M j= Kza . We construct a model I = ( IO [ IV ; I ) of K similarly to the way we proved Lemma 1 but this time datatypes will have to be taken into account: let IO be de ned inductively as before and IO = val (A) [ V . The set V will be constructed starting from val (A) in order to `cure' the attribute successors as follows. For each datatype T and each attribute U , let
T 0 = fv 2 val (A) j M j= T vg and
U 0 = f(a; v) j U (a; v) 2 Ag: For every attribute U 2 att(K), we can de ne the required U -rank r(U; d) of d 2 D and the actual U -rank r0(R; w) of w 2 IO as before, treating U as a role name (the only di erence is that there will be only one step, and so, the actual rank is needed only for step 0). We can also consider the equivalence relation induced by the sub-attribute relation in T , then we can choose representatives and a linear order on them respecting the sub-attribute relation of T . We can start from the smaller attributes and `cure' their defects. Let w 2 IO and q = r(U; cp(w)) r0(U; w) > 0. Take q fresh elements v1; : : : ; vq, add those fresh values to V , add pairs (w; v1); : : : ; (w; vq) to U 0 and add v1; : : : ; vq to T 0 for each datatype T with M j= U T [cp(w)]. Let U I and T I be the resulting relations. Now, it can be shown that if M j= Kza then I j= ' for every ' 2 K. We only note here that fresh values vj cannot be added to two disjoint datatypes T and T 0 because of formula U2 (x).
Now, given a KB with a Bool or Horn TBox, Kza is a universal one-variable formula or a universal one-variable Horn formula, respectively, which immediately gives the NP and PTime upper complexity bounds for the Bool and Horn fragments. The NLogSpace upper bound for KBs with core TBoxes is not so straightforward because U2 (x) is not a binary clause. In this case we note that Kza is still a universal one-variable Horn formula and therefore, Kza is satis able i it is true in the `minimal' model. The minimal model can be constructed in the bottom-to-top fashion by using only positive clauses of Kza (i.e., clauses of the form 8x (B1(x) ^ ^ Bk(x) ! H(x))) and then checking whether the negative clauses of Kza (i.e., clauses of he form 8x (B1(x) ^ ^ Bk(x) ! ?)) hold in the constructed model. By inspection of the structure of Kza , one can see that all its positive clauses are in fact binary, and therefore, whether an atom is true in its minimal model or not can be checked in NLogSpace.
It is of interest to note that the complexity of KB satis ability increases in the case of Krom TBoxes: Theorem 4. KB satis ability is NP-complete in DL-LitekNroAm, and so, in DL-LitekHrNomA even under (inter) and (inter2).
Proof. (Sketch) The proof exploits the ternary disjointness formula U2 (x) in Kza . In fact, if T u T 0 v ? 2 T then the following concept inclusion, although not in the syntax of DL-LitekNroAm, is a logical consequence of T (cf. U2 (x)): 8U:T u 8U:T 0 u 9U v ?: Using such ternary intersections one can encode 3SAT. Let ' = Vim=1 Ci be a 3CNF, where the Ci are ternary clauses over variables p1; : : : ; pn. Now, suppose pji1 _ :pji2 _ pji3 is the ith clause of '. It is equivalent to :pji1 ^ pji2 ^ :pji3 ! ? and so, can be encoded as follows:
Ti1 u Ti2 v ?; :Aji1 v 8Ui:Ti1;
Aji2 v 8Ui:Ti2; :Aji3 v 9Ui; where the A1; : : : ; An are concept names for the variables p1; : : : ; pn, and Ui is an attribute and Ti1 and Ti2 are datatypes for the ith clause (note that Krom concept inclusions of the form :B v B0 are required, which is not allowed in the core TBoxes). Let T consist of all such inclusions for clauses in '. It can be seen that ' is satis able i T is satis able.
Conclusions We studied two di erent extensions of the DL-Lite logics. First, local attributes allow to use the same attribute associated to di erent concepts with di erent datatype range restrictions. We showed that the extension with attributes is harmless with the only notable exception of the Krom fragment, where the complexity rises from NLogSpace to NP.
Second, we consider weak syntactic restrictions on interaction between
cardinality constraints and role inclusions and study their impact on the complexity
of satis ability. For example, under (inter) [
As a future work, we intend to ll the gaps in Table 1 and, in particular, to see whether the NP-hardness results have a matching upper bound. We are also working on query answering in the languages with attributes.