Incremental computation of nested relational query expressions

Reviewer: Clement R. Attanasio

This extensive paper addresses the computation of nested relational queries that may contain subqueries as operands of set relations, such as in and contains. The authors' solution consists of two steps: transform the query to an equivalent “flat” one, which does not contain nested subqueries; and then apply traditional flat query optimization techniques, in particular, incremental computation rather than recomputation. The paper comprises an extensive roadmap to related work, a categorization of nested query expressions, an algebra that the authors use to prove the correctness of their transformations of nested subqueries to flat queries, and finally a discussion and analysis of the performance advantages of incremental computation. The authors clearly state the constraints within which their analyses apply. Perhaps most significant is that they do not treat queries that contain aggregate functions. Their performance analyses are based on relations of modest size, of the order of six megabytes each. They clearly state that set relations appear in many contexts, but the example they give is of databases that describe two- and three-dimensional objects, where operators like overlaps and contains appear naturally. The paper ends with a description of required future work, including an implementation to validate the performance models and an expansion of the I/O cost model for incremental computation of any relational query, rather than the restricted model reported herein.