The containment problem for Real conjunctive queries with inequalities
The containment problem for Real conjunctive queries with inequalities
复制标题
不等式实连接查询的包含问题
DOI：
10.1145/1142351.1142363
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Erik Vee
中科院分区：
文献类型：
--
作者：
T. S. Jayram;Phokion G. Kolaitis;Erik Vee
查询遏制是数据库查询处理和优化中的基本算法问题。在设置的语义下，长期以来，已知对连接查询的查询包含问题是NP完整的。但是，在实际数据库系统中，通常在Bag语义下评估查询，而不是设置语义。特别是，SQL查询是在Bag Sponics中评估的，并作为答案返回多组，因为除非明确要求，否则不会消除重复项。十多年来，在袋子语义下查询查询问题的确切复杂性是一个开放的问题。实际上，甚至还不知道这个问题是否可以决定。在这里，我们在袋子语义下调查了与不平等的连接查询的查询 - 接触问题。以前已经表明，在集合语义下，对于多项式层次结构的第二级，此问题是完整的。我们的主要结果断言，在袋式语义下，不平等的连接查询的查询包含问题是不可确定的。实际上，即使以下两个限制同时存在：（1）查询仅使用一个二进制关系； （2）不等式的总数受一定固定值的界限。此外，同样的不可证明的结果在袋装语义下保留。
Query containment is a fundamental algorithmic problem in database query processing and optimization. Under set semantics, the query-containment problem for conjunctive queries has long been known to be NP-complete. In real database systems, however, queries are usually evaluated under bag semantics, not set semantics. In particular, SQL queries are evaluated under bag semantics and return multisets as answers, since duplicates are not eliminated unless explicitly requested. The exact complexity of the query-containment problem for conjunctive queries under bag semantics has been an open problem for more than a decade; in fact, it is not even known whether this problem is decidable.Here, we investigate, under bag semantics, the query-containment problem for conjunctive queries with inequalities. It has been previously shown that, under set semantics, this problem is complete for the second level of the polynomial hierarchy. Our main result asserts that, under bag semantics, the query-containment problem for conjunctive queries with inequalities is undecidable. Actually, we establish the stronger result that this problem is undecidable even if the following two restrictions hold at the same time: (1) the queries use just a single binary relation; and (2) the total number of inequalities is bounded by a certain fixed value. Moreover, the same undecidability results hold under bag-set semantics.