Weighted hypertree decompositions and optimal query plans
Weighted hypertree decompositions and optimal query plans
复制标题
加权超树分解和最优查询计划
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
N. Leone
中科院分区：
文献类型：
--
作者：
Francesco Scarcello;G. Greco;N. Leone
超树宽度[22，25]是超图循环度的度量。来自不同领域的一些相关问题，例如，数据库理论中的合取查询或人工智能中的约束满足的评价，当它们的底层超图具有有界的超树宽度时是易于处理的。然而，在实际的情况下，如数据库查询的评估，我们有更多的信息，除了查询的结构。例如，我们知道关系中元组的数量，属性的选择性等等.事实上，所有商业查询优化器都是基于定量方法，不关心结构属性.本文定义了加权超树分解的概念，以便将结构分解方法与定量方法结合起来.加权超树分解配备了成本函数，可以用于建模许多情况下，我们有更多的信息，在给定的问题，除了它的超图表示。我们分析了计算的超树分解具有最小的权重，称为最小超树分解的复杂性。我们表明，在许多情况下，增加权重，我们松散的易处理性。然而，我们证明了，在一些-不是很严重-的限制，允许的成本函数和目标超树，最佳加权超树分解可以计算在多项式时间。对于一些更简单的超树加权函数，这个问题也是高度并行化的。然后，我们提供了一个成本函数，模型查询评估成本，并展示了如何利用加权超树分解确定（逻辑）查询计划回答合取查询。最后，我们提出了这种查询优化技术与商业DBMS的查询优化的实验比较的结果。这些初步结果是非常有希望的，因为对于一些大型查询（有许多连接），我们的混合技术明显优于商业优化器。
Hypertree width [22, 25] is a measure of the degree of cyclicity of hypergraphs. A number of relevant problems from different areas, e.g., the evaluation of conjunctive queries in database theory or the constraint satisfaction in AI, are tractable when their underlying hypergraphs have bounded hypertree width. However, in practical contexts like the evaluation of database queries, we have more information besides the structure of queries. For instance, we know the number of tuples in relations, the selectivity of attributes and so on. In fact, all commercial query-optimizers are based on quantitative methods and do not care about structural properties.In this paper, we define the notion of weighted hypertree decomposition, in order to combine structural decomposition methods with quantitative approaches. Weighted hypertree decompositions are equipped with cost functions, that can be used for modelling many situations where we have further information on the given problem, besides its hypergraph representation. We analyze the complexity of computing the hypertree decompositions having the smallest weights, called minimal hypertree decompositions. We show that, in many cases, adding weights we loose tractability. However, we prove that, under some - not very severe - restrictions on the allowed cost functions and on the target hypertrees, optimal weighted hypertree decompositions can be computed in polynomial time. For some easier hypertree weighting functions, this problem is also highly parallelizable. Then, we provide a cost function that models query evaluation costs and show how to exploit weighted hypertree decompositions for determining (logical) query plans for answering conjunctive queries. Finally, we present the results of an experimental comparison of this query optimization technique with the query optimization of a commercial DBMS. These preliminary results are very promising, as for some large queries (with many joins) our hybrid technique clearly outperforms the commercial optimizer.