Query Optimization by Quantifier Elimination

Query optimizers have a limited arsenal of techniques for optimizing nested queries. In this paper, we develop a new approach for query optimization based on quantifier elimination. Quantifier elimination is a well-established tool for proving the decidability of logical theories. Here, however, we show that it can be turned into an effective query optimization technique that may yield asymptotic improvements in query processing efficiency. In addition, the technique establishes a foundation for certain well-known but previously little-understood aggregation based techniques for optimizing nested queries.