一句话：证明若合取查询 Q 存在重写，则当 Q 无环时也存在无环重写，并厘清无环视图重写问题的可处理边界。
论文研究合取查询的视图重写问题：给定合取查询 Q 与视图集 V，判定是否存在定义在 V 上且与 Q 等价的合取查询 Q'。作者聚焦查询、视图和/或目标重写的无环性及更受限情形，证明若 Q 无环，则只要存在重写就存在无环重写；对 free-connex 无环、hierarchical、q-hierarchical 查询有类似结论。复杂度方面，论文划出可处理与（可能）难解的边界：有界元数下，即使 Q 与视图均无环或 hierarchical，无环重写仍 NP 难；但当视图为 free-connex 无环（体无环，加入头部为额外原子后仍无环）时问题可处理。
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}
}