Using Differential Techniques to Efficiently Support Transaction Time

Abstract. We present an architecture for query processing in the relational model extended with transaction time. The architecture integrates standard query op-timization and computation techniques with new differential computation tech-niques. Differential computation computes a query incrementally or decremen-tally from the cached and indexed results of previous computations. The use of dif-ferential computation techniques is essential in order to provide efficient process-ing of queries that access very large temporal relations. Alternative query plans are integrated into a state transition network, where the state space includes backlogs of base relations, cached results from previous computations, a cache index, and intermediate results; the transitions include standard relational algebra operators, operators for constructing differential files, operators for differential computation, and combined operators. A rule set is presented to prune away parts of state tran-sition networks that are not promising, and dynamic programming techniques are used to identify the optimal plans from the remaining state transition networks. An extended logical access path serves as a "structuring " index on the cached re-suits and contains, in addition, vital statistics for the query optimization process (including statistics about base relations, backlogs, and queries--previously com-puted and cached, previously computed, or just previously estimated)