A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom

06/07/2020
by   Olga Gerasimova, et al.
0

Aiming to understand the data complexity of answering conjunctive queries mediated by an axiom stating that a class is covered by the union of two other classes, we show that deciding their first-order rewritability is PSpace-hard and obtain a number of sufficient conditions for membership in AC0, L, NL, and P. Our main result is a complete syntactic AC0//NL/P/coNP tetrachotomy of path queries under the assumption that the covering classes are disjoint.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset