Efficient approximations of conjunctive queries
Efficient approximations of conjunctive queries
复制标题
连接查询的高效近似
DOI：
10.1145/2213556.2213591
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Barceló P
中科院分区：
文献类型：
--
作者：
Barceló P
当在大型数据库上查找查询的精确答案是不可行的时候，很自然地会用一个更有效的查询来近似查询，这个查询来自一个对查询求值的复杂性有良好界限的类。在本文中，我们研究了合取查询的这种近似。这些查询在数据库中特别重要，并且我们对允许快速查询求值的类有很好的理解，例如无环查询或有界（超）树宽查询。我们将给定queryQas的近似值定义为来自其中一个类的查询，这些类与qas的分歧尽可能小。我们主要集中在保证返回正确答案的近似值上。我们证明了对于上述可处理的并置查询，近似总是存在的，并且在原始查询的大小上最多是多项式。这是由我们建立的将合取查询类的闭包性质与近似的存在性联系起来的一般结果得出的。我们还表明，在许多情况下，近似的大小受到它们所近似的查询的大小的限制。我们建立了一些结果，显示了查询的组合属性如何影响其近似值的属性，研究了近似值数量的界限，以及查找和识别近似值的复杂性。我们还查看返回所有正确答案的近似值，并研究它们的性质。
When finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. In this paper we study such approximations for conjunctive queries. These queries are of special importance in databases, and we have a very good understanding of the classes that admit fast query evaluation, such as acyclic, or bounded (hyper)treewidth queries.We define approximations of a given queryQas queries from one of those classes that disagree withQas little as possible. We mostly concentrate on approximations that are guaranteed to return correct answers. We prove that for the above classes of tractable conjunctive queries, approximations always exist, and are at most polynomial in the size of the original query. This follows from general results we establish that relate closure properties of classes of conjunctive queries to the existence of approximations. We also show that in many cases, the size of approximations is bounded by the size of the query they approximate. We establish a number of results showing how combinatorial properties of queries affect properties of their approximations, study bounds on the number of approximations, as well as the complexity of finding and identifying approximations. We also look at approximations that return all correct answers and study their properties.
登录
查看更多内容
数据库约束和同态对偶性
DOI：
--
发表时间：
2010
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
B. T. Cate;Phokion G. Kolaitis;W. Tan
通讯作者：
W. Tan
DOI：
10.1145/1938551.1938575
发表时间：
2011-03
期刊：
--
影响因子：
--
作者：
Robert Fink;Dan Olteanu
通讯作者：
Robert Fink;Dan Olteanu
DOI：
--
发表时间：
2008
期刊：
Complexity of Constraints
影响因子：
--
作者：
Phokion G. Kolaitis;Moshe Y. Vardi
通讯作者：
Moshe Y. Vardi
DOI：
10.1007/3-540-36285-1_2
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
Y. Ioannidis
通讯作者：
Y. Ioannidis
DOI：
--
发表时间：
2012
期刊：
Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management
影响因子：
--
作者：
Barcelo, P
通讯作者：
Barcelo, P