Gaetano Geck ; Jens Keppeler ; Thomas Schwentick ; Christopher Spinrath - Rewriting with Acyclic Queries: Mind Your Head

lmcs:10166 - Logical Methods in Computer Science, November 29, 2023, Volume 19, Issue 4 - https://doi.org/10.46298/lmcs-19(4:17)2023
Rewriting with Acyclic Queries: Mind Your HeadArticle

Authors: Gaetano Geck ; Jens Keppeler ; Thomas Schwentick ; Christopher Spinrath

    The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query $Q$ and a set $\mathcal{V}$ of views, there is a conjunctive query $Q'$ over $\mathcal{V}$ that is equivalent to $Q$, for cases where the query, the views, and/or the desired rewriting are acyclic or even more restricted. It shows that, if $Q$ itself is acyclic, an acyclic rewriting exists if there is any rewriting. An analogous statement also holds for free-connex acyclic, hierarchical, and q-hierarchical queries. Regarding the complexity of the rewriting problem, the paper identifies a border between tractable and (presumably) intractable variants of the rewriting problem: for schemas of bounded arity, the acyclic rewriting problem is NP-hard, even if both $Q$ and the views in $\mathcal{V}$ are acyclic or hierarchical. However, it becomes tractable if the views are free-connex acyclic (i.e., in a nutshell, their body is (i) acyclic and (ii) remains acyclic if their head is added as an additional atom).


    Volume: Volume 19, Issue 4
    Published on: November 29, 2023
    Accepted on: August 15, 2023
    Submitted on: October 18, 2022
    Keywords: Computer Science - Databases,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 793 times.
    This article's PDF has been downloaded 198 times.