Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
= PODS'01 Website
= SIGMOD/PODS'01 Plena
<<< = PODS'01 Papers>>>
= Invited Talks
= Award Talks
= Tutorials
SIGMOD RECORD 2001
CIKM 2001
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Multiobjective Query Optimization


Christos H. Papadimitriou and Mihalis Yannakakis

  View Paper (PDF)  

Return to Queries / Optimization


Abstract

The optimization of queries in distributed database systems is known to be subject to delicate trade-offs. Forcexample, 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 inmultiobjective optimization algorithms to this problem, we show that the optimum cost-delay trade-o (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 tradeo (without the restriction of Mariposa's heuristic stride subdivision).


DiSC'02 © 2003 Association for Computing Machinery