On Acyclic Conjunctive Queries and Constant Delay Enumeration
On Acyclic Conjunctive Queries and Constant Delay Enumeration
复制标题
关于非循环连接查询和常延迟枚举
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
E. Grandjean
中科院分区：
文献类型：
--
作者：
Guillaume Bagan;Arnaud Durand;E. Grandjean
研究了非循环不等式合取查询自然扩展的枚举复杂性。在这种语言中，可以表达许多NP完全问题。我们首先改进了先前的结果Papadimitriou和Yannakakis证明，这样的查询可以计算时间c。| M| ċ|（男）|其中M是结构，（M）是查询的结果集，c是公式大小的简单指数。我们的方法的一个后果是，在一般情况下，这样的查询元组可以枚举两个元组之间的线性延迟。
然后，我们引入了一个大的子类的非循环公式称为CCQ的查询，并证明了一个CCQ的查询元组可以枚举与线性时间预计算和连续的解决方案之间的恒定延迟。此外，在两个n×n布尔矩阵的乘法不能在O（n2）时间内完成的假设下，这导致了非循环查询的以下二分法：这样的查询要么在CCQ中，要么不能用线性预计算和常数延迟枚举。证明了在多项式时间内可以检验一个非循环公式是否在CCQ中。
最后，定义了结构的自由连接树宽的概念。我们表明，对于每一个查询的自由连接树的宽度有界的一些常数k，枚举的结果可以做O（|M| k+1）预计算步骤和恒定延迟。
We study the enumeration complexity of the natural extension of acyclic conjunctive queries with disequalities. In this language, a number of NP-complete problems can be expressed. We first improve a previous result of Papadimitriou and Yannakakis by proving that such queries can be computed in time c.|M|ċ|ϕ(M)| where M is the structure, ϕ(M) is the result set of the query and c is a simple exponential in the size of the formula ϕ. A consequence of our method is that, in the general case, tuples of such queries can be enumerated with a linear delay between two tuples.
We then introduce a large subclass of acyclic formulas called CCQ≠ and prove that the tuples of a CCQ≠ query can be enumerated with a linear time precomputation and a constant delay between consecutive solutions. Moreover, under the hypothesis that the multiplication of two n×n boolean matrices cannot be done in time O(n2), this leads to the following dichotomy for acyclic queries: either such a query is in CCQ≠ or it cannot be enumerated with linear precomputation and constant delay. Furthermore we prove that testing whether an acyclic formula is in CCQ≠ can be performed in polynomial time.
Finally, the notion of free-connex treewidth of a structure is defined. We show that for each query of free-connex treewidth bounded by some constant k, enumeration of results can be done with O(|M|k+1) precomputation steps and constant delay.
计算机科学逻辑
DOI：
10.1007/978-3-642-15205-4_34
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Nenov Y
通讯作者：
Nenov Y