Incremental computation of complex object queries

Abstract

The need for incremental algorithms for evaluating database queries is well known, but constructing algorithms that work on object-oriented databases (OODBs) has been difficult. The reason is that OODB query languages involve complex data types including composite objects and nested collections. As a result, existing algorithms have limitations in that the kinds of database updates are restricted, the operations found in many query languages are not supported, or the algorithms are too complex to be described precisely. We present an incremental computation algorithm that can handle any kind of database updates, can accept any expressions in complex query languages such as OQL, and can be described precisely. By translating primitive values and records into collections, we can reduce all query expressions into ones composed of only one kind of operation, namely comprehension. This makes the problems with incremental computation less complicated and thus allows us to describe the algorithm precisely. Our incremental algorithm consists of two parts: one is to maintain the consistency in each comprehension occurrence and the other is to update the value of an entire expression. The algorithm is so flexible that we can use strict updates, lazy updates, and their combinations. By comparing the performance of applications built with our mechanism and that of equivalent hand written update programs, we show that our incremental algorithm can be implemented efficiently.