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

Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey

  • Chapter
  • First Online:
Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering (Reasoning Web 2016)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 9885))

Included in the following conference series:

Abstract

The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What ‘safe replacement’ means depends on the intended application of the ontology. If, for example, it is used to query data, then the answers to any relevant ontology-mediated query should be the same over any relevant data set; if, in contrast, the ontology is used for conceptual reasoning, then the entailed subsumptions between concept expressions should coincide. This gives rise to different notions of ontology inseparability such as query inseparability and concept inseparability, which generalize corresponding notions of conservative extensions. In this chapter, we survey results on various notions of inseparability in the context of description logic ontologies, discussing their applications, useful model-theoretic characterizations, algorithms for determining whether two ontologies are inseparable (and, sometimes, for computing the difference between them if they are not), and the computational complexity of this problem.

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

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.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.

    http://www.ihtsdo.org/snomed-ct.

  2. 2.

    For DLs that admit role inclusions, one additionally considers entailment of these.

  3. 3.

    An alternative elementary proof is given in [52].

  4. 4.

    This should not be confused with the size of uniform interpolants, which can even be triple exponential in \(\mathcal{EL}\) [54].

  5. 5.

    Similar robustness properties and notions of equivalence have been discussed in logic programming, we refer the reader to [69,70,71] and references therein. We will discuss this robustness property further in Sect. 8.

  6. 6.

    In fact, when we say ‘Horn DL’, we mean a DL in which every KB has a universal model.

  7. 7.

    \(\mathcal {I} _2'\) is a subinterpretation of \(\mathcal {I} _2\) if \(\varDelta ^{\smash {\mathcal {I} '_2}} \subseteq \varDelta ^{\smash {\mathcal {I} _2}}\), \(A^{\smash {\mathcal {I} '_2}} = A^{\smash {\mathcal {I} _2}} \cap \varDelta ^{\smash {\mathcal {I} '_2}}\) and \(r^{\smash {\mathcal {I} '_2}} = r^{\smash {\mathcal {I} _2}} \cap (\varDelta ^{\smash {\mathcal {I} '_2}} \times \varDelta ^{\smash {\mathcal {I} '_2}})\), for all concept names A and role names r.

  8. 8.

    Robustness under replacement can be defined for KBs as well and is equally important in that case. In this short discussion, however, we only consider TBox inseparability.

References

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

    MATH  Google Scholar 

  2. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 364–369 (2005)

    Google Scholar 

  3. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-Lite family. J. Autom. Reason. 39(3), 385–429 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  4. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009)

    MathSciNet  MATH  Google Scholar 

  5. Hustadt, U., Motik, B., Sattler, U.: Reasoning in description logics by a reduction to disjunctive Datalog. J. Autom. Reason. 39(3), 351–384 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  6. Kazakov, Y.: Consequence-driven reasoning for Horn-SHIQ ontologies. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 2040–2045 (2009)

    Google Scholar 

  7. Glimm, B., Lutz, C., Horrocks, I., Sattler, U.: Answering conjunctive queries in the \(\cal{SHIQ}\) description logic. J. Artif. Intell. Res. (JAIR) 31, 150–197 (2008)

    MATH  Google Scholar 

  8. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2006), pp. 260–270 (2006)

    Google Scholar 

  9. Calvanese, D., Eiter, T., Ortiz, M.: Answering regular path queries in expressive description logics: an automata-theoretic approach. In: Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI 2007), pp. 391–396 (2007)

    Google Scholar 

  10. Konev, B., Lutz, C., Walther, D., Wolter, F.: Formal properties of modularisation. In: Stuckenschmidt et al. [21], pp. 25–66. http://dx.doi.org/10.1007/978-3-642-01907-4_3

  11. Konev, B., Ludwig, M., Walther, D., Wolter, F.: The logical difference for the lightweight description logic EL. J. Artif. Intell. Res. (JAIR) 44, 633–708 (2012)

    MATH  Google Scholar 

  12. Conradi, R., Westfechtel, B.: Version models for software configuration management. ACM Comput. Surv. (CSUR) 30(2), 232–282 (1998)

    Article  Google Scholar 

  13. Noy, N.F., Musen, M.A.: PromptDiff: a fixed-point algorithm for comparing ontology versions. In: Proceedings of the 18th National Conference on Artificial Intelligence (AAAI 2002), pp. 744–750. AAAI Press, Menlo Park (2002)

    Google Scholar 

  14. Klein, M., Fensel, D., Kiryakov, A., Ognyanov, D.: Ontology versioning and change detection on the web. In: Gómez-Pérez, A., Benjamins, V.R. (eds.) EKAW 2002. LNCS (LNAI), vol. 2473, pp. 197–212. Springer, Heidelberg (2002). doi:10.1007/3-540-45810-7_20

    Chapter  Google Scholar 

  15. Redmond, T., Smith, M., Drummond, N., Tudorache, T.: Managing change: an ontology version control system. In: Proceedings of the 5th International Workshop on OWL: Experiences and Directions (OWLED 2008). CEUR Workshop Proceedings, vol. 432, CEUR-WS.org (2008)

    Google Scholar 

  16. Jimenez-Ruiz, E., Cuenca Grau, B., Horrocks, I., Llavori, R.B.: Supporting concurrent ontology development: framework, algorithms and tool. Data Knowl. Eng. 70(1), 146–164 (2011)

    Article  Google Scholar 

  17. Konev, B., Walther, D., Wolter, F.: The logical difference problem for description logic terminologies. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol. 5195, pp. 259–274. Springer, Heidelberg (2008). doi:10.1007/978-3-540-71070-7_21

    Chapter  Google Scholar 

  18. Kontchakov, R., Wolter, F., Zakharyaschev, M.: Can you tell the difference between DL-Lite ontologies. In: Proceedings of the 11th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2008), pp. 285–295 (2008)

    Google Scholar 

  19. Ghilardi, S., Lutz, C., Wolter, F.: Did I damage my ontology? A case for conservative extensions in description logic. In: Proceedings of the 10th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2006), pp. 187–197. AAAI Press (2006)

    Google Scholar 

  20. Cuenca-Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontologies: theory and practice. J. Artif. Intell. Res. (JAIR) 31, 273–318 (2008)

    MathSciNet  MATH  Google Scholar 

  21. Stuckenschmidt, H., Parent, C., Spaccapietra, S. (eds.): Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization. LNCS, vol. 5445. Springer, Heidelberg (2009)

    MATH  Google Scholar 

  22. Kutz, O., Mossakowski, T., Lücke, D.: Carnap, Goguen, and the hyperontologies: logical pluralism and heterogeneous structuring in ontology design. Log. Univers. 4(2), 255–333 (2010). doi:10.1007/s11787-010-0020-3

    Article  MathSciNet  MATH  Google Scholar 

  23. Kontchakov, R., Wolter, F., Zakharyaschev, M.: Logic-based ontology comparison and module extraction, with an application to DL-Lite. Artif. Intell. 174, 1093–1141 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Shvaiko, P., Euzenat, J.: Ontology matching: state of the art and future challenges. IEEE Trans. Knowl. Data Eng. 25(1), 158–176 (2013). doi:10.1109/TKDE.2011.253

    Article  Google Scholar 

  25. Solimando, A., Jiménez-Ruiz, E., Guerrini, G.: Detecting and correcting conservativity principle violations in ontology-to-ontology mappings. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8797, pp. 1–16. Springer, Heidelberg (2014). doi:10.1007/978-3-319-11915-1_1

    Google Scholar 

  26. Kharlamov, E., et al.: Ontology based access to exploration data at Statoil. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9367, pp. 93–112. Springer, Heidelberg (2015). doi:10.1007/978-3-319-25010-6_6

    Chapter  Google Scholar 

  27. Jiménez-Ruiz, E., Payne, T.R., Solimando, A., Tamma, V.A.M.: Limiting logical violations in ontology alignnment through negotiation. In: Proceedings of the 15th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2016), pp. 217–226 (2016)

    Google Scholar 

  28. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005). doi:10.1016/j.tcs.2004.10.033

    Article  MathSciNet  MATH  Google Scholar 

  29. Arenas, M., Botoeva, E., Calvanese, D., Ryzhikov, V.: Knowledge base exchange: the case of OWL 2 QL. Artif. Intell. 238, 11–62 (2016). ISSN 0004-3702

    Article  MathSciNet  MATH  Google Scholar 

  30. Cuenca-Grau, B., Motik, B.: Reasoning over ontologies with hidden content: the import-by-query approach. J. Artif. Intell. Res. (JAIR) 45, 197–255 (2012)

    MathSciNet  MATH  Google Scholar 

  31. Reiter, R., Lin, F.: Forget it! In: Proceedings of AAAI Fall Symposium on Relevance, pp. 154–159 (1994)

    Google Scholar 

  32. Pitts, A.: On an interpretation of second-order quantification in first-order intuitionistic propositional logic. J. Symb. Logic 57, 33–52 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  33. D’Agostino, G., Hollenberg, M.: Uniform interpolation, automata, and the modal \(\mu \)-calculus. In: Advances in Modal Logic, vol. 1 (1998)

    Google Scholar 

  34. Visser, A.: Uniform interpolation and layered bisimulation. In: Hájek, P. (ed.) Gödel ’96 (Brno, 1996). Lecture Notes Logic, vol. 6. Springer, Berlin (1996)

    Google Scholar 

  35. Ghilardi, S., Zawadowski, M.: Undefinability of propositional quantifiers in the modal system S4. Stud. Logica 55, 259–271 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  36. French, T.: Bisimulation quantifiers for modal logics. Ph.D. thesis, University of Western Australia (2006)

    Google Scholar 

  37. Su, K., Sattar, A., Lv, G., Zhang, Y.: Variable forgetting in reasoning about knowledge. J. Artif. Intell. Res. (JAIR) 35, 677–716 (2009). doi:10.1613/jair.2750

    MathSciNet  MATH  Google Scholar 

  38. Konev, B., Walther, D., Wolter, F.: Forgetting and uniform interpolation in large-scale description logic terminologies. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 830–835 (2009). http://ijcai.org/papers09/Papers/IJCAI09-142.pdf

  39. Wang, Z., Wang, K., Topor, R.W., Pan, J.Z.: Forgetting for knowledge bases in DL-Lite. Ann. Math. Artif. Intell. 58(1–2), 117–151 (2010). doi:10.1007/s10472-010-9187-9

    Article  MathSciNet  MATH  Google Scholar 

  40. Lutz, C., Wolter, F.: Foundations for uniform interpolation and forgetting in expressive description logics. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 989–995. IJCAI/AAAI (2011)

    Google Scholar 

  41. Wang, K., Wang, Z., Topor, R.W., Pan, J.Z., Antoniou, G.: Eliminating concepts and roles from ontologies in expressive descriptive logics. Comput. Intell. 30(2), 205–232 (2014). doi:10.1111/j.1467-8640.2012.00442.x

    Article  MathSciNet  MATH  Google Scholar 

  42. Koopmann, P., Schmidt, R.A.: Count and forget: uniform interpolation of \(\cal{SHQ}\)-ontologies. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014. LNCS (LNAI), vol. 8562, pp. 434–448. Springer, Heidelberg (2014). doi:10.1007/978-3-319-08587-6_34

    Google Scholar 

  43. Nikitina, N., Rudolph, S.: (Non-)succinctness of uniform interpolants of general terminologies in the description logic EL. Artif. Intell. 215, 120–140 (2014). doi:10.1016/j.artint.2014.06.005

    Article  MathSciNet  MATH  Google Scholar 

  44. Koopmann, P., Schmidt, R.A.: Uniform interpolation and forgetting for \(\cal{ALC}\) ontologies with ABoxes. In: Proceedings of the 29th National Conference on Artificial Intelligence (AAAI 2015), pp. 175–181 (2015). http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9981

  45. Goranko, V., Otto, M.: Model theory of modal logic. In: Blackburn, P., van Benthem, J., Wolter, F. (eds.) Handbook of Modal Logic, pp. 249–330. Elsevier, Amsterdam (2006)

    Google Scholar 

  46. Lutz, C., Piro, R., Wolter, F.: Description logic TBoxes: model-theoretic characterizations and rewritability. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 983–988. AAAI Press, Menlo Park (2011)

    Google Scholar 

  47. Lutz, C., Walther, D., Wolter, F.: Conservative extensions in expressive description logics. In: Proceedings of the 20th Internatioanl Joint Conference on Artificial Intelligence (IJCAI), pp. 453–458. AAAI Press, Menlo Park (2007)

    Google Scholar 

  48. Wilke, T.: Alternating tree automata, parity games, and modal \(\mu \)-calculus. Bull. Belgian Math. Soc. 8(2), 359–391 (2001)

    MathSciNet  MATH  Google Scholar 

  49. Konev, B., Lutz, C., Wolter, F., Zakharyaschev, M.: Conservative rewritability of description logic TBoxes. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016) (2016)

    Google Scholar 

  50. Horrocks, I., Sattler, U.: A description logic with transitive and inverse roles and role hierarchies. J. Log. Comput. 9(3), 385–410 (1999). doi:10.1093/logcom/9.3.385

    Article  MathSciNet  MATH  Google Scholar 

  51. Ghilardi, S., Lutz, C., Wolter, F., Zakharyaschev, M.: Conservative extensions in modal logics. In: Proceedings of the AiML, vol. 6, pp. 187–207 (2006)

    Google Scholar 

  52. Lutz, C., Wolter, F.: Deciding inseparability and conservative extensions in the description logic EL. J. Symb. Comput. 45(2), 194–228 (2010)

    Article  MATH  Google Scholar 

  53. Lutz, C., Seylan, I., Wolter, F.: An automata-theoretic approach to uniform interpolation and approximation in the description logic EL. In: Proceedings of the 13th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2012), pp. 286–296. AAAI Press (2012)

    Google Scholar 

  54. Nikitina, N., Rudolph, S.: ExpExpExplosion: uniform interpolation in general EL terminologies. In: Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 618–623 (2012). doi:10.3233/978-1-61499-098-7-618

  55. Clarke, E., Schlingloff, H.: Model checking. In: Handbook of Automated Reasoning, vol. II, chap. 24, pp. 1635–1790. Elsevier (2001)

    Google Scholar 

  56. Ludwig, M., Walther, D.: The logical difference for \(\cal{ELH}^r\)-terminologies using hypergraphs. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014). Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 555–560. IOS Press (2014)

    Google Scholar 

  57. Feng, S., Ludwig, M., Walther, D.: Foundations for the logical difference of EL-TBoxes. In: Global Conference on Artificial Intelligence (GCAI 2015). EPiC Series in Computing, vol. 36, pp. 93–112. EasyChair (2015). ISSN 2040-557X

    Google Scholar 

  58. Byers, P., Pitt, D.: Conservative extensions: a cautionary note. EATCS-Bull. 41, 196–201 (1990)

    MATH  Google Scholar 

  59. Veloso, P.: Yet another cautionary note on conservative extensions: a simple case with a computing flavour. EATCS-Bull. 46, 188–193 (1992)

    MATH  Google Scholar 

  60. Veloso, P., Veloso, S.: Some remarks on conservative extensions. A socratic dialog. EATCS-Bull. 43, 189–198 (1991)

    MATH  Google Scholar 

  61. Diaconescu, J.G.R., Stefaneas, P.: Logical support for modularisation. In: Huet, G., Plotkin, G. (eds.) Logical Environments (1993)

    Google Scholar 

  62. Maibaum, T.S.E.: Conservative extensions, interpretations between theories and all that!. In: Bidoit, M., Dauchet, M. (eds.) CAAP 1997. LNCS, vol. 1214, pp. 40–66. Springer, Heidelberg (1997). doi:10.1007/BFb0030588

    Chapter  Google Scholar 

  63. Konev, B., Lutz, C., Walther, D., Wolter, F.: Model-theoretic inseparability and modularity of description logic ontologies. Artif. Intell. 203, 66–103 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  64. Berger, R.: The Undecidability of the Domino Problem. Memoirs of the AMS, issue 66. American Mathematical Society, Providence (1966)

    Google Scholar 

  65. Robinson, R.: Undecidability and nonperiodicity for tilings of the plane. Inventiones Math. 12, 177–209 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  66. Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, Heidelberg (1997)

    Book  MATH  Google Scholar 

  67. Feferman, S., Vaught, R.L.: The first-order properties of algebraic systems. Fundamenta Math. 47, 57–103 (1959)

    MathSciNet  MATH  Google Scholar 

  68. Bonatti, P., Faella, M., Lutz, C., Sauro, L., Wolter, F.: Decidability of circumscribed description logics revisited. In: Eiter, T., Strass, H., Truszczyński, M., Woltran, S. (eds.) Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation. LNCS (LNAI), vol. 9060, pp. 112–124. Springer, Heidelberg (2015). doi:10.1007/978-3-319-14726-0_8

    Chapter  Google Scholar 

  69. Maher, M.J.: Equivalences of logic programs. In: Foundations of Deductive Databases and Logic Programming, pp. 627–658. Morgan Kaufmann (1988)

    Google Scholar 

  70. Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Trans. Comput. Logic 2(4), 526–541 (2001). doi:10.1145/502166.502170

    Article  MathSciNet  Google Scholar 

  71. Eiter, T., Fink, M.: Uniform equivalence of logic programs under the stable model semantics. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 224–238. Springer, Heidelberg (2003). doi:10.1007/978-3-540-24599-5_16

    Chapter  Google Scholar 

  72. Cuenca Grau, B., Horrocks, I., Kazakov, Y., Sattler, U.: Extracting modules from ontologies: a logic-based approach. In: Stuckenschmidt, H., Parent, C., Spaccapietra, S. (eds.) Modular Ontologies. LNCS, vol. 5445, pp. 159–186. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01907-4_8

    Chapter  Google Scholar 

  73. Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: Just the right amount: extracting modules from ontologies. In: Proceedings of the 16th International World Wide Web Conference (WWW 2007), pp. 717–726. ACM (2007)

    Google Scholar 

  74. Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: A logical framework for modularity of ontologies. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 298–303 (2007)

    Google Scholar 

  75. Sattler, U., Schneider, T., Zakharyaschev, M.: Which kind of module should I extract? In: Proceedings of the 22th International Workshop on Description Logics (DL 2009). CEUR Workshop Proceedings, vol. 477. CEUR-WS.org (2009)

    Google Scholar 

  76. Romero, A.A., Grau, B.C., Horrocks, I., Jiménez-Ruiz, E.: MORe: a modular OWL reasoner for ontology classification. In: ORE. CEUR Workshop Proceedings, vol. 1015, pp. 61–67. CEUR-WS.org (2013)

    Google Scholar 

  77. Romero, A.A., Grau, B.C., Horrocks, I.: Modular combination of reasoners for ontology classification. In: Proceedings of the 25th International Workshop on Description Logics (DL 2012). CEUR Workshop Proceedings, vol. 846. CEUR-WS.org (2012)

    Google Scholar 

  78. Romero, A.A., Kaminski, M., Grau, B.C., Horrocks, I.: Module extraction in expressive ontology languages via Datalog reasoning. J. Artif. Intell. Res. (JAIR) 55, 499–564 (2016)

    MathSciNet  MATH  Google Scholar 

  79. Bienvenu, M., ten Cate, B., Lutz, C., Wolter, F.: Ontology-based data access a study through Disjunctive Datalog, CSP, and MMSNP. ACM Trans. Database Syst. 39(4), 33:1–33:44 (2014)

    Article  MathSciNet  Google Scholar 

  80. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semant. 10, 133–173 (2008)

    MATH  Google Scholar 

  81. Botoeva, E., Kontchakov, R., Ryzhikov, V., Wolter, F., Zakharyaschev, M.: Games for query inseparability of description logic knowledge bases. Artif. Intell. 234, 78–119 (2016). doi:10.1016/j.artint.2016.01.010. http://www.sciencedirect.com/science/article/pii/S0004370216300017, ISSN 0004-3702

    Article  MathSciNet  MATH  Google Scholar 

  82. Lutz, C., Wolter, F.: Non-uniform data complexity of query answering in description logics. In: Proceedings of KR. AAAI Press (2012)

    Google Scholar 

  83. Chang, C.C., Keisler, H.J.: Model Theory. Studies in Logic and the Foundations of Mathematics, vol. 73. Elsevier, Amsterdam (1990)

    Google Scholar 

  84. Botoeva, E., Lutz, C., Ryzhikov, V., Wolter, F., Zakharyaschev, M.: Query-based entailment and inseparability for ALC ontologies (Full Version). CoRR Technical report abs/1604.04164, arXiv.org e-Print archive (2016). http://arxiv.org/abs/1604.04164

  85. Botoeva, E., Lutz, C., Ryzhikov, V., Wolter, F., Zakharyaschev, M.: Query-based entailment and inseparability for ALC ontologies. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pp. 1001–1007 (2016)

    Google Scholar 

  86. Schaerf, A.: Query answering in concept-based knowledge representation systems: algorithms, complexity, and semantic issues. Ph.D. thesis, Dipartimento di Informatica e Sistemistica, Università di Roma La Sapienza (1994)

    Google Scholar 

  87. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Boston (1995)

    MATH  Google Scholar 

  88. Mazala, R.: Infinite games. In: Grädel, E., Thomas, W., Wilke, T. (eds.) Automata Logics, and Infinite Games. LNCS, vol. 2500, pp. 23–38. Springer, Heidelberg (2002). doi:10.1007/3-540-36387-4_2

    Chapter  Google Scholar 

  89. Chatterjee, K., Henzinger, M.: An O(\(n^2\)) time algorithm for alternating Büchi games. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1386–1399. SIAM (2012)

    Google Scholar 

  90. Baader, F., Bienvenu, M., Lutz, C., Wolter, F.: Query and predicate emptiness in ontology-based data access. J. Artif. Intell. Res. (JAIR) 56, 1–59 (2016)

    MathSciNet  MATH  Google Scholar 

  91. Konev, B., Ludwig, M., Wolter, F.: Logical Difference Computation with CEX2.5. In: Gramlich, B., Miller, D., Sattler, U. (eds.) IJCAR 2012. LNCS (LNAI), vol. 7364, pp. 371–377. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31365-3_29

    Chapter  Google Scholar 

  92. Bienvenu, M., Hansen, P., Lutz, C., Wolter, F.: First order-rewritability and containment of conjunctive queries in Horn description logics. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pp. 965–971 (2016)

    Google Scholar 

  93. Bienvenu, M., Rosati, R.: Query-based comparison of mappings in ontology-based data access. In: Proceedings of the 15th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2016), pp. 197–206 (2016). http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12902

  94. Arenas, M., Gottlob, G., Pieris, A.: Expressive languages for querying the semantic web. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014, Snowbird, UT, USA, 22–27 June 2014, pp. 14–26 (2014). doi:10.1145/2594538.2594555

  95. Fagin, R., Kolaitis, P.G., Nash, A., Popa, L.: Towards a theory of schema-mapping optimization. In: Proceedings of the 27th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS 2008), pp. 33–42 (2008). doi:10.1145/1376916.1376922

  96. Pichler, R., Sallinger, E., Savenkov, V.: Relaxed notions of schema mapping equivalence revisited. Theory Comput. Syst. 52(3), 483–541 (2013). doi:10.1007/s00224-012-9397-0

    Article  MathSciNet  MATH  Google Scholar 

  97. Konev, B., Kontchakov, R., Ludwig, M., Schneider, T., Wolter, F., Zakharyaschev, M.: Conjunctive query inseparability of OWL 2 QL TBoxes. In: Proceedings of the 25th National Conference on Artificial Intelligence (AAAI 2011), pp. 221–226. AAAI Press (2011)

    Google Scholar 

  98. Vescovo, C., Klinov, P., Parsia, B., Sattler, U., Schneider, T., Tsarkov, D.: Empirical study of logic-based modules: cheap is cheerful. In: Alani, H., et al. (eds.) ISWC 2013. LNCS, vol. 8218, pp. 84–100. Springer, Heidelberg (2013). doi:10.1007/978-3-642-41335-3_6

    Chapter  Google Scholar 

  99. Gatens, W., Konev, B., Wolter, F.: Lower and upper approximations for depleting modules of description logic ontologies. In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), vol. 263, pp. 345–350. IOS Press (2014)

    Google Scholar 

  100. Nortje, R., Britz, A., Meyer, T.: Module-theoretic properties of reachability modules for SRIQ. In: Proceedings of the 26th International Workshop on Description Logics (DL 2013). CEUR Workshop Proceedings, vol. 1014, pp. 868–884. CEUR-WS.org (2013)

    Google Scholar 

  101. Nortje, R., Britz, K., Meyer, T.: Reachability modules for the description logic \(\cal{SRIQ}\). In: McMillan, K., Middeldorp, A., Voronkov, A. (eds.) LPAR 2013. LNCS, vol. 8312, pp. 636–652. Springer, Heidelberg (2013). doi:10.1007/978-3-642-45221-5_42

    Chapter  Google Scholar 

  102. Gonçalves, R.S., Parsia, B., Sattler, U.: Concept-based semantic difference in expressive description logics. In: Cudré-Mauroux, P., et al. (eds.) ISWC 2012. LNCS, vol. 7649, pp. 99–115. Springer, Heidelberg (2012). doi:10.1007/978-3-642-35176-1_7

    Chapter  Google Scholar 

  103. Wang, K., Wang, Z., Topor, R., Pan, J.Z., Antoniou, G.: Concept and role forgetting in \({\cal{ALC}}\) ontologies. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 666–681. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04930-9_42

    Chapter  Google Scholar 

  104. Zhou, Y., Zhang, Y.: Bounded forgetting. In: Burgard, W., Roth, D. (eds.) Proceedings of the 25th National Conference on Artificial Intelligence (AAAI 2011). AAAI Press (2011)

    Google Scholar 

  105. Ludwig, M., Konev, B.: Practical uniform interpolation and forgetting for \(\cal{ALC}\) tboxes with applications to logical difference. In: Proceedings of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR 2014). AAAI Press (2014)

    Google Scholar 

  106. Gabbay, D.M., Schmidt, R.A., Szałas, A.: Second-Order Quantifier Elimination: Foundations, Computational Aspects and Applications. Studies in Logic: Mathematical Logic and Foundations, vol. 12. College Publications (2008). ISBN 978-1-904987-56-7

    Google Scholar 

  107. Zhao, Y., Schmidt, R.A.: Concept forgetting in \(\cal{ALCOI}\)-ontologies using an ackermann approach. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9366, pp. 587–602. Springer, Heidelberg (2015). doi:10.1007/978-3-319-25007-6_34

    Chapter  Google Scholar 

Download references

Acknowledgments

Elena Botoeva was supported by EU IP project Optique, grant n. FP7-318338. Carsten Lutz was supported by ERC grant 647289. Boris Konev, Frank Wolter and Michael Zakharyaschev were supported by the UK EPSRC grants EP/M012646, EP/M012670, EP/H043594, and EP/H05099X.

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Free University of Bozen-Bolzano, Bolzano, Italy

    Elena Botoeva & Vladislav Ryzhikov

  2. Department of Computer Science, University of Liverpool, Liverpool, UK

    Boris Konev & Frank Wolter

  3. Faculty of Informatics, University of Bremen, Bremen, Germany

    Carsten Lutz

  4. Department of Computer Science and Information Systems, Birkbeck University of London, London, UK

    Michael Zakharyaschev

Authors
  1. Elena Botoeva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Boris Konev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carsten Lutz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vladislav Ryzhikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Frank Wolter
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Michael Zakharyaschev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frank Wolter .

Editor information

Editors and Affiliations

  1. University of Aberdeen , Aberdeen, United Kingdom

    Jeff Z. Pan

  2. Free University of Bozen-Bolzano , Bolzano, Italy

    Diego Calvanese

  3. University of Technology Vienna , Vienna, Austria

    Thomas Eiter

  4. University of Oxford , Oxford, United Kingdom

    Ian Horrocks

  5. Stony Brook University , Stony Brook, New York, USA

    Michael Kifer

  6. University of Science and Technology , Hong Kong, China

    Fangzhen Lin

  7. University of Aberdeen , Aberdeen, United Kingdom

    Yuting Zhao

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this chapter

Cite this chapter

Botoeva, E., Konev, B., Lutz, C., Ryzhikov, V., Wolter, F., Zakharyaschev, M. (2017). Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey. In: Pan, J., et al. Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering. Reasoning Web 2016. Lecture Notes in Computer Science(), vol 9885. Springer, Cham. https://doi.org/10.1007/978-3-319-49493-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-49493-7_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-49492-0

  • Online ISBN: 978-3-319-49493-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation