Using History Information to Process Delayed Database Updates
Sunil K. Sarin, Charles W. Kaufman, Janet E. Somers · Very Large Data Bases · 1986
An algorithm is described which processes database updates arriving out of order in a way that maintains a -consistent view of the data. This problem arises in the context of a high availability replicated database architecture in which updates are totally ordered by timestamp but do not necessarily arrive at a site in timestamp order. The algorithm uses a history of object values written and objects read, by updates. When a new update arrives and is executed, higher-timestamped updates that read its results are scheduled for undoing and reexecution; such reexecution may in turn cause additional updates to be reexecuted, and so on. A major goal of the algorithm is to avoid this kind of cascading when reexecution of an update would have the same effect as it had before. A prototype implementation of the algorithm for a relational database is described. It is suggested that the algorithm may be of use outside its original context, in the maintenance of historical databases.