Incremental computation of nested relational query expressions

Abstract

Efficient algorithms for incrementally computing nested query expressions do not exist. Nested query expressions are query expressions in which selection/join predicates contain subqueries. In order to respond to this problem, we propose a two-step strategy for incrementaly computing nested query expressions. In step (1), the query expression is transformed into an equivalent unnested flat query expression. In step (2), the flat query expression is incrementally computed. To support step (1), we have developed a very concise algebra-to-algebra transformation algorithm, and we have formally proved its correctness. The flat query expressions resulting from the transformation make intensive use of the relational set-difference operator. To support step (2), we present and analyze an efficient algorithm for incrementally computing set differences based on view pointer caches. When combined with existing incremental algorithms for SPJ queries, our incremental set-difference algorithm can be used to compute the unnested flat query expressions efficiently. It is important to notice that without our incremental set-difference algorithm the existing incremental algorithms for SPJ queries are useless for any query involving the set-difference operator, including queries that are not the result of unnesting nested queries.