Carsten Lutz ; Inanc Seylan ; Frank Wolter - The Data Complexity of Ontology-Mediated Queries with Closed Predicates

lmcs:4804 - Logical Methods in Computer Science, August 28, 2019, Volume 15, Issue 3 - https://doi.org/10.23638/LMCS-15(3:23)2019
The Data Complexity of Ontology-Mediated Queries with Closed Predicates

Authors: Carsten Lutz ; Inanc Seylan ; Frank Wolter

    In the context of ontology-mediated querying with description logics (DLs), we study the data complexity of queries in which selected predicates can be closed (OMQCs). We provide a non-uniform analysis, aiming at a classification of the complexity into tractable and non-tractable for ontologies in the lightweight DLs DL-Lite and EL, and the expressive DL ALCHI. At the level of ontologies, we prove a dichotomy between FO-rewritable and coNP-complete for DL-Lite and between PTime and coNP-complete for EL. The meta problem of deciding tractability is proved to be in PTime. At the level of OMQCs, we show that there is no dichotomy (unless NP equals PTime) if both concept and role names can be closed. If only concept names can be closed, we tightly link the complexity of query evaluation to the complexity of surjective CSPs. We also identify a class of OMQCs based on ontologies formulated in DL-Lite that are guaranteed to be tractable and even FO-rewritable.


    Volume: Volume 15, Issue 3
    Published on: August 28, 2019
    Accepted on: August 28, 2019
    Submitted on: September 5, 2018
    Keywords: Computer Science - Logic in Computer Science,68
    Fundings :
      Source : OpenAIRE Research Graph
    • iTract: Islands of Tractability in Ontology-Based Data Access; Funder: UK Research and Innovation; Code: EP/M012646/1
    • Custom-Made Ontology Based Data Access; Funder: European Commission; Code: 647289

    Linked data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1809.00134
    • 10.48550/arxiv.1809.00134
    The Data Complexity of Ontology-Mediated Queries with Closed Predicates
    Lutz, Carsten ; Seylan, Inanc ; Wolter, Frank ;

    Share

    Consultation statistics

    This page has been seen 414 times.
    This article's PDF has been downloaded 234 times.