Query Processing Techniques For Correlated Queries

This paper studies query processing techniques for correlated queries, and generalized these techniques to address a variety of related query processing problems. We analyze the traditional technique of Nested Iteration and show how its performance can be improved. We then describe the Magic Decorrelation rewrite technique, demonstrating that several existing decorrelation algorithms are special cases of Magic Decorrelation. Further, we show that Nested Iteration and Magic Decorrelation are two ends of a continuous range of evaluation policies for correlated queries.