Answering Conjunctive Queries with Inequalities
Answering Conjunctive Queries with Inequalities
复制标题
回答带有不等式的连接查询
DOI：
10.1007/s00224-016-9684-2
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Paraschos Koutris;Tova Milo;Sudeepa Roy;Dan Suciu
在本文中，我们研究了与不平等的结合查询（CQ）的复杂性（≠）。这使我们能够为给定的CQ使用任何精选的项目加入查询计划，而无需不平等，以不等式回答CQ，并且在运行时间的额外因素仅取决于查询。关键的想法是定义一个新的投影操作员，该操作员将一组小元组映射到投影的输出中的一组元组；查询的不等式。 CQ没有不等式。树宽，但也可以是NP固定的，我们说明了增强图的疑问和不平等的类别，但是最终可以评估不等式，我们提供了必要的属性和足够的特性，使CQ类具有相对于任何不等式模式的聚时间组合的复杂性。基于的技术优于本文中讨论的替代方法。
In this paper, we study the complexity of answering conjunctive queries (CQ) with inequalities (≠). In particular, we are interested in comparing the complexity of the query with and without inequalities. The main contribution of our work is a novel combinatorial technique that enables us to use any Select-Project-Join query plan for a given CQ without inequalities in answering the CQ with inequalities, with an additional factor in running time that only depends on the query. The key idea is to define a new projection operator, which keeps a small representation (independent of the size of the database) of the set of input tuples that map to each tuple in the output of the projection; this representation is used to evaluate all the inequalities in the query. Second, we generalize a result by Papadimitriou and Yannakakis (1997) and give an alternative algorithm based on the color-coding technique (2008) to evaluate a CQ with inequalities by using an algorithm for the CQ without inequalities. Third, we investigate the structure of the query graph, inequality graph, and the augmented query graph with inequalities, and show that even if the query and the inequality graphs have bounded treewidth, the augmented graph not only can have an unbounded treewidth but can also be NP-hard to evaluate. Further, we illustrate classes of queries and inequalities where the augmented graphs have unbounded treewidth, but the CQ with inequalities can be evaluated in poly-time. Finally, we give necessary properties and sufficient properties that allow a class of CQs to have poly-time combined complexity with respect to any inequality pattern. We also illustrate classes of queries where our query-plan-based technique outperforms the alternative approaches discussed in the paper.
算法百科全书
DOI：
10.1007/978-0-387-30162-4_347
发表时间：
2008
期刊：
--
影响因子：
--
作者：
Lyngsø R
通讯作者：
Lyngsø R