This paper presents an ontology reviser plug-in for Protege. The plug-in implements several belief base contraction and revision operations for expressive Description Logics. The operations can be selected by choosing the desired properties of the outcome from a menu. 1 http://www.w3.org/2004/OWL/
It has been argued that ontologies are necessary for the development of the semantic web [BLHL01]. In the web context, the role of ontologies is to give a formal representation for conceptual knowledge. For this reason in 2004 the W3C 1 has adopted an ontology language (OWL) as web standard. OWL comes in three avors: OWL-lite, OWL-DL and OWL-full. The latter two of them have their semantics based on the well known Description Logics (DLs) SHIF (D) and SHOIN (D) respectively [Hor03].
Because knowledge in the web is not static the dynamic of ontologies must be studied also. The study of ontology dynamic is the main goal of a growing sub- eld of the knowledge representation called ontology evolution (see [HS04] for a good overview).
One important approach to deal with knowledge base (KB) dynamics is belief revision. In belief revision three operations are de ned: expansion (B + ), contraction (B ) and revision (B ). Expansion simply adds a new sentence to the KB, contraction removes a sentence from the consequences of the KB and revision adds a new sentence to the KB maintaining the consistency. Contraction and revision are de ned by sets of rationality postulates (postulates that the operation must satisfy). An important result in belief revision is the equivalence between a set of rationality postulates and a speci c construction for an operation. This is result is called the representation theorem for the operation and the construction. The most in uential work in the belief revision eld [AGM85] proved that a set of rationality postulates for contraction/revision is equivalent to three distinct constructions: partial meet contraction/revision, safe contraction/revision and epistemic entrenchment. The framework became known as the AGM paradigm.
In the past few years some authors have tried to apply belief revision techniques in description logics. In [Flo06] the author proved that AGM paradigm can not be applied to SHIF (D) and SHOIN (D) . In [FPA06,RW06] the authors presented two di erent ways to change the AGM paradigm so that it can be used with SHIF (D) and SHOIN (D) . Both works deal with belief sets (logically closed sets). Belief sets are usually in nite which makes the problem computationally impractical. The sub eld of belief revision called belief base revision deals with the dynamic of belief bases, which are simply sets of sentences (not necessarily closed by logical consequence). [Han97b] presents constructions and postulates for belief base contraction and revision. The constructions for contraction can be applied to the logics we are interested in, as shown in [HW02]. However, revision can not be directly applied because it assumes the logic to be closed under negation. For this reason, in [RW07,RW08] the authors presented constructions and postulates for belief base revision that are compliant to SHIF (D) and SHOIN (D) .
In this work we are going to present an ontology reviser that implements the operations presented in [RW08]. The program is a plug-in for the ontology editor Protege 4 2. The implementation uses the OWL API 3 and the OWL DL reasoner Pellet 4.
In the following we are going to use Greek lower case letters ; ; : : : for sentences, the upper case letter B possibly with a subscript B1; B2; : : : for sets of sentences (belief bases), upper case letter words OW L; BIRD; : : : for concepts in a DL and lower case letter words tweety; hut; : : : for individuals in a DL.
In the next section, we are going to show an example to explain the importance of some postulates for revision. Section 3 will sum up the revision operators that were implemented. In Section 4 we will brie y explain the constructions that are equivalent to these operations. In the last two sections we are going to explain how the constructions were implemented and suggest some future work. Screenshots of the plug-in can be found in the last pages of this paper. 2
Suppose we are developing an ontology and we begin to add axioms to it. First we want to state that there is an owl called \Huh", that owls are birds and that birds y. As we are writing about birds we think our knowledge base should have knowledge about penguins also. We write that penguins are birds and we end up with the following ontology which will be called B: 2 http://protege.stanford.edu/ 3 http://owlapi.sourceforge.net/ 4 http://pellet.owldl.com/
Although not explicitly written in our ontology, we can infer that penguins y. This is because every model that satis es the axioms P EN GU IN v BIRD and BIRD v F LY should also satisfy the axiom P EN GU IN v F LY . But we know that penguins don't y and suppose we want to make the revision B (P EN GU IN v :F LY ). What should be the result of this revision?
Earlier we said that a revision should add a sentence , in this case P EN GU IN v :F LY , to a knowledge base, in this case B. Hence, we must have that 2 B . This is the rst postulate for the revision (success).
(Success)
2 B
The second thing we said about revision is that it should maintain the consistency. The second postulate for revision, which is called consistency, states precisely that B must be consistent.
(Consistency) B
is consistent
However, we have not de ned what consistency is. In DLs there are two di erent notions of consistency. The rst one states that an ontology B is inconsistent if it has no model. In other words, there is no domain set 6= ; that satis es all the axioms. This notion of consistency is closer to classical consistency because it trivializes the base, any sentence can be inferred from an inconsistent B. The second notion of consistency states that, if a knowledge base B is inconsistent, there is some concept in B that is necessarily empty. In this work we will follow [FHP+06] and call this second notion coherence and use the word consistency only for the case that B has no model.
Let us go back to our example. We have that penguins are birds and that birds y and we want to add that penguins don't y. If we add this sentence, our ontology would still have a model, but the concept P EN GU IN can be inferred to be empty. Hence, the resulting ontology is consistent, but incoherent. One may argue that incoherences are not errors. However, since the concept penguin was explicitly mentioned, the fact that it must be empty normally indicates that there is a modeling error. If we want to deal with this kind of error we must change our second postulate to a coherence postulate.
(Coherence) B
is coherent
Suppose that we meet our well know penguin \Tweety" and we add the sentence tweety 2 P EN GU IN to our ontology. Now if we add P EN GU IN v :F LY to our ontology it will have an inconsistency.
Until now we have stated that B must satisfy success and consistency or coherence. However, if these are the only postulates for revision, the revision B (P EN GU IN v :F LY ) could be just the single sentence ontology:
P EN GU IN v :F LY
This ontology is consistent and it contains . So it satis es success and consistency. Notice, however, that the fact that \Huh" is a owl (huh 2 OW L) and that owls are birds (OW L v BIRD) are not related to the fact that the original ontology is inconsistent with the sentence added. We would like to maintain this kind of sentences. We need a postulate which states that sentences that are not related, in some sense, with the inconsistency should be kept in the revision. We need a minimality postulate. One postulate that guaranties this kind of minimality is core-retainment :
(Core-retainment) If 2 B n B then there is B0 B [ f g such that B0 is consistent/coherent and B0 [ f g is not consistent/coherent.
With this postulate we are forced to keep at least huh 2 OW L and OW L v BIRD from the old ontology. All other sentences are relevant to infer the inconsistency and, hence, may be removed.
Now, assume that we have that penguins are birds, \Tweety" is a penguin, penguins don't y, birds y and that in order to y one must have exactly two wings as the following ontology is showing:
P EN GU IN v :F LY tweety 2 P EN GU IN
Suppose now that we nd out that \Tweety" has only one wing and we want to add it to this ontology ( is now tweety 2 haveW ing 1 uhaveW ing 1). In this case, the sentences BIRD v F LY and F LY v haveW ing 2 uhaveW ing 2 can be removed. What is a little bit strange in this example is that the second sentence is only relevant to infer inconsistency together with the sentence P EN GU IN v :F LY . The relevance postulate tries to capture this intuition.
(Relevance) If 2 B n B then there is B B0 B [ f g such that B0 is consistent/coherent and B0 [ f g is not consistent/coherent.
Belief base revision is the study of the dynamics of belief bases. A belief base is simply a set of sentences. In base revision eld three operations for belief bases are de ned: contraction, expansion and revision. Expansion is de ned as B + = B [ f g. Contraction and revision are not uniquely de ned, but are constrained by sets of postulates. In this work we are going the focus in the postulates for revision. Postulates for revision do not tell us how to construct a revision. Constructions for revision are based on constructions for contraction and they will be informally presented in the next section.
We are going to show the postulates for base revision presented in [RW08]. In [RW08] six operations for revision were presented. Each of them can be de ned for coherence and for consequence (twelve operations). Most of the postulates used to de ne these operations were already presented in the previous section and the rest of them will be presented now.
Until now we have that a revision should add a new sentence (success), in a consistent way (consistency/coherence) and should keep sentences unrelated with the inconsistency (core-retainment/relevance). These postulates do not guaranty that we can not add irrelevant sentences. We need a postulate that guaranties that no irrelevant sentences are added to the base: (Inclusion) B
B +
Furthermore, notice that, if is itself inconsistent/incoherent, then success and consistency can not be satis ed at the same time. We need weaker versions of them: (Weak Success) If is consistent/coherent then 2 B (Weak Consistency) If tent/coherent is consistent/coherent then B is consis
For now on success will be called strong success and consistency will be called strong consistency.
We will call kernel revision the revision operations that satisfy core-retainment. Thus, kernel revision with strong success for consistency is characterized by the postulates: strong success, weak consistency, inclusion, core-retainment and a postulate named pre-expansion.
(Pre-expansion) B +
= B
The revision operations that satisfy relevance will be called partial meet revision and they also satisfy inclusion and pre-expansion. We can de ne the following revision operations: { kernel revision with strong success for consistency { kernel revision with strong success for coherence { kernel revision with weak success for consistency { kernel revision with weak success for coherence { partial meet revision with strong success for consistency { partial meet revision with strong success for coherence { partial meet revision with weak success for consistency { partial meet revision with weak success for coherence
The other four operations showed in [RW08] are not real revision operations, they are called semi-revisions (B? ). A semi-revision [Han97a] was proposed to be used when one does not want to give the input sentence a higher priority. For this reason semi-revisions do not satisfy success. Kernel semi-revision for DLs were studied in [HWKP06]. A kernel semi-revision for consistency is characterized by the postulates: inclusion, core-retainment, strong consistency, pre-expansion and a postulate called internal exchange.
(Internal Exchange) If ; 2 B then B? = B?
Every semi-revision satis es internal exchange, inclusion and pre-expansion and we can distinguish the last four operations: { kernel semi-revision for consistency { kernel semi-revision for coherence { partial meet semi-revision for consistency { partial meet semi-revision for coherence 4
In the previous section we presented rationality postulates for revision. In this section we are going to present constructions that are equivalent to those sets of postulates.
We are going to present two kinds of constructions for revision: kernel and partial meet revision. Kernel revisions are equivalent to those sets of postulates that satisfy core-retainment and partial meet revisions are equivalent to those that satisfy relevance. All these constructions rst add the new sentence and then contract the inconsistencies/incoherences. They di er from each other in how they contract the inconsistencies/incoherences. 4.1
Kernel Revisions Kernel revisions try to contract the inconsistencies/incoherences by nding all minimal inconsistent/incoherent subsets of B + , which is called kernel of B + , and then removing at least one element of every one of them.
This construction is equivalent to kernel semi-revision. To satisfy strong success we need to protect the input . We do that by not choosing to be removed from B. To satisfy strong consistency/coherence we must protect only the consistent/coherent inputs . The strategy adopted by partial meet revision is to nd all maximal subsets of B + that are consistent/coherent, which will be called the remainder set of B + . Then we choose some, at least one, of these sets and get their intersection.
Like in the previous section this construction is equivalent to the partial meet semi-revision. To satisfy strong success we also need to protect the input and we do that by choosing every maximal consistent subset of B that contains . Furthermore, in order to satis es the strong consistency/coherence we must protect only consistent/coherent inputs. A representation theorem proves that a set of postulates is equivalent to a construction. This means that, in one hand, the construction satis es all the postulates in the respective set of postulates. On the other hand, if an operation satis es every postulate in this set of postulates then it can be constructed by the respective construction.
Every revision presented in section 3 is equivalent to a construction informally presented in 4.1 and 4.2. For example the kernel revision with strong success for consistency of the section 3 is equivalent to the kernel construction that protects the input of the section 4.1.
For more details about these operations, constructions, their representation theorems and proofs see [RW08]. 5
The di cult part of these constructions is to nd the kernel and the remainder set of B + . In this section we are going to show how we implemented these operations. To nd the kernel we used the algorithms for ontology debugging presented in [KPSH05,SC03]. To nd the remainder set we used Reiter algorithm [Rei87] in the kernel.
[KPSH05] presents two algorithms to nd what the authors call justi cations for a sentence in an ontology: glass box and black box algorithm.
The glass box algorithm depends on the reasoner. It tries to trace the axioms used to prove the inconsistency. The result is inconsistent/incoherent subset of the ontology. Glass box algorithm is already implemented in the OWL API with Pellet: PelletOptions.USE_TRACING = true; Reasoner pellet = new Reasoner( OWLManager.createOWLOntologyManager() ); pellet.loadOntology( B ); pellet.getKB().setDoExplanation( true );
The resulting subset is not guarantied to be minimal. To guaranty the minimality of this subset we used the black box algorithm. Black box algorithm (algorithm 1) does not depend on the reasoner. It consists in two parts: the rst (expand) adds axioms until the set becomes inconsistent/incoherent. The second part (shrink) removes elements one by one and veri es if the ontology remains inconsistent, if not then the removed axiom must be part of the kernel and so it is left in the ontology. The black box algorithm returns a minimal inconsistent/incoherent subset of the ontology, in other words, an element of the kernel. It can be used alone, but it is much more e cient if it is used with the result of the glass box algorithm forming a hybrid algorithm.
Algorithm 1 Black Box Algorithm
To nd the other elements of the kernel we implemented the following recursive algorithm: Algorithm 2 Algorithm to nd all the element of the Kernel Kernel(B + ) 1 This algorithm returns the kernel of B + 2 if B + is consistent/coherent 3 then return ; 4 min Hybrid(B + ) 5 B0 B0fming 6 for 2 min 7 do B0 B0 [ kernel(B + n f g) 8 return B0
Once the kernel is computed, the remainder set can be computed nding the minimal cuts (hitting sets) of the kernel. A cut is a set that contains at least one element of each set in a class of sets. In [Was00] it was proved that a minimal cut in the kernel corresponds to B minus an element of the remainder set and vice-versa. Hence, the remainder set can be computed using the Reiter's algorithm to nd minimal hitting sets of a class of sets [Rei87,GSW89]. When the user opens the revision view inside Protege, he is given a menu of postulates to choose (see Figure 1). The user has a choice between success, weak success or no success, between core-retainment and relevance as minimality conditions, and between strong consistency, weak consistency, strong coherence and weak coherence. After picking up the desired set of postulates and entering the new sentence at the Input Editor (Figure 1), the user is given the corresponding kernel or remainder set as shown in Figure 3. He can then select at least one sentence from each element of the kernel (Figure 3, left hand side) or select at least one element of the remainder set (Figure 3, right hand side) and press Finish. The ontology is then revised accordingly (Figure 4).
The plug-in also o ers the possibility of performing kernel or partial-meet contractions, as can be seen in Figure 2. 6
We have presented here a plug-in for Protege that implements the two operations for contraction and the twelve operations for revision presented in [RW08]. The implementation uses the algorithm presented in [HWKP06] using the OWL API and the pellet reasoner.
At this moment the plug-in is compliant with the build 53 of Protege 4. We are trying to make it compliant with the last build of Protege 4. Future works also include testing and improving e ciency of the implementation and testing if it is better to compute remainder sets directly or to use the Reiter's algorithm (as we are doing).
Fig. 3. In the left the elements of the kernel generated by the last example of section 2. In the right elements of the remainder set generated by the same example [FPA06] Giorgos Flouris, Dimitris Plexousakis, and Grigoris Antoniou. On generalizing the agm postulates. In Proceedings of the 3rd European Starting AI Researcher Symposium (STAIRS-06), 2006. [GSW89] Russel Geriner, Barbara A. Smth, and Ralph W. Wilkerson. A correction to the algorithm in reiter's theory of diagnosis. Arti cial Intelligence, 41(1):79{88, 1989. [Han97a] Sven Ove Hansson. Semi-revision (invited paper). Journal of Applied Non
Classical Logics, 7(2), 1997. [Han97b] Sven Ove Hansson. A Textbook of Belief Dynamics. Kluwer Academic
Publishers, 1997. [Hor03] Ian Horrocks. Reducing OWL entailment to description logic satis ability.
In Proc. of the 2nd International Semantic Web Conference (ISWC), 2003. [HS04] Peter Haase and York Sure. State-of-the-art on ontology evolution. SEKT informal deliverable 3.1.1.b, Institute AIFB, University of Karlsruhe, 2004. [HW02] Sven Ove Hansson and Renata Wassermann. Local change. Studia Logica, 70(1):49{76, 2002. [HWKP06] Christian Halaschek-Wiener, Yarden Katz, and Bijan Parsia. Belief base revision for expressive description logics. In OWL: Experiences and Directions 2006, 2006. [KPSH05] Aditya Kalyanpur, Bijan Parsia, Evren Sirin, and James Hendler. Debugging unsatis able classes in OWL ontologies. Journal of Web Semantics Special Issue of the Semantic Web Track of WWW2005, 3(4), 2005. [Rei87] Raymond Reiter. A theory of diagnosis from rst principles. Arti cial
Intelligence, 32:57{95, 1987. [RW06] Marcio Moretto Ribeiro and Renata Wassermann. First steps towards revising ontologies. In Proceedings of the Second Workshop on Ontologies and their Applications (WONTO 2006), 2006. [RW07] Marcio Moretto Ribeiro and Renata Wassermann. Base revision in description logics - preliminary results. In Proceedings of International Workshop on Ontology Dynamics (IWOD'07), JUN 2007. [RW08] Marcio Moretto Ribeiro and Renata Wassermann. Base revision for ontology debugging. Accepted for publication in the special issue for ontology dynamics in the Journal of Logic and Computation, 2008. [SC03] Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In Georg Gottlob and Toby Walsh, editors, IJCAI, pages 355{362. Morgan Kaufmann, 2003. [Was00] Renata Wassermann. An algorithm for belief revision. In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000). Morgan Kaufmann, 2000.