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 equivalence of a PTime/coNP-dichotomy for ALC and ALCI-ontologies of unrestricted depth to the famous dichotomy conjecture for CSPs by Feder and Vardi, and the failure of PTime/coNP-dichotomy theorem for ALCF-ontologies. Regarding the latter DL, we also show that it is undecidable whether a given ontology admits PTime query evaluation.
from cs.AI updates on arXiv.org http://arxiv.org/abs/1611.02453
via IFTTT
No comments:
Post a Comment