Carsten Lutz ; Frank Wolter - The Data Complexity of Description Logic Ontologies

lmcs:2203 - Logical Methods in Computer Science, November 13, 2017, Volume 13, Issue 4 - https://doi.org/10.23638/LMCS-13(4:7)2017
The Data Complexity of Description Logic OntologiesArticle

Authors: Carsten Lutz ; Frank Wolter

    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.


    Volume: Volume 13, Issue 4
    Published on: November 13, 2017
    Accepted on: October 22, 2017
    Submitted on: November 9, 2016
    Keywords: Computer Science - Artificial Intelligence
    Funding:
      Source : OpenAIRE Graph
    • Custom-Made Ontology Based Data Access; Funder: European Commission; Code: 647289

    5 Documents citing this article

    Consultation statistics

    This page has been seen 1303 times.
    This article's PDF has been downloaded 472 times.