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).
@InProceedings{geck_et_al:LIPIcs.ICDT.2022.8, author = {Geck, Gaetano and Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher}, title = {{Rewriting with Acyclic Queries: Mind Your Head}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-223-5}, ISSN = {1868-8969}, year = {2022}, volume = {220}, editor = {Olteanu, Dan and Vortmeier, Nils}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.8}, URN = {urn:nbn:de:0030-drops-158829}, doi = {10.4230/LIPIcs.ICDT.2022.8}, annote = {Keywords: rewriting, acyclic rewriting, acyclic conjunctive queries, free-connex queries, hierarchical queries, NP-hardness} }
Feedback for Dagstuhl Publishing