2026-07-23T01:41:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15882 2024-03-06T10:56:25Z ddc:004 open_access

Rewriting with Acyclic Queries: Mind Your Head Geck, Gaetano Keppeler, Jens Schwentick, Thomas Spinrath, Christopher rewriting acyclic rewriting acyclic conjunctive queries free-connex queries hierarchical queries NP-hardness The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query Q and a set 𝒱 of views, there is a conjunctive query Q' over 𝒱 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 𝒱 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gaetano Geck and Jens Keppeler and Thomas Schwentick and Christopher Spinrath 2022 Is Part Of LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2022.8 urn:nbn:de:0030-drops-158829 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode