Evolution of Knowledge Bases (KBs) expressed in Description Logics (DLs) proved its importance. Recent studies of evolution in DLs mostly focussed on model-based approaches. They showed that evolution of KBs in tractable DLs, such as DL-Lite, suffers from inexpressibility, i.e., the result of evolution cannot be captured in DL-Lite. What is missing in these studies is understanding: in which DL-Lite fragments evolution can be captured, what causes the inexpressibility, which logics is sufficient to express evolution, and whether one can approximate it in DL-Lite. This paper provides some understanding of these issues for both update and revision. We found what DL-Lite formulas make evolution inexpressible and how to capture evolution in their absence. We introduce the notion of prototypes that gives an understanding of how to capture evolution for a rich DL-Lite fragment in FO[2]. Decidability of FO[2] gives possibility for approximations.
knowledge by means of Knowledge Bases (KBs) K that are composed of two components: TBox (describes intensional or general knowledge about an application domain) and ABox (describes facts about individual objects). DLs constitute the foundations for various dialects of OWL, the Semantic Web ontology language.
Traditionally DLs have been used for modeling static and structural aspects of
application domains [
set of formulas. In the case where N interacts with K in an undesirable way, e.g., by
causing the KB or relevant parts of it to become unsatisfiable, N cannot simply be
added to the KB. Instead, suitable changes need to be made in K so as to avoid this
undesirable interaction. Different choices for changes are possible, corresponding to
different approaches to semantics for KB evolution [
is called model-based (MBAs). Under MBAs the result of evolution K N is a set of
models of N that are minimally distanciated from models of K. Depending on what the
distance between models is and how to measure it, eight different MBAs were introduced
(see Section 3 for details). Since K N is a set of models, while K and N are logical
theories, it is desirable to represent K N as a logical theory using the same language as
for K and N . Thus, looking for representations of K N is the main challenge in studies
of evolution under MBAs. When K and N are propositional theories, representing K N
is well understood [
not surprising since DL-Lite is the basis of OWL 2 QL, a tractable OWL 2 profile. It has been shown that for every of the eight MBAs one can find DL-Lite K and N such that
evolution. This phenomenon was also noted in [
(1) What fragments of DL-Lite are closed under model-based evolutions? What DL-Lite formulas are responsible for inexpressibility of model-based evolutions? (2) What are sufficient extensions of DL-Lite to capture model-based evolutions of
(3) For DL-Lite K and N , is it possible and how to do “good” approximations of K N ?
is a new ABox and the TBox of K should remain the same after the evolution. ABox evolution is important for areas, e.g., bioinformatics, where the structural knowledge
relationships between different MBAs. In Section 5 we introduce DL-Lite+ , a restriction R on DL-LiteR where disjointness of concepts with role projections is forbidden. We show that DL-Lite+ is closed under most of MBA evolutions and provide tractable
R algorithms computing K N . In Section 6 we study two important MBAs where distance between models is based on atoms and prove that DL-Lite+ is a sufficient borderline R of expressibility for these semantics: the class of KBs that are in DL-LiteR but not in DL-Lite+ is not closed under these semantics. We also introduce and study DL-Lite I
R R that restricts DL-LiteR, extends DL-Lite+ and not closed under MBAs. In order to
R
capture evolution of DL-Lite RI KBs in FO, we introduce prototypes, based on which
we show that the evolution can be expressed in FO[
DL-LiteR
(complex) concepts and roles: (i) B ::= A j 9R, (ii) C ::= B j :B, (iii) R ::= P j P ,
where A and P stand for an atomic concept and role, respectively, which are just
names. A knowledge base (KB) K = (T ; A) is compound of two sets of assertions:
TBox T , and ABox A. DL-LiteR TBox assertions are concept inclusion assertions of
the form B v C and role inclusion assertions R1 v R2, while ABox assertions are
membership assertions of the form A(a), :A(a), and R(a; b). The active domain of K,
denoted adom(K), is the set of all constants occurring in K. The DL-Lite family has nice
computational properties, for example, KB satisfiability has polynomial-time complexity
in the size of the TBox and logarithmic-space in the size of the ABox [
all over the same countable domain . An interpretation I is a function I that assigns to each C a subset CI of , and to R a binary relation RI over in such a way that (:B)I = n BI , (9R)I = fa j 9a0:(a; a0) 2 RI g, and (P )I = f(a2; a1) j (a1; a2) 2 P I g. We assume that contains the constants and that cI = c, i.e., we adopt standard names. Alternatively, we view an interpretation as a set of atoms and say that
of a membership assertion A(a) (resp., :A(a)) if a 2 AI (resp., a 2= AI ), of P (a; b) if (a; b) 2 P I , and of an inclusion assertion D1 v D2 if D1I D2I .
As usual, we use I j= F to denote that I is a model of an assertion F , and I j= K to denote that I j= F for each assertion F in K. We use Mod(K) to denote the set of all models of K. A KB is satisfiable if it has at least one model. We use entailment on KBs K j= K0 in the standard sense. An ABox A T -entails an ABox A0, denoted A j=T A0, if T [ A j= A0, and A is T -equivalent to A0, denoted A T A0 if A j=T A0 and A0 j=T A.
is the set of all TBox (resp., positive ABox) assertions F such that T j= F (resp., A j=T F ). Clearly in DL-LiteR cl(T ) (and clT (A)) is computable in time quadratic in the number of assertions of T , i.e., jT j, (resp., jT [ Aj). In our work we assume that all TBoxes and ABoxes are closed, while results are extendable to arbitrarily KBs. For satisfiable KBs K = (T ; A) a full closure of A, denoted fclT (A), is the set of all membership assertions f (both positive and negative) over adom(K) such that A j=T f .
satisfying: (i) h(a) = a for every constant a; (ii) if 2 AI (resp., ( ; ) 2 P I ), then
h( ) 2 AJ (resp., (h( ); h( )) 2 P J ) for every A (resp., P ). We write I ,! J if there
is a homomorphism from I to J . A canonical model I of K, denoted as IKcan or just
Ican when K is clear from the context, is a model of K which can be homomorphically
embedded in every model of K [
This section is based on [
possibly in polynomial time, a DL-LiteR K0 = (T ; A0) (with the same TBox as K) that
captures the evolution, and which we call the (ABox) evolution of K under N . Based on
the evolution principles of [
I1 Mod(T ∪ N ) :
J0 J1 J2 J3
Distance is built upon global: G local: L
atoms: a symbols: s
Approach set: ⊆ number: #
Type of distance
of evolution of a KB K wrt new knowledge N is a set K N of models. The idea of
models. Katsuno and Mendelzon [
K
N = [ I2Mod(K) I
N =
arg min J 2Mod(T [N ) dist(I; J ): where dist( ; ) is a function whose range is a partially ordered domain and arg min stands for the argument of the minimum, that is, in our case, the set of models J for which the value of dist(I; J ) reaches its minimum value, given I. The distance function dist varies from approach to approach and commonly takes as values either numbers or subsets of some fixed set. To get a better intuition of the local semantics, consider Figure 1, left, where we present two model I0 and I1 of a KB K and four models J0; : : : ; J3 of (T ; N ).
of a line connecting them. Solid lines correspond to minimal distances, dashed lines to distances that are not minimal. In this figure fJ0g = arg minJ 2fJ0;:::;J3g dist(I0; J ) and fJ2; J3g = arg minJ 2fJ0;:::;J3g dist(I1; J ).
K
N = arg min dist(Mod(K); J );
J 2Mod(N )
(1)
arg minJ 2fJ0;:::;J3g dist(fI0; I1g; J ).
where dist(Mod(K); J ) = minI2Mod(K) dist(I; J ). Consider again Figure 1, left, and
assume that the distance between I0 and J0 is the global minimum, hence, fJ0g =
Measuring Distance Between Interpretations. The classical MBAs were developed for
propositional theories [
One can extend these distances to DL interpretations in two different ways. One way is to consider interpretations I, J as sets of atoms. Then I J is again a set of atoms and we can define distances as in Equation (2). We denote these distances as dista (I; J ) and dista#(I; J ). Another way is to define distances at the level of the concept and role symbols in the signature underlying the interpretations: dists (I; J ) = fS 2 j SI 6= SJ g; and dists#(I; J ) = jfS 2 j SI 6= SJ gj:
eight semantics of evolution according to MBAs by choosing: (1) the local or the global approach, (2) atoms or symbols for defining distances, and (3) set inclusion or cardinality to compare symmetric differences. In Figure 1, right, we depict these three dimensions.
the choice in each dimension, e.g. La# denotes the local semantics where the distances are expressed in terms of cardinality of sets of atoms.
above. We say D is closed under evolution wrt M (or evolution wrt M is expressible in D) if for any KBs K and N written in D, there is a KB K0 written in D such that Mod(K0) = K N , where K N is the evolution result under semantics M .
based semantics. The observation underlying these results is that on the one hand, the minimality of change principle intrinsically introduces implicit disjunction in the evolved
allow one to express genuine disjunction (see Lemma 1 in [
4
by S2 wrt D, denoted (S1 4sem S2)(D), or just S1 4sem S2 when D is clear from the context, if K S1 N K S2 N for all satisfiable KBs K and N written in D, where K Si N denotes evolution under Si. Two semantics S1 and S2 are equivalent (wrt D), denoted (S1 sem S2)(D), if (S1 4sem S2)(D) and (S2 4sem S1)(D). Further in this section we will consider K and N written in DL-LiteR. The following theorem shows the subsumption relation between different semantics, which we also depict with solid arrows in Figure 2. The figure is complete in the following sense: there is a solid path between any two semantics S1 and S2 iff there is a subsumption S1 4sem S2. a G#
a G⊆
a L#
a L⊆
s G#
s G⊆
s L#
s L⊆
Mod(K) :I min
→ I1 Mod(K
N ) : min
J → J1 Fig. 2. Left: Subsumptions for evolution semantics. “ ”: in DL-LiteR (Theorem 1). “ ”: in DL-Lite+R (Theorems 6, 7). Dashed frame surrounds semantics under which DL-Lite+ is closed.
R Right: commutation diagram for La semantics, “I ) J ” denotes that J 2 I N .
Theorem 1. Let 2 fa; sg and
2 f ; #g. Then G 4sem L ;
G# 4sem G ; and
Ls# 4sem Ls : Proof. Let dist be one of the four considered distances, EG = K N wrt G and EL = K N wrt L be corresponding global and local semantics based on dist. For given K and N , let J 0 2 EG . Then, there is I0 j= K such that for every I00 j= K and J 00 j= T [ N it does not hold dist(I00; J 00) dist(I0; J 0): In particular, when I00 = I0, there is no J 00 j= T [ N such that dist(I0; J 00) dist(I0; J 0), which yields that J 0 2 arg minJ 2Mod(Ts[N ) dist(I0; J ), and J 0 2 EL. We conclude that: G#a 4sem La#; Ga 4sem La ; G# 4sem Ls#; Gs 4sem Ls :
Now consider E# = K N wrt L#, which is based on dist#, and E = K N wrt L , which is based on dist . Assume J 0 2 E# and J 0 62 E . Then, from the former assumption we conclude existence of I0 j= K such that J 0 2 arg minJ 2Mod(T [N ) dist#(I0; J ). From the latter assumption, J 0 2= E , we conclude existence of a model J 00 such that dist (I0; J 00) ( dist (I0; J 0). This yields that dist#(I0; J 00) dist#(I0; J 0), which contradicts the fact that J 0 2 E#, assuming that dist (I0; J 0) is finite. Thus,
when = s since the signature of K [ N is finite. It is easy to check that dist (I; J ) may not be finite when = a, hence, La# 64sem La .
Similarly one can show that G#s 4sem Gs . It also holds that G#a 4sem Ga due to the finite model property in DL-LiteR. tu 5
Evolution in DL-Lite+
R Here we consider a restriction of DL-LiteR, which we call DL-Lite+ . A KB K = (T ; A) R is in DL-Lite+R if it is in DL-LiteR and T 6j= 9R v :B for any role R and any concept B. Intuitively, “+” emphasizes absence of disjointness for roles (only positive inclusions involving roles are permitted). DL-Lite+ is defined semantically, while one R can syntactically check (in quadratic time), given a DL-LiteR KB K, whether K is in DL-Lite+ : one computes a closure of K, checks that no assertions of the form 9R v :B
R are in the closure and if it is the case, then K is in DL-Lite+ . DL-Lite+ is an extension R R of RDFS ontology language (of its FO fragment). DL-Lite+ adds to RDFS the ability of R expressing disjointness of concepts (A1 v :A2) and mandatory participation (A v 9R). Since DL-Lite+ restricts DL-LiteR, the semantics relations from Theorem 1) are also
R correct for DL-Lite+ . We now study what further 4sem-relations hold in DL-Lite+ .
R R INPUT : consistent KBs (T ; A) and N
OUTPUT: a set A0 fclT (A) of ABox assertions 1 A0 := ;; S := fclT (A); 2 repeat 3 choose some 2 S; S := S n f g; 4 if f g [ fclT (N ) is consistent then A0 := A0 [ f g 5 until S = ; ;
5.1
Capturing Atom-Based Evolution We first study evolution under La . Let I be an interpretation and N a knowledge base. An alignment of I with N , denoted Align(I; N ), is the interpretation J = ff j f 2 I and f is satisfiable with N g. There is a tight connection (Lemma 2) between an alignment of a model and its evolution under La semantics. Moreover, alignment preserves homomorphic relationship on interpretations (Lemma 3). Let N be a set of membership assertions and I an interpretation. A union I [N denotes the model I [JN , where JN = ff j f 2 N and f is positiveg.
Lemma 2. Let K = (T ; A) and (T ; N ) be satisfiable DL-Lite+ KBs, and I j= K. Then I N = fAlign(I; N ) [ N g; under La semantics: R Lemma 3. Let K and N be satisfiable DL-Lite+ KBs and I be a model of K. Then R Align(IKcan; N ) ,! Align(I; N ):
Lemmas 3 and 2 imply that (Ican N ) ,! (I N ) for every I 2 Mod(K) under La , where we apply ,! to the sets (Ican N ) and (I N ), instead of their single models. We depict this phenomenon in Figure 2, right: evolution preserves homomorphic embeddability of Ican into I. This fundamental property implies that Ican N consists of the universal model of K N wrt La .
alignment Align(Ican; N ): it drops all the assertions of fclT (A) contradicting N and keeps the rest. Using AlignAlg we can compute K N : Theorem 4. Let K = (T ; A) and (T ; N ) be satisfiable DL-Lite+ KBs. Then: R K
N = Mod(T ; AlignAlg(K; N ) [ N ) (wrt La ):
computation of K N is also polynomial.
Example 5. Consider T = fB0 v B; B v :Cg, A = fC(a)g, and N = B(a). Then, fclT (A) = fC(a); :B0(a); :B(a)g. The alignment of (T ; A) with N is the set AlignAlg((T ; A); N ) = fB(a); :B(a)g. Hence, the result of evolution under every the model-based semantics with atom-based distance is (T ; fB(a); :B0(a)g). Relationships Between Atom-Based Semantics. Next theorem shows that evolutions wrt all four model-based semantics on atoms coincide wrt DL-Lite+ . We depict these R relations between semantics in Figure 2 using a dashed arrow, e.g., between La 4sem G#a.
only if there is a subsumption wrt DL-Lite+ . R a
sem La
a sem G#
sem Ga .
Theorems 6 and 4 imply that in DL-Lite+ one can use AlignAlg to compute evolution R under all MBAs on atoms. 5.2
Capturing Symbol-Based Evolution
Theorem 7. The following relations hold: (i) La 4sem G#s, while G#s 64sem La ; (ii) Ls sem Ls#, and Gs sem G#s, while Ls 64sem G#s.
general does not work for computing evolution under any of the symbol-based semantics.
semantics, while it approximates global semantics better than the local ones.
symbols. It works as follows: for every atom in N it checks whether satisfies a condition (Line 4). If it does, the algorithm deletes all those literals that share their concept name with . Both local and global semantics have their own : G and L.
true iff : 2 fclT (A) n AlignAlg((T ; A); N ). Intuitively, SymAlg for global semantics works as follows: having contradiction between N and A on = B(c), the change of
theorem shows correctness of this algorithm.
Theorem 8. Let K = (T ; A) and (T ; N ) be satisfiable DL-Lite+ KBs. Then DL-Lite+ R R is closed under Gs and G#s, and for both K N = Mod(T ; SymAlg(K; N ; G ));
we use algorithm SymAlg in Figure 2 with the following L: L( ) is true iff 2= S1. That is, L checks whether the ABox T -entails A(c) 2 fclT (N ), and if it does, the INPUT : consistent DL-Lite+R KB (T ; A) and ABox N , a formula property OUTPUT: a set A0 fclT (A) [ fclT (N ) of ABox assertions 1 A0 := ;; S1 := AlignAlg((T ; A); N ); S2 := fclT (N ); 2 repeat 3 choose some 2 S2; S2 := S2 n f g; 4 if ( ) = TRUE then S1 := S1 n f 0 j and 0 have the same concept nameg 5 until S2 = ; ; 6 A0 := S1 [ fclT (N )
K N under Gs and G#s semantics and minimal sound approximation under Ls and Ls# semantics algorithm deletes all the assertions from fclT (A) that share the concept name with A(c).
in interpretation of A by choosing a model of K which does not include A(c). Clearly,
theorem shows correctness of the algorithm. In the previous section we considered evolution in DL-Lite+ . Here we show that R DL-Lite+ is essentially a maximal fragment of DL-LiteR closed under atom-based
R
evolution, and present a wide fragment of DL-LiteR, namely DL-Lite RI, that is not
closed under atom-based evolution while the evolution can be captured in FO[
negation relation is essential, and even a minimal violation leads to inexpressibility of evolution. The minimal way to violate conditions of DL-Lite+ is to have two assertions: R
Theorem 11. Let assertions fA v 9R; 9R v :Cg be entailed from a DL-LiteR TBox T , for some R and C, Then there exist ABoxes A and N such that (T ; A) N is inexpressible in DL-LiteR under La and under La#.
The following example provides reasons why DL-Lite+ restrictions are important R for expressibility of atom-based MBAs. We will further use this example to show how to capture La evolution in FO for KBs violating DL-Lite+R restrictions.
Example 12. Consider the following DL-Lite KBs K1 = (T1; A1) and N1 = fC(b)g: T1 = fA v 9R; 9R v :Cg;
A1 = fA(a); C(e); C(d); R(a; b)g:
I: AI = fa; xg, CI = fd; eg, RI = f(a; b); (x; b)g, where x 2 n adom. We now show that the following models belong to I will be used further to capture K1 N1.
J0: AI = ;, CI = fd; e; bg, RI = ;, J1: AI = fxg, CI = fe; bg, RI = f(x; d)g, J2: AI = fxg, CI = fd; bg, RI = f(x; e)g, J3: AI = fa; xg, CI = fbg, RI = f(a; d); (x; e)g,
J4: AI = fxg, CI = fd; e; bg, RI = f(x; 1)g, where 1 2 nadom(K1). Clearly all five models satisfy N1 and T1. To see that they are in I N1 observe that every model J (I) 2 (I N1) can be obtained from I by making modifications that guarantee that J (I) j= (N1 [ T1) and that the distance between I and J (I) is minimal. What are these modifications? Since in every such J (I) the new knowledge C(b) holds and (C v :9R ) 2 T1, there should be no R-arc incoming into b in J (I), hence the necessary modification of I is to forbid the R-arcs going from a and from x to point into b. Where in J (I) should this R-arcs point in? There are only three mutually exclusive cases for each of a and x: (i) there is no R-arc in J (I) that points from a (resp., x), we simply drop it from I, (ii) it points to some element 2 n fd; e; bg, that is, J (I) j= R(a; ). (iii) it points to an element of fd; eg, that is, J (I) j= R(a; ). Case (i) for both a and x corresponds to J0, hence, J0 2 I N1.
for a corresponds to J1 and J2, hence, both J1 and J2 are in I N1. Case (iii) for both a and x corresponds to J3, hence, J3 2 I N1. There are clearly more models I N1 than these five.
AI = fxg, CI = fe; bg, RI = f(x; d); (x; 1)g.
ery model I0 2 Mod(K1) it holds that I0 j= C(d) and I0 6j= R(x; d), we have that fC(d); R(x; d)g I0 J5. At the same time J4 j= C(d) and J4 6j= R(x; d), while J4 and J5 agree on all the atoms but C(d) and R(x; d). Hence, (I0 J4) ( (I0 J5) and J5 62 (I N1). Moreover, since I0 is an arbitrary model of K1, J5 2= (K1 N1).
Let us make a closer look at J5: it extends J1 with the atom R(x; 1), and this is the reason why it is not in the result of evolution K1 N1. This observation gives a restriction on all the models J on K1 N1: if in J there is one R-arc from some x into d, then J has no other arcs from x. In a way, we have a functionality restriction on the role R, when it connects two specific elements of the domain: x and d. The same kind of functionality holds for x and e, and both of them are not expressible in DL-Lite. This functionality for x and d, and for x and e can be formally written as the following and , respectively: = 8x8y: [R(x; d) ^ R(x; y) ! y = d] ; = 8x8y: [R(x; e) ^ R(x; y) ! y = e] :
of Horn logics [
Besides the fact that both and are inexpressible in DL-LiteR, while should be
entailed by the result of evolution, there is another observation also responsible for
inexpressibility of K1 N1: it has no canonical model. At the same time, one can see that
the set K1 N1 can be divided in four subsets, where each has a canonical model. We
now show that these four canonical models, which we call prototypes for K1 N1, can
be used to capture K1 N1 in FO[
R R Definition 13. Let K be a DL-LiteR KB and N be an ABox. A prototypal set for K N is a minimal subset J = fJ1; : : : ; Jng of K N satisfying the property: for every J 2 K N there is Ji 2 J such that Ji ,! J . Every Ji 2 J is a prototype for K N .
J6: AI = fx1; x2g, CI = fbg, RI = f(x1; d); (x2; e)g. Note that J6 ,! J3 and J0 ,! J4.
La can be captured in FO using prototypes. DL-Lite RI (where I stands for (mutual) independence of roles) is a restriction of DL-LiteR in which TBoxes T satisfy: for any two roles R and R0, T 6j= 9R v 9R0 and T 6j= 9R v :9R0. That is, we forbid direct role interaction (subsumption and disjointness) between role projections. The interaction is still possible but in a simple manner only, e.g., projections may contain the same concept. This restriction allows us to analyze evolution that affects roles independently for every role. For the ease of exhibition of the following procedure constructing J, we further assume that in DL-Lite RI for each role R there is exactly one concept AR such that K j= AR v 9R. As for DL-Lite+ , one can syntactically check (in quadratic time),
R given a DL-LiteR KB K, whether K is in DL-Lite RI using the closure of K.
T -entail f . The procedure BP (K; N ) (where BP stands for build prototypes) of constructing J for the case of DL-Lite RI, generalizes what was done in Example 12 in the following way: In Items 1 and 2 it takes into account all the roles and concepts that may be interpreted differently in different resulted models (R, A and C in our example) and all the constants that could not be present at the second coordinate of those roles in the models of the original KB (e and d in our example). In Items 3, 4, and 5 it builds the prototype J0. Finally in Item 6 it builds the rest of prototypes basing on J0. A pseudocode of the procedure BP (K; N ) is the following: 1. SR = fR1; : : : ; Rng is a set of all roles such that (i) N j=T :Ri (bi) for some bi and (ii) for every Ri(ai; bi) in fclT (A), an atom AR(ai) 2 fclT (A) and R(ai; b0i) 2=
Align(fclT (A); N ), where b0i 2= fbj gjn=1.
Sat = Sn
j=1fRj (a; bj ) j Rj (a; bj ) 2 fclT (A)g. 2. FA(Ri) is equal to the following set fD(c) 2FfAcl=T (SA) j 9Ri (c) ^ D(c) j=T ? and N 6j=T D(c); and N 6j=T :D(c)g. Then Ri2SR FA(Ri), FC = fc j D(c) 2 FAg, where the acronyms FA and FC stand for forbidden atoms and constants, respectively. 3. I0 := Align(Ican; N ) [ N , where Ican is the canonical model of K. 4. For each R(a; b) 2 Sat, do I0 := I0 n fAR(a)g. 5. J0 := I0, J := fJ0g. 6. For each subset D = fD1(c1); : : : ; Dk(ck)g FA do for each R = (Ri1 ; : : : ; Rik ) such that Dj (cj ) 2 FA(Rij ) for j = 1; : : : ; k do J [D; R] := hJ0 n Sik=1 rootT (Di(ci))i [ Sik=1 clT (Ri0(xi; ci)) [ fARi0 (xi)g ; where all xi’s are different constants from n adom(K), fresh for Ican.
J := J [ fJ [D; R]g.
Theorem 14. Let K = (T ; A) be a DL-Lite RI KB, and N a DL-LiteR ABox consistent with T . Then the set BP (K; N ) is a prototypal set for K N .
We proceed to correctness of BP in capturing evolution in DL-Lite RI.
Theorem 15. Let K = (T ; A) be a DL-Lite RI KB, N a DL-LiteR ABox consistent with T , and BP (K; N ) = fJ0; : : : ; Jng is a prototypal set for K N . Then K
N = Mod(T ) \ Mod(A1 _ : : : _ An) \ Mod( ^ ); where Ai is a DL-LiteR ABox such that Ji is a canonical model for (T ; Ai), and = ^ 8x: [(R(x; cj ) ! AR(x)) ^ 8y: (R(x; cj ) ^ R(x; y) ! y = cj )] ; = cj2F^C R(a;b)2Sat
9R(a) ! AR(a):
Note that Theorem 4 about computation of K N for DL-Lite+ is a particular case
R
of Theorem 15 when FC = ; and there is just one prototype. Next theorem allows us to
approximate result of evolution by a DL-LiteR KB, since FO[
N under La for KBs in DL-Lite RI is in FO[
subfamilies of DL-LiteR: DL-Lite+ and DL-Lite RI, that both extend RDFS. The first one
R
is closed under most of the evolution semantics, while the second one is not closed even
under MBAs were distance is based on atoms. We isolated conditions on TBox assertions
that lead to inexpressibility: pairs of assertions of the form A v 9R and 9R v :C
bring inexpressibility. Note that this condition is similar to the notion of unexpected facts
introduces in [
study of evolution in more expressive DLs and what to expect from MBAs in such logics.
evolution is important in understanding whether it is possible and how to do reasonable approximations of evolution results. We also believe that our techniques of capturing semantics based on prototypes give a better understanding of how MBAs behave on
general DL-LiteR KBs.