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}
}
BibTeX

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 ... BibTeX

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 BibTeX

References

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

Referenced by

  1. Esther Pacitti, Eric Simon: Update Propagation Strategies to Improve Freshness in Lazy Master Replicated Databases. VLDB J. 8(3-4): 305-318(2000)
  2. Esther Pacitti, Pascale Minet, Eric Simon: Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases. VLDB 1999: 126-137
  3. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:28 2009