Staggered Maintenance of Multiple Views

A materialized view needs to be maintained in response to changes to the tables used to derive the view. Incremental maintenance is typically done in two steps -- (1) compute the changes to the materialized view, and (2) refresh the materialized view by applying these changes. In this paper, we show that it is possible to interleave change computation of one view with refresh of other views so that the changes can be computed more efficiently than would be possible if the two steps were to occur sequentially in either order. The algebraic equations to compute the changes to a view are simplest when written in terms of both the pre-update and postupdate states of the deriving tables. By interleaving the refresh and change computation steps, we can guarantee that a table is always in the correct state during change computation. Such an interleaving corresponds to a staggered evaluation of the algebraic equations defining the changes -- hence the technique is called the staggered maintena..