When modeling an ontology, one very often wants to add new information and keep the resulting ontology consistent. Belief Revision deals with the problem of consistently adding new formulas to a knowledge base. In this paper, we present some steps towards applying belief revision methods to ontologies based on description logics. We depart from the well known AGM-paradigm and show how it can be adapted in order to be applied to description logics.
Recently, with the advent of the Semantic Web [BLHL01], there has been a growing interest in the use of ontologies for representing domain knowledge. When ontologies evolve and are re-used in different contexts, inconsistency may arise.
In [HvHtT05], at least four different reasons for the presence of inconsistency in ontologies are described: mis-representation of defaults (stating that birds can fly and then that penguins are birds and cannot fly), polisemy (words with different meanings), problems of translation between different formalism, and multiple sources.
There are different approaches concerning how to deal with inconsistencies. In [HvHH+05], four different approaches are described under a unifying framework. The first, consistent evolution, consists in preventing the introduction of inconsistency in a consistent ontology. The second, repairing, consists in making an inconsistent ontology consistent. The third reasoning with inconsistency does not change the inconsistent ontology, but tries to derive meaningful conclusions from it. Finally, the fourth approach, versioning, keeps track of changes and compatibility issues between different versions of ontologies.
In this paper, we study the applicability of Belief Revision methods to ontologies. Belief Revision [G¨ar88,Han99] deals with the problem of restoring the consistence of a knowledge base after the introduction of new, possibly inconsistent knowledge. We note that, from the four approaches above, only the last one (versioning) is not addressed by the Belief Revision literature. Rott has proposed in [Rot01] the classification of methods for Belief Revision into vertical or horizontal. In the vertical mode, revision is reduced to the simple addition of the new formula to the knowledge base, while some non-classical notion of inference is used to answer queries. The inference machinery is responsible for dealing with the inconsistency, as in the third approach above. On the other hand, the horizontal mode of belief revision relies on classical notions of inference, but uses sophisticated operations of revision to keep or restore the consistency in the knowledge base. This addresses the first two approaches (consistent evolution and repairing) and will be followed in the rest of the paper. The most well known paradigm for horizontal belief revision is known as the AGM theory, due to the initial of the names of the authors of the seminal paper [AGM85].
Although our results are more general, we have in mind the revision of ontologies described in OWL [MvH04]. OWL has been a W3C recommendation since 2004 and is now seen as the standard language for representing ontologies. It was defined as three different sub-languages, with increasing expressivity (and complexity for reasoning): OWL-Lite, OWL-DL and OWL-Full. We will concentrate on the first two, since there is no complete reasoner for OWL-Full. It was already shown that OWL-Lite and OWL-DL are equivalent to the description logics SHIF (D) and SHOIN (D) [HPS04], so we will concentrate our examples on description logics.
We will first briefly review the AGM-theory. Then, in Section 3 we will present some results from [FPA04,FPA05] which show that in the description logics behind OWL there is no operation possible conforming to the AGM-theory. We then show that the AGM-theory can be slightly adapted so that AGM-like revision can be applied to SHIF (D) and SHOIN (D).
In the rest of this paper, we call consequence operation any total function taking sets of formulas to sets of formulas. We use Cn to denote consequence operators. A Tarskian consequence operator is an operator Cn that satisfies monotony (A ⊆ B ⇒ Cn(A) ⊆ Cn(B)), inclusion (A ⊆ Cn(A)) and idempotency or iteration (Cn(Cn(A)) = Cn(A)). 2
AGM
In this section, we briefly introduce the AGM paradigm for belief change. For a more complete exposition, the reader is referred to [G¨ar88],[GR95] or [Han99].
In the AGM model, belief states are represented by theories (possibly together with some selection mechanism), that is, sets of formulas K such that Cn(K) = K.These theories are called belief sets. The consequence operator Cn is assumed to be tarskian, compact, satisfy the deduction theorem and supraclassicality. We will sometimes refer to these properties as the AGM-assumptions.
In AGM theory, there are three operations that can be performed on belief sets: contraction, expansion and revision. Contraction consists of giving up (at least) as many beliefs as it is needed so that the new belief set does not imply (and so, does not contain) a specified sentence. Expansion consists of adding new information to the belief set. If the old and the new information are not logically compatible, then the new belief state after expansion will be inconsistent. Revision is consistent incorporation of new information, i.e., if the input sentence is consistent, then the new belief set will be consistent (even if the old belief set was not). If necessary, consistency is obtained by deleting parts of the original belief set. 2.1
Of the three AGM operations, only expansion is characterised in a unique way. When a belief set K is expanded with a proposition ϕ, the resulting set K + ϕ is obtained by simply adding the new belief to the old belief set and taking the logical consequences of the resulting set:
K + ϕ = Cn(K ∪ {ϕ}).
The name expansion is justified by the fact that K ⊆ K + ϕ.
Contraction and revision operations are not directly defined, but constrained by a set of rationality postulates.1 For the contraction of a belief set K in relation to a sentence ϕ (denoted K − ϕ), six basic postulates are given [AGM85] (` is the consequence relation associated with Cn): (K-1) K − ϕ is a belief set (closure) (K-2) K − ϕ ⊆ K (inclusion) (K-3) If ϕ 6∈ K, then K − ϕ = K (vacuity) (K-4) If not ` ϕ, then ϕ 6∈ K − ϕ (success) (K-5) K ⊆ (K − ϕ) + ϕ (recovery) (K-6) If ` ϕ ↔ ψ, then K − ϕ = K − ψ (extensionality)
These postulates are supposed to capture the intuition behind the operation of giving up a belief in a rational way. Postulate (K-1) says that the result of contracting a belief set by a formula should again be a belief set. The next postulate assures that in an operation of contraction no new formulas are added to the initial belief set. If the formula to be contracted is not an element of the initial belief set, then by (K-3) nothing changes. Postulate (K-4) says that unless the sentence to be contracted is logically valid (and hence, an element of every theory), it is not an element of the resulting belief set. The recovery postulate (K-5) is the most controversial one [Mak87]. It says that a contraction should be recoverable, that is, that the original belief set should be recovered by expanding by the formula that was contracted. The last postulate assures that contraction by logically equivalent sentences produces the same output. 1 Originally, expansion was also defined by means of a set of postulates, but it can be completely determined by the postulates.
Contraction and revision can be defined in terms of each other via the Harper or the Levi identities [G¨ar88]. Revising with a belief ϕ corresponds to contracting by the negation of ϕ and then expanding with ϕ:
K ∗ ϕ = (K − ¬ϕ) + ϕ (Levi identity) The thus defined operator ∗ will be called the revision operator associated with the contraction operator −. Analogously, the following identity defines a contraction operator associated with a revision operator:
K − ϕ = (K ∗ ¬ϕ) ∩ K (Harper identity) 2.2
The postulates above do not determine unique contraction or revision operators for a belief set, but only restrict the set of possible such operators. In [AGM85] a particular construction is presented that, given a belief set and an input belief, returns the result of contracting (or revising) the given set by the input.
This construction makes use of the concept of a remainder set, the set of maximal subsets of a given set not implying a given sentence. Formally: Definition 1. [AM82] Let X be a set of formulas and α a formula. The remainder set X⊥α of X and α is defined as follows. For any set Y , Y ∈ X⊥α if and only if: – Y ⊆ X – Y 6` α – For all Y 0 such that Y ⊂ Y 0 ⊆ X, Y 0 ` α.
Observation 1 [AGM85] If K is closed under logical deduction, then so are the elements of K⊥α.
If X ⊆ K and β ∈/ Cn(X) then there is a X0 such that X ⊆ X0inK⊥β.
It is assumed that there is some way of picking out the best (in some sense) elements of a remainder set. This is formalised by means of a selection function: Definition 2. [AGM85] A selection function for X is a function γ such that: – If X ⊥ α 6= ∅, then ∅ =6 γ(X ⊥ α) ⊆ X ⊥ α. – Otherwise, γ(X ⊥ α) = {X}.
A contraction is obtained by taking the intersection of the best subsets of K that do not imply α: 2 This property follows from compactness and the axiom of choice. Definition 3. [AGM85] For any sentence α, the operation of partial meet contraction over a belief set K determined by the selection function γ is given by:
K −γ α = T γ(K ⊥ α)
Partial meet revision is obtained from partial meet contraction and expansion by means of the Levi identity: Definition 4. Let K be a belief set and γ a selection function. For any sentence α, the operation of partial meet revision over K determined by γ is given by: K ∗γ α = Cn(T γ(K ⊥ α) ∪ {α})
In their paper [AGM85], Alchourr´on, G¨ardenfors and Makinson show that partial meet constructions bear a very special relation to the contraction and revision postulates. They prove the following representation results: Theorem 1. [AGM85] Let − be a function which, given a formula α, takes a belief set K into a new belief set K − α. For every theory K, − is a partial meet contraction operation over K if and only if − satisfies the basic postulates ((K-1)-(K-6)) for contraction. 3
In this section, we show that not every logic admits a contraction operation satisfying the AGM postulates. We show some results presented in [FPA04,FPA05] characterising the logics that admit such operations and then propose an alternative set of postulates that can be used with a wider family of logics.
Although the AGM theory was formulated having in mind some general notion of logic, some assumptions were made which limit the kind of logic that can be really used. In their work [FPA04], Flouris, Plexousakis and Antoniou have shown that not even all Tarskian logics admit a contraction operation satisfying the six AGM postulates. As an example, they present a logic containing only two formulas, a and b and with a consequence operator as follows: C(∅) = ∅, C({a}) = C({a, b}) = {a, b} and C{b} = {b}. It is easy to see that if we try to contract b from {a, b}, because of the success postulate, the result must be ∅. But then, the recovery postulate is not satisfied.
Flouris, Plexousakis and Antoniou define a logic to be AGM-compliant if it admits a contraction operation satisfying the six AGM postulates. They have given a condition to test for AGM-compliance: Definition 5. [FPA04] A logic is called decomposable if and only if for all sets of formula A, B, such that Cn(∅) ⊂ Cn(B) ⊂ Cn(A), there exists a set of formulas Cn such that Cn(C) ⊂ Cn(A) and Cn(A) = Cn(B ∪ C). Theorem 2. [FPA04] A logic is AGM-compliant iff it is decomposable.
The logic in the example above is not decomposable (take A = {a} and B = {b}). But a more interesting negative example for us is the description logic SHOIN (D), which is shown not to be decomposable. This means that the AGM theory cannot be directly applied to this logic, which is the basis for OWL. An example of a logic which is AGM-compliant is the logic ALC 3
We propose here an alternative approach. Instead of accepting the six postulates as they are, we note that the problem of AGM-compliance is due to the presence of the recovery postulate. If we consider only the other five postulates, then every logic admits a contraction operation satisfying them.
The recovery postulate has been criticised in the literature [Mak87,Fer01] as being the most polemic and less intuitive. The idea behind the postulate is to guarantee some kind of minimal change, i.e., that as much information as possible will be preserved. If we want to avoid the recovery postulate, we need some other condition to preserve information.
In [Han89], Hansson has proposed that minimal change could be captured by the following intuition: in a contraction operation, when a belief is removed, it must contribute somehow for the derivation of the contracted belief, that is, no belief is removed for no reason. This idea is formalised by the postulate: (relevance) If β ∈ K and β 6∈ K − α, then there is a set K0 such that K − α ⊆ K0 ⊆ K and that α 6∈ Cn(K0), but α ∈ Cn(K0 ∪ {β}).
For logics which satisfy the AGM-assumptions, Fuhrmann and Hansson have shown that the relevance postulate is stronger than recovery, but on the presence of the other postulates, they are equivalent: Observation 3 [FH94] Let K be a belief set and − a contraction operator for K. Then: 1. If − satisfies relevance, then it satisfies recovery. 2. If − satisfies closure, inclusion, vacuity and recovery, then it satisfies relevance.
The result above makes the relevance postulate a good candidate to substitute recovery. Although the new set of postulates is equivalent to the original one in classical logic, this is not the case for any logic, as we show next.
Flouris, Plexousakis and Antoniou have already shown that the only problematic postulate is indeed recovery: Theorem 3. [FPA04] Every tarskian logic admits a contraction operator that satisfies the AGM postulates without recovery.
As we have seen in the example in the beginning of this section, there are indeed tarskian logics where no contraction with recovery is possible. But it is not difficult to see that relevance does not present this problem: 3 provided it is equipped with infinite roles and empty ABox, as shown in [Flo06]. Theorem 4. Every tarskian logic admits a contraction operator that satisfies the AGM postulates with relevance instead of recovery.
Proof. Take for example the construction K − α = T γ(K⊥α), where γ is a selection function. It is easy to show, based on the proof for classical logic found in [G¨ar88], that it satisfies the postulates (K-1)-(K-4) and (K-6) for any tarskian logic. We only have to show that it also satisfies the relevance postulate. In the limit case where α is a tautology, K⊥α is empty and K −α = K, so the postulate is trivially satisfied. If K⊥α is not empty, take any K0 ∈ γ(K⊥α) and β ∈ K and β 6∈ K − α. By the definition of K − α and remainder sets, we have that K − α ⊆ K0 ⊆ K and that α 6∈ Cn(K0), but α ∈ Cn(K0 ∪ {β}).
We can now prove the following representation theorem: Theorem 5. For every belief set K closed under a tarskian logical consequence, − is a partial meet contraction operation over K if and only if − satisfies the postulates (K-1)-(K-4), (K-6) and (relevance).
Proof. One side of the implication follows from the proof of theorem 4, namely that every partial meet contraction satisfies the six postulates.
To see that every operator − satisfying the six postulates can be constructed as a partial meet contraction, just define the selection function γ as γ(K⊥α) = {K} when K⊥α = ∅ and γ(K⊥α) = {X ∈ K⊥α : K − α ⊆ X} otherwise.
From extensionality it follows that ` α ↔ β, then K − α = K − β, so the function γ is well defined. Moreover from success, inclusion and the upper bound property (Observation 2), it follows that if K⊥α 6= ∅, then γ(K⊥α) 6= ∅, i.e., γ is a selection function.
To prove that K − α = T γ(K⊥α) we must split the problem in two. First suppose that α ∈ Cn(∅) it follows by definition that K − α = T γ(K⊥α) = {K}. Now suppose that α ∈/ Cn(∅), we have by the definition of γ that K − α ⊆ T γ(K⊥α). To prove that T γ(K⊥α) ⊆ K − α we will prove that if β ∈/ K − α then β ∈/ T γ(K⊥α). If β ∈/ K then (by definition) β ∈/ T γ(K⊥α), so let us suppose that β ∈ K. By relevance, we have that there is a K0 such that K − α ⊆ K0 ⊆ K, α ∈/ Cn(K0), but α ∈ Cn(K0 ∪ {β}). By the upper bound property we have that there is K00 such that K0 ⊆ K00 ∈ K⊥α, but it is easy to see that β ∈/ K00 (otherwise we would have α ∈ Cn(K00)). It follows from K − α ⊆ K0 ⊆ K00 that K00 ∈ γ(K⊥α) and we conclude that β ∈/ T γ(K⊥α) 4
As we have seen in the previous section, there are logics which are not AGMcompliant, but for which a contraction operator can be constructed which satisfies the AGM postulates with recovery substituted by relevance. We start this section with an example of a simple logic with these characteristics. Example 1. Consider a description logic L with a language containing only two roles R and S, a single concept A, the constructor ∀ and the connective v. The set of tautologies in this logic is given by:
Γ = {R v R, S v S, A v A, ∀R.A ⊆ ∀R.A, ∀S.A v ∀S.A} With this, we can define the whole language:
L = {R v S, S v R, ∀R.A v ∀S.A, ∀S.A v ∀R.A} ∪ Γ In this logic, we have that : (1) (2) (3) (4) (5)
Cn({R v S}) = {R v S, ∀R.A v ∀S.A} ∪ Γ
Let K = Cn({R v S, ∀R.A v ∀S.A}). By inclusion, success, and closure, we have that:
K − (∀R.A v ∀S.A) = Cn(∅) = Γ Note that recovery is not satisfied, since:
Cn(K − (∀R.A v ∀S.A) ∪ {∀R.A v ∀S.A}) = {∀R.A v ∀S.A} ∪ Γ On the other hand, to see that the relevance postulate is satisfied, let K0 = Γ and consider the two options for β: R v S or ∀R.A v ∀S.A. In both cases, ∀R.A v ∀S.A is in Cn(K0 ∪ β).
Actually, Flouris, Plexousakis and Antoniou have shown the following result: Theorem 6. [FPA05] Any description logic which admits: – At least two role names and one concept name – At least one of the operators ∀, ∃, (≥n), (≤n) for some n – Any (or none) of the operators ¬, t, u, −, ⊥, >, {...} – Only the connective v applicable to both concept and roles is not AGM-compliant.
As the theorem above shows, most expressive description logics are not AGM-compliant. We are particularly interested in the logics SHIF (D) and SHOIN (D), which are the underlying logics of OWL-Lite and OWL-DL. It follows from the theorem above, that these two logics are not AGM-compliant. What happens when we substitute the recovery postulate for relevance? The only requirements for the existence of a contraction operator is a tarskian consequence operation and compactness. So it follows that: Corollary 1. There exists a contraction operation for the logics SHIF (D) and SHOIN (D) satisfying the AGM postulates with relevance instead of recovery.
In [FPA06], Flouris, Plexousakis and Antoniou have also proposed substituting the recovery postulate for guaranteeing the existence of contraction operators. They stated that any candidate substitute for recovery should satisfy two properties: 1. Existence: There should exist a contraction operator satisfying the new set of postulates in any logic. 2. AGM-Rationality: For logics which are AGM-compliant, the two sets of postulates should be equivalent.
In their paper, they formulate the following candidate to substitute recovery4: (K-5’) If (K − α) + α ⊂ Cn(Y ∪ {α}) for some Y ⊆ K, then Cn(∅) ⊂ Cn({α}) ⊆ Cn(Y ).
The intuition behind this postulate is that instead of requiring that (K − α) + α is equal to K, the resulting set is only required to be maximal (thus preserving as much information as possible), in the sense that, if there was some subset Y of K that when expanded by α would give a “larger” set than (K − α), the closure of this Y would necessarily contain α and hence not be suitable as a result of contraction by α.
Flouris, Plexousakis and Antoniou have shown in [FPA06] that although this postulate satisfies the requirement of AGM-Rationality, it does not satisfy Existence.
On the other hand, we have shown that relevance satisfies Existence in Theorem 4. Unfortunately we were not able to prove AGM-Rationality (we plan to establish whether it holds or not in future work). However, from Observation 3, it follows that in any logic satisfying the AGM-assumptions, the postulates with relevance in place of recovery are equivalent to the original ones. This is a weaker result because every logic that satisfies AGM-assumptions also satisfies AGM-compliance, but the opposite is not true in general.
In [Fuh97], the AGM-postulates were generalised so that the contraction on belief sets could be applied to remove sets of formulas instead of just a single formula. For this purpose, Fuhrmann proposed two kinds of contraction: package contraction (where every formula on the set should be contracted) and choice contraction (where at least one formula of the set should be contracted). For each of these contractions he proposed a different generalisation of the postulates success, extensionality, inclusion and relevance. Furthermore he proved that the postulates of closure and vacuity follow from the others. Our approach can be seen as a particular case of his contractions, when we consider only contraction by singletons. 5
In this paper we presented the first steps towards a theory of belief revision which is applicable to ontologies. We have shown that although the AGM postulates are not compatible with the description logics behind OWL, with a slight generalisation of the recovery postulate, the theory can be applied. 4 The formulation in [FPA06] is slightly different, as they are dealing with contractions by multiple sentences.
Previous work by Flouris, Plexousakis and Antoniou [FPA06] established two desiderata for a candidate substitute for recovery: Existence and AGMRationality. They proposed a postulate which satisfies AGM-Rationality, but does not satisfy Existence. In particular, the postulate does not help with the logics in which we are interested (SHIF (D) and SHOIN (D)). The postulate which we use (relevance), satisfies Existence. In particular, it is good for the revision of ontologies described in OWL-Lite and OWL-DL. On the other hand, we do not know yet whether it satisfies AGM-Rationality.
Future work includes a similar study of theories for belief revision which make use of finite bases instead of logically closed sets. This step is essential if one wants to implement tools to revise inconsistent ontologies.
Acknowledgements: The first author was supported by grants from CNPq and FAPESP. The second author is partially supported by CNPq grant 304486/20043. This work started during CNPq project 550222/2003-0 and is currently being developed under FAPESP project 2004/14107-2.