Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal Repairs in the Description Logic \(\mathcal{E}\mathcal{L}\) Revisited

  • Conference paper
  • First Online:
Logics in Artificial Intelligence (JELIA 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14281))

Included in the following conference series:

Abstract

Ontologies based on Description Logics may contain errors, which are usually detected when reasoning produces consequences that follow from the ontology, but do not hold in the modelled application domain. In previous work, we have introduced repair approaches for \(\mathcal{E}\mathcal{L}\) ontologies that are optimal in the sense that they preserve a maximal amount of consequences. In this paper, we will, on the one hand, review these approaches, but with an emphasis on motivation rather than on technical details. On the other hand, we will describe new results that address the problems that optimal repairs may become very large or need not even exist unless strong restrictions on the terminological part of the ontology apply. We will show how one can deal with these problems by introducing concise representations of optimal repairs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://www.w3.org/TR/owl2-overview/.

  2. 2.

    see. e.g., https://bioportal.bioontology.org and https://www.snomed.org/.

  3. 3.

    The paper [16] actually calls repairs “compliant anonymisations” and repair requests “privacy policies” since it considers a situation where consequences are to be removed not because they are incorrect, but since this information should be hidden.

  4. 4.

    This condition differs from the one given in [7]. However, this third condition is only employed in Lemma XIII in [8] to show that the canonical repairs are saturated, for which the simpler condition given here suffices.

References

  1. Baader, F.: Optimal repairs in ontology engineering as pseudo-contractions in belief change. In: Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing (SAC 2023), Tallinn, Estonia, 27–31 March 2023, pp. 983–990. Association for Computing Machinery (2023). https://doi.org/10.1145/3555776.3577719

  2. Baader, F., Borgwardt, S., Morawska, B.: SAT encoding of unification in \(\cal{ELH}_{{R}^+}\) w.r.t. cycle-restricted ontologies. In: Gramlich, B., Miller, D., Sattler, U. (eds.) IJCAR 2012. LNCS (LNAI), vol. 7364, pp. 30–44. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31365-3_5

    Chapter  Google Scholar 

  3. Baader, F., Brandt, S., Lutz, C.: Pushing the \(\cal{EL} \) envelope. In: Kaelbling, L.P., Saffiotti, A. (eds.) IJCAI 2005, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, 30 July–5 August 2005, pp. 364–369. Professional Book Center (2005). http://ijcai.org/Proceedings/05/Papers/0372.pdf

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

    Google Scholar 

  5. Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press (2017). https://doi.org/10.1017/9781139025355

  6. Baader, F., Koopmann, P., Kriegel, F.: Optimal repairs in the description logic \(\cal{EL} \) revisited (extended version). LTCS-Report 23-03, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany (2023). https://doi.org/10.25368/2023.121

  7. Baader, F., Koopmann, P., Kriegel, F., Nuradiansyah, A.: Computing optimal repairs of quantified ABoxes w.r.t. static \(\cal{EL}\) TBoxes. In: Platzer, A., Sutcliffe, G. (eds.) CADE 2021. LNCS (LNAI), vol. 12699, pp. 309–326. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79876-5_18

    Chapter  Google Scholar 

  8. Baader, F., Koopmann, P., Kriegel, F., Nuradiansyah, A.: Computing optimal repairs of quantified ABoxes w.r.t. static \(\cal{EL} \) TBoxes (extended version). LTCS-Report 21-01, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany (2021). https://doi.org/10.25368/2022.64

  9. Baader, F., Koopmann, P., Kriegel, F., Nuradiansyah, A.: Optimal ABox repair w.r.t. static \(\cal{EL} \) TBoxes: from quantified ABoxes back to ABoxes. In: Groth, P., et al. (eds.) ESWC 2022. LNCS, vol. 13261, pp. 130–146. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06981-9_8

    Chapter  Google Scholar 

  10. Baader, F., Koopmann, P., Kriegel, F., Nuradiansyah, A.: Optimal ABox repair w.r.t. static \(\cal{EL} \) TBoxes: from quantified ABoxes back to ABoxes (extended version). LTCS-Report 22-01, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany (2022). https://doi.org/10.25368/2022.65

  11. Baader, F., Kriegel, F.: Pushing optimal ABox repair from \(\cal{EL} \) towards more expressive Horn-DLs. In: Kern-Isberner, G., Lakemeyer, G., Meyer, T. (eds.) Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, KR 2022, Haifa, Israel, 31 July–5 August 2022, pp. 22–32 (2022). https://doi.org/10.24963/kr.2022/3

  12. Baader, F., Kriegel, F., Nuradiansyah, A.: Privacy-preserving ontology publishing for \(\cal{EL} \) instance stores. In: Calimeri, F., Leone, N., Manna, M. (eds.) JELIA 2019. LNCS (LNAI), vol. 11468, pp. 323–338. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19570-0_21

    Chapter  Google Scholar 

  13. Baader, F., Kriegel, F., Nuradiansyah, A.: Error-tolerant reasoning in the description logic \(\cal{EL} \) based on optimal repairs. In: Governatori, G., Turhan, A. (eds.) RuleML+RR 2022. LNCS, vol. 13752, pp. 227–243. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-21541-4_15

    Chapter  Google Scholar 

  14. Baader, F., Kriegel, F., Nuradiansyah, A.: Treating role assertions as first-class citizens in repair and error-tolerant reasoning. In: Proceedings of the 38th ACM/SIGAPP Symposium on Applied Computing (SAC 2023), Tallinn, Estonia, 27–31 March 2023, pp. 974–982. Association for Computing Machinery (2023). https://doi.org/10.1145/3555776.3577630

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

  16. Baader, F., Kriegel, F., Nuradiansyah, A., Peñaloza, R.: Computing compliant anonymisations of quantified ABoxes w.r.t. \(\cal{EL} \) policies. In: Pan, J.Z., et al. (eds.) ISWC 2020. LNCS, vol. 12506, pp. 3–20. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-62419-4_1

    Chapter  Google Scholar 

  17. Baader, F., Suntisrivaraporn, B.: Debugging SNOMED CT using axiom pinpointing in the description logic \(\cal{EL} ^+\). In: Cornet, R., Spackman, K.A. (eds.) Proceedings of the Third International Conference on Knowledge Representation in Medicine, Phoenix, Arizona, USA, 31st May–2nd June 2008. CEUR Workshop Proceedings, vol. 410. CEUR-WS.org (2008). http://ceur-ws.org/Vol-410/Paper01.pdf

  18. Brachman, R.J., Fikes, R., Levesque, H.J.: Krypton: a functional approach to knowledge representation. Computer 16(10), 67–73 (1983). https://doi.org/10.1109/MC.1983.1654200

    Article  Google Scholar 

  19. Colmerauer, A.: Prolog and infinite trees. In: Clark, K., Tarnlund, S.A. (eds.) Logic Programming, pp. 231–251. Academic Press, New York (1982)

    MATH  Google Scholar 

  20. Cuenca Grau, B., Kostylev, E.V.: Logical foundations of linked data anonymisation. J. Artif. Intell. Res. 64, 253–314 (2019). https://doi.org/10.1613/jair.1.11355

    Article  MathSciNet  MATH  Google Scholar 

  21. Du, J., Qi, G., Fu, X.: A practical fine-grained approach to resolving incoherent OWL 2 DL terminologies. In: Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM 2014), pp. 919–928 (2014). http://doi.acm.org/10.1145/2661829.2662046

  22. Greiner, R., Smith, B.A., Wilkerson, R.W.: A correction to the algorithm in Reiter’s theory of diagnosis. Artif. Intell. 41(1), 79–88 (1989). https://doi.org/10.1016/0004-3702(89)90079-9

    Article  MathSciNet  MATH  Google Scholar 

  23. Horridge, M., Parsia, B., Sattler, U.: Laconic and precise justifications in OWL. In: Sheth, A., et al. (eds.) ISWC 2008. LNCS, vol. 5318, pp. 323–338. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88564-1_21

    Chapter  Google Scholar 

  24. Kazakov, Y., Krötzsch, M., Simancik, F.: The incredible ELK - from polynomial procedures to efficient reasoning with \(\cal{EL} \) ontologies. J. Autom. Reason. 53(1), 1–61 (2014). https://doi.org/10.1007/s10817-013-9296-3

    Article  MathSciNet  MATH  Google Scholar 

  25. Kriegel, F.: Optimal fixed-premise repairs of \(\cal{EL} \) TBoxes. In: Bergmann, R., Malburg, L., Rodermund, S.C., Timm, I.J. (eds.) KI 2022. LNCS, vol. 13404, pp. 115–130. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15791-2_11

    Chapter  Google Scholar 

  26. Lam, J.S.C., Sleeman, D.H., Pan, J.Z., Vasconcelos, W.W.: A fine-grained approach to resolving unsatisfiable ontologies. J. Data Semant. 10, 62–95 (2008). https://doi.org/10.1007/978-3-540-77688-8_3

    Article  MATH  Google Scholar 

  27. Levesque, H.J.: Foundations of a functional approach to knowledge representation. Artif. Intell. 23(2), 155–212 (1984). https://doi.org/10.1016/0004-3702(84)90009-2

    Article  MATH  Google Scholar 

  28. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the description logic \(\cal{EL} \). J. Symb. Comput. 45(2), 194–228 (2010). https://doi.org/10.1016/j.jsc.2008.10.007

    Article  MATH  Google Scholar 

  29. Ortiz, M., Rudolph, S., Šimkus, M.: Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010 (2010). http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1296

  30. Parsia, B., Matentzoglu, N., Gonçalves, R.S., Glimm, B., Steigmiller, A.: The OWL reasoner evaluation (ORE) 2015 competition report. J. Autom. Reason. 59(4), 455–482 (2017). https://doi.org/10.1007/s10817-017-9406-8

    Article  MathSciNet  MATH  Google Scholar 

  31. Parsia, B., Rudolph, S., Hitzler, P., Krötzsch, M., Patel-Schneider, P.: OWL 2 web ontology language primer (second edition). W3C recommendation (2012). http://www.w3.org/TR/2012/REC-owl2-primer-20121211/

  32. Parsia, B., Sirin, E., Kalyanpur, A.: Debugging OWL ontologies. In: Ellis, A., Hagino, T. (eds.) Proceedings of the 14th International Conference on World Wide Web, WWW 2005, Chiba, Japan, 10–14 May 2005, pp. 633–640. ACM (2005). https://doi.org/10.1145/1060745.1060837

  33. Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987). https://doi.org/10.1016/0004-3702(87)90062-2. See the erratum [22]

  34. Schlobach, S., Huang, Z., Cornet, R., van Harmelen, F.: Debugging incoherent terminologies. J. Autom. Reason. 39(3), 317–349 (2007). https://doi.org/10.1007/s10817-007-9076-z

    Article  MathSciNet  MATH  Google Scholar 

  35. Troquard, N., Confalonieri, R., Galliani, P., Peñaloza, R., Porello, D., Kutz, O.: Repairing ontologies via axiom weakening. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI 2018), The 30th Innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI 2018), New Orleans, Louisiana, USA, 2–7 February 2018, pp. 1981–1988. AAAI Press (2018). https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17189

Download references

Acknowledgements

This work has been supported by Deutsche Forschungsgemeinschaft (DFG) in projects 430150274 (Repairing Description Logic Ontologies) and 389792660 (TRR 248: Foundations of Perspicuous Software Systems).

Author information

Authors and Affiliations

  1. Theoretical Computer Science, Technische Universität Dresden, Dresden, Germany

    Franz Baader, Patrick Koopmann & Francesco Kriegel

  2. Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden/Leipzig, Dresden, Germany

    Franz Baader

Authors
  1. Franz Baader
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Patrick Koopmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Francesco Kriegel
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

FB and FK contributed equally to the paper. PK ran the experiments and wrote the description of them. He also wrote a first version of the proof of the last proposition in Sect. 5 of [6].

Corresponding author

Correspondence to Franz Baader .

Editor information

Editors and Affiliations

  1. TU Dresden, Dresden, Germany

    Sarah Gaggl

  2. Artificial Intelligence Research Institute - IIIA CSIC, Barcelona, Spain

    Maria Vanina Martinez

  3. Umeå University, Umeå, Sweden

    Magdalena Ortiz

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Baader, F., Koopmann, P., Kriegel, F. (2023). Optimal Repairs in the Description Logic \(\mathcal{E}\mathcal{L}\) Revisited. In: Gaggl, S., Martinez, M.V., Ortiz, M. (eds) Logics in Artificial Intelligence. JELIA 2023. Lecture Notes in Computer Science(), vol 14281. Springer, Cham. https://doi.org/10.1007/978-3-031-43619-2_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-43619-2_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-43618-5

  • Online ISBN: 978-3-031-43619-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation