ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

ACM SIGMOD Anthology

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Baruch Awerbuch, Shimon Even: Efficient and Reliable Broadcast is Achievable in an Eventually Connected Network. PODC 1984: 278-281 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
James Clifford, David Scott Warren: Formal Semantics for Time in Databases. ACM Trans. Database Syst. 8(2): 214-254(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
...
[8]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David R. Jefferson, Amihai Motro: The Time Warp Mechanism for Database Concurrency Control. ICDE 1986: 474-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:58 2010 by Michael Ley (ley@uni-trier.de)