首页 | 官方网站   微博 | 高级检索  
     


Conjunctive query evaluation by search-tree revisited
Authors:Albert Atserias
Affiliation:Universitat Politècnica de Catalunya, c/Jordi Girona Salgado 1-3, 08034 Barcelona, Spain
Abstract:The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database DD, a conjunctive query QQ, and a tuple aa, tests whether Q(a)Q(a) holds in DD in time bounded by a polynomial in (sn)logk(sn)loglogn(sn)logk(sn)loglogn and nrnr, where nn is the size of the domain of the database, kk is the number of bound variables of the conjunctive query, ss is the size of the optimal search-tree, and rr is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the nO(k)nO(k) bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks.
Keywords:Conjunctive query  Constraint-satisfaction problem  Treewidth
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号