Revision of knowledge bases (KBs) expressed in description logics (DLs) has gained a lot of attention lately. Existing revision algorithms can be divided into two groups: model-based approaches (MBAs) and formula-based approaches (FBAs). MBAs are ne-grained and independent of the syntactical forms of KBs; however, they only work for some restricted forms of the DL-Lite family. FBAs can deal with more expressive DLs such as SHOIN , but they are syntax-dependent and not ne-grained. In this paper, we present a new method for instancelevel revision of KBs. In our algorithm, a non-redundant depth-bounded model is rstly constructed for the KB to be revised; then a revision process based on justi cations is carried out on this model by treating a model as a set of assertions; nally the resulting model is mapped back to a KB which will be returned by the algorithm. Our algorithm is syntax-independent and ne-grained, and works for the DL EL?.
Description logics (DLs) are playing a central role in the Semantic Web, serving
as the basis of the W3C-recommended Web ontology language OWL [
Traditionally DLs have been used for representing and reasoning about
knowledge of static application domains [
A KB K based on DL is generally composed of two parts: a TBox T for
representing intensional knowledge, and an ABox A for representing extensional
knowledge. Let K = hT ; Ai be an original KB and N a set of new information,
then there are three types of revision problems based on DLs: (1) TBox revision,
where N consists of TBox assertions only and A is empty [
In order to capture the basic ideas and properties of revision, some postulates
were proposed and well-studied in the literature [
Among these properties the last one is not precisely speci ed, since there are
di erent approaches to de ne minimality for di erent applications; it is
wellaccepted that there is no general notion of minimality that will do the right
thing under all circumstances [
According to the semantics adopted for de ning minimality, existing revision operators and algorithms can be divided into two groups: model-based approaches (MBAs) and formula-based approaches (FBAs).
In model-based approaches, the semantics of minimal change is de ned by
measuring the distance between the models of new information N and the models
of original KB K [
In formula-based approaches, the semantics of minimal change is re ected in
the minimality of formulas which will be changed. One group of FBAs is based
on the deductive closure of KBs; they are powerful enough to guarantee
syntaxindependent but only works for restricted forms of DL-Lite [
In this paper we present a new method for ABox revision problem. Compared
to MBAs and the FBAs based on deductive closures, our method is capable to
support the DL E L?. Compared to the FBAs based on justi cations, our method
is syntax-independent and ne-grained for the minimal change principle. The
proofs of all of our technical results are given in the technical report [
The DL E L? extends E L with bottom concept (and consequently disjointness
statements) [
The semantics is de ned by means of an interpretation I = ( I ; I ), where the interpretation domain I is a non-empty set composed of individuals, and I is a function which maps each concept name A 2 NC to a set AI I , maps each role name r 2 NR to a binary relation rI I I , and maps each individual name a 2 NI to an individual aI 2 I . The function I is inductively extended to arbitrary concepts by setting >I := I , ?I := ;, (C u D)I := CI \ DI , and (9r:C)I := fx 2 I j there exists y 2 I such that (x; y) 2 rI and y 2 CI g.
A TBox T is a nite set of general concept inclusions (GCIs) of the form C v D, where C and D are concepts. An ABox A is a nite set of concept assertions of the form C(a) and role assertions of the form r(a; b), where a; b 2 NI , r 2 NR and C is a concept. A knowledge base (KB) is a pair K = hT ; Ai.
The satisfaction relation \j=" is de ned inductively as follows: I j= C v D i CI DI ; I j= T i I j= X for every X 2 T ; I j= C(a) i aI 2 CI ; I j= r(a; b) i (aI ; bI ) 2 rI ; and I j= A i I j= X for every X 2 A.
I is a model of a KB K = hT ; Ai if I j= T and I j= A. We use mod(K) to denote the set of models of a KB K. Two KBs K1 and K2 are equivalent (written K1 K2) i mod(K1) = mod(K2).
A KB K = hT ; Ai is consistent (or A is consistent w.r.t. T ) if mod(K) 6= ;. A KB K entails a GCI, assertion or ABox X (written K j= X) if I j= X for every I 2 mod(K). It is obvious that K is inconsistent i K j= > v ? i K j= ?(a) for some individual name a occurring in K. We say that K entails a clash if K is inconsistent.
Let X be a concept, GCI, ABox assertion, TBox, ABox or KB, then NCX (resp., NRX and NIX ) is the set of concept names (resp., role names and individual names) occurring in X, and sig(X) = NCX [ NRX [ NIX .
For any concept C, the role depth rd(C) is the maximal nesting depth of \9" in C. Let X be an ABox or TBox, sub(X) = fC j C(a) 2 Xg if X is an ABox, and sub(X) = S fC; Dg if X is a TBox, then the depth of X is de ned as
CvD2X depth(X) = maxfrd(C) j C 2 sub(X)g. 3
Firstly we de ne the ABox revision problem in E L? as follows.
De nition 1. An E L? KB K = hT ; Ai and an ABox N is a revision setting if N is consistent w.r.t. T .
A KB K0 = hT ; A0i is a solution for a revision setting K = hT ; Ai and N if K0 is consistent and K0 j= N .
In a revision setting, K = hT ; Ai is called original KB and N is new information. The task is to incorporate new information into original KB while preserving the TBox T and guaranteeing the consistency of KB.
If we only consider the requirements on solutions speci ed in the above definition, then a straightforward solution for a revision setting K = hT ; Ai and N is the KB K00 = hT ; N i. However, obviously it is not a \good" solution, since information contained in the ABox A is completely lost. Therefore, besides the two necessary requirements, we hope that a solution has the properties speci ed by R3-R5 in Section 1 of the paper. In the following subsections, we will show that existing revision approaches not work well for E L? with respect to these properties, and then illustrate our method by an example. 3.1
Model-based Approaches
MBAs de ne revision operators over the distance between interpretations [
N = fJ 2 mod(hT ; N i) j there exists I 2 mod(K) such that dist(I; J ) = minfdist(I0; J 0) j I0 2 mod(K); J 0 2 mod(hT ; N i)g g:
Let be the set of concept names and role names occurring in K and N . There are four di erent approaches for measuring the distance dist(I; J ): { dist]s(I; J ) = ]fX 2 j XI 6= XJ g, { dists (I; J ) = fX 2 j XI 6= XJ g, { dist]a(I; J ) = sum ](XI XJ ),
X2 { dista (I; J ; X) = XI
XJ for every X 2
where XI XJ = (XI n XJ ) [ (XJ n XI ). Distances under dist]s and dist]a are
natural numbers and are compared in the standard way. Distances under dists
are sets and are compared by set inclusion. Distances under dista are compared
as follows: dista (I1; J1) dista (I2; J2) i dista (I1; J1; X) dista (I2; J2; X)
for every X 2 . It is assumed that all models have the same interpretation
domain and the same interpretation on individual names. In [
It was shown that, under these semantics, the ABox revision problem in
DLLite su ers from inexpressibility (i.e., the result of revision cannot be expressed
in DL-Lite) [
Since E L? does not support disjunction, it is obvious that it su ers from the
same problem of inexpressibility. However, in this paper, we do not require the
solution to be a single KB. In the case that implicit disjunction is introduced by
the revision process, we will generate more than one KBs Ki0 (1 i n) such
that S mod(Ki0) = K N . As a result, the cause for inexpressibility studied
1 i n
in [
There are two reasons for us to permit multi solutions. Firstly, in some applications, what we care about is to check whether an assertion ' holds or not after the revision process. In this case, we can represent all the possible solutions as a set of KBs, and check whether ' holds or not in each KB. Secondly, the implicit disjunction introduced by revision process means that there are di erent possible results for the revision process. We can compute and represent all the possible results as a set of KBs and let the user or experts to select the best one.
However, although the inexpressibility problem studied in [
T = fA v 9R:A; A v C; E u 9R:A v ?g; A1 = fA(a)g:
Firstly, we apply the semantics Gs and G]s. Let = fA; C; E; Rg. It is obvious that, for any interpretations I 2 mod(K1) and J 2 mod(hT ; N i), it must be AI 6= AJ and EI 6= EJ . Therefore, fA; Eg is the minimal set of signatures whose interpretations must be changed. So, under both Gs and G]s, we have that K1 N = fJ 2 mod(hT ; N i) j there exists I 2 mod(K1) such that
For every positive integer k, construct an interpretation Jk = ( Jk ; Jk ) as follows: Jk = fx1; :::; xkg, aJk = x1, AJk = ;, EJk = fx1g, CJk = fx1; :::; xkg, and RJk = f(x1; x2), ..., (xk 1; xk), (xk; xk)g. It is obvious that Jk 2 mod(hT ; N i). Furthermore, let Ik = ( Ik ; Ik ) be an interpretation with Ik = Jk , aIk = aJk , AIk = fx1; :::; xkg, EIk = ;, CIk = CJk , and RIk = RJk . Then it is obvious that Ik 2 mod(K1) and consequently Jk 2 K1 N .
For every positive integer k, construct another interpretation Jk0 = ( Jk0 ; Jk0 ) as follows: Jk0 = fx1; :::; xkg, aJk0 = x1, AJk0 = ;, EJk0 = fx1g, CJk0 = fx1; :::; xkg, and RJk0 = f(x1; x2), ..., (xk 1; xk)g. Then, although Jk0 2 mod(hT ; N i), there is no interpretation Ik0 2 mod(K1) with RIk0 = RJk0 . So, we have Jk0 2= K1 N .
Now, suppose solution for the revision setting under Gs and G]s is a nite number of KBs Ki0 = hT ; A0ii (1 i n) such that S mod(Ki0) = K1 N . 1 i n Consider the case that k 2. From Jk 2 K1 N , there must be some solution Ki0 = hT ; A0ii (1 i n) such that Jk 2 mod(Ki0). At the same time, from Jk0 2= K1 N , we have Jk0 2= mod(Ki0). Therefore, the ABox A0i must contain some concept assertion X(a) such that the role depth rd(X) equals k. Since the value of k can be in nitely big, such an ABox does not exist. In other words, solutions under the semantics Gs and G]s can not be expressed.
Secondly, we apply the semantics Ga and G]a. It is obvious that, for any interpretations I 2 mod(K1) and J 2 mod(hT ; N i), it must be aI 2 AI , aJ 2 EJ , aJ 2= AJ , and aI 2= EI . Therefore, under G] , we have minfdist]a(I0; J 0) j I0 2 a mod(K1); J 0 2 mod(hT ; N i)g = 2; under Ga , we have minfdista (I0; J 0; X)j I0 2 mod(K1); J 0 2 mod(hT ; N i)g = fag for X 2 fA; Eg, and minfdista (I0; J 0, X) j I0 2 mod(K1); J 0 2 mod(hT ; N i)g = ; for X 2 Ga and G]a, we have n fA; Eg. So, under both K1
N = fJ 2 mod(hT ; N i) j there exists I 2 mod(K1) such that
AI
AJ = EI
EJ = faI g; and
We can construct a KB K10 = hT , fE(a); C(a); R(a; a)gi that satis es mod(K10) = K1 N . Therefore, under both Ga and G]a, K10 is a solution for the revision setting. However, this solution is very strange, since there seems to be no \good" reason to enforce the assertion R(a; a) to hold. tu
To sum up, there are four notions of computing models in existing MBAs. For the ABox revision problem in E L?, two notions su er from inexpressibility and the other two notions are semantically questionable. 3.2
Formula-based Approaches
There are two typical formula-based approaches. The rst one is based on
deductive closures [
The second FBA is based on justi cations [
This solution is not so good, since it loses many information which is entailed by K1 and not con icted with N , such as the assertions C(a) and 9R:C(a). tu Example 3. Consider another revision setting K2 = hT ; A2i and N , where A2 = fA(a); C(a); 9R:C(a)g. Apply the FBA based on justi cations again, we will get a solution K20 = hT ; fE(a); C(a); 9R:C(a)gi.
Since the KBs K1 and K2 are logically equivalent, it is unhelpful that we get two di erent solutions w.r.t. the same new information N . tu
To sum up, for ABox revision in EL?, existing FBAs either can not be applied directly, or can be applied but is syntax-dependent and not ne-grained. 3.3
Our Approach Our method is composed of three steps. Given an ABox revision setting K = hT ; Ai and N , we rstly construct a non-redundant depth-bounded model G (called k-MW in this paper) for the initial KB K, and treat G as an ABox AG which contains some auxiliary variables. Then we execute a justi cation-based revision process on the KB K0 = hT ; AGi plus the new information N , and get a consistent KB K0 = hT ; (AG n R) [ N i. Finally we map AG n R back into an ABox A0 by \rolling up" auxiliary variables, and get a solution K0 = hT ; A0 [N i. Example 4. Consider the revision setting K1 = hT ; A1i and N described in Example 1. Firstly, since maxfdepth(K1); depth(N )g = 1, we will introduce two variables x1; x2, and construct a 1-MW G for the KB K1 (details will be given in Section 4.1 and 4.2). By treating G as an ABox, we get AG = fA(a); C(a); R(a; x1); A(x1); C(x1); R(x1; x2); A(x2); C(x2)g:
Secondly, for the clash hT ; AG [N i j= ?(a), there are two justi cations: J1 = fA v 9R:A; Eu9R:A v ?; E(a); A(a)g and J2 = fEu9R:A v ?; E(a); R(a; x1), A(x1)g. Since T is protected and E(a) 2 N , we can get two possible minimal repairs for removing the clash: R1 = fA(a); A(x1)g and R2 = fA(a); R(a; x1)g. However, since R2 contains a role assertion R(a; x1) where x1 a variable, all the information related to x1 will be lost if we apply R2 as a repair. Therefore, we choose R1 as the repair and get a consistent KB K0 = hT ; (AG n R1) [ N i = hT ; fC(a); R(a; x1); C(x1); R(x1; x2); A(x2); C(x2)g [ N i.
Finally, by rolling up variables occurring in the ABox of K0, we get a solution K0 = hT ; fC(a); 9R:(C u 9R:(A u C))(a); E(a)gi. tu
In our solution, information contained in K1 is inherited as more as possible. Furthermore, as we will see later, since the depth-bounded model G constructed in the rst step is non-redundant, our solution is syntax-independent. 4
Before presenting our revision algorithm, we introduce three procedures which will be used in the revision algorithm. 4.1
Calculating Witness for Knowledge Base The rst procedure will construct a possibly redundant depth-bounded model for the initial KB based on a structure named revision graph.
A revision graph for EL? is a directed graph G = (V; E; L), where { V is a nite set of nodes composed of individual names and variables; { E V V is a set of edges satisfying: there is no edge from variables to individual names, and for each variable y 2 V , there is at most one node x with hx; yi 2 E; { each node x 2 V is labelled with a set of concepts L(x); and { each edge hx; yi 2 E is labelled with a set of role names L(hx; yi); furthermore, if y is a variable then ]L(hx; yi) = 1.
For each edge hx; yi 2 E, we call y a successor of x and x a predecessor of y. Descendant is the transitive closure of successor.
For any node x 2 V , we use level(x) to denote the level of x in the graph, and de ne it inductively as follows: level(x) = 0 if x is an individual name, level(x) = level(y) + 1 if x is a variable with a predecessor y, and level(x) = +1 if x is a variable without predecessor.
Procedure 1 Given a KB K = hT ; Ai and a non-negative integer k, construct a revision graph G = (V; E; L) by the following steps: Step 1. Initialize the graph G as: { V = NIK, { L(a) = fC j C(a) 2 Ag for each node a 2 V , { E = fha; bi j there is some R with R(a; b) 2 Ag, { L(ha; bi) = fR j R(a; b) 2 Ag for each edge ha; bi 2 E.
Step 2. Expand the graph by applying the following rules, until none of these rules is applicable: GCIInd-rule: if x 2 NIK, C v D 2 T , D 2= L(x), and hT ; Ai j= C(x), then set L(x) = L(x) [ fDg.
GCIV ar-rule: if x 2= NIK, C v D 2 T , D 2= L(x), and hT ; fE(x) j E 2
L(x)gi j= C(x), then set L(x) = L(x) [ fDg. u-rule: if C1 u C2 2 L(x), and fC1; C2g * L(x), then set L(x) = L(x) [ fC1; C2g. 9-rule: if 9R:C 2 L(x), x has no successor z with C 2 L(z), and level(x) k, then introduce a new variable z, set V = V [ fzg, E = E [ fhx; zig, L(z) = fCg, and L(hx; zi) = fRg.
Step 3. Return the graph G = (V; E; L).
Given any KB K = hT ; Ai and non-negative integer k, we call the revision graph G returned by Procedure 1 a k-role-depth-bounded witness (k-W) for K.
Revision graphs can be seen as ABoxes with variables. Given a revision graph G = (V; E; L), we call AG = S fC(x) j C 2 L(x)g [ S fR(x; y) j R 2 x2V hx;yi2E L(hx; yi)g as the ABox representation of G, and call G as the revision-graph representation of AG.
Proposition 1. Let G = (V; E; L) be a k-W for a KB K = hT ; Ai, and let AG be the ABox representation of G. Then, for any ABox assertion with sig( ) sig(K) and depth( ) k, K j= i h;; AGi j= . A k-W of KB possibly contains some redundant information which will make two logically equivalent KBs have di erent witnesses. In this subsection, we introduce a procedure to remove these redundant information.
A graph B = (V 0; E0; L0) is a branch of a revision graph G if B is a tree and a subgraph of G.
A branch B1 = (V1; E1; L1) is subsumed by another branch B2 = (V2; E2; L2) if B1 and B2 have the same root node, ](V1 \ V2) = 1, and there is a function f : V1 ! V2 such that: f (x) = x if x is the root node, L1(x) L2(f (x)) for every node x 2 V1, hf (x); f (y)i 2 E2 for every edge hx; yi 2 E1, and L1(hx; yi) L2(hf (x); f (y)i) for every edge hx; yi 2 E1.
A branch B is redundant in G if every node in B except the root is a variable, and B is subsumed by another branch in G.
Procedure 2 Given a KB K = hT ; Ai and a non-negative integer k, let G = (V; E; L) be a k-W for K, construct a revision graph G0 = (V 0; E0; L0) by the following steps: Step 1. Initialize the graph G0 = (V 0; E0; L0) as { V 0 = V , E0 = E, L0(hx; yi) = L(hx; yi) for every hx; yi 2 E0, and { L0(x) = fC 2 L(x) j C is a concept nameg for every x 2 V 0.
Step 2. Prune G0 by the following rule until the rule is not applicable: R-rule: if there is a redundant branch B = (VB; EB; LB) in G0, then set
E0 = E0 n EB and V 0 = V 0 n (VB n fxBg), where xB is the root of B. Step 3. Return the graph G0.
For any KB K and non-negative integer k, we call the graph G0 returned by Procedure 2 a k-role-depth-bounded minimal witness (k-MW) for K. Proposition 2. Let G0 be a k-MW for a KB K = hT ; Ai, and let AG0 be the ABox representation of G0. Then, for any ABox assertion with sig( ) sig(K) and depth( ) k, K j= i h;; AG0 i j= .
The following proposition states that, for any logically equivalent KBs K and K0, their k-MW are identical up to variable renaming in the case that k is su ciently large.
Proposition 3. Let Ki = hT ; Aii (i = 1; 2) be two consistent KBs, let k be an integer with k depth(T ), k depth(A1) and k depth(A2), and let Gi = (Vi; Ei; Li) be a k-MW for Ki (i = 1; 2). If mod(K1) = mod(K2), then there is a bijection f : V1 ! V2 such that { f (x) = x if x is an individual name, { L1(x) = L2(f (x)) for every node x 2 V1, { hx; yi 2 E1 i hf (x); f (y)i 2 E2, and { L1(hx; yi) = L2(hf (x); f (y)i) for every edge hx; yi 2 E1.
Transforming a Witness Back into a Knowledge Base In this subsection we introduce a procedure to transform a revision graph into an ABox without variables. hT ; AG i j= A.
Procedure 3 Given a TBox T and a revision graph G = (V; E; L), construct an ABox by the following steps: Step 1. Delete from V all the variables which are not descendants of any individual names in G.
Step 2. Roll up the graph G by applying the following substeps repeatedly, until there is no variable contained in V : 1. Select a variable y 2 V that has no successor. 2. Let x be the predecessor of y. 3. If L(y) 6= ;, then let Cy be the concept d C, else let Cy be >. Proposition 4. For any revision graph G and TBox T , let A be the ABox returned by Procedure 3, and let AG be the ABox representation of G. Then,
Algorithm 1 Given a revision setting K = hT ; Ai and N , given a non-negative integer k, construct a nite number of KBs by the following steps: Step 1. If A [ N is consistent w.r.t. T , then return K0 = hT ; A [ N i, else continue the following steps.
Step 2. Construct a k-MW G for K.
Step 3. Let AG be the ABox representation of G. Calculate all the (AG ; N )repairs R1; :::; Rn for clash w.r.t. T .
Step 4. For each Ri (1 i n) do the following operations: 1. Construct an ABox Ai = AG n Ri. 2. Let Gi be the revision-graph representation of Ai. Call Procedure 3 to generate an ABox A0i by taking T and Gi as inputs.
The following theorems state that our algorithm satis es the properties speci ed by R1-R4 in Section 1 of the paper.
Theorem 1. For any revision setting K = hT ; Ai and N , let K0 = hT 0; A0i be any KB returned by Algorithm 1. Then, (1) K0 is consistent, (2) K0 j= N and T 0 = T , and (3) A0 = A [ N if A [ N is consistent w.r.t. T .
Theorem 2. Given any two revision settings Ki = hT ; Aii and Ni (i = 1; 2), and any integer k such that k depth(X) for X 2 fT ; A1; A2; N1; N2g. If K1 K2 and hT ; N1i hT ; N2i, then for any KB K10 returned by Algorithm 1 for the revision setting K1 and N1, there must be a KB K20 returned by the algorithm for the revision setting K2 and N2 such that K10 K20.
Theorem 2 is based on Proposition 3 where k is required to be su ciently large. Theorem 1 has no requirement on k; the rst result of it is based on Proposition 4, and the other two results are obvious from the algorithm.
In our algorithm, the k-MW G for the KB K is in fact a non-redundant k-depth-bounded model for K. Therefore, our revision process works on negrained representation of models and guarantees the minimal change principle in a ne-grained level. So, our algorithm satis es the property speci ed by R5. Theorem 3. For any revision setting K = hT ; Ai and N , assume the role depth of every concept occurring in K and N is bounded by some integer k, then Algorithm 1 runs in time exponential with respect to the size of K and N . 5
Conclusion We studied instance level KB revision in E L?. There are two main families of approaches to revision: model-based ones and formula-based ones. We illustrated that they both have disadvantages and are inappropriate for E L?. We presented a new method for the revision problem. Our method is closer in spirit to the formula-based approaches, but it also inherits some ideas of model-based ones. We showed that our algorithm behaves well for E L? in that it satis es the postulates proposed in the literature for revision operators.
For future work, we will extend our method to support ABox revision in E L++. Another work is to formalize the notion of minimality of change. Finally, we will make an optimization to the algorithm and test the feasibility of it in practice.
Acknowledgments. This work was partially supported by the National Natural Science Foundation of China (Nos. 61363030, 61262030) and the China Scholarship Council.