A tetrachotomy of ontology-mediated queries with a covering axiom
  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^p_2-complete for combined
complexity and can be in AC0 or LogSpace-, 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 AC0/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.
