Using History Information to Process Delayed Database Updates.

Sunil K. Sarin, Charles W. Kaufman, Janet E. Somers: Using History Information to Process Delayed Database Updates. VLDB 1986: 71-78

@inproceedings{DBLP:conf/vldb/SarinKS86,
  author    = {Sunil K. Sarin and
               Charles W. Kaufman and
               Janet E. Somers},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Using History Information to Process Delayed Database Updates},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {71-78},
  ee        = {db/conf/vldb/SarinKS86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents

References

[1]: Baruch Awerbuch, Shimon Even: Efficient and Reliable Broadcast is Achievable in an Eventually Connected Network. PODC 1984: 278-281
[2]: Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982)
[3]: Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58
[4]: James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983)
[5]: Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75
[6]: ...
[7]: ...
[8]: David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162
[9]: David R. Jefferson, Amihai Motro: The Time Warp Mechanism for Database Concurrency Control. ICDE 1986: 474-481
[10]: ...
[11]: Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978)
[12]: Vincent Y. Lum, Peter Dadam, R. Erbe, Jürgen Günauer, Peter Pistor, Georg Walch, H. Werner, John Woodfill: Designing DBMS Support for the Temporal Dimension. SIGMOD Conference 1984: 115-130
[13]: Douglas Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David A. Edwards, Stephen Kiser, Charles S. Kline: Detection of Mutual Inconsistency in Distributed Systems. IEEE Trans. Software Eng. 9(3): 240-247(1983)
[14]: ...
[15]: Sunil K. Sarin, Barbara T. Blaustein, Charles W. Kaufman: System Architecture for Partition-Tolerant Distributed Databases. IEEE Trans. Computers 34(12): 1158-1163(1985)
[16]: Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979)