How to Contract Ontologies

Abstract

The dynamic nature of knowledge development has motivated the formal study of ontology evolution problems. In this paper, we study ontology contraction|the problem of retracting information that is no longer considered to hold. Our prime interest is to focus on ontologies expressed in Description Logics DL-Lite and EL, which underpin the OWL 2 QL and OWL 2 EL pro les. Our goal is to understand how to compute contractions under di erent kinds of semantics. As we have already shown in [1, 2], ontology contraction is technically very challenging.

-

{ 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 should remain the same. Consider scenarios for TBox and ABox contraction. OWL TBoxes are extensively used in the clinical sciences, and clinical ontologies such as SNOMED CT3 and NCI4 are subject to frequent modi cations that involve retracting unintended consequences from the TBox [ 18 ]. For example, the developers of NCI perform over 900 monthly changes [ 18 ]. Furthermore, ABox contraction is important for applications relying on widely-used reference TBoxes. For example, bio-informaticians working on gene extraction can describe the experimental results using an ABox according to standard gene TBoxes. New experiments may imply that some facts about speci c individuals no longer hold, which should be re ected in the ABox; at the same time, TBoxes should clearly not be a ected by these manipulations of the data. 2

Practical View of Contraction

Approaches to ontology contraction, typically adopted in practice (especially when changes occur at the TBox-level), are essentially syntactic [ 9, 13, 19 ]. Many such approaches are based on the notion of a justi cation: a minimal subset of the ontology that entails a given consequence [ 20, 21 ]. For example, to retract an axiom entailed by K, it su ces to compute all justi cations for in K, nd a minimal subset R of K (a \repair") with at least one axiom from each justi cation, and take Ko = K n R as the result of the contraction. Retracting results in the deletion of a minimal set of axioms and hence the structure of K is maximally preserved. 3

Logic-Based View of Contraction

From a logic-based perspective, the desirable properties of contraction should be dictated by the principle of minimal change [ 16 ], according to which the semantics of the ontology should change \as little as possible", thus ensuring that the contraction has the least possible impact.

Logic-based semantics derived from the principle of minimal change have been recently studied in the more general context of ontology evolution. These semantics are either model-based (MBS) or formula-based (FBS). Under both types of semantics, evolution of an ontology K written in a DL DL results in a DL-ontology Ko in which the required information is incorporated, retracted, or updated; the di erence is in the way Ko is obtained. Under MBS the set of all models M of K evolves into a new set M0 of models that are \as close as possible" to those in M (w.r.t. some notion of distance between models); then, Ko is the ontology that axiomatises M0 [10{12, 22, 23]. Under FBS, Ko is an ontology de ned in terms of the deductive closure of K that satis es the evolution requirements. FBS, however, have been less studied in the context of ontologies [ 1, 2, 11, 24 ]. 3 http://www.nlm.nih.gov/research/umls/Snomed/snomed_main.html 4 National Cancer Institute Thesaurus

Under both MBS and FBS, we are interested in computing an \optimal" contraction |that is, a contraction that is as similar as possible to the original ontology. In particular, an optimal contraction of a DL-ontology K with an axiom is a DL-ontology Ko such that (i) K entails Ko, (ii) Ko does not entail , and (iii) Ko is \as similar as possible" to K according to the particular notion of minimal change adopted by the semantics under consideration. 4

Issues with Practical and Logic-Based Approaches

Practical approaches su er from intrinsic information loss. More precisely, by removing R from K, one may inadvertently retract consequences of K other than , which are \intended". Identifying and recovering such intended consequences is an important issue. For example, if K consists of two TBox axioms: 1 = \VW is-a car", 2 = \car is-a vehicle", with an implicit information 3 = \VW is-a vehicle", and = 1, then Ko = f 2g; thus, 3 is lost.

Logic-based approaches limit information loss, but they su er from the following two problems. First, given a DL-ontology K and an axiom , an optimal contraction Ko may not exist in DL, that is DL may not be closed under contraction. It has been shown [ 11, 22 ] that DL-Lite is not closed under so-called update and revision on both TBox and ABox levels; in [ 1 ] these results were extended to TBox and ABox contraction. In [ 1, 2 ] it has been shown that EL is not closed under TBox and ABox contraction.

The second problem is that logic-based approaches are also problematic from a modeling point of view. Indeed, in contrast to syntactic approaches, these semantics do not distinguish between the axioms in the deductive closure that are explicit in K, and those that are merely implied. Ontologies, however, are the result of a time-consuming modeling process, and thus contractions should also preserve as much as possible the structure of K. For example, consider a DL-Lite-ontology K with the following two axioms 2 = \car is-a vehicle" and 4 = \VW is-a car and golf", and let = \lecturer is-a professor". Clearly is unrelated to K, and the optimal contraction of K with is expected to be K itself. At the same time, the ontology Ko consisting of the following axioms is a valid contraction too (under any FBS and MBS considered in the ontology evolution literature): 2 = \car is-a vehicle" and 5 = \VW is-a car", 6 = \VW is-a golf", 7 = \VW is-a vehicle". Returning such Ko as the contraction result might be undesirable from a practical point of view.

We believe that our results in [ 1 ] suggest that classical approaches to ontology contraction, which are well-understood and well-behaved for propositional logics, are intrinsically problematical in the context of ontology languages. 5

Bridging Logics and Practice

In [ 2 ], these limitations of both syntactic and logic-based approaches were addressed (at least partly). On the one hand, the semantics in [ 2 ] provides a \bridge" between syntactic and formula-based approaches; on the other hand, this semantics provides a distinction between the languages DL in which the original ontology 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 re ected along two dimensions: (i) structural, where the explicit axioms in K are maximally preserved; (ii) deductive, where the consequences of K in LP are maximally preserved.

More formally, the semantics of [ 2 ] can be de ned as follows in the context of contraction.

De nition 1. Let DL and LP be description logics with LP DL. Let K be a DL-ontology, and let be a DL-axiom such that K j= .

A DL-ontology Ko is an optimal contraction of K with w.r.t. the preservation language LP if (i) K j= Ko; (ii) Ko 6j= ; (iii) Ko [ f g j= , for each 2 K n Ko; and (iv) Ko [ f g j= , for each LP-axiom that is entailed by K but not by Ko. 6

Our Goals

The contraction algorithms we proposed and implemented in [ 2 ] are speci c to TBox contraction. We would like to extend them to cover more expressive DLs. Another next step is to develop algorithms for ABox contraction. Acknowledgements. 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. Grau , B.C. , Kharlamov , E. , Zheleznyakov , D. : Ontology contraction: Beyond propositional paradise . In: Proc. Alberto Mendelzon International Workshop on Foundations of Data Management (AMW) . ( 2012 )

2. Grau , B.C. , Jimenez-Ruiz , E. , Kharlamov , E. , Zheleznyakov , D. : Ontology evolution under semantic constraints . In: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR) , Rome, Italy ( 2012 )

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

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

5. Baader , F. , Calvanese , D. , McGuinness , D.L. , Nardi , D. , Patel-Schneider , P.F., eds.: The Description Logic Handbook: Theory, Implementation, and Applications . In Baader, F., Calvanese , D. , McGuinness , D.L. , Nardi , D. , Patel-Schneider , P.F., eds.: Description Logic Handbook, Cambridge Uni. Press ( 2003 )

6. Flouris , G. , Manakanatas , D. , Kondylakis , H. , Plexousakis , D. , Antoniou , G.: Ontology change: classi cation and survey . Knowledge Engineering Review 23 ( 2 ) ( 2008 ) 117 { 152

7. Fridman Noy , N. , Kunnatur , S. , Klein , M. , Musen , M. : Tracking changes during ontology evolution . In: Proc. of International Semantic Web Conference (ISWC) . Volume 3298 of LNCS ., Springer ( 2004 ) 259 { 273

8. Haase , P., van Harmelen , F. , Huang , Z. , Stuckenschmidt , H. , Sure , Y. : A framework for handling inconsistency in changing ontologies . In: International Semantic Web Conference (ISWC) . ( 2005 ) 353 { 367

9. Haase , P. , Stojanovic , L. : Consistent evolution of OWL ontologies . In: Proc. of Extended Semantic Web Conference (ESWC) . ( 2005 )

10. Qi , G. , Du , J.: Model-based revision operators for terminologies in Description Logics . In: Proc. of International Joint Conference on Arti cial Intelligence . ( 2009 ) 891 { 897

11. Calvanese , D. , Kharlamov , E. , Nutt , W. , Zheleznyakov , D. : Evolution of DL-Lite Knowledge Bases . In: Proc. of International Semantic Web Conference (ISWC) , Shanghai, China ( 2010 )

12. Wang , Z. , Wang , K. , Topor , R.W.: Revising general knowledge bases in Description Logics . In: Proc. of International Conference on Principles of Knowledge Representation and Reasoning (KR) . ( 2010 )

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

14. Konev , B. , Walther , D. , Wolter , F. : The logical di erence problem for description logic terminologies . In: Proc. of International Joint Conference on Automated Reasoning (IJCAR) . ( 2008 )

15. Goncalves , R.S. , Parsia , B. , Sattler , U. : Analysing the evolution of the NCI thesaurus . In: Proc. of CBMS . ( 2011 ) 1{ 6

16. Alchourron , C.E. , Gardenfors, P. , Makinson , D. : On the logic of theory change: Partial meet contraction and revision functions . In Journal of Symbolic Logics 50 ( 2 ) ( 1985 ) 510 { 530

17. Peppas , P. : Belief revision . In F. van Harmelen , V.L. , Porter , B., eds.: Handbook of Knowledge Representation . ( 2007 )

18. Hartung , M. , Kirsten , T. , Rahm , E.: Analyzing the evolution of life science ontologies and mappings . In: Proc. of Data Integration in The Life Sciences workshop (DILS) . Volume 5109 of LNCS ., Springer ( 2008 ) 11 { 27

19. Kalyanpur , A. , Parsia , B. , Sirin , E. , Grau , B.C. : Repairing unsatis able concepts in OWL ontologies . In: Proc. of Extended Semantic Web Conference (ESWC) . ( 2006 ) 170 { 184

20. Kalyanpur , A. , Parsia , B. , Sirin , E. , Hendler , J.A. : Debugging unsatis able classes in OWL ontologies . In Journal of Web Semantics 3 ( 4 ) ( 2005 ) 268 { 293

21. Schlobach , S. , Huang , Z. , Cornet , R., van Harmelen , F. : Debugging incoherent terminologies . Journal of Automated Reasoning 39 ( 3 ) ( 2007 ) 317 { 349

22. Kharlamov , E. , Zheleznyakov , D. : Capturing instance level ontology evolution for DL-Lite . In: Proc. of International Semantic Web Conference (ISWC) , Bonn, Germany ( 2011 )

23. Wang , Z. , Wang , K. , Topor , R.W.: A new approach to knowledge base revision in DL-Lite . In: Proc. of Conference on Arti cial Intelligence (AAAI) . ( 2010 )

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