On the data complexity of ontology-mediated queries with a covering axiom
Olga Gerasimova, Stanislav Kikot, Vladimir Vladimirovich Podolskii, Michael Zakharyaschev · BIROn (Birkbeck, University of London) · 2017
This paper reports on our ongoing work that aims at a classification of conjunctive queries q according to the data complexity of answering ontologymediated queries ({A T F}; q). We give examples of queries from the complexity classes ϵ {AC0; L; NL; P; CONP}, and obtain a few syntactical conditions for -membership and -hardness.