Multiobjective query optimization
Multiobjective query optimization
复制标题
DOI：
10.1145/375551.375560
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou;M. Yannakakis
中科院分区：
文献类型：
--
作者：
C. Papadimitriou;M. Yannakakis
众所周知，分布式数据库系统中的查询优化需要进行微妙的权衡。例如，马里波萨数据库系统允许用户指定期望的延迟-成本权衡（即，提供递减函数u（d），指定用户愿意支付多少钱以便在时间d内接收查询结果）;马里波萨将查询图划分为水平“步幅”，分析每个步幅，并使用贪婪启发式来为所有步幅找到“最佳”计划。我们表明，马里波萨的贪婪启发式可以任意远离所需的最优。应用最近的方法在多目标优化算法，这个问题，我们表明，最佳的成本延迟权衡（帕累托）曲线在马里波萨的框架内可以近似快速在任何所需的精度。我们还提出了一个多项式算法的一般多目标查询优化问题，近似任意以及最佳的成本延迟权衡（没有限制的马里波萨的启发式步幅细分）。
The optimization of queries in distributed database systems is known to be subject to delicate trade-offs. For example, the Mariposa database system allows users to specify a desired delay-cost tradeoff (that is, to supply a decreasing function u(d), specifying how much the user is willing to pay in order to receive the query results within time d); Mariposa divides a query graph into horizontal “strides,” analyzes each stride, and uses a greedy heuristic to find the “best” plan for all strides. We show that Mariposa's greedy heuristic can be arbitrarily far from the desired optimum. Applying a recent approach in multiobjective optimization algorithms to this problem, we show that the optimum cost-delay trade-off (Pareto) curve in Mariposa's framework can be approximated fast within any desired accuracy. We also present a polynomial algorithm for the general multiobjective query optimization problem, which approximates arbirarily well the optimum cost-delay tradeoff (without the restriction of Mariposa's heuristic stride subdivision).