TY - JOUR
T1 - A tetrachotomy of ontology-mediated queries with a covering axiom
AU - Gerasimova, Olga
AU - Kikot, Stanislav
AU - Kurucz, Agi
AU - Podolskii, Vladimir
AU - Zakharyaschev, Michael
N1 - Funding Information:
The work of O. Gerasimova was funded by RFBR , project number 20-31-90123 . The work of V. Podolskii was supported by the HSE University Basic Research Program. The work of M. Zakharyaschev was supported by the EPSRC U.K. grant EP/S032282 . We are grateful to Frank Wolter for his remarks that helped us improve the article. Thanks are also due to the anonymous referees for their careful reading, valuable comments and constructive suggestions.
Publisher Copyright:
© 2022 The Author(s)
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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 Π2p-complete for combined complexity and can be in [Formula presented] or L-, NL-, P-, or CONP-complete for data complexity (with the problem of recognising FO-rewritability of d-sirups being 2EXPTIME-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 [Formula presented]/NL/P/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.
AB - 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 Π2p-complete for combined complexity and can be in [Formula presented] or L-, NL-, P-, or CONP-complete for data complexity (with the problem of recognising FO-rewritability of d-sirups being 2EXPTIME-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 [Formula presented]/NL/P/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.
UR - http://www.scopus.com/inward/record.url?scp=85130801472&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2022.103738
DO - 10.1016/j.artint.2022.103738
M3 - Article
SN - 0004-3702
VL - 309
JO - ARTIFICIAL INTELLIGENCE
JF - ARTIFICIAL INTELLIGENCE
IS - 103738
M1 - 103738
ER -