{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:40:28Z","timestamp":1755999628609,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The paper studies the rewriting problem, that is, the decision problem\nwhether, for a given conjunctive query $Q$ and a set $\\mathcal{V}$ of views,\nthere is a conjunctive query $Q'$ over $\\mathcal{V}$ that is equivalent to $Q$,\nfor cases where the query, the views, and\/or the desired rewriting are acyclic\nor even more restricted. It shows that, if $Q$ itself is acyclic, an acyclic\nrewriting exists if there is any rewriting. An analogous statement also holds\nfor free-connex acyclic, hierarchical, and q-hierarchical queries. Regarding\nthe complexity of the rewriting problem, the paper identifies a border between\ntractable and (presumably) intractable variants of the rewriting problem: for\nschemas of bounded arity, the acyclic rewriting problem is NP-hard, even if\nboth $Q$ and the views in $\\mathcal{V}$ are acyclic or hierarchical. However,\nit becomes tractable if the views are free-connex acyclic (i.e., in a nutshell,\ntheir body is (i) acyclic and (ii) remains acyclic if their head is added as an\nadditional atom).<\/jats:p>","DOI":"10.46298\/lmcs-19(4:17)2023","type":"journal-article","created":{"date-parts":[[2023,11,29]],"date-time":"2023-11-29T12:00:14Z","timestamp":1701259214000},"source":"Crossref","is-referenced-by-count":1,"title":["Rewriting with Acyclic Queries: Mind Your Head"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Gaetano","family":"Geck","sequence":"first","affiliation":[]},{"given":"Jens","family":"Keppeler","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]},{"given":"Christopher","family":"Spinrath","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2023,11,29]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12612\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12612\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,29]],"date-time":"2023-11-29T12:00:15Z","timestamp":1701259215000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,29]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:17)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2201.05129v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2201.05129v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2201.05129","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2201.05129","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,11,29]]},"article-number":"10166"}}