A tetrachotomy of ontology-mediated queries with a covering axiom. (English) Zbl 07554486
Summary: Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to standard database queries. Originated in ontology-based data access and datalog optimisation, this problem is known to be computationally very complex in general, with no explicit syntactic characterisations available. In this article, aiming to understand the fundamental roots of this difficulty, we strip the problem to the bare bones and focus on Boolean conjunctive queries mediated by a simple covering axiom stating that one class is covered by the union of two other classes. We show that, on the one hand, these rudimentary ontology-mediated queries, called disjunctive sirups (or d-sirups), capture many features and difficulties of the general case. For example, answering d-sirups is \(\Pi_2^p\)-complete for combined complexity and can be in or L-, NL-, P-, or coNP-complete for data complexity (with the problem of recognising FO-rewritability of d-sirups being \(2\)ExpTime-hard); some d-sirups only have exponential-size resolution proofs, some only double-exponential-size positive existential FO-rewritings and single-exponential-size nonrecursive datalog rewritings. On the other hand, we prove a few partial sufficient and necessary conditions of FO- and (symmetric/linear-) datalog rewritability of d-sirups. Our main technical result is a complete and transparent syntactic \(\mathrm{AC}^0/\mathrm{NL}/\mathrm{P}/\mathrm{coNP}\) tetrachotomy of d-sirups with disjoint covering classes and a path-shaped Boolean conjunctive query. To obtain this tetrachotomy, we develop new techniques for establishing P- and coNP-hardness of answering non-Horn ontology-mediated queries as well as showing that they can be answered in NL.
MSC:
| 68T30 | Knowledge representation |
Keywords:
ontology-mediated query; description logic; Datalog; disjunctive Datalog; first-order rewritability; data complexityReferences:
| [1] | Schaerf, A., On the complexity of the instance checking problem in concept languages with existential quantification, J. Intell. Inf. Syst., 2, 265-278 (1993) |
| [2] | (Baader, F.; Calvanese, D.; McGuinness, D. L.; Nardi, D.; Patel-Schneider, P. F., The Description Logic Handbook (2007), Cambridge University Press) · Zbl 1132.68055 |
| [3] | Baader, F.; Horrocks, I.; Lutz, C.; Sattler, U., An Introduction to Description Logic (2017), Cambridge University Press · Zbl 1373.68002 |
| [4] | Poggi, A.; Lembo, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Rosati, R., Linking data to ontologies, J. Data Semant. X, 133-173 (2008) · Zbl 1132.68061 |
| [5] | 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 |
| [6] | Xiao, G.; Calvanese, D.; Kontchakov, R.; Lembo, D.; Poggi, A.; Rosati, R.; Zakharyaschev, M., Ontology-based data access: a survey, (Lang, J., Proc. IJCAI 2018 (2018)), 5511-5519 |
| [7] | Xiao, G.; Ding, L.; Cogrel, B.; Calvanese, D., Virtual knowledge graphs: an overview of systems and use cases, Data Intell., 1, 201-223 (2019) |
| [8] | Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Addison-Wesley · Zbl 0848.68031 |
| [9] | Immerman, N., Descriptive Complexity (1999), Springer · Zbl 0918.68031 |
| [10] | Civili, C.; Rosati, R., A broad class of first-order rewritable tuple-generating dependencies, (Proc. of the 2nd Int. Datalog 2.0 Workshop. Proc. of the 2nd Int. Datalog 2.0 Workshop, Lecture Notes in Computer Science, vol. 7494 (2012), Springer), 68-80 |
| [11] | Gottlob, G.; Orsi, G.; Pieris, A., Query rewriting and optimization for ontological databases, ACM Trans. Database Syst., 39, 25:1-25:46 (2014) · Zbl 1474.68103 |
| [12] | Baget, J.; Leclère, M.; Mugnier, M.; Salvat, E., On rules with existential variables: walking the decidability line, Artif. Intell., 175, 1620-1654 (2011) · Zbl 1225.68247 |
| [13] | König, M.; Leclère, M.; Mugnier, M.; Thomazo, M., Sound, complete and minimal UCQ-rewriting for existential rules, Semant. Web, 6, 451-475 (2015) |
| [14] | Hustadt, U.; Motik, B.; Sattler, U., Data complexity of reasoning in very expressive description logics, (Kaelbling, L. P.; Saffiotti, A., Proc. IJCAI 2005 (2005), Professional Book Center), 466-471 |
| [15] | Rosati, R., On conjunctive query answering in EL, (Calvanese, D.; Franconi, E.; Haarslev, V.; Lembo, D.; Motik, B.; Turhan, A.; Tessaris, S., Proc. DL 2007. Proc. DL 2007, CEUR Workshop Proceedings, vol. 250 (2007)) |
| [16] | Pérez-Urbina, H.; Motik, B.; Horrocks, I., Tractable query answering and rewriting under description logic constraints, J. Appl. Log., 8, 186-209 (2010) · Zbl 1192.68218 |
| [17] | Eiter, T.; Ortiz, M.; Šimkus, M.; Tran, T.; Xiao, G., Query rewriting for Horn-\( \mathcal{SHIQ}\) plus rules, (Hoffmann, J.; Selman, B., Proc. AAAI 2012 (2012), AAAI Press) |
| [18] | Gabbay, D.; Kurucz, A.; Wolter, F.; Zakharyaschev, M., Many-Dimensional Modal Logics: Theory and Applications, Studies in Logic and the Foundations of Mathematics, vol. 148 (2003), Elsevier · Zbl 1051.03001 |
| [19] | Motik, B., Reasoning in description logics using resolution and deductive databases (2006), Karlsruhe Institute of Technology: Karlsruhe Institute of Technology Germany, Ph.D. thesis |
| [20] | Hustadt, U.; Motik, B.; Sattler, U., Reasoning in description logics by a reduction to disjunctive datalog, J. Autom. Reason., 39, 351-384 (2007) · Zbl 1132.68735 |
| [21] | Cuenca Grau, B.; Motik, B.; Stoilos, G.; Horrocks, I., Computing datalog rewritings beyond Horn ontologies, (Rossi, F., Proc. IJCAI 2013, IJCAI/AAAI (2013)), 832-838 |
| [22] | Hovland, D.; Kontchakov, R.; Skjæveland, M. G.; Waaler, A.; Zakharyaschev, M., Ontology-based data access to Slegge, (d’Amato, C.; Fernández, M.; Tamma, V. A.M.; Lécué, F.; Cudré-Mauroux, P.; Sequeda, J. F.; Lange, C.; Heflin, J., Proc. ISWC 2017, Part II. Proc. ISWC 2017, Part II, Lecture Notes in Computer Science, vol. 10588 (2017), Springer), 120-129 |
| [23] | Carral, D.; Feier, C.; Cuenca Grau, B.; Hitzler, P.; Horrocks, I., EL-ifying ontologies, (Demri, S.; Kapur, D.; Weidenbach, C., Proc. IJCAR 2014. Proc. IJCAR 2014, Lecture Notes in Computer Science, vol. 8562 (2014), Springer), 464-479 · Zbl 1423.68487 |
| [24] | Zhou, Y.; Cuenca Grau, B.; Nenov, Y.; Kaminski, M.; Horrocks, I., PAGOdA: pay-as-you-go ontology query answering using a datalog reasoner, J. Artif. Intell. Res., 54, 309-367 (2015) · Zbl 1343.68073 |
| [25] | Botoeva, E.; Calvanese, D.; Santarelli, V.; Savo, D. F.; Solimando, A.; Xiao, G., Beyond OWL 2 QL in OBDA: rewritings and approximations, (Schuurmans, D.; Wellman, M. P., Proc. AAAI 2016 (2016), AAAI Press), 921-928 |
| [26] | Bötcher, A.; Lutz, C.; Wolter, F., Ontology approximation in Horn description logics, (Kraus, S., Proc. IJCAI 2019 (2019)), 1574-1580 |
| [27] | Kharlamov, E.; Hovland, D.; Skjæveland, M. G.; Bilidas, D.; Jiménez-Ruiz, E.; Xiao, G.; Soylu, A.; Lanti, D.; Rezk, M.; Zheleznyakov, D.; Giese, M.; Lie, H.; Ioannidis, Y. E.; Kotidis, Y.; Koubarakis, M.; Waaler, A., Ontology based data access in Statoil, J. Web Semant., 44, 3-36 (2017) |
| [28] | Kaminski, M.; Nenov, Y.; Cuenca Grau, B., Datalog rewritability of disjunctive datalog programs and non-Horn ontologies, Artif. Intell., 236, 90-118 (2016) · Zbl 1357.68228 |
| [29] | Lutz, C.; Wolter, F., Non-uniform data complexity of query answering in description logics, (Brewka, G.; Eiter, T.; McIlraith, S. A., Proc. KR 2012 (2012), AAAI Press) |
| [30] | 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, 33, 1-44 (2014) · Zbl 1474.68082 |
| [31] | Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 57-104 (1998) · Zbl 0914.68075 |
| [32] | Bulatov, A. A., A dichotomy theorem for nonuniform CSPs, (Umans, C., Proc. FOCS 2017 (2017), IEEE Computer Society), 319-330 |
| [33] | Zhuk, D., A proof of CSP dichotomy conjecture, (Umans, C., Proc. FOCS 2017 (2017), IEEE Computer Society), 331-342 |
| [34] | Lutz, C.; Sabellek, L., Ontology-mediated querying with the description logic EL: trichotomy and linear datalog rewritability, (Sierra, C., Proc. IJCAI 2017 (2017)), 1181-1187 |
| [35] | Lutz, C.; Sabellek, L., A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL (2019), CoRR |
| [36] | Feier, C.; Kuusisto, A.; Lutz, C., Rewritability in monadic disjunctive datalog, MMSNP, and expressive description logics, Log. Methods Comput. Sci., 15 (2019) · Zbl 1421.68037 |
| [37] | Hansen, P.; Lutz, C.; Seylan, I.; Wolter, F., Efficient query rewriting in the description logic EL and beyond, (Proc. IJCAI 2015, AAAI (2015)), 3034-3040 |
| [38] | Kaminski, M.; Cuenca Grau, B., Sufficient conditions for first-order and datalog rewritability in ELU, (Eiter, T.; Glimm, B.; Kazakov, Y.; Krötzsch, M., Proc. DL. Proc. DL, CEUR Workshop Proceedings, vol. 1014 (2013)), 271-293 |
| [39] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press · Zbl 1193.68112 |
| [40] | Cosmadakis, S. S.; Kanellakis, P. C., Parallel evaluation of recursive rule queries, (Silberschatz, A., Proc. PODS 1986 (1986), ACM), 280-293 |
| [41] | Vardi, M. Y., Decidability and undecidability results for boundedness of linear recursive queries, (Edmondson-Yurkanan, C.; Yannakakis, M., Proc. PODS 1988 (1988), ACM), 341-351 |
| [42] | Gottlob, G.; Papadimitriou, C. H., On the complexity of single-rule datalog queries, Inf. Comput., 183, 104-122 (2003) · Zbl 1055.68033 |
| [43] | Kanellakis, P. C., Elements of relational database theory, (van Leeuwen, J., Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (1990), Elsevier and MIT Press), 1073-1156 · Zbl 0900.68090 |
| [44] | Kikot, S.; Kurucz, A.; Podolskii, V.; Zakharyaschev, M., Deciding boundedness of monadic sirups, (Proc. PODS 2021 (2021), ACM Press) |
| [45] | Cosmadakis, S. S.; Gaifman, H.; Kanellakis, P. C.; Vardi, M. Y., Decidable optimization problems for database logic programs, (Proc. STOC 1988 (1988)), 477-490 |
| [46] | Benedikt, M.; ten Cate, B.; Colcombet, T.; Vanden Boom, M., The complexity of boundedness for guarded logics, (Proc. LICS 2015 (2015)), 293-304 · Zbl 1401.03064 |
| [47] | Afrati, F. N.; Papadimitriou, C. H., The parallel complexity of simple logic programs, J. ACM, 40, 891-916 (1993) · Zbl 0783.68051 |
| [48] | Dantchev, S. S.; Riis, S., “Planar” tautologies hard for resolution, (Proc. FOCS 2001 (2001), IEEE Computer Society), 220-229 |
| [49] | Alekhnovich, M., Mutilated chessboard problem is exponentially hard for resolution, Theor. Comput. Sci., 310, 513-525 (2004) · Zbl 1071.68028 |
| [50] | Bienvenu, M.; Kikot, S.; Kontchakov, R.; Podolskii, V.; Zakharyaschev, M., Ontology-mediated queries: combined complexity and succinctness of rewritings via circuit complexity, J. ACM, 65, 28:1-28:51 (2018) · Zbl 1426.68075 |
| [51] | Hernich, A.; Lutz, C.; Ozaki, A.; Wolter, F., Schema.org as a description logic, (Yang, Q.; Wooldridge, M. J., Proc. IJCAI 2015 (2015), AAAI Press), 3048-3054 |
| [52] | Ullman, J. D., Principles of Database and Knowledge-Base Systems, Volume II (1989), Computer Science Press |
| [53] | Gerasimova, O.; Kikot, S.; Kurucz, A.; Podolskii, V.; Zakharyaschev, M., A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom, (Calvanese, D.; Erdem, E.; Thielscher, M., Proc. KR 2020 (2020)), 403-413 |
| [54] | Naughton, J. F., Data independent recursion in deductive databases, (Silberschatz, A., Proc. PODS 1986 (1986), ACM), 267-279 |
| [55] | Ullman, J. D.; Gelder, A. V., Parallel complexity of logical query programs, Algorithmica, 3, 5-42 (1988) · Zbl 0646.68062 |
| [56] | Naughton, J. F., Minimizing function-free recursive inference rules, J. ACM, 36, 69-91 (1989) · Zbl 0677.68109 |
| [57] | Ramakrishnan, R.; Sagiv, Y.; Ullman, J. D.; Vardi, M. Y., Proof-tree transformation theorems and their applications, (Silberschatz, A., Proc. PODS 1989 (1989), ACM Press), 172-181 |
| [58] | Saraiya, Y. P., Linearizing nonlinear recursions in polynomial time, (Silberschatz, A., Proc. PODS 1989 (1989), ACM Press), 182-189 |
| [59] | Wang, K., Some positive results for boundedness of multiple recursive rules, (Gottlob, G.; Vardi, M. Y., Proc. ICDT 1995. Proc. ICDT 1995, Lecture Notes in Computer Science, vol. 893 (1995), Springer), 383-396 |
| [60] | Dantsin, E.; Eiter, T.; Gottlob, G.; Voronkov, A., Complexity and expressive power of logic programming, ACM Comput. Surv., 33, 374-425 (2001) |
| [61] | Ioannidis, Y. E., A time bound on the materialization of some recursively defined views, (Pirotte, A.; Vassiliou, Y., Proc. VLDB 1985 (1985), Morgan Kaufmann), 219-226 |
| [62] | van der Meyden, R., Predicate boundedness of linear monadic datalog is in PSPACE, Int. J. Found. Comput. Sci., 11, 591-612 (2000) · Zbl 0971.68043 |
| [63] | Naughton, J. F.; Sagiv, Y., A decidable class of bounded recursions, (Vardi, M. Y., Proc. PODS 1987 (1987), ACM), 227-236 |
| [64] | Hillebrand, G. G.; Kanellakis, P. C.; Mairson, H. G.; Vardi, M. Y., Undecidable boundedness problems for datalog programs, J. Log. Program., 25, 163-190 (1995) · Zbl 0876.68021 |
| [65] | Marcinkowski, J., Achilles, turtle, and undecidable boundedness problems for small DATALOG programs, SIAM J. Comput., 29, 231-257 (1999) · Zbl 0943.68045 |
| [66] | Gaifman, H.; Mairson, H. G.; Sagiv, Y.; Vardi, M. Y., Undecidable optimization problems for database logic programs, J. ACM, 40, 683-713 (1993) · Zbl 0785.68021 |
| [67] | 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 |
| [68] | Baader, F.; Brandt, S.; Lutz, C., Pushing the EL envelope, (Kaelbling, L. P.; Saffiotti, A., Proc. IJCAI 2005 (2005), Professional Book Center), 364-369 |
| [69] | Baader, F.; Lutz, C.; Suntisrivaraporn, B., Efficient reasoning in EL+, (Parsia, B.; Sattler, U.; Toman, D., Proc. DL 2006. Proc. DL 2006, CEUR Workshop Proceedings, vol. 189 (2006)) |
| [70] | Baader, F.; Brandt, S.; Lutz, C., Pushing the EL envelope further, (Clark, K.; Patel-Schneider, P. F., Proc. OWLED 2008 DC Workshop on OWL: Experiences and Directions (2008)) |
| [71] | Calì, A.; Gottlob, G.; Lukasiewicz, T., A general datalog-based framework for tractable query answering over ontologies, J. Web Semant., 14, 57-83 (2012) |
| [72] | Calì, A.; Gottlob, G.; Pieris, A., Towards more expressive ontology languages: the query answering problem, Artif. Intell., 193, 87-128 (2012) · Zbl 1270.68293 |
| [73] | Kaminski, M.; Nenov, Y.; Cuenca Grau, B., Datalog rewritability of disjunctive datalog programs and its applications to ontology reasoning, (Brodley, C. E.; Stone, P., Proc. AAAI 2014 (2014), AAAI Press), 1077-1083 |
| [74] | Trivela, D.; Stoilos, G.; Chortaras, A.; Stamou, G. B., Optimising resolution-based rewriting algorithms for OWL ontologies, J. Web Semant., 33, 30-49 (2015) |
| [75] | Trivela, D.; Stoilos, G.; Chortaras, A.; Stamou, G., Resolution-based rewriting for horn-SHIQ ontologies, Knowl. Inf. Syst., 62, 107-143 (2020) |
| [76] | Bienvenu, M.; Lutz, C.; Wolter, F., First-order rewritability of atomic queries in Horn description logics, (Rossi, F., Proc. IJCAI 2013, IJCAI/AAAI (2013)), 754-760 |
| [77] | Bienvenu, M.; Hansen, P.; Lutz, C.; Wolter, F., First order-rewritability and containment of conjunctive queries in Horn description logics, (Kambhampati, S., Proc. IJCAI 2016 (2016), IJCAI/AAAI Press), 965-971 |
| [78] | Barceló, P.; Berger, G.; Lutz, C.; Pieris, A., First-order rewritability of frontier-guarded ontology-mediated queries, (Lang, J., Proc. IJCAI 2018 (2018)), 1707-1713 |
| [79] | Bourhis, P.; Lutz, C., Containment in monadic disjunctive datalog, MMSNP, and expressive description logics, (Baral, C.; Delgrande, J. P.; Wolter, F., Proc. KR 2016 (2016), AAAI Press), 207-216 |
| [80] | Hernich, A.; Lutz, C.; Papacchini, F.; Wolter, F., Dichotomies in ontology-mediated querying with the guarded fragment, ACM Trans. Comput. Log., 21, 20:1-20:47 (2020) · Zbl 1446.68056 |
| [81] | Saraiya, Y. P., Polynomial-time program transformations in deductive databases, (Rosenkrantz, D. J.; Sagiv, Y., Proc. PODS 1990 (1990), ACM Press), 132-144 |
| [82] | Zhang, W.; Yu, C. T.; Troy, D., Necessary and sufficient conditions to linearize double recursive programs in logic databases, ACM Trans. Database Syst., 15, 459-482 (1990) |
| [83] | Afrati, F. N.; Gergatsoulis, M.; Toni, F., Linearisability on datalog programs, Theor. Comput. Sci., 308, 199-226 (2003) · Zbl 1068.68052 |
| [84] | Schaefer, T. J., The complexity of satisfiability problems, (Lipton, R. J.; Burkhard, W. A.; Savitch, W. J.; Friedman, E. P.; Aho, A. V., Proc. STOC 1978 (1978), ACM), 216-226 · Zbl 1282.68143 |
| [85] | Bulatov, A. A.; Jeavons, P.; Krokhin, A. A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 720-742 (2005) · Zbl 1071.08002 |
| [86] | Larose, B.; Loten, C.; Tardif, C., A characterisation of first-order constraint satisfaction problems, Log. Methods Comput. Sci., 3 (2007) · Zbl 1131.68098 |
| [87] | Hell, P.; Nesetril, J., Colouring, constraint satisfaction, and complexity, Comput. Sci. Rev., 2, 143-163 (2008) · Zbl 1302.68251 |
| [88] | Chen, H.; Larose, B., Asking the metaquestions in constraint tractability, ACM Trans. Comput. Theory, 9, 11:1-11:27 (2017) · Zbl 1427.68115 |
| [89] | Gerasimova, O.; Kikot, S.; Zakharyaschev, M., Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna, (Lutz, C.; Sattler, U.; Tinelli, C.; Turhan, A.; Wolter, F., Description Logic, Theory Combination, and All That. Description Logic, Theory Combination, and All That, Lecture Notes in Computer Science, vol. 11560 (2019), Springer), 329-351 · Zbl 1444.68067 |
| [90] | Gault, R.; Jeavons, P., Implementing a test for tractability, Constraints, 9, 139-160 (2004) · Zbl 1074.68610 |
| [91] | Chang, C.-L.; Lee, R. C.-T., Symbolic Logic and Mechanical Theorem Proving (1973), Academic Press · Zbl 0263.68046 |
| [92] | Egri, L.; Larose, B.; Tesson, P., Symmetric datalog and constraint satisfaction problems in logspace, (Proc. LICS 2007 (2007), IEEE), 193-202 |
| [93] | Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1:1-1:24 (2007) · Zbl 1312.68101 |
| [94] | Stockmeyer, L. J., The polynomial-time hierarchy, Theor. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024 |
| [95] | Gottlob, G.; Kikot, S.; Kontchakov, R.; Podolskii, V.; Schwentick, T.; Zakharyaschev, M., The price of query rewriting in ontology-based data access, Artif. Intell., 213, 42-59 (2014) · Zbl 1390.68246 |
| [96] | Rossman, B., Homomorphism preservation theorems, J. ACM, 55, 15:1-15:53 (2008) · Zbl 1326.03038 |
| [97] | Comon, H.; Dauchet, M.; Gilleron, R.; Löding, C.; Jacquemard, F.; Lugiez, D.; Tison, S.; Tommasi, M., Tree automata techniques and applications (2007), Available at |
| [98] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049 |
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.
