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).

@article{paperbot2177,
  title = {Rewriting with Acyclic Queries: Mind Your Head},
  author = {Gaetano Geck and Jens Keppeler and Thomas Schwentick and Christopher Spinrath},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 4},
  year = {2023},
  doi = {10.46298/lmcs-19(4:17)2023}
}