The Data Complexity of Description Logic Ontologies
  We analyze the data complexity of ontology-mediated querying where the
ontologies are formulated in a description logic (DL) of the ALC family and
queries are conjunctive queries, positive existential queries, or acyclic
conjunctive queries. Our approach is non-uniform in the sense that we aim to
understand the complexity of each single ontology instead of for all ontologies
formulated in a certain language. While doing so, we quantify over the queries
and are interested, for example, in the question whether all queries can be
evaluated in polynomial time w.r.t. a given ontology. Our results include a
PTime/coNP-dichotomy for ontologies of depth one in the description logic
ALCFI, the same dichotomy for ALC- and ALCI-ontologies of unrestricted depth,
and the non-existence of such a dichotomy for ALCF-ontologies. For the latter
DL, we additionally show that it is undecidable whether a given ontology admits
PTime query evaluation. We also consider the connection between PTime query
evaluation and rewritability into (monadic) Datalog.
