Optimal Repairs in Ontology Engineering as Pseudo-Contractions in Belief Change

Abstract

The question of how a given knowledge base can be modified such that certain unwanted consequences are removed has been investigated in the area of ontology engineering under the name of repair and in the area of belief change under the name of contraction. Whereas in the former area the emphasis was more on designing and implementing concrete repair algorithms, the latter area concentrated on characterizing classes of contraction operations by certain postulates they satisfy. In the classical setting, repairs and contractions are subsets of the knowledge base that no longer have the unwanted consequence. This makes these approaches syntax-dependent and may result in removal of more consequences than necessary. To alleviate this problem, gentle repairs and pseudo-contractions have been introduced in the respective research areas, and their connections have been investigated in recent work. Optimal repairs preserve a maximal amount of consequences, but they may not always exist. We show that, if they exist, then they can be obtained by certain pseudo-contraction operations, and thus they comply with the postulates that these operations satisfy. Conversely, under certain conditions, pseudo-contractions are guaranteed to produce optimal repairs.

Keywords

• eol>Belief change
• Ontology repair
• Optimal repair
• Pseudo-contraction

-

how to repair the knowledge base such that no new consequences are added, the unwanted consequence no longer follows, and other consequences are not lost unnecessarily. The classical approaches for ontology repair consider as repairs maximal subsets of the ontology (viewed as a set of logical sentences) that do not have the unwanted consequence, and employ methods inspired by model-based diagnosis [ 1 ] to compute these sets [ 2, 3, 4 ], which are called optimal classical repairs in [ 5 ]. While these approaches preserve as many of the sentences in the ontology as possible, they need not preserve a maximal amount of consequences.

Example 1. As an example, consider a Description Logic [ 6 ] knowledge base that describes some of the beliefs of Tom. Tom thinks that Ben has a parent called Jerry, who is both rich and famous. He also believes that people that have a rich and famous parent are arrogant. The former belief is represented in the ABox := { has_parent(BEN, JERRY), Famous(JERRY), Rich(JERRY) } whereas the latter is expressed in the TBox := { ∃ has_parent. (Famous ⊓ Rich) ⊑ Arrogant }. Clearly, the knowledge base consisting of this TBox and ABox has Arrogant(BEN) as a consequence. Now assume that Tom actually meets Ben and notices that he is not arrogant. Since Tom insists on sticking with the prejudice that children of rich and famous people are arrogant, the unwanted consequence Arrogant(BEN) can only be removed by modifying the ABox. In the classical repair approach, this can be achieved by removing one of its three assertions from . Let us assume that Tom decides to remove Famous(JERRY). This gets rid of the unwanted consequence Arrogant(BEN), but also the consequence ∃ has_parent. Famous(BEN). Removing Famous(JERRY) from , but adding the assertion ∃ has_parent. Famous(BEN) to the ABox yields a repair that retains more consequences than the classical repair. This improved repair corresponds to Tom’s new belief that Jerry is only rich, and that Ben has another famous parent, whose name is not known to him.

To overcome the problem that classical repairs may remove too many consequences, more gentle repair approaches have been introduced, e.g., in [ 7, 8, 5 ], but these methods still need not produce optimal repairs, i.e., ones that preserve a maximal set of consequences. In general, such optimal repairs need not exist [ 5 ]. In the setting of repairing ABoxes of the description logic ℰℒ w.r.t. static ℰℒ TBoxes, methods for computing optimal repairs (if they exist) are available [ 9 ].

Contractions in belief change

In belief change [ 10 ], one usually assumes, as in the above example, that the knowledge base represents the beliefs of a rational agent. These beliefs may change if the agent receives new information, and the question is how this can be reflected by a change of the knowledge base. Removing (implied) information is called contraction in the belief change community. Instead of directly constructing contraction operations, researchers in this area have formulated properties (called postulates) that should be satisfied by reasonable contraction operations, and then developed approaches for constructing concrete contraction operations, such as partial meet contraction [ 11, 12 ] and kernel contraction [13], which capture exactly those contraction operations that satisfy a certain combination of postulates. This approach, which was pioneered in [ 11 ], is called the AGM approach. The original AGM approach works with belief sets, which are assumed to be closed under consequences. From a practical point of view, it makes more sense to work with non-deductively closed (and ideally finite) representations of belief sets, called belief bases [14, 15, 12]. Similar to classical repairs, the original approaches for belief base contraction consider subsets of the knowledge base as possible contractions. For the same reasons as for repairs, operations that preserve more consequences, called pseudo-contractions, have been introduced in the belief change literature [16, 17]. To obtain pseudo-contractions that retain more consequences than contractions, approaches for constructing pseudo-contractions ifrst add some of its logical consequences to the given belief base, and then apply the partial meet or the kernel contraction approach to the resulting extended belief base [18, 19, 20].

Connecting the two approaches

Although contractions and classical repairs as well as pseudo-contractions and repairs tackle basically the same problems, there has until recently been little interaction between the two communities, and thus the connections between the developed approaches remained unclear. The papers [19, 20] address this problem, with an emphasis on showing connections between gentle repairs and the pseudo-contraction approaches based on partial meet and kernel contractions. In the paper [21], on which this extended abstract reports, we concentrate on optimal repairs, both in the classical and the general sense. We show that, under certain conditions, operations that compute optimal (classical) repairs can be obtained as partial meet and kernel pseudo-contractions (contractions), and vice versa. This demonstrates, on the one hand, that the approaches developed in ontology engineering satisfy the postulates required in belief change. On the other hand, under certain conditions, the approaches developed in belief change yield optimal (classical) repairs. We instantiate our results using the setting of repairing ABoxes of the description logic ℰℒ w.r.t. static ℰℒ TBoxes [ 9 ].

The main novelty of the work described in [21] is that we consider the relationship of contraction operations from belief change with optimal repairs (both in the classical and the general sense), i.e., repairs that are maximal subsets of the knowledge base to be repaired (classical case) or repairs that are entailed by the knowledge base to be repaired and preserve a maximal amount of consequences (general case). This notion of optimality usually does not play an important rôle in belief change (there is no optimality postulate), but under the assumption that the repair process should not lose consequences unnecessarily, it is important for ontology engineering. In [19, 20], classical repairs and gentle repairs are respectively set in relationship with contraction and pseudo-contraction operations, but optimal repairs are not considered. Work on revision and contraction for description logics [22] usually adapts the approaches from the belief change community to description logics as underlying logical formalism, but does not compare them with other ontology repair approaches, and in particular not with optimal repairs.

Overview of the paper [21]

After an introduction, which basically is a shorter version of the exposition above, Section 2 introduces the general notion of a logical consequence operator, and then instantiates it with entailment from ℰℒ ABoxes w.r.t. an ℰℒ TBox. The definitions of contractions and repairs in the subsequent sections are formulated in the general setting, with the concrete instance providing us with (counter-)examples. Section 3 first reviews relevant notions from belief change. In particular, it introduces partial meet and kernel contractions, and recalls the postulates they satisfy. Then it shows that certain partial meet and kernel contractions always yield optimal classical repairs. Conversely, it points out that a contraction operation that always returns an optimal classical repair (in case there is any repair) satisfies three of the four postulates characterizing partial meet contractions, but not the fourth (called uniformity). Section 4 introduces pseudo-contractions and in particular the “pseudo-versions” of partial meet and kernel contraction [18, 20]. Roughly speaking, it is shown in this section that there always exists a partial meet pseudo-contraction that produces optimal repairs whenever such repairs exist, and optimal classical repairs otherwise. In general, however, partial meet pseudo-contractions need not yield optimal repairs (even if they exist) unless an additional property is satisfied, which requires that the optimal repairs cover all repairs in the sense that every repair is entailed by an optimal repair.

Conclusion

The results shown in [21] complement recent results [19, 20] on the relationship between gentle repairs and pseudo-contractions by demonstrating that there are close connections between optimal repairs and certain pseudo-contraction operations. These results are illustrated on the use case of repairing ℰℒ ABoxes with respect to static ℰℒ TBoxes, where optimal repairs can efectively be computed (if they exists) [ 9 ].

In [23], it was shown that optimal repairs always exist and cover all repairs if one uses quantified ABoxes (where some of the individuals can be anonymized by representing them as existentially quantified variables) in place of ABoxes. Extending the result of the present paper to this setting poses new challenges since the first-order translation of a quantified ABox is not a set of sentences, but a single one, which starts with an existential quantifier prefix. Thus, considering subsets when constructing contractions does not make sense. We conjecture that this problem can be overcome by introducing an “inclusion” relation on quantified ABoxes that shares enough properties with set inclusion for the constructions and proofs regarding (pseudo-)contractions to continue working.

On a more conceptual level, there are certain diferences between repair approaches in ontology engineering and contraction approaches in belief change that are worth investigating. On the one hand, the work on optimal repairs [ 23, 9 ] usually considers a single repair problem and does not investigate the relationship between repairs for diferent unwanted consequences, whereas postulates like uniformity in belief change make statements on how results for diferent unwanted consequences should be connected under certain conditions on these consequences. It would be interesting to see whether and how postulates like uniformity and their variants in the context of pseudo-contractions [18, 20] can be satisfied by methods that compute optimal repairs. On the other hand, contraction and pseudo-contraction operators produces a single belief base as output, whereas work on optimal repairs is also concerned with how to compute the set of all such repairs and investigates properties of this set (like whether it covers all repairs or not). In contrast, on the belief change side, there are no postulates about the sets of all pseudo-contractions that can be obtained be applying a certain approach (e.g., in the partial meet case, if one looks at all possible selection functions). It would be interesting to see whether taking this “set view” can lead to interesting kinds of new postulates.

Acknowledgments This work was partially supported by the German Research Foundation (DFG) in Project 430150274 and SFB/TRR 248. [12] S. O. Hansson, Reversing the Levi identity, J. Philos. Logic 22 (1993) 637–669. doi:10.

1007/BF01054039. [13] S. O. Hansson, Kernel contraction, J. Symb. Log. 59 (1994) 845–859. doi:10.2307/2275912. [14] S. O. Hansson, In defense of base contraction, Synthese 92 (1992) 239–245. doi:10.1007/

BF00413568. [15] A. Fuhrmann, Theory contraction through base contraction, J. Philos. Logic 20 (1991) 175–203. doi:10.1007/BF00284974. [16] S. O. Hansson, New operators for theory change, Theoria 55 (1989) 114–132. doi:10.

1111/j.1755-2567.1989.tb00725.x. [17] S. O. Hansson, Changes of disjunctively closed bases, J. Log. Lang. Inf. 2 (1993) 255–284.

doi:10.1007/BF01181682. [18] Y. D. Santos, V. B. Matos, M. M. Ribeiro, R. Wassermann, Partial meet pseudo-contractions,

Int. J. Approx. Reason. 103 (2018) 11–27. doi:10.1016/j.ijar.2018.08.006. [19] V. B. Matos, R. Guimarães, Y. D. Santos, R. Wassermann, Pseudo-contractions as gentle repairs, in: C. Lutz, U. Sattler, C. Tinelli, A. Turhan, F. Wolter (Eds.), Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, volume 11560 of Lecture Notes in Computer Science, Springer, 2019, pp. 385–403. doi:10.1007/978-3-030-22102-7\_18. [20] V. B. Matos, R. Wassermann, Repairing ontologies via kernel pseudo-contraction, in: O. Arieli, G. Casini, L. Giordano (Eds.), Proceedings of the 20th International Workshop on Non-Monotonic Reasoning, NMR 2022, Part of the Federated Logic Conference (FLoC 2022), Haifa, Israel, August 7-9, 2022, volume 3197 of CEUR Workshop Proceedings, CEUR-WS.org, 2022, pp. 16–26. URL: http://ceur-ws.org/Vol-3197/paper2.pdf. [21] F. Baader, Optimal repairs in ontology engineering as pseudo-contractions in belief change, in: J. Hong, M. Lanperne, J. W. Park, T. Cerný, H. Shahriar (Eds.), Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing, SAC 2023, Tallinn, Estonia, March 27-31, 2023, ACM, 2023, pp. 983–990. doi:10.1145/3555776.3577719. [22] G. Qi, F. Yang, A survey of revision approaches in description logics, in: D. Calvanese, G. Lausen (Eds.), Web Reasoning and Rule Systems, Second International Conference, RR 2008, Karlsruhe, Germany, October 31-November 1, 2008. Proceedings, volume 5341 of Lecture Notes in Computer Science, Springer, 2008, pp. 74–88. doi:10.1007/ 978-3-540-88737-9\_7. [23] F. Baader, P. Koopmann, F. Kriegel, A. Nuradiansyah, Computing optimal repairs of quantiifed ABoxes w.r.t. static ℰℒ TBoxes, in: A. Platzer, G. Sutclife (Eds.), Automated Deduction - CADE 28 - 28th International Conference on Automated Deduction, Proceedings, volume 12699 of LNCS, Springer, 2021, pp. 309–326. doi:10.1007/978-3-030-79876-5\_18.

References

[1] R. Reiter , A theory of diagnosis from first principles , Artif. Intell . 32 ( 1987 ) 57 - 95 . doi: 10 .1016/ 0004 - 3702 ( 87 ) 90062 - 2 .

[2] B. Parsia , E. Sirin , A. Kalyanpur , Debugging OWL ontologies , in: A. Ellis , T. Hagino (Eds.), Proceedings of the 14th International Conference on World Wide Web, WWW 2005 , Chiba, Japan, May 10 -14, 2005 , ACM, 2005 , pp. 633 - 640 . doi: 10 .1145/1060745.1060837.

[3] S. Schlobach , Z. Huang , R. Cornet , F. Harmelen , Debugging incoherent terminologies, J. Automated Reasoning 39 ( 2007 ) 317 - 349 . doi: 10 .1007/s10817-007-9076-z.

[4] F. Baader , B. Suntisrivaraporn , Debugging SNOMED CT using axiom pinpointing in the description logic ℰ ℒ+ , in: R. Cornet , K. A . Spackman (Eds.), Proceedings of the Third International Conference on Knowledge Representation in Medicine , Phoenix, Arizona, USA, May 31st - June 2nd, 2008 , volume 410 of CEUR Workshop Proceedings, CEUR-WS.org , 2008 . URL: http://ceur-ws. org/ Vol- 410 /Paper01.pdf.

[5] F. Baader , F. Kriegel , A. Nuradiansyah , R. Peñaloza , Making repairs in description logics more gentle , in: M. Thielscher , F. Toni , F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018 , Tempe, Arizona, 30 October - 2 November 2018 , AAAI Press, 2018 , pp. 319 - 328 . URL: https://aaai.org/ocs/index.php/KR/KR18/paper/view/18056.

[6] F. Baader , I. Horrocks, C. Lutz , U. Sattler , An Introduction to Description Logic, Cambridge University Press, 2017 . doi: 10 .1017/9781139025355.

[7] J. S. C. Lam , D. H. Sleeman , J. Z. Pan , W. W. Vasconcelos , A fine-grained approach to resolving unsatisfiable ontologies , J. Data Semant . 10 ( 2008 ) 62 - 95 . doi: 10 .1007/ 978-3- 540 -77688-8\_3.

[8] N. Troquard , R. Confalonieri , P. Galliani , R. Peñaloza , D. Porello , O. Kutz , Repairing ontologies via axiom weakening , in: S. A. McIlraith , K. Q. Weinberger (Eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence , (AAAI-18) , AAAI Press, 2018 , pp. 1981 - 1988 . URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/ 17189.

[9] F. Baader , P. Koopmann , F. Kriegel , A. Nuradiansyah , Optimal ABox repair w .r.t. static ℰ ℒ TBoxes: From quantified ABoxes back to ABoxes , in: The Semantic Web - 19th International Conference, ESWC 2022 , Proceedings , volume 13261 of LNCS , Springer, 2022 , pp. 130 - 146 . doi: 10 .1007/978-3- 031 -06981-9\_8.

[10] P. Gärdenfors (Ed.), Belief Revision , Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1992 . doi: 10 .1017/CBO9780511526664.

[11] C. E. Alchourrón , P. Gärdenfors , D. Makinson , On the logic of theory change: Partial meet contraction and revision functions , J. Symb. Log . 50 ( 1985 ) 510 - 530 . doi: 10 .2307/ 2274239.