×

Games for query inseparability of description logic knowledge bases. (English) Zbl 1351.68263

Summary: We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature – a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-\(\mathcal{ALCHI}\), including the description logics underpinning OWL2QL and OWL2EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL2QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.

MSC:

68T27 Logic in artificial intelligence
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation
91A43 Games involving graphs
91A80 Applications of game theory

Software:

Ontop; ContentCVS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Polleres, A.; Hogan, A.; Delbru, R.; Umbrich, J., RDFS and OWL reasoning for Linked Data, (The 9th Int. Summer School on Reasoning Web (RW 2013). The 9th Int. Summer School on Reasoning Web (RW 2013), Lecture Notes in Computer Science, vol. 8067 (2013), Springer), 91-149
[2] Poggi, A.; Lembo, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Rosati, R., Linking data to ontologies, J. Data Semant., 10, 133-173 (2008) · Zbl 1132.68061
[3] Giese, M.; Calvanese, D.; Haase, P.; Horrocks, I.; Ioannidis, Y.; Kllapi, H.; Koubarakis, M.; Lenzerini, M.; Möller, R.; Rodriguez-Muro, M.; Özcep, O.; Rosati, R.; Schlatte, R.; Schmidt, M.; Soylu, A.; Waaler, A., Scalable end-user access to big data, (Big Data Computing (2013), CRC Press)
[4] Hitzler, P.; Krötzsch, M.; Rudolph, S., Foundations of Semantic Web Technologies (2009), Chapman & Hall/CRC
[5] Hustadt, U.; Motik, B.; Sattler, U., Data complexity of reasoning in very expressive description logics, (Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI) (2005)), 466-471
[6] 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, 385-429 (2007) · Zbl 1132.68725
[7] Lutz, C.; Toman, D.; Wolter, F., Conjunctive query answering in the description logic EL using a relational database system, (Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI) (2009)), 2070-2075
[8] Kontchakov, R.; Zakharyaschev, M., An introduction to description logics and query rewriting, (The 10th Int. Summer School on Reasoning Web (RW 2014). The 10th Int. Summer School on Reasoning Web (RW 2014), Lecture Notes in Computer Science, vol. 8714 (2014), Springer), 195-244
[9] Jiménez Ruiz, E.; Cuenca Grau, B.; Horrocks, I.; Berlanga, R., Supporting concurrent ontology development: framework, algorithms and tool, Data Knowl. Eng., 70, 146-164 (2011)
[10] Konev, B.; Ludwig, M.; Walther, D.; Wolter, F., The logical difference for the lightweight description logic EL, J. Artif. Intell. Res., 44, 633-708 (2012) · Zbl 1253.68303
[11] (Stuckenschmidt, H.; Parent, C.; Spaccapietra, S., Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization. Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, Lecture Notes in Computer Science, vol. 5445 (2009), Springer) · Zbl 1163.68005
[12] Konev, B.; Walther, D.; Wolter, F., Forgetting and uniform interpolation in large-scale description logic terminologies, (Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI) (2009), AAAI Press), 830-835
[13] Koopmann, P.; Schmidt, R. A., Uniform interpolation and forgetting for ALC ontologies with ABoxes, (Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015) (2015), AAAI Press), 175-181
[14] Arenas, M.; Barceló, P.; Libkin, L.; Murlak, F., Foundations of Data Exchange (2014), Cambridge University Press
[15] Arenas, M.; Botoeva, E.; Calvanese, D.; Ryzhikov, V.; Sherkhonov, E., Exchanging description logic knowledge bases, (Proc. of the 13th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2012) (2012), AAAI Press), 563-567
[16] Arenas, M.; Pérez, J.; Reutter, J. L., Data exchange beyond complete data, J. ACM, 60, 28 (2013) · Zbl 1281.68105
[17] 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) · Zbl 1238.68154
[18] Shvaiko, P.; Euzenat, J., Ontology matching: state of the art and future challenges, IEEE Trans. Knowl. Data Eng., 25, 158-176 (2013)
[19] Cuenca Grau, B.; Motik, B., Reasoning over ontologies with hidden content: the import-by-query approach, J. Artif. Intell. Res., 45, 197-255 (2012) · Zbl 1280.68251
[20] Krötzsch, M.; Rudolph, S.; Hitzler, P., Complexities of Horn description logics, ACM Trans. Comput. Log., 14, 2 (2013) · Zbl 1353.68268
[21] Artale, A.; Calvanese, D.; Kontchakov, R.; Zakharyaschev, M., The DL-Lite family and relations, J. Artif. Intell. Res., 36, 1-69 (2009) · Zbl 1192.68657
[22] Baader, F.; Brandt, S.; Lutz, C., Pushing the EL envelope, (Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI) (2005)), 364-369
[23] Arenas, M.; Botoeva, E.; Calvanese, D.; Ryzhikov, V., Exchanging OWL 2 QL knowledge bases, (Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI 2013) (2013), IJCAI/AAAI)
[24] Konev, B.; Kontchakov, R.; Ludwig, M.; Schneider, T.; Wolter, F.; Zakharyaschev, M., Conjunctive query inseparability of OWL 2 QL TBoxes, (Proc. of the 25th AAAI Conf. on Artificial Intelligence (AAAI 2011) (2011), AAAI Press), 221-226
[25] Imieliński, T.; Lipski, W., Incomplete information in relational databases, J. ACM, 31, 761-791 (1984) · Zbl 0632.68094
[26] Kazakov, Y., Consequence-driven reasoning for Horn SHIQ ontologies, (Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI) (2009)), 2040-2045
[27] Rosati, R., On conjunctive query answering in EL, (Proc. of the 2007 Int. Workshop on Description Logics (DL 2007), vol. 250 (2007), CEUR-WS)
[28] Eiter, T.; Gottlob, G.; Ortiz, M.; Simkus, M., Query answering in the description logic Horn-\(SHIQ\), (Proc. of the 11th European Conf. on Logics in Artificial Intelligence (JELIA 2008). Proc. of the 11th European Conf. on Logics in Artificial Intelligence (JELIA 2008), Lecture Notes in Computer Science, vol. 5293 (2008), Springer), 166-179 · Zbl 1178.68558
[29] Tobies, S., Complexity results and practical algorithms for logics in knowledge representation (2001), LuFG Theoretical Computer Science, RWTH-Aachen: LuFG Theoretical Computer Science, RWTH-Aachen Germany, Ph.D. thesis
[30] Brandt, S., Polynomial time reasoning in a description logic with existential restrictions, GCI axioms, and—what else?, (Proc. of the 16th European Conf. on Artificial Intelligence (ECAI 2004) (2004), IOS Press), 298-302
[31] Lutz, C.; Wolter, F., Deciding inseparability and conservative extensions in the description logic EL, J. Symb. Comput., 45, 194-228 (2010) · Zbl 1187.68572
[32] Mazala, R., Infinite games, (Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], Lecture Notes in Computer Science, vol. 2500 (2002), Springer), 23-42
[33] Chatterjee, K.; Henzinger, M., An \(O(n^2)\) time algorithm for alternating Büchi games, (Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) (2012), SIAM), 1386-1399 · Zbl 1421.68110
[34] Kozen, D., Theory of Computation (2006), Springer
[35] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[36] Wang, Z.; Wang, K.; Topor, R. W.; Pan, J. Z., Forgetting for knowledge bases in DL-Lite, Ann. Math. Artif. Intell., 58, 117-151 (2010) · Zbl 1205.68410
[37] Cuenca Grau, B.; Horrocks, I.; Kazakov, Y.; Sattler, U., Modular reuse of ontologies: theory and practice, J. Artif. Intell. Res., 31, 273-318 (2008) · Zbl 1183.68479
[38] Del Vescovo, C.; Parsia, B.; Sattler, U.; Schneider, T., The modular structure of an ontology: atomic decomposition, (Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI 2011) (2011), AAAI Press), 2232-2237
[39] Nikitina, N.; Rudolph, S., (Non-)succinctness of uniform interpolants of general terminologies in the description logic EL, Artif. Intell., 215, 120-140 (2014) · Zbl 1308.68110
[40] Nikitina, N.; Glimm, B., Hitting the sweetspot: economic rewriting of knowledge bases, (Proc. of the 11th Int. Semantic Web Conf. (ISWC 2012), Part I. Proc. of the 11th Int. Semantic Web Conf. (ISWC 2012), Part I, Lecture Notes in Computer Science, vol. 7649 (2012), Springer), 394-409
[41] Lutz, C.; Seylan, I.; Wolter, F., An automata-theoretic approach to uniform interpolation and approximation in the description logic EL, (Proc. of the 13th Int. Conf. on Principles of Knowledge Representation (KR 2012) (2012), AAAI Press), 286-296
[42] Koopmann, P.; Schmidt, R. A., Count and forget: uniform interpolation of \(SHQ\)-ontologies, (Proc. of the 7th Int. Joint Conf. on Automated Reasoning (IJCAR 2014). Proc. of the 7th Int. Joint Conf. on Automated Reasoning (IJCAR 2014), Lecture Notes in Computer Science, vol. 8562 (2014), Springer), 434-448 · Zbl 1423.68482
[43] Nortje, R.; Britz, K.; Meyer, T., Reachability modules for the description logic \(SRIQ\), (Proc. of 19th Int. Conf. on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-19). Proc. of 19th Int. Conf. on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-19), Lecture Notes in Computer Science, vol. 8312 (2013), Springer), 636-652 · Zbl 1407.68475
[44] Rodriguez-Muro, M.; Kontchakov, R.; Zakharyaschev, M., Ontology-based data access: ontop of databases, (Proc. of the 12th Int. Semantic Web Conf. (ISWC 2013), Part I. Proc. of the 12th Int. Semantic Web Conf. (ISWC 2013), Part I, Lecture Notes in Computer Science, vol. 8218 (2013), Springer), 558-573
[45] Bienvenu, M.; Rosati, R., Query-based comparison of OBDA specifications, (Proc. of the 28th Int. Workshop on Description Logics (DL 2015), vol. 1350 (2015), CEUR-WS)
[46] Lutz, C.; Wolter, F., Foundations for uniform interpolation and forgetting in expressive description logics, (Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI 2011) (2011), IJCAI/AAAI), 989-995
[47] Patel-Schneider, P. F., Analyzing Schema.org, (Proc. of the 13th Int. Semantic Web Conf. (ISWC 2014), Part I. Proc. of the 13th Int. Semantic Web Conf. (ISWC 2014), Part I, Lecture Notes in Computer Science, vol. 8796 (2014), Springer), 261-276
[48] Hernich, A.; Lutz, C.; Ozaki, A.; Wolter, F., Schema.org as a description logic, (Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI 2015) (2015), AAAI Press), 3048-3054
[49] Lutz, C.; Wolter, F., Non-uniform data complexity of query answering in description logics, (Proc. of the 13th Int. Conf. on Principles of Knowledge Representation (KR 2012) (2012), AAAI Press), 297-307
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.