Ontology Contraction: Beyond the Propositional Paradise

Abstract

The dynamic nature of ontology development has motivated the formal study of ontology evolution problem. This paper addresses contraction -the problem of retracting information that should no longer hold in an ontology. We survey existing model and formula based semantics to contraction and investigate their properties for the description logics DL-Lite and E L, which underpin the QL and EL profiles of OWL 2. Our results suggest that these contraction semantics, which are well-understood and well-behaved for propositional logics, are intrinsically problematical in the context of ontology languages. We believe that a starting point for addressing these problems might be the recent semantics proposed in [1].

Introduction

of K satisfying the evolution requirements, with FBS differing in their subset selection mechanism. FBS have been less studied in the context of ontologies [ 8, 17 ].

Approaches to ontology contraction typically adopted in practice are, however, syntactic [ 6, 10, 18, 19 ]. For example, to retract an axiom entailed by K, it suffices to compute a maximal subset of K that does not entail . This solution complies with a syntactical notion of minimal change: retracting results in the deletion of a minimal set of axioms, and the structure of K is maximally preserved. By removing axioms from K, however, we may also be retracting consequences of K other than , which are intended. Identifying and recovering such intended consequences is an important issue.

In this paper we compare different syntactic, model-based, and formula-based semantics for ontology contraction, and study their basic properties. We consider two scenarios, which are important for many ontology design and management tasks: – TBox contraction, where the axiom to be retracted is a TBox axiom; and – ABox contraction, where is an ABox assertion, and the TBox of the original ontology cannot be modified as a result of the contraction.

OWL TBoxes are extensively used in the clinical sciences, and ontologies such as SNOMED are subject to frequent modifications that involve retracting TBox consequences [ 20 ]. ABox contraction is important for applications relying on widely-used reference TBoxes. For example, experimental results on gene extraction can be described using an ABox according to standard gene TBoxes. New experiments may imply that facts about specific genes no longer hold, which should be reflected in the ABox; at the same time, TBoxes should clearly not be affected by these manipulations of the data.

In our formal study of ontology contraction problems we will put special emphasis on expressibility: given a DL-ontology K, an axiom to be retracted, and a “protected” part P of K, we will study whether a DL-ontology Kop entailed by K exists – an optimal contraction – such that (i) Kop 6j= , (ii) Kop j= P, and (iii) Kop is “as similar as possible” to K according to the notion of minimal change in the semantics under consideration.

Our framework is general, and applies to arbitrary first-order languages. When studying expressibility problems, however, we provide results for two prominent (families of) DLs: DL-Lite [ 21 ] and E L [ 22 ]. which underpin OWL 2 QL and OWL 2 EL, respectively. We show that existing inexpressibility results obtained for the problem of update and revision in DL-Lite under MBS [ 8, 15 ] also hold for contraction with minor modifications; furthermore, we conjecture that these results might hold even if the optimal contraction of a DL-Lite ontology is allowed to be expressed in full first-order logic. Concerning FBS, we focus on two semantics: the so-called bold semantics [ 8 ] and WIDTIO semantics [ 8, 23 ]; in both cases, we show inexpressibility results that apply to both TBox and ABox contraction in E L.

Furthermore, we show that existing MBS, FBS, and syntactic approaches to ontology contraction are rather incompatible. Although one would expect FBS approaches to behave better in terms of expressibility, this is not always the case; in particular, we identify simple cases for which inexpressibility can be shown in the FBS approach, but which can be easily captured using a model-based semantics.

Our results suggest that classical approaches to ontology contraction, which are wellunderstood and well-behaved for propositional logics, are intrinsically problematical in DL-Lite

?, > C1 u C2 9R:C

R concepts, roles

semantics ;, I , resp.

C1I \ C2I fa j 9b s.t. (a; b) 2 RI ; b 2 CI g f(a; b) j (b; a) 2 RI g concepts, roles axioms C := ? j > j A j 9R:C j C1 u C2

C1 v C2 C := ? j > j A j 9R:> R := P j P

C1 v C2, C1 v :C2, C v C1 u C2, (funct R), R1 v R2

axiom C1 v C2 C1 v :C2 (funct R) R1 v R2

semantics C1I C2I C1I I n C2I RI is functional R1I R2I the context of ontology languages. A starting point for addressing these problems might be the semantics in [ 1 ], which unifies and extends FBS and syntactic approaches: the challenge remains to extend this semantics to encompass also MBS contraction. 2

Preliminaries

We discuss contraction in the context of first-order logic (FOL). Our work, however, is motivated by description logic ontologies, so we will use DL terminology throughout the paper. We assume standard definitions of (function-free) FOL signature, predicates, formulae, sentences, interpretations and models, satisfiability, and entailment.

An ontology K = T [ A consists of finite sets of first-order sentences T (the TBox) and ground atoms A (the ABox). In the most general setting, a description logic can be defined as a recursive set of ontologies closed under renaming of constants and the subset relation. Predicates in DL signatures are typically restricted to be unary (atomic concepts) or binary (atomic roles). DLs use a specialised syntax, where variables are omitted, and which provides operators for constructing complex concepts and roles from simpler ones, as well as a set of axioms.

We consider two (families of) DLs: DL-Lite [ 21 ] and E L [ 22 ]. The syntax of (the variants of) DL-Lite and E L considered here are given in Figure 1, where A is an atomic concept, C, C1, and C2 are arbitrary concepts, and > and ? are special concepts which are mapped by every interpretation to the domain and the empty set, respectively. TBoxes in DL-Lite are restricted: first, > cannot occur on the left-hand side of axioms; second, for each R2 s.t. R1 v R2 2 T , it holds that T 6j= (funct R2) and T 6j= (funct R2 ).

Let DL and DL0 be DLs with DL0 DL. The closure ClDL0 (K) of K 2 DL w.r.t. DL0 is the set of all DL0-axioms entailed by K.

The evaluation of DL-Lite and E L concepts and axioms under I = ( I ; I ) is also given in Figure 1. We adopt the standard name assumption and assume that cI = c for each constant c; that is, we do not distinguish between constants and domain elements. 3

The Ontology Contraction Problem

As already mentioned, contraction can be seen at a high level as the process of retracting an axiom that holds in an ontology K while preserving a protected part P of K.

The following notion of a contraction setting formalises the basic requirements that K, and P must satisfy for the contraction process to make sense.

Definition 1. Let DL be a DL. A DL-contraction setting is a triple C = (K; P; ), with K = T [ A a DL-ontology, a DL-axiom s.t. K j= , and P a DL-ontology s.t. K j= P and P 6j= . We say that C is a TBox-contraction setting if is a TBox axiom in DL; C is an ABox contraction setting if is an ABox assertion in DL and P j= T . tu

A contraction for a DL-setting C = (K; P; ) can now be defined as a DL-ontology Kop that preserves P and in which no longer holds. Furthermore, since Kop should not add new information to K, we also require Kop to be entailed by K.

Definition 2. Let C = (K; P; ) be a DL-contraction setting. We say that Kop 2 DL is a contraction for C if (i) K j= Kop; (ii) Kop j= P; and (iii) Kop 6j= . tu

The properties that an “optimal” contraction needs to satisfy are dictated by the principle of minimal change according to which the semantics of the ontology should be changed “as little as possible”, thus ensuring that modifications have the least possible impact. Hence, the contraction problem can be understood at a high level as follows: [CONTRACT]: Is a given DL-ontology Kop an optimal contraction for a given DL-contraction setting C = (K; P; )?; in other words, is Kop a contraction for C such that no other contraction Ko0p for C is “more similar” to K that Kop? Thus, optimal contractions are those that are “as similar to K as possible”. The notion of optimal contraction immediately suggests the following expressibility problem. [EXPRESS]: Does an optimal contraction exist for a given DL-contraction setting? Contraction semantics essentially differ in their formalisation of optimality. These can roughly be divided into three groups, which we shall discuss next: model-based semantics (MBS), formula-based semantics (FBS), and syntactic approaches. 4

Syntactic Contraction

Approaches to ontology contraction typically adopted in practice are essentially syntactic [ 6, 10, 18 ]. In particular, to retract an axiom entailed by K, it suffices to compute a maximal subset Kop of K that does not entail . Thus, retracting results in the deletion of a minimal set of axioms and hence the structure of K is maximally preserved. In this setting, optimal contractions can be defined as follows.

Definition 3. Let C = (K; P; ) be a DL-contraction setting. A contraction Kop for C is syntactically optimal if Kop K and no contraction K0 for C exists s.t. Kop K0 K. tu

In this case, [CONTRACT] and [EXPRESS] essentially amount to entailment checking. Furthermore, practical algorithms for computing such optimal Kop have been implemented in ontology development platforms. By adopting this approach to contraction, however, we may inadvertently retract consequences of K that are “intended”. Identifying and recovering such intended consequences is an important issue. Example 4. Let C = (K; P; ), where K = fA v B u C; A v 9R:A u Cg, P = ;, and = A v C. Clearly, Kop = ; is syntactically optimal. By computing Kop, however, we have also retracted consequences of K unrelated to , i.e., A v B and A v 9R:A. tu

I0

I1 Ji |= P Ji 6|= ↵

J0 J1 J2 J3 local: L

Approach set: ✓

number: # Distance is built upon

atoms: a symbols: s

Type of distance Intuitively, under an MBS a contraction Kop for a setting C = (K; P; ) is optimal if the set of models Mod(Kop) of Kop is precisely the union of the models Mod(K) of K and the set of interpretations I such that (i) I j= P, (ii) I 6j= ; and (iii) I is “minimally distant” from the models of K [ 13, 24, 25 ].

Calvanese et al. [ 8 ] considered two notions of “minimal distance”, which they called local and global. We next define these semantics in the context of our framework. Definition 5. Let C = (K; P; ) be a DL-contraction setting, and let dist( ; ) be a distance function between interpretations. For I an interpretation, let loc min(I; P; ) be the set of interpretations J s.t., J j= P, J 6j= , and on J the value of dist(I; J ) is minimal for the given I. Then, Kop 2 DL is L-optimal for C if the following holds:

Mod(Kop) = Mod(K) [ SIj=K loc min(I; P; ):

Thus, under local semantics, the models of I of K are considered one by one and Mod(K) is extended with those models J of P such that J 6j= and J is minimally distant from I. The specific distance under consideration can vary, but it typically maps each pair of interpretations to either a number or a subset of some fixed set.

To get a better intuition of local semantics, consider the left hand side of Figure 2, which depicts two models I0 and I1 of K and four interpretations J0; : : : ; J3 which satisfy P but not . The distance between Ii and Jj is represented by the length of the line connecting them; solid lines correspond to minimal distances, and dashed lines to distances that are not minimal. In this case, J0 must be included in Mod(Kop) because of I0, and J2; J3 must be included in Mod(Kop) because of I1.

Definition 6. Let C = (K; P; ) be a DL-contraction setting, and dist( ; ) a distance function between interpretations. For an interpretation J , let dist(Mod(K); J ) = minI2Mod(K) dist(I; J ). Furthermore, let glob min(K; P; ) be the set of interpretations J s.t. J j= P, J 6j= , and for each interpretation J 0 such that J 0 j= P and J 0 6j= it does not hold that dist(Mod(K); J 0) < dist(Mod(K); J ).

Then, Kop 2 DL is G-optimal for C if the following condition holds:

Mod(Kop) = Mod(K) [ glob min(K; P; ):

If we consider again Figure 2 and assume that the distance between I0 and J0 is the global minimum, then J2 and J3 are not included in Mod(Kop).

Finally, note that if Kop is optimal (either locally or globally), then Kop is a contraction for C, as in Definition 2. Furthermore, L-optimal and G-optimal contractions are also clearly unique modulo logical equivalence. tu tu 5.1

Measuring Distance Between Interpretations.

Classical MBS semantics were originally developed for propositional theories [ 23 ]. In this setting, interpretations can be seen as finite sets of propositional symbols, and the symmetric difference “ ” between such sets can be used to define specific distance functions. More precisely, we can define I J as the set (I n J ) [ (J n I) and introduce the following two distance functions, where jI J j is the cardinality of the set I J : dist (I; J ) = I

J and dist#(I; J ) = jI

J j: (1) Distances under dist are compared using set inclusion: dist (I1; J1) dist (I2; J2) iff dist (I1; J1) dist (I2; J2). Finite distances under dist# are natural numbers and are compared in the standard way.

These distances can be extended to DL interpretations in two ways. First, one can consider interpretations I and J as sets of atoms, in which case the symmetric difference I J and the corresponding distances are defined as in the propositional case. In contrast to the propositional case, however, I J (and hence also distances) can be infinite. We denote the distances in Equation (1) as dista (I; J ) and dista#(I; J ), respectively.

Finally, one can also 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:

To sum up, we can classify MBS semantics along three dimensions, which in turn lead to eight different MBS semantics for contraction: (1) local vs. global approach, (2) atom-based vs. symbol-based distances; and (3) set inclusion vs. cardinality to compare symmetric differences.

These three dimensions are depicted on the right-hand side of Figure 2. We denote each of the resulting eight semantics by using a combination of three symbols, indicating 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. We can then define Lyx-optimality (respectively, Gyx-optimality) as in Definition 5 (respectively, as in Definition 6) by using the specific distances determined by the values of x and y.

Since in the propositional case there is no distinction between atom and symbol-based semantics, we use our notation without superscripts for propositional MBS. The classical local MBS by Winslett [ 26 ] and Forbus [ 27 ] correspond to L , and L#, respectively. Borgida’s semantics [ 28 ] is a variant of L . The classical global MBS proposed by Satoh [ 29 ] and Dalal [ 30 ] correspond to G , and G#, respectively.

Definition 7. Let DL be a DL and let Myx with M 2 fL; Gg, x 2 f ; #g, and y 2 fs; ag be an MBS contraction semantics. We say DL is closed under Myx-contraction (or Myx-contraction is expressible in DL) if for each DL-contraction setting C, an ontology Kop 2 DL exists such that Kop is Myx-optimal.

Analogously, DL is closed under TBox (resp. ABox) Myx-contraction if for each TBox (resp. ABox) DL-contraction setting C, an Myx-optimal Kop 2 DL exists. tu

Challenges in Capturing MBS Contractions.

MBS contraction is not always expressible in lightweight DLs, such as DL-Lite and E L. Inexpressibility problems mainly originate from the inability of these logics to express disjunction, as shown in the next proposition [ 8 ].

Proposition 8. Let K be either a DL-Lite or an E L ontology. If K j= A(a) _ B(b), with A; B atomic concepts, then either K j= A(a) or K j= B(b).

We next illustrate inexpressibility issues for DL-Lite and E L under each of the eight MBS contraction semantics introduced in this paper. We start with TBox contraction. Example 9. Let DL 2 fDL-Lite; E Lg and let C = (K; P; ), where K = fA v B u C; A(a)g, P = fA(a)g, and = A v B u C. Pick an MBS semantics Myx and assume Kop 2 DL exists s.t. Kop is Myx-optimal for C.

First, observe that the following conditions hold for each I 2 Mod(K) and each J j= P s.t. J 6j= (both seen as sets of atoms): (i) B(a); C(a) 2 I; (ii) either fB(a)g dist (I; J ) or fC(a)g dist (I; J ) for J 2 Mod(Kop); (iii) 1 dist#(I; J ) for J 2 Mod(Kop); (iv) if J is such that B(a) 2= J and C(a) 2= J , then J 2= Mod(Kop).

Now, consider the following models: J1 = fA(a); B(a)g, and J2 = fA(a); C(a)g. From Items (ii) and (iii) we conclude that Ji 2 loc min(fA(a); B(a); C(a)g; P; ). Then, we can use items (i) and (iv) to conclude that Kop j= B(a)_C(a). By Proposition 8, we must have either Kop j= B(a) or Kop j= C(a). But then, since items (ii) and (iii) ensure that Kop 6j= B(a) and Kop 6j= C(a), we obtain a contradiction. tu

Observe next that similar issues arise for ABox contraction under local MBS. Example 10. Let DL = E L and let K = (T ; A) be the following DL-ontology: T = fA v 9R:B; B u C v ?g;

A = fA(a); R(a; b); B(b); C(c); C(d)g: Finally, let C be the DL-contraction setting defined by K, P = T [ fA(a)g, and = R(a; b). Pick a local MBS semantics Lyx and assume Kop 2 DL exists s.t. Kop is Lyx-optimal for C. Consider the following interpretations:

I0 : J1 : J2 :

AI = fag; AI = fag; AI = fag;

BI BI BI = fbg; = fb; cg; = fb; dg;

CI = CI = CI =

I n fbg; I n fb; cg; I n fb; dg;

RI RI RI = f(a; b)g; = f(a; c)g; = f(a; d)g: Clearly, I0 j= K and one can check that J1; J2 2 loc min(I0; P; ). Moreover, since J1 6j= C(c) and J2 6j= C(d), we have Kop 6j= C(c) and Kop 6j= C(d). At the same time, one can show that Kop j= C(c) _ C(d). Proposition 8 then leads to a contradiction.

Inexpressibility of DL-Lite ABox contraction can be shown analogously by taking A, P, and as before and using a TBox T = fA v 9R:>; 9R :> v B; B v :Cg, which “mimics” the behaviour of the E L-TBox considered before. tu Theorem 11. Let DL 2 fDL-Lite; E Lg and let M 2 fL; Gg, x 2 f ; #g and y 2 fs; ag. Then, DL is not closed under TBox Myx-contraction. Furthermore, DL is not closed under ABox Lyx-contraction.

These inexpressibility results can be overcome by allowing fewer models in optimal contractions. To this effect, one can define a partial order on models where J1 J2 if J1 changes certain aspects of Mod(K) less than J2; then, Kop can only have models that are -minimal. For example, in [ 7 ] changes in concepts rather than roles were preferred. Formally, J1 RK J2 if there is I 2 Mod(K) such that dists (I; J2) contains a role and dists (I; J1) contains only concepts. Another example of is to order the signature of K, e.g., A B if B is a “more important concept” than B; that is, if dista (I; J2) = fA(a)g and dista (I; J1) = fB(a); B(b)g, then J1 J2 since J2 changes a more important concept A.

Definition 12. Let be a partial order on the class of all first-order interpretations and min the class of interpretations minimal w.r.t. . Let C = (K; P; ) be a DLcontraction setting. We say that Kop 2 DL is [ ; L]-optimal for C if it holds that: Mod(Kop) = Mod(K) [ [ (loc min(I; P; ) \ min ) :

Ij=K Finally, Kop 2 DL is [ ; G]-optimal for C if the following condition holds: Mod(Kop) = Mod(K) [ (glob min(K; P; ) \ min ) : tu We next show that this solution can lead to even more severe inexpressibility problems; in particular, optimal contractions might not even be expressible with FOL ontologies. Example 13. Let DL = E LF I, which extends E L with functionality and inverses. Let C be defined by = A(a1), P = T , and the following DL ontology K = T [ A: T = fA v 9R:B; B v 9R:A; AuB v ?; (funct R); (funct R )g; A = fA(a1)g: Each model I of K is of one of the following two types (see Figure 3): (i) I contains a cycle of the form R(a1; a2); : : : ; R(a2n; a1) for some n 2 N such that for each 1 k 2n we have A(ak) 2 I if k is odd and B(ak) 2 I if k is even; (ii) I contains an infinite R-chain R(a1; a2); : : : R(ak; ak+1); : : : such that for each k 1 we have A(ak) 2 I if k is odd and B(ak) 2 I if k is even.

Assume there exists a FOL ontology Kop that is [ R; Gs ]-optimal for C. By DefK inition 12, Mod(Kop) consists of following two disjoint sets of models: Mod(K) and S = glob min(K; P; ) \ min . Observe that S consists of the models obtained from Mod(K) as described next (see r.h.s. of Figure 3). If I is of Type (i), then one has to drop all atoms of the form A(ak) and B(ak) for each ak involved in the cycle, which gives us again a cyclic model; let S1 be the set of all such models. If I is of Type (ii), then one must drop only A(a1), which yields a model with an infinite chain; let S2 be the set of all such models. Clearly, S1, S2, and Mod(K) are mutually disjoint. The following ontology has exactly S2 as models: K2 = T [ f9R:B(a1); :A(a1)g. We next use the locality property of FOL to show that no FOL ontology K1 exists s.t. Mod(K1) = S1. Assume such K1 exists and consider J1 containing an R-cycle of even length, and J2 containing an R-cycle of odd length. If the cycle’s length is big enough, K1 cannot distinguish between J1 and J2; thus, J2 2 Mod(K1), a contradiction. Finally, Mod(Kop ^ :K ^ :K2) = S1, which contradicts the fact that S1 cannot be captured by a FOL ontology. Hence, no optimal Kop exists.3 tu 3 We denote with :K(i) the formula obtained by negating the conjunction of all formulas in K(i).

A a1 a2n

B a2 a3

a1 · · · · · ·b1 a1

B a2

B a2

A a3 · · · A a3 · · · Given a contraction setting C, the bold semantics [ 8 ] selects a maximal subset of the closure of the corresponding ontology that is a contraction for C.

Definition 14. Let C = (K; P; ) be a DL-contraction setting and M(C) the class of maximal subsets S of ClDL(K) s.t. S j= P and S 6j= . Then, Kop 2 DL is BS-optimal for C if there exists S 2 M(C) such that Kop S. tu Note that under Bold semantics Kop is not unique in general (even modulo equivalence). There have been several proposals for combining all elements of M(C) into a single set of formulas [ 8, 23, 26 ]. Under Cross-Product (CP) semantics, an optimal evolution is equivalent to the “disjunction” of all relevant maximal subsets of the closure, whereas under When In Doubt Throw It Out (WIDTIO) semantics, one takes the “intersection”. Definition 15. Let C = (K; P; ) be a DL-contraction setting. Then, Kop 2 DL is CPoptimal for C if Kop fWS2M(C)(V 2S )g, WIDTIO-optimal if Kop TS2M(C) S. tu

Expressibility of optimal contractions can now be defined in the obvious way. Definition 16. Let DL be a DL and let S2fBS; CP; WIDTIOg be an FBS contraction semantics. We say DL is closed under S-contraction (or S-contraction is expressible in DL) if for each DL-contraction setting C, an S-optimal Kop 2 DL exists. tu

Intuitively, CP has the advantage of not “losing information”; however, CP-optimal contractions can be exponentially larger than the original ontology, even if its closure is a finite set. In addition, even if we consider a DL-Lite contraction setting C, the corresponding CP-optimal contraction for C may not be expressible in DL-Lite, since a language with disjunction may be required. In contrast, WIDTIO-optimal contractions for DL-Lite are always expressible, but important information may be lost.

Thus, both CP and WIDTIO semantics are somewhat problematic, even for languages such as DL-Lite, where the deductive closure is always a finite set. In contrast, BS semantics is well-behaved for DL-Lite: optimal contractions always exist; furthermore, in the case of ABox contraction they are also unique and computable in polynomial time [ 8 ]. In general, however, BS-optimal contractions are non-unique for TBox contractions. 6.1

Expressibility issues for EL.

Unfortunately, as soon as we consider logics such as E L, for which the closure of an ontology can be infinite, WIDTIO and BS semantics lead to inexpressibility problems. This is illustrated by the following example (adapted from Lemma 19 in [ 1 ]). Example 17. Let C = (T ; P; ) be the E L contraction setting defined as follows: T = fZ v 9R:A; A v 9R:A; 9R:B v B; A v Bg; = A v B;

P = T n f g Furthermore, for each k 2 N, let k = Z v 9Rk:(A u B); k = Z v 9Rk:B; k = f i j 1 i kg: For each k 2 N, observe that k j= k, k 6j= k+1, and k 2 ClEL(T ); also, P [ k 6j= . Let Top be BS-optimal for C; we then have Top j= k for each k 2 N. Furthermore, for each finite S ClEL(T ) there is n such that P [ n j= S. Thus, such n = n0 exists for Top and hence n0 6j= n0+1 and by monotonicity of FOL, Top 6j= n0+1 and we obtain a contradiction to the maximality of Top; hence, Top cannot be BS-optimal. tu

We formalize the intuition from the example in the next theorem (which is an adaptation of Theorem 20 from [ 1 ]).

Theorem 18. E L is not closed under TBox BS-contraction.

A similar inexpressibility result can be obtained for ABox contraction. Example 19. Let C = (A; ;; ) be the E L-ABox contraction setting defined by A = fA(a); R(a; a)g, and = R(a; a). Then, for each k 2 N, we have k = 9Rk:A(a) is in ClEL(A). Clearly, Skf kg 6j= . Thus, if an E L BS-contraction Aop for C exists, then Aop j= k for each k. One can show that no such finite Aop exists. tu Theorem 20. E L is not closed under ABox BS-contraction.

Examples 17 and 19 can also be used to illustrate inexpressibility of WIDTIOoptimal contractions. Indeed, observe that in Example 19 every maximal subset Aop of ClEL(A) contains the infinite set Skf kg.

Theorem 21. E L is not closed under ABox and TBox WIDTIO-contraction. 6.2

FBS vs MBS We next show that some contraction settings for which no MBS-optimal contraction exists can be easily captured using FBS (and vice versa). Thus, there seem to be certain key points of “incompatibility” between model-based and formula-based contraction semantics, which require further investigation.

Example 22. Consider the setting C in Example 9. Let A0 = fA(a); B(a); C(a)g. Under BS semantics we have two optimal contractions, namely Ko1p = A0 [ fA v Bg and Ko2p = A0 [ fA v Cg, which are both in DL-Lite and E L.

Next, recall the E L-setting C from Example 10. There is a unique (modulo equivalence) BS-optimal contraction for C, namely Kop = K n f g.

Finally, recall Example 19. Under all model-based contraction semantics considered in this paper, the optimal contraction for C can be shown to be Aop = fA(a)g. tu

Extending the Formula Based Approach As already discussed, formula-based semantics are well-behaved for DLs such as DL-Lite, where the closure of an ontology is always finite [ 8, 15 ]. FBS are, however, problematic for DLs like E L, which do not provide such guarantee. Inexpressibility issues for BSsemantics originate from the requirement that optimal contractions for C = (K; P; ) must be equivalent to a maximal subset S of ClDL(K) satisfying P but not ; if ClDL(K) is infinite, it might be that no such S is equivalent to a finite set of DL formulas.

FBS are also problematic from a modeling point of view: in contrast to syntactic approaches, they do not distinguish between the axioms in the closure that are explicit in K, and those that are implied. Ontologies, however, are the result of a time-consuming modeling process, and thus contractions should also aim at preserving the structure of K.

In [ 1 ], these limitations of FBS approaches were addressed (at least partly). On the one hand, the semantics in [ 1 ] provides a “bridge” between syntactic and FBS approaches; on the other hand, this semantics provides a distinction between the languages DL in which both K and the resulting contraction are expressed, and the language LP (the preservation language), which expresses the entailments of K that must be maximally preserved. The principle of minimal change is reflected along two dimensions: (i) structural, where the explicit axioms in K are maximally preserved; (ii) deductive, where the consequences in ClLP (K) are maximally preserved. Definition 23. Let C = (K; P; ) be a DL-contraction setting and let LP contraction Kop for C is SD-optimal4 for C and LP if (i) Kop [ f g j= 2 K n Kop; and (ii) Kop [ f g j= , for each 2 ClLP (K) n ClLP (Kop).

DL. A , for each tu

The notion of expressibility can be formalised as in Definition 16 in the obvious way. Note that the preservation language LP provides “control” over the consequences to be preserved. Furthermore, syntactic contractions can be easily captured by taking LP to be the empty set. We next illustrate SD-contractions with an example.

Example 24. Let DL = E L and let LP be the DL consisting of all atomic subsumptions of the form A v B. Let K = fA v B; B v Cg and let = A v B. Clearly, Kop = fB v C; A v Cg is an SD-optimal contraction for LP and C = (K; ;; ). tu

As shown in [ 1 ], there exist practically relevant DLs DL and LP such that, on the one hand, DL is closed under SD-contraction for LP and, on the other hand, ClLP (K) is in general an infinite set for K 2 DL. For example, one may consider DL to be the set of acyclic E L ontologies – roughly speaking, those E L ontologies that do not entail cyclic axioms involving existential quantifiers on the right hand side of the axiom (e.g., axioms such as A v 9R:A). Many E L ontologies such as SNOMED, satisfy such acyclicity condition. In this setting, restrictions to LP also apply (see [ 1 ] for details). 7

Conclusion and Future Work

In propositional logic, contraction is always expressible under both MBS and FBS. In the case of propositional MBS, contraction results are finite sets of finite models, which 4 SD stands for Structural-Deductive can always be axiomatised as a set of propositional formulas. The problem of interest in the propositional case is the complexity of axiomatisation [ 23 ]. For FBS the situation is similar: deductive closure of any propositional theory is a finite set (modulo equivalence); thus, BS, CP, WIDTIO, or SD-optimal contractions always exist. Again, the challenge here is the complexity of optimal contraction computation [ 23 ].

However, as soon as we move from propositional to first-order logic (and even to computationally well-behaved fragments such as Description Logics), we are also forced to leave propositional paradise. As we have shown, inexpressibility issues arise in rather simple cases for both FBS and MBS. These results suggest that classical approaches to contraction are intrinsically problematical in the context of ontologies. A starting point for addressing these problems might be the semantics in [ 1 ], which unifies and extends FBS and syntactic approaches; the challenge remains to extend this semantics to encompass also MBS contraction —an inspiring problem for future work.

Interesting further steps include: (i) understanding the impact of the standard-names assumption on expressibility and computation of contraction, (ii) better understanding FOL inexpressibility (e.g., see Example 13) (iii) isolating fragments of DL-Lite and E L for which contraction is well-behaved (see preliminary results in [ 1, 15 ]), Acknowledgements. We thank Balder Ten Cate for helpful discussions and anonymous reviewers for the inspiring feedback. B. Cuenca Grau is supported by a Royal Society Fellowship. E. Kharlamov is supported by the EPSRC EP/G004021/1, EP/H017690/1, and ERC FP7 grant Webdam (n. 226513). E. Kharlamov and D. Zheleznyakov are supported by the EU project ACSI (FP7-ICT-257593).

References

1. Cuenca Grau , B. , Jimenez-Ruiz , E. , Kharlamov , E. , Zheleznyakov , D. : Ontology evolution under semantic constraints . In: KR , Rome, Italy ( 2012 )

2. Horrocks , I. , Patel-Schneider , P.F. , van Harmelen , F. : From SHIQ and RDF to OWL: the making of a web ontology language . Journal of Web Semantics 1 ( 1 ) ( 2003 ) 7 - 26

3. Cuenca Grau , B. , Horrocks , I. , Motik , B. , Parsia , B. , Patel-Schneider , P. , Sattler , U. : OWL 2: The next step for OWL . Journal of Web Semantics 6 ( 4 ) ( 2008 ) 309 - 322

4. Baader , F. , Calvanese , D. , McGuinness , D.L. , Nardi , D. , Patel-Schneider , P.F. : The description logic handbook: Theory, implementation, and applications . In: Description Logic Handbook , Cambridge Uni. Press ( 2003 )

5. Flouris , G. , Manakanatas , D. , Kondylakis , H. , Plexousakis , D. , Antoniou , G.: Ontology change: classification and survey . Knowledge Eng. Review 23 ( 2 ) ( 2008 ) 117 - 152

6. Haase , P. , Stojanovic , L. : Consistent evolution of OWL ontologies . In: ESWC. ( 2005 )

7. Qi , G. , Du , J.: Model-based revision operators for terminologies in Description Logics . In: IJCAI. ( 2009 ) 891 - 897

8. Calvanese , D. , Kharlamov , E. , Nutt , W. , Zheleznyakov , D. : Evolution of DL-Lite Knowledge Bases . In: ISWC, Shanghai, China ( 2010 )

9. Wang , Z. , Wang , K. , Topor , R.W.: Revising general knowledge bases in Description Logics . In: KR. ( 2010 )

10. Jimenez-Ruiz , E. , Cuenca Grau , B. , Horrocks , I. , Berlanga , R.: Supporting concurrent ontology development: Framework, algorithms and tool . Data and Know. Eng. 70 : 1 ( 2011 )

11. Konev , B. , Walther , D. , Wolter , F. : The logical difference problem for description logic terminologies . In: IJCAR . ( 2008 )

12. Gonc¸alves, R.S., Parsia , B. , Sattler , U. : Analysing the evolution of the NCI thesaurus . In: CBMS. ( 2011 ) 1 - 6

13. Alchourro´n, C.E. , Ga¨rdenfors, P. , Makinson , D. : On the logic of theory change: Partial meet contraction and revision functions . J. Symb. Log . 50 ( 2 ) ( 1985 ) 510 - 530

14. Peppas , P. : Belief revision . In: Handbook of Knowledge Representation . ( 2007 )

15. Kharlamov , E. , Zheleznyakov , D. : Capturing instance level ontology evolution for DL-Lite . In: ISWC. ( 2011 )

16. Wang , Z. , Wang , K. , Topor , R.W.: A new approach to knowledge base revision in DL-Lite . In: AAAI. ( 2010 )

17. Lenzerini , M. , Savo , D.F. : On the evolution of the instance level of DL-Lite knowledge bases . In: DL. ( 2011 )

18. Kalyanpur , A. , Parsia , B. , Sirin , E. , Grau , B.C. : Repairing unsatisfiable concepts in OWL ontologies . In: ESWC. ( 2006 ) 170 - 184

19. Schlobach , S. , Huang , Z. , Cornet , R., van Harmelen , F. : Debugging incoherent terminologies . J. Automated Reasoning 39 ( 3 ) ( 2007 ) 317 - 349

20. Hartung , M. , Kirsten , T. , Rahm , E.: Analyzing the evolution of life science ontologies and mappings . In: DILS. ( 2008 ) 11 - 27

21. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and efficient query answering in Description Logics: The DL-Lite family . Journal of Automated Reasoning 39 ( 3 ) ( 2007 ) 385 - 429

22. Baader , F. , Brandt , S. , Lutz , C. : Pushing the EL envelope . In: IJCAI. ( 2005 ) 364 - 369

23. Eiter , T. , Gottlob , G.: On the complexity of propositional knowledge base revision, updates, and counterfactuals . In: PODS. ( 1992 ) 261 - 273

24. Katsuno , H. , Mendelzon , A.O. : On the difference between updating a knowledge base and revising it . In: KR. ( 1991 )

25. Giacomo , G.D. , Lenzerini , M. , Poggi , A. , Rosati , R.: On instance-level update and erasure in description logic ontologies . Journal Logic and Computation 19 ( 5 ) ( 2009 ) 745 - 770

26. Winslett , M. : Updating Logical Databases. Cambridge Tracts in Theor. Comp. Sci. ( 1990 )

27. Forbus , K.D.: Introducing actions into qualitative simulation . In: IJCAI . ( 1989 )

28. Borgida , A. : Language features for flexible handling of exceptions in information systems . ACM Transactions on Database Systems 10 ( 4 ) ( 1985 ) 565 - 603

29. Satoh , K. : Nonmonotonic reasoning by minimal belief revision . In: FGCS . ( 1988 )

30. Dalal , M. : Investigations into a theory of knowledge base revision . In: AAAI . ( 1988 ) 475 - 479