Previous works have shown that the AGM theory cannot be used as the basis for defining contraction operators for several ontology representation languages. In this paper, we examine the postulate of relevance which has been proposed in the belief revision literature as a more intuitive alternative to the AGM postulate of recovery. Even though relevance and recovery have been proven to be equivalent in the presence of the other AGM postulates in classical logics, we show that this is not true for nonclassical ones. Based on this fact, we are able to show that the relevance postulate is a very attractive alternative to recovery for ontology evolution, as it can be used to define contraction operators in all interesting ontology representation languages.
The field of ontology evolution is a relatively new research field which handles the process of modifying an ontology in response to a certain change in the domain or its conceptualization [FMK+08]. It has been argued [FP06] that ontology evolution can greatly benefit from advances in the related, and much more mature, field of belief revision (also referred to as belief change), which deals with the problem of modifying a Knowledge Base (KB) in response to new information [G¨ar92].
Belief revision studies the dynamics of epistemic states, and admits three main change operations: expansion, which deals with the addition of knowledge to a KB without taking any special provisions for maintaining consistency, revision which is similar to expansion, with the important difference that the result should be a consistent set of beliefs, and contraction, which is required when one wishes to consistently remove a sentence from their beliefs instead of adding one [AGM85]. Expansion is a straightforwardly definable operation, but revision and contraction cannot be defined in a unique way; in their seminal work [AGM85], Alchour´on, G¨ardenfors and Makinson proposed a set of rationality postulates that revision and contraction operators should satisfy, called the AGM postulates (per the authors’ initials), as well as certain results on them, collectively referred to as the AGM theory. Our work deals mainly with the operation of contraction; this decision is motivated by the fact that contraction is considered the most basic operation of the three [G¨ar92]. We also deal with expansion, which is a trivial operation, but dealing with revision is reserved for future work.
Even though the AGM theory is the dominating paradigm in the field of belief revision, its application to ontology evolution is problematic, because the AGM assumptions regarding the underlying logical formalism happen not to hold for the most common ontology representation formalisms [FPA05a]. In [FPA04], a generalized version of the AGM postulates for contraction was proposed to address this problem, but later work [FPA05b] showed that in many ontology representation languages, such as OWL 1.0 [DSB+04] and many Description Logics (DLs) [BCM+03], one cannot define a contraction operator satisfying the generalized postulates.
A further problem with the application of the AGM theory of contraction is related to one of the proposed postulates for contraction, namely the recovery postulate, which was heavily criticized [Han91] in the literature as non-intuitive. In [Mak87], the class of operators that satisfy all the AGM contraction postulates but recovery (withdrawal operators) was introduced, but it was noticed that such operators don’t comply with the Principle of Minimal Change, i.e., they may cause the elimination of more information than necessary during a removal. In another work [Han91], the relevance postulate was proposed as a more intuitive alternative to recovery, but was shown to be equivalent to the recovery postulate under the assumptions of the AGM theory, a result which is generally regarded as a negative one.
The starting point of this work is the observation that the relevance and the recovery postulates are not necessarily equivalent for representation formalisms that don’t satisfy the AGM assumptions [RW06]. Motivated by this result, we perform a systematic study of the applicability of the standard AGM postulates (with recovery), as well as the AGM postulates with relevance instead of recovery, in various ontology representation formalisms. The main conclusion of this study is the fact that the recovery postulate is not applicable for most such formalisms, but the relevance postulate can be used for all interesting ones. Therefore, the relevance postulate can be used as the basis for the definition of intuitive and rational contraction operations for ontology representation formalisms.
In the next section, we present some basic notions related to our work, namely the considered formal framework and an introduction to belief revision (including the AGM theory, the relevance postulate and the related results); in Section 3, we present various ontology representation formalisms and show that most of them are not compatible with the generalized AGM postulates for contraction; in Section 4, we present some results regarding the relevance postulate and show that it can be used to define contraction operations for most of the aforementioned ontology representation formalisms; finally, we conclude in Section 5. 2 2.1
In this paper, we will view a representation formalism in a very abstract way, i.e., as a generic logic !L , Cn", where L is a set containing all the formulas of the logic (language) and Cn is a function (consequence operator ) mapping sets of formulas to their consequences (also a set of formulas). The consequence operator is considered to be Tarskian i.e., to satisfy monotony (A ⊆ B implies Cn(A) ⊆ Cn(B)), idempotence (Cn(A) = Cn(Cn(A))) and inclusion (A ⊆ Cn(A)). 2.2
The AGM tion
The AGM theory focuses on Tarskian logics that satisfy certain intuitive properties such as compactness and deductiveness; we call such logics classical. Expansion (+) and contraction (−) were defined as operations between a belief set K ⊆ L (i.e., a set closed under logical consequence K = Cn(K)) and a sentence a ∈ L . As argued in [FPA04], several interesting logics are not classical, including most logics used for ontological representation; furthermore, for non-classical logics, we should be able to expand and contract sets of beliefs, rather than single sentences only, as there may be beliefs which are not expressible using a single formula [FPA04]. For this reason, a generalization was proposed, in which the underlying logical formalism can be any Tarskian logic, whereas expansion and contraction are defined as operations between belief sets (K ⊆ L , K = Cn(K)) and finite sets of formulas (A ⊆ L , A finite) [FPA04].
Given that the generalized AGM theory proposed in [FPA04] is a simple extension of the original one for a more general class of logics, and the fact that the focus of this paper is on non-classical logics, we will present the generalized theory only. The generalized version of expansion is uniquely defined (as in the original AGM theory) as K + A = Cn(K ∪ A). Generalized contraction can only be defined through a set of rationality postulates, which have been generalized as follows: (closure) K − A = Cn(K − A) (success) If A ! Cn(∅) then A ! K − A (inclusion) K − A ⊆ K (extensionality) If Cn(A) = Cn(B) then K − A = K − B (recovery) K ⊆ (K − A) + A
It is trivial to see that the generalized postulates are equivalent to the original ones (see [AGM85]) under the standard setting. The (generalized) AGM postulates restrict the result of a contraction to be a theory (closure). Since contraction is an operation that is used to remove knowledge from a KB, the result should not contain any new, previously unknown, information (inclusion); removal of information should occur only when necessary (vacuity). Moreover, contraction should return a new KB such that the contracted belief is no longer believed or implied (success). Finally, the result should be syntax-independent (extensionality) and should remove as little information from the KB as possible, in accordance with the Principle of Minimal Change (recovery).
As shown in [FPA04], there are several non-classical logics in which no contraction operation satisfying all the generalized AGM postulates can be defined. Here is a simple example:
Example 2.1: [FPA04] Consider the following simple logic !L , Cn": L = {a, b}
Cn(∅) = ∅
Cn(a) = {a}
Cn(b) = Cn(L ) = L It can be easily verified that this logic is Tarskian, but non-classical. Now consider the operation {b}−{a}; any of the four possible results of {b} −{ a} (namely: ∅, {a}, {b}, {a, b}) would violate either the success postulate or the recovery postulate. Therefore, it is not possible to define a contraction operator in !L , Cn" that would satisfy all AGM postulates.
Based on this observation, in [FPA04], a logic !L , Cn" was defined to be AGM-compliant iff for every K, A ⊆ L , there is at least one result K! = K − A satisfying all the AGM postulates. In the same paper, the properties that a logic should satisfy in order to be AGM-compliant were studied, and the most important result was the following: Theorem 2.2 [FPA04] A logic !L , Cn" is AGM-compliant iff for every K, A ⊆ L such that Cn(∅) ⊂ Cn(A) ⊂ Cn(K) there is a K! ⊆ L such that Cn(K!) ⊂ Cn(K) and K! + A = K.
The problem of non-AGM-compliance for some logics was shown to be caused by the interaction of the recovery with the rest of the postulates; in particular, it was shown that all Tarskian logics admit a withdrawal operator. 2.3
The AGM postulates specify the properties that a contraction operator should satisfy, but don’t tell us how such a contraction operator can be constructed. One of the main related results in the literature is that there is a number of different and intuitive methods for constructing contraction operators, which turn out to construct exactly the operators that satisfy the postulates. One of the main such construction methods, that is relevant with this paper, appeared in [AGM85] and is called partial meet contraction. In short, a partial meet contraction operator is defined as the intersection of some maximal subsets of K that do not imply A. Formally: Definition 2.3 (Remainder Set) [AGM85] The remainder set of K w.r.t. A, denoted by K ⊥ A ⊆ 2L , is a set such that X ∈ K ⊥ A iff: • X ⊆ K • A ! Cn(X) • if X ⊂ X! ⊆ K then A ⊆ Cn(X!)
A selection function for K ⊥ A(γ) is a function that returns some non-empty subset of K ⊥ A if K ⊥ A is not empty and {K} otherwise. The partial meet contraction is defined as the intersection of the elements chosen by γ: Definition 2.4 (Partial Meet Contraction) [AGM85] The partial meet contraction −γ is defined as K −γ A = ! γ(K ⊥ A)
The following representation theorem proves that the partial meet contraction and the AGM postulates for contraction are in fact equivalent: Representation Theorem 2.5 [AGM85] For classical logics, a contraction operation − satisfies the AGM postulates iff it is a partial meet contraction. 2.4
The recovery postulate captures the Principle of Minimal Change by requiring that, whenever some information is removed during a contraction, the subsequent re-addition of the contracted expression will restore (recover) the original KB. The intuition behind this interpretation of the Principle of Minimal Change was questioned in [Han91], and the relevance postulate was defined as an alternative:
(relevance) If β ∈ K \ K − A, then there is a set K! such that K − A ⊆ K! ⊆ K and A ! Cn(K!), but A ⊆ Cn(K! ∪ {β}).
The relevance postulate captures minimality by establishing that a formula β is allowed to be removed during a contraction only if it is somehow “helping” to infer A, i.e., there is some subset of K that doesn’t imply A, but would imply A if β was added. Even though relevance was proposed as an alternative to recovery, it was shown that they are, in fact, equivalent, in the AGM setting: Theorem 2.6 [Han91] Consider a contraction operation − in a classical logic that satisfies closure, success, inclusion, vacuity and extensionality. Then − satisfies recovery if and only if it satisfies relevance. 3
In this section we will briefly introduce some of the standard formalisms to represent ontologies on the web. Since their formal definitions are out of the scope of this paper, we will point to full definitions.
Each of these formalisms is proved not to be AGM-compliant which is a good reason to investigate possible alternatives for AGM-postulates. 3.1
RDF and RDFS are the standard languages to represent information about resources on the web. The information is represented in RDF by the means of RDF triples: subject, property, object. The set of RDF triples forms a RDF graph. The RDF graph is a directed graph where nodes represent subjects/objects and the arrows represent properties.
Formally we define three sets: U (the set of URI that uniquely identifies a resource), L (the set of literals) and B (an infinite set of blank nodes). An RDF triple is defined as (v1, v2, v3) where v1 ∈ U ∪ B, v2 ∈ U, v3 ∈ L ∪ U ∪ B and the RDF graph is simply a set of such triples. The semantics of RDF is formally described in [Hay04]. According to [GHM04] an RDF Graph K implies another RDF graph A (written K ! A or A ⊆ Cn(K)) iff there is a map µ from K to A that preserves literals and URIs i.e.: if v ∈ L ∪ U then v = µ(v).
From this definition of entailment we have that RDF is not AGM-compliant, since there is no possibility for G−A with G = {(v1, v2, v3)} and A = {(u, v2, v3)} with v1 ∈ B and v2, v3, u ∈ U.
RDFS is a semantic extension of RDF which provides mechanisms to better describe properties and relations between resources. The semantics of RDFS is also given in [Hay04] as G ! A iff there is a map from G to A to the RDFclosure 1 of A. RDFS is also not AGM-compliant. For the proof, just notice that if G = Cn({(a,sc, b), (b,sc, c)}) where sc is the RDFS property subclass, a, b, c ∈ U and A = {(a,sc, c)} then there is no X ⊂ G such that X = Cn(X) and X + A.
1see [GHM04] 3.2
A full definition of the syntax and the semantics of DLs are out of the scope of this paper (see [BCM+03] for an introduction of the subject). Briefly, though, a DL is formed by three disjoint sets of atomic symbols: concepts, roles and individuals. Complex concepts/roles are defined using constructors. Each DL defines its set of constructors and axiom types. For example, the logic ALC admits conjunction (A*B), complement (¬A) and existential restriction (∃R.C) as concept constructor and concept subsumption (A , B), individual assignment A(a) and role assignment (R(a, b)) as axiom types.
In [FPA05b] the authors proved a theorem that can be used to prove a big class of description logics are not AGM compliant. The following is an extension of this theorem in order for it to be applicable to the logics behind OWL 2.0: Theorem 3.3 Any DL !L , Cn" with the following properties is not AGMcompliant: • The DL admits at least two role names (R, S) and one concept name (A). • The DL admits at least one operator: value restriction (restricted or not), existential restriction (restricted or not), number restriction (qualified or not). • The DL admits any (or none) of the operator on concepts: conjunction, disjunction, complement, top, bottom and nominals. • The DL admits any (or none) of the properties: reflexive (local or not), irreflexive, antissimetric roles, negated role assertion and universal role. • The DL admits subsumption between concepts, subsumption between roles (complex or not) and it can accept disjoint roles as axiom types. 3.3
OWL 1 OWL is the standard language to represent ontologies on the web. The first version of OWL came in three flavors: OWL-lite, OWL-DL and OWL-full. The first two of them are based on well known description logics SHIF (D) and SHOIN (D) respectively [HPS04].
These logics are very expressive DLs that add inverse, transitive and function roles and concrete datatypes and role hierarchy to ALC and, in the case on SHOIN (D) also nominal and role number restriction. In spite of the big expressive power, entailment in both these logics is still decidable (the class of complexity for SHIF (D) is Exp-Time complete and for SHOIN (D) is NExp-Time complete).
In [FPA05b] these logics were proved not to be AGM-compliant due to the fact that they admit role hierarchy while not admitting any other role constructors: Theorem 3.4 [FPA05b] SHIF (D) and SHOIN (D) (the logics behind OWL 1 DL and OWL 1 lite) are not AGM compliant. 3.4
OWL 2 The new version of OWL, called OWL 2, is based on the description logic SHROIQ(D) [HKS06] which enhances the SHOIN (D) with disjoint roles, (local) reflexive, irreflexive and antissimetric roles, complex role inclusion and universal role. SHROIQ(D) is still decidable. Like SHOIN (D) and SHIF (D) , SHROIQ(D) is not AGM-compliant: Theorem 3.5 SHROIQ(D) is not AGM-compliant 3.5
OWL 2 profiles OWL 2 profiles (or fragments) [MGH+08] are a syntactic restrictions of OWL 2 that have better computational complexity. Although less expressive, each of these profiles are still very useful for a different class of applications. 3.5.1
OWL 2 EL OWL 2 EL is useful for ontologies that have a big amount of properties and classes. The logic behind this profile is the description logic called E L + +. In spite of its low computational complexity (reasoning tasks in this DL is polynomial), it is still expressive enough to represent a large class of ontologies on the web [BBL08].
The logic E L + + restricts OWL 2 by only accepting existential restriction ∃R.C, conjunction of concepts A * B, nominals ({a}), concrete datatypes, the top - and the bottom ⊥ as concept constructions and concept and role subsumption as axiom type. From theorem 3.3 we have that this logic is also not AGM-compliant: Theorem 3.6 The logic E L + + is not AGM-compliant. 3.5.2
OWL 2 QL OWL 2 QL is useful for ontologies that have a big number of instances and where query answering is the most important reasoning task. The logic behind this language is a DL from the DL-lite family [ACKZ09] called DL-liteR.
Although this logic restricts very much the use of constructors it still admits role hierarchy and existential restriction. Hence, it is also not AGM-compliant: Theorem 3.7 The logic DL-liteR is not AGM compliant. 3.5.3
OWL 2 RL OWL 2 RL was inspired in description logic programs [GHVD03] and is a useful tradeoff between complexity and expressive power. As in the case of the OWL 2 QL, the restrictions on this language doesn’t change the fact that it admit role hierarchy and existential restriction and, hence, it is not AGM-compliant:
In the last section we showed why the AGM-paradigm cannot be applied to most logics for representing ontologies on the web. These results suggests the need for a different set of rationality postulates for contraction. This new set of postulates should be compliant to these logics while keeping the intuition behind the AGM postulates. In this section we defend that one possible choice of postulates is the AGM postulates with recovery exchanged by the relevance postulate presented in section 3.
Relevance has the following advantages: it is well know in the literature [Han91, Han99, FH94], it is equivalent to recovery in classical logics (see theorem 2.6) and, as argued in section 2.4, it captures the intuition of minimality of change. However, there are still open questions about relevance: Is there some construction that characterizes this set of postulates? Which logic is compliant with relevance (plus the other AGM postulates)? In particular, which of the logics presented in section 3 are compliant with relevance? The main goal of this section is to answer these questions.
For classical logics the answer of the first question follows trivially from theorems 2.5 and 2.6: partial meet contraction. What is a little surprising is that this representation theorem, in fact, holds for every monotonic and compact logic.
Representation Theorem 4.1 2 Consider a monotonic an compact logic. An operation K − A satisfies the withdrawal postulates plus relevance iff K − A is a partial meet contraction.
Before answering the second question, let us precise the notion of relevancecompliance: Definition 4.2 (Relevance-compliance) A logic !L , Cn" is relevance-compliant iff for every K, A ⊆ L such that K is a belief set and A is finite, there is at least one K − A satisfying all the withdrawal postulates plus relevance.
Notice that, since we can construct partial meet in every compact logic, as a corollary of representation theorem 4.1 we have that every monotonic compact logic is relevance-compliant.
Corollary 4.3 Every monotonic and compact logic is relevance-compliant.
In order to answer the last question we will prove that all the logics from section 3 are compact. In fact, in general, it can be proved that every DL which is a subset of first order logic is compact: Theorem 4.4 Every DL which is a subset of first order logic is compact.
2This theorem is a generalization of the representation theorem presented in [RW06] and is a correction of a theorem presented in [FH94]
Since all the logics from section 3 are subsets of first order logic, we have that all of them are compact and, hence, relevance-compliant.
Corollary 4.5 F L0, E L, E L + +, DL-litecore, DL-liteR, DL-liteF , SHOIN (D) , SHIF (D) and SHROIQ(D) are all compact and hence relevance-compliant. 5
It has been argued [FP06] that ontology evolution will benefit from the incorporation and use of belief revision techniques and theories. Unfortunately, the most influential belief revision theory, the AGM theory [AGM85], as well as its generalization [FPA04], have been shown to be incompatible with many ontology representation formalisms [FPA05a]. Our proposal to address this problem is to use the more intuitive relevance postulate [Han91] as an alternative to recovery for such logics. This choice was motivated by two main factors: first, because recovery has always been the most controversial postulate whereas recovery is generally considered a more intuitive formalization of the Principle of Minimal Change [Han91], and, second, because the replacement of recovery with relevance allows us to define contraction operators for all interesting semantic web languages, as was shown in this paper.
Most interestingly, the two postulates are equivalent in the original setting considered by AGM in the presence of the other postulates, but this equivalence breaks when considering non-classical logics [RW06]. In our paper we determined the ontology representation languages which are compatible with the relevance and the recovery postulate respectively. The main conclusion of this work is that the proposed set of postulates (i.e., with relevance instead of recovery) is far more adequate than the original AGM set as far as ontology evolution is concerned, mainly for the following reasons: • The proposed postulates are compatible will all compact logics, and all the interesting ontology representation formalisms are based on compact logics. • Relevance captures the Principle of Minimal Change in a manner different (some would say better [Han91]) than the controversial recovery postulate. • The proposed set is equivalent to partial meet contraction for all compact logics (thus, for all interesting ontology representation formalisms); this gives us a construction method for contraction operators, which would not be available if the original AGM set was used. • The proposed set incorporates all the non-controversial AGM postulates (closure, success, inclusion, vacuity, extensionality). • The proposed set of postulates is equivalent to the AGM set of postulates in classical logics.
As future work we intend to further investigate the relevance postulate and establish a more accurate account of its relation with recovery. Moreover, we plan to consider the relation of the AGM revision postulates with non-classical logics, including logics used for representing ontologies.
language
RDF
RDFS OWL 2 DL (SHROIQ(D) ) OWL 1 DL (SHOIN (D) ) OWL 1 lite (SHIF (D) )
OWL 2 EL (E L + +) OWL 2 QL (DL-liteR)
OWL 2 RL
AGM-compliance no (theorem 3.1) no (theorem 3.2) no (theorem 3.5) no [FPA05b] no [FPA05b] no (theorem 3.6) no (theorem 3.7) no (theorem 3.8) relevance-compliance yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) yes (theorem 3.3) [AGM85] [BBL08] [DSB+04] [FH94]
Mike Dean, Gus Schreiber, Sean Bechhofer, Frank van Harmelen, Jim Hendler, Ian Horrocks, Deborah L. McGuinness, Peter F. PatelSchneider, and Lynn Andrea Stein. OWL web onotology language reference. W3C Recomendation, 2004.
Andr´e Fuhrmann and Sven Ove Hansson. A survey of multiple contractions. Journal of Logic, Language and Information, 3(1):39– 75, January 1994. [FP06] [FPA04] [FPA05a] [FPA05b] [G¨ar92] [GHM04]
Giorgos Flouris and Dimitris Plexousakis. Evolution and belief change. In Grigoris Antoniou, George Potamias, Costas Spyropoulos, and Dimitris Plexousakis, editors, Proceedings of the 4th Hellenic Conference on Artificial Intelligence (SETN-06), volume 3955, pages 486–489. Springer-Verlag, 2006.
Giorgos Flouris, Dimitris Plexousakis, and Grigoris Antoniou. Generalizing the AGM postulates: preliminary results and applications. In James P. Delgrande and Torsten Schaub, editors, Proceedings of the 10th International Workshop on Non-Monotonic Reasoning 2004 (NMR-04), pages 171–179, Westin Whistler Resort and Spa, Whistler BC, Canada, June 6-8 2004.
Giorgos Flouris, Dimitris Plexousakis, and Grigoris Antoniou. On applying the AGM theory to DLs and OWL. In Y. Gil et al., editor, ISWC 2005, number 3729 in LNCS, pages 353–367. SpringerVerlang, 2005.
Giorgos Flouris, Dimitris Plexousakis, and Grigoris Antoniou. Updating description logics using the AGM theory. In Proceedings of the 7th International Symposium on Logical Formalizations of Commonsense Reasoning, Corfu, Greece, May 2005.
Peter G¨ardenfors. Belief Revision: An Introduction. Cambridge University Press, 1992.
Claudio Gutierrez, Carlos Hurtado, and Alberto O. Mendelzon. Foundations of semantic web databases. In PODS ’04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 95–106, New York, NY, USA, 2004. ACM Press. [GHVD03] Benjamin N. Grosof, Ian Horrocks, Raphael Volz, and Stefan Decker. Description logic programs: combining logic programs with description logic. In WWW ’03: Proceedings of the 12th international conference on World Wide Web, pages 48–57, New York, NY, USA, 2003. ACM Press. [Han91] [Han99]
Sven Ove Hansson. Belief contraction without recovery. Studia Logica, 50(2):251–260, 1991.
Sven Ove Hansson. A Textbook of Belief Dynamics. Theory Change and Database Updating. Kluwer Academic, 1999.