Rewriting with acyclic queries: mind your head

The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query Q and a set V of views, there is a conjunctive query Q ' over 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 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).