Evolution of Knowledge Bases expressed in Description Logics (DLs) proved its importance. Most studies on evolution in DLs have focused on modelbased approaches to evolution semantics and in particular on Winslett's semantics (WS). It was understood that evolution under WS even in tractable DLs, such as DL-Lite, suffers from inexpressibility, i.e., the result of evolution cannot be expressed in the same logics. In this work we show which combination of DLLite logical constructs is responsible for the inexpressibility and explain reasons for such a behaviour. We present novel techniques, based on what we called prototypes, to capture Winslett's evolution in FO[2] for DL-LiteR. We also discuss which fragments of DL-LiteR are closed under evolution.
1 Introduction Description Logics (DLs) provide excellent mechanisms for representing structured 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 [
One approach to evolution semantics that proved its importance is Winslett’s
semantics (WS) [
In this work we study how WS can be applied to evolution of KBs under the following
two assumptions. First, we assume that both K and N are written in a language of the
DL-Lite family [
There are several works on WS for both DL-Lite and more expressive DLs. Liu,
Lutz, Milicic, and Wolter studied Winslett’s evolution in expressive DLs [
Current work extends the preliminary results of [
We would also like to promote prototypes since we believe they are an useful tool to study evolution of ontologies and might be not only of DL-Lite ones.
In Sections 2 and 3 we define DL-LiteR and ABox evolution under WS. In Section 4
we give an intuition of our approach to capture WS of evolution for DL-LiteR KBs using
prototypes and FO[
DL-LiteR
We introduce some basic notions of DLs (see [
The semantics of DL-Lite KBs is given in the standard way: using first order interpretations I, all over the same countable domain . We assume that contains the constants and cI = c, i.e., we adopt standard names. Alternatively, we view interpretations as sets of atoms: A(a) 2 I iff a 2 AI and P (a; b) 2 I iff (a; b) 2 P I .
Definitions of I being a model of an ABox or a TBox assertion F , denoted I j= F , and a KB K, denoted I j= K, are standard, as well as the notion of satisfiability. We use Mod(K) to denote the set of all models of K. 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.
The deductive closure of a TBox T , denoted cl(T ), is the set of all TBox assertions F such that T j= F . For satisfiable KBs K = (T ; A), a full closure of A (wrt T ), fclT (A), is the set of all membership assertions f (both positive and negative) over adom(K) such that A j=T f . Clearly, in DL-LiteR both cl(T ) and cl ( ) are computable in time T A quadratic in, respectively, jT j, i.e., the number of assertions of T , and jT [ Aj. For the ease of exhibition and wlg we assume that all TBoxes and ABoxes are closed.
A homomorphism h from a model I to a model J is a structure-preserving mapping
from to 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 [
Winslett’s Semantics for Evolution of Knowledge Bases
We start with ABox evolution of single models under Winslett’s semantics. Let K =
(T ; A) be a DL-LiteR KB, I a model of K, and N a new ABox satisfiable with T .
Evolution of a model I of K is based on the symmetric difference : S1 S2 =
(S1 n S2) [ (S2 n S1), and defined as follows. The (result of) evolution of I with N
under Winslett’s semantics (WS) [
Note that in Case (i) we have Mod of both T and N , which means that the evolution
preserves both the old TBox and the new knowledge. Case (ii) guarantees the principle
of minimal change [
The result of evolution of K with N under WS, denoted K N , is the following set of models:
N = [I2Mod(K)I
K
In terms of [
N :
The input for evolution is two finite syntactic objects: a KB K = (T ; A) and a new information N , while the output K N is a set of models, which is an infinite object for DL-LiteR. Indeed, K N is in general infinite. One can easily come up with examples where K N has an infinite number of infinite models. These observations imply that storing K N is infeasible and in practice one would like to represent the evolution as a KB K0. Moreover, one would like to stay within the same formalism and express K0 in DL-LiteR. Formally, we say that a logic L is closed under Winslett’s evolution if for every K and N in L, the result of evolution K N is expressible in L, that is, there is a KB K0 = (T ; A0) in L such that Mod(K0) = K N .
Example 1. Consider the following DL-Lite KB K1 = (T1; A1) and N1 = fC(b)g:
A1 = fA(a); C(e); C(d); R(a; b)g:
T1 = fA v 9R; 9R v :Cg; Consider the following model I of K1:
I:
AI = fa; xg, CI = fd; eg,
RI = f(a; b); (x; b)g, where x 2 n adom. The following models belong to I 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.
Indeed, all the 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 J (I) the new assertion C(b) holds and (C v :9R ) 2 T1, there should be no R-atoms with b-fillers at the second coordinate in J (I). Hence, the necessary modifications of I are either to drop (some of) the Ratoms R(a; b) and R(x; b), or to modify (some of) them, by substituting the b-fillers with another ones, while keeping the elements a and x on the first position. The model J0 corresponds to the case when both R-atoms are dropped, while in J1 and J2 only R(a; b) is dropped and R(x; b) is modified to R(x; d) and R(x; e), respectively. Note that the modification in R(x; b) leads to a further change in the interpretation of C in both J1 and J2, namely, C(d) and C(e) should be dropped, respectively. 4
Prototypes for Winslett’s Semantics
We first present a general discussion on issues with capturing WS in DL-Lite, then give
an intuition of our approach for capturing it in FO[
ABox Evolution of a DL-Lite KB K with an ABox N is the set of models K N
that may not have a canonical one [
Example 2. We now illustrate the lack of canonical models in K1 N1 from Example 1. One can verify that any model Jcan that can be homomorphically embedded into J0, J1, and J2 is such that AJcan = RJcan = ;, and e; d 2= CJcan . It is easy to check that such a model does not belong to K1 N1. Hence, there is no canonical model in K N and it is inexpressible in DL-Lite. Mod(K(J0))
Mod(K(J1))
Mod(K(J2)) J0
J1
J2 K N
S0
S1
S2
S3
J3
Mod(K(J3))
A closer look at sets K N for different K and N gave a surprising outcome: all of them satisfy the following property.
Theorem 3. K N can be divided (but in general not partitioned) into finitely many subsets S0; : : : ; Sn of models, where each Si has a canonical model Ji. Each of these canonical models is a minimal element in K N wrt homomorphisms.
We called these Jis prototypes [
We construct K0 in two steps. First, we construct DL-LiteR KBs K(Ji) for each Ji
such that K(Ji) is a sound approximations of Sis, that is, Si Mod(K(Ji)). Second,
based on K and N , we construct an FO[
To get a better intuition on our approach, consider Figure 1, where the result of evolution K N is depicted as the figure with solid-line borders (each point within the figure is a model in K N ). Assume that K N can be divided in four subsets S0; : : : ; S3. To emphasize this fact, K N looks similar to a hand with four fingers, where each finger represents an Si. Consider the left part of Figure 1. Each of Sis has a canonical model depicted as a star. Using DL-LiteR , we can provide KBs K(J0); : : : ; K(J3) that are sound approximation of corresponding Sis. We depict the models Mod(K(Ji)) as ovals with dashed-line boarders. Consider the right part of Figure 1. In this figure we depict in grey the models Mod(K(Ji)) n Si that are cut off by .
Before proceeding to the next section where we formalize our approach, we introduce prototypes formally.
Definition 4. Let K be a DL-LiteR KB and N be an ABox. A prototypal set for K is a minimal subset J = fJ0; : : : ; Jng of K N satisfying the property: N for every J 2 K N there is Ji 2 J such that Ji ,! J .
We call every Ji 2 J a prototype for K N . Note that prototypes generalize canonical models in the sense that every set of models with a canonical one, say Mod(K) for a DL-LiteR KB K, has a prototype, which is exactly the canonical model. 5
Computing Winslett’s Semantics When No Roles Interact We first discuss some of the reasons of WS inexpressibility in our examples and DL-LiteR.
BZP (K; N ) 1. 2. 3.
J0 := Align(Ican; N ) [ N , where Ican is the canonical model of K.
For each R(a; b) 2 AA(K; N ), do J0 := J0 n fR(a; b)g,
if there is no R(a; ) 2 A n AA(K; N ) do J0 := J0 n rootaTt(9R(a)).
Return J0. Dual-Affection of Roles. As we discussed in the previous section and illustrated in Example 1, sets of models K N that result from Winslett’s evolution do not have canonical models. We now give an intuition why in K N canonical models are missing. Observe that in Example 1 the role R is affected by the old TBox T1 as follows: (i) T1 places (i.e., enforces the existence of) R-atoms in the evolution result, and on one of coordinates of these R-atoms, there are constants from specific sets, e.g., A v 9R of T1 enforces R-atoms with constants from A on the first coordinate, and (ii) T1 forbids R-atoms in K1 N1 with specific constants on the other coordinate, e.g., 9R v :C forbids R-atoms with C-constants on the second coordinate. Due to this dual-affection (both positive and negative) of the role R in T1, we were able to provide an ABox A1 and N1, which together triggered the case analyses of modifications on the model I, that is, A1 and N1 were triggers for R. Existence of such an affected R and triggers A1 and N1 made K1 N1 inexpressible in DL-LiteR. Therefore, we now learn how to detect dually-affected roles in TBoxes and how to understand whether these roles are triggered by an ABox and a new (ABox) information.
Formally, let T be a TBox, a role R is dually-affected in T if for some concepts A and B it holds that T j= A v 9R and T j= 9R v :B. Let N be an ABox satisfiable with T , then a dually-affected role R is triggered by N if there is a concept B such that T j= 9R v :B and N j=T B(b) for some constant b. The set TR(T ; N ) (or simply TR) is the set of all roles (dually-affected in T ) that are triggered by N . lDateesrcprirpetsieonnt aLnogaligcsorDithLm-LittoecI a.ptWuree nWoSwusshinogwparorteosttyrpicatliosent.oDfDL-LL-iLteitIeR(wfhoerrwehIiscthanwdes R
R 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. Some interaction is still possible: role projections may contain the same concept. This restriction allows us to analyze evolution affecting roles independently for every role. Components for Computation. We now introduce several notions and notations that we further use in the description of our algorithm. An alignment of a model I with N , denoted Align(I; N ), is the interpretation:
Align(I; N ) = ff j f 2 I and f is satisfiable with N g: An auxiliary set of atoms AA (Auxiliary Atoms) that, due to evolution, should be deleted from the original KB and have some extra condition on the first coordinate is: AA(T ; A; N ) = fR(a; b) 2 fclT (A) j T j= A v 9R; A j=T A(a); N j=T :9R (b)g: For the set TR we define the set of forbidden atoms FA[T ; A; N ](Ri) of the original ABox as: fD(c) 2 fclT (A) j 9Ri (c) ^ D(c) j=T ?; N 6j=T
D(c); and N 6j=T :D(c)g:
BP (K; N ; J0) 1. J := fJ0g. 2. 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 for each B = (Ai1 ; : : : ; Aik ) such that Aj 2 SC(Rj) do J [D; R; B] := J0 n Sik=1 rootT (Di(ci)) [ Sik=1 hfclT (Ri0(xi; ci)) [ fARi0 (xi)g ; h i i where all xi’s are different constants from n adom(K), fresh for Ican.
J := J [ fJ [D; R; B]g. 3. Return J. Consequently, the set of forbidden atoms for the entire KB (T ; A) and N is
FA(T ; A; N ) = [Ri2TRFA(T ; A; N )(Ri): In the following we omit the arguments (T ; A; N ) whenever they are clear from the context. For a role R, the set SC(R), where SC stands for sub-concepts, is a set of those concepts which are immediately under 9R in the concept hierarchy generated by T : SC(R) = fA j T j= A v 9R and there is no A0 s.t. T j= A v A0 and T j= A0 v 9Rg: If f is an ABox assertion, then rootat(f ) is a set of all the atoms that T -entail f . For
T example, A(x) 2 rootaTt(9R(x)) if T j= A v 9R.
We are ready to proceed to construction of prototypes.
Constructing Zero-Prototype. The procedure BZP (K; N ) (Build Zero Prototype) in Figure 2 constructs the main prototype J0 for K and N from DL-Lite RI, which we call zero-prototype. Based on J0 we will construct all the other prototypes. To build J0 one has to align the canonical model of K with N , and then delete from the resulting set of atoms all the auxiliary atoms R(a; b) (from AA(K; N )). In the case when no R(a; ) for some constant such that R(a; ) 2 AA(K; N ) is in the canonical model, we also delete atoms rootat(9R(a)), since their presence in the model and the absence of R-atoms with
T a at the first coordinate would contradict the TBox.
Constructing Other Prototypes. The procedure BP (K; N ; J0) (Build Prototypes) of constructing J for the case of DL-Lite RI, takes J0 and manipulates with it by first dropping atoms from FA and then adding atoms in order to compensate the dropped ones so that the result is an evolved model under WS. It can be found in Figure 3
We conclude the discussion on the algorithms with a theorem: Theorem 5. 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 ; BZP (K; N )) is a prototypal set for K N .
Continuing with Example 1, it is easy to check that the prototypal set for K1 and N1 is fJ0; J1; J2; J3g, where J0, J1, and J2 are described in the example and J3:
AI = fx; yg,
CI = fbg,
RI = f(x; d); (y; e)g.
We proceed to correctness of BP in capturing evolution in DL-Lite RI, where we use the following set FC[T ; A; N ](Ri) = fc j D(c) 2 FA[T ; A; N ](Ri)g, that collects all the constants that participate in the forbidden atoms. Theorem 6. Let K = (T ; A) be a DL-Lite RI KB, N a DL-LiteR ABox consistent with T , and BP (K; N ; BZP (K; N )) = fJ0; : : : ; Jng is a prototypal set for K N . Then K
N = Mod(T ) \ Mod(A0 _ : : : _ An) \ Mod( ^ ); where Ai is a DL-LiteR ABox such that Ji is a canonical model for (T ; Ai), and = ^
^ Ri2TR cj2FC[Ri] 8x: Ri(x; cj) ! (rootaTt(9Ri(x)) 6= ;) ^
8y: (Ri(x; cj) ^ Ri(x; y) ! y = cj)] ; = ^
9R(a) ! rootaTt(9R(a)) \ fclT (A):
R(a;b)2Sat
The Ai mentioned in Theorem 6, can be constructed in the similar way that the corresponding prototypes Ji, taking the original ABox A instead of Ican. Note that an ABox may include a negative literals, like :B(c). Those should be treated in the same way that the positive literal (atoms) are. We will denote such an ABox as A[Ji]. Theorem 7. A prototype Ji is a canonical model of the KB (T ; A[Ji]).
Continuing with Example 1, the ABoxes A[J0] and A[J1] are as follows: A[J0] = fC(d); C(e); C(b)g;
A[J1] = fA(x); C(e); C(b); R(x; d)g:
A[J2] and A[J3] can be built in the similar way. Note that only A[J0] is in DL-LiteR,
while writing A[J1]; : : : ; A[J3] requires variables in ABoxes. Variables, also known
as soft constants, are not allowed in DL-LiteR ABoxes, while present in DL-LiteRS
ABoxes. Soft constants x are constants not constrained by the Unique Name Assumption:
it is not necessary that xI = x. Since DL-LiteRS is tractable and FO rewritable [
Computing Winslett’s Semantics with Roles Interaction The algorithm BP for constructing prototypal set works only when roles do not interact. The following example illustrates that it does not work in a general case. Example 8. Consider a KB K2 = (T2; A2) and a new ABox N2 = fC(b)g: TBox T2: 9R v :9P , 9R v :C, A v 9R, B v 9P ; ABox A2: R(a; b), A(a), R(f; g), A(f ), P (c; d), B(c), One can check that the following model J 0 is in K2 N2: C(e).
AJ 0 = fyg;
BJ 0 = fzg;
CJ 0 = fb; eg;
RJ 0 = f(y; d)g;
P J 0 = f(z; g)g: At the same time, BP over K2 and N2 returns the following four prototypes only: AJi
BJi
CJi
RJi
P Ji i = 0 ff g fcg fb; eg f(f; g)g f(c; d)g i = 1 ff; xg fcg fbg f(f; g); (x; e)g f(c; d)g i = 2 ff; yg ; fb; eg f(f; g); (y; d)g ; i = 3 ff; x; yg ; fbg f(f; g); (x; e); (y; d)g ; where x and y are fresh constants. It is easy to see that none of Jis is homomorphically embeddable in J 0. Thus, BP does not capture J 0 and it is incomplete.
BPrec(K; N ) 1. Compute J := BP (K; N ; BZP (K; N )). 2. Repeat
J0 := J; for each J 2 J0 do J := J [ BP (K; N [ S; J ),
where S = ff 2 J j a fresh constant from n adom(K) appears in f g; until J = J0. 3. Return J.
For general DL-LiteR KBs, BP algorithm does return prototypes but not all of them. The reason is: when, while constructing prototypes with BP, we delete a forbidden atom (an atom from FA), it may trigger another dually-affected role and such triggering may require further modifications, which are not accounted by BP. In order to compute all prototypes we should run BP recursively: considering the prototypes obtained at the previous step as zero ones. We present a recursive algorithm BPrec for building prototypes for general DL-LiteR KBs in Figure 4. The following theorem shows the correctness of the algorithm.
Theorem 9. Let K = (T ; A) be a DL-LiteR KB and N a DL-LiteR ABox consistent with T . Then the algorithm BPrec(K; N ) terminates and returns the finite set which is a prototypal set for K N .
We illustrate BPrec on the following example.
Example 10. Consider KB K2 = (T2; A2) and a new ABox N2 from Example 8. Let us compute BPrec(K2; N2). First we run BP (K; N ; J0) and it returns four prototypes: J0, J1, J2, and J3 (see Example 8). Now we apply the BP procedure to J1, J2, and J3. It is easy to see that BP (K; N [ fA(x); R(x; e)g; J1) = ;, since no role atom except for R(a; b) was affected. Consider BP (K; N [ fA(y); R(y; d)g; J2): it consists of the only prototype J4:
AJ4 = fyg;
BJ4 = fzg;
CJ4 = fb; eg;
RJ4 = f(y; d)g;
P J4 = f(z; g)g:
The uniqueness of the prototype follows from the fact that the role atom that was affected in J2 is P (c; d) and FA[T ; A; N [ fA(y); R(y; d)g](P ) = f9R (g)g. Finally, running BP (T ; N [ fA(y); R(y; d); B(z); P (z; g)g; J4) we obtain a prototype J5: AJ5 = fy; vg; BJ5 = fzg; CJ5 = fbg; RJ5 = f(y; d); (v; e)g; P J5 = f(z; g)g:
Note that BP (T ; N [fA(y); R(y; d); B(z); P (z; g); A(v); R(v; e)g; J5) = ;. Analogously, J6 can be obtained by running BP (K; N [fA(x); A(y); R(x; e); R(y; d)g; J3): AJ6 = fx; yg; BJ6 = fzg; CJ6 = fbg; RJ6 = f(x; e); (y; d)g; P J6 = f(z; g)g: Thus, the prototypal set J for K
N is fJigi6=0.
We conclude with the theorem that BPrec gives a sound approximation for WS. Theorem 11. Let K = (T ; A) be a DL-LiteR KB, N a DL-LiteR ABox consistent with T , and BPrec(K; N ) = fJ0; : : : ; Jng is a prototypal set for K N . Then K N
Mod(T ) \ Mod(A0 _ : : : _ An) \ Mod( ^ ); where Ai is a DL-LiteR ABox such that Ji is a canonical model for (T ; Ai) and are as they defined in Theorem 6. and
N under WS for KBs in DL-LiteR can be captured in FO[
As a future work we are going to study ways to approximate the resulted FO[
Finally, we discuss cases when the result of Winslett’s evolution is expressible in DL-LiteR. The following formulas appearing in Theorem 6 are not expressible in DL-LiteR: (i) the disjunction of the ABoxes A0 _ : : : _ An and (ii) formula ^ . The disjunction of ABoxes becomes expressible when it is of the length one, i.e., there is the only prototype: J0. The last statement yields that FC = ; and therefore is always true. The formula becomes trivially true when AA = ;, i.e., for every atom R(a; b) 2 fclT (A) either N 6j=T :9R (b) or rootaTt(9Ri(ai)) \ fclT (A) = ;. As one can see, the condition of expressibility of the result in DL-LiteR (emptiness of FA and AA), depends on a TBox, an ABox, and a new information. Hence, if we do a chain of evolution, at some step the result may be not expressible in DL-LiteR. Since TBox stays unchangeable, to guarantee the expressibility we need to find TBoxes T such that (T ; A) N is expressible in DL-LiteR for every A and N . A condition that guarantees the emptiness of FA and AA is: for every role R 2 (K [N ) at least one of the following items holds: (1) there is no concept C such that T j= 9R v :C, or (2) there is no concept A such that T j= A v 9R. The former conditions gives that TR = ; since N 6j=T :9R (b), which leads to FA = AA = ;. The latter one yields that SC(R) = ;, therefore TR again is empty.
As a practical summary of this section, given a KB K and a new ABox N , one can
check (in polynomial time) whether any dually-affected role is “triggered” by N . If it
is not the case, one can compute (in polynomial time) an evolved KB K0 that exactly
captures K N . Otherwise, it is the case that K N is inexpressible in DL-LiteR.
Thus, one can compute an FO[
Conclusion
We studied how to capture ABox evolution for DL-LiteR under WS. In general the
result of evolution requires constructs that are not present in DL-LiteR, and even not
in DL-Lite, such as disjunction. Moreover, in general the result of evolution, which is
a set of models, does not even have a canonical model, which should always exist for
any DL-Lite theory. It turned out that the inexpressibility is caused by a condition on the
TBox level, which we called dual-interaction: by pairs of assertions of the form A v 9R
and 9R v :B. In order to capture evolution results in the presence of dual-interactions,
we introduced prototypes. Our approach is based on the observation that evolution results
can be divided into a finite number of subsets and each of them has a canonical model,
i.e., a prototype. These subsets can be captured by theories guided by prototypes and the
disjunction of these theories, compensated with two formulas, captures evolution results
and is in FO[
Acknowledgements We are thankful to Diego Calvanese and Werner Nutt for insightful discussions. The authors are supported by EU projects ACSI (FP7-ICT-257593), Ontorule (FP7-ICT-231875). The first author was supported by the ERC FP7 grant Webdam (agreement n. 226513). Part of this work was carried out while the first author was visiting Department of Computer Science of Oxford University.