Cristina Feier ; Antti Kuusisto ; Carsten Lutz - Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

lmcs:4568 - Logical Methods in Computer Science, May 23, 2019, Volume 15, Issue 2 - https://doi.org/10.23638/LMCS-15(2:15)2019
Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description LogicsArticle

Authors: Cristina Feier ; Antti Kuusisto ; Carsten Lutz

    We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NExpTime-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NExpTime and 3ExpTime. We also analyze the shape of rewritings, which in the MMSNP case correspond to obstructions, and give a new construction of canonical Datalog programs that is more elementary than existing ones and also applies to formulas with free variables.


    Volume: Volume 15, Issue 2
    Published on: May 23, 2019
    Accepted on: April 23, 2019
    Submitted on: June 6, 2018
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Databases
    Funding:
      Source : OpenAIRE Graph
    • Custom-Made Ontology Based Data Access; Funder: European Commission; Code: 647289

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1148 times.
    This article's PDF has been downloaded 249 times.