论文标题
用无环查询重写：注意你的头
Rewriting with Acyclic Queries: Mind Your Head
论文作者
论文摘要
论文研究了重写问题，即决策问题，是否对于给定的查询$ q $和设置的$ \ mathcal {v} $的视图，有一个连接性查询$ q'$ q'$ q of $ \ nathcal {v} $等于$ q $，对于$ q $，对于查询，查询和/或求解的情况，请参见和求解。它表明，如果$ q $本身是无环的，则如果有任何重写，则存在无环的重写。一个类似的陈述还具有自由连续的无环，分层和Q层次的查询。关于重写问题的复杂性，本文确定了可拖动和（可能是）棘手的重写问题变体之间的边界：对于有界的ARITE的模式，即使$ Q $既有$ q $又是$ \ vients $ \ \ \ \ Mathcal {v} $ is acycyclic is acycyclic ancycarlical或herierarcart。但是，如果视图是自由连续的无环（即，简而言之，它们的身体是（i）无环，并且（ii）如果将其头部作为附加原子添加）。
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).
