Efficient Approximation of Optimization Queries Under Parametric Aggregation Constraints Sudipto Guha, Dimitrios Gunopulos, Nick Koudas, Divesh Srivastava, and Michail Vlachos   View Paper (PDF)   Return to Query Optimization (Session C2) Abstract We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that constitute so- lutions of a large class of optimization problems in- volving the database tuples. The constraints and the objective function are speci ed in terms of aggregate functions of relational attributes, and the parameter values identify the constants used in the aggregation constraints. We develop algorithms that preprocess relations and construct indices to efficiently provide answers to OPAC queries. The answers returned by our indices are approximate, not exact, and provide guarantees for their accuracy. Moreover, the indices can be tuned easily to meet desired accuracy levels, provid- ing a graceful tradeoff between answer accuracy and index space. We present the results of a thorough experimental evaluation analyzing the impact of sev- eral parameters on the accuracy and performance of our techniques. Our results indicate that our method- ology is effective and can be deployed easily, utiliz- ing index structures such as R-trees. ©2004 Association for Computing Machinery