Algebraic Unnesting for Nested Queries
David M Quan Wang · 1999
Both relational and object query languages allow nested queries (queries with sub-queries). Nested queries are typically inefficient to execute in their original form [K82], and are difficult to optimize. Most existing query unnesting techniques are based on source-to-source, query graph, or calculus transformations; few are based on algebraic transformations. Algebraic unnesting is desirable for cost-based algebraic optimization, because it allows such optimizers to be more readily extended with unnesting capabilities. Also it facilitates more integrated unnesting, transformation, costing, and pruning during optimization. However, the existing algebraic approaches [CM93, S95] apply to a limited subset of nested queries. In many cases, they cannot unnest sub-queries that contain collection-valued attributes. In this paper, we propose a sound and complete rule set and algorithm that unnest a significantly larger range of nested queries than the existing algebraic approaches do. We demonstrate that Magic Decorrelation, which subsumes most existing relational unnesting techniques [SPL98], can be implemented algebraically using the proposed technique.