On-the-Fly, Incremental, Consistent Reading of Entire Databases.

@inproceedings{DBLP:conf/vldb/Pu85,
  author    = {Calton Pu},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {On-the-Fly, Incremental, Consistent Reading of Entire Databases},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {369-375},
  ee        = {db/conf/vldb/Pu85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We describe an algorithm to read entire databases with locking concurrency control allowing multiple readers or an exclusive writer. The algorithm runs concurrently with the normal transaction processing (on-the-fly), and locks the en- tities in the database one by one (incremental). We prove the algorithm produces consistent pictures of the database. We also show that the algorithm aborts a minimal number of updates in the class of on-the-fly, incremental, consistent algorithms.

On-the-fly, incremental algorithms to read entire data- bases consistently can improve system availability and reli- ability. Most existing systems either require the transaction processing to stop, or produce potentially inconsistent re- sults. Our algorithm does not change the database physical design, so it can be adapted to existing systems by expand- ing their lock table. Finally, we extend the algorithm in a straightforward way to read entire distributed databases.

Copyright © 1985 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

• 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

• 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

References

[1]

Rony Attar, Philip A. Bernstein, Nathan Goodman: Site Initialization, Recovery, and Backup in a Distributed Database System. IEEE Trans. Software Eng. 10(6): 645-650(1984) BibTeX

[2]

Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) BibTeX

[3]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[4]

Michael J. Fischer, Nancy D. Griffeth, Nancy A. Lynch: Global States of a Distributed System. IEEE Trans. Software Eng. 8(3): 198-202(1982) BibTeX

[5]

Hector Garcia-Molina, Gio Wiederhold: Read-Only Transactions in a Distributed Database. ACM Trans. Database Syst. 7(2): 209-234(1982) BibTeX

[6]

Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX

[7]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[8]

Won Kim: Highly Available Systems for Database Applications. ACM Comput. Surv. 16(1): 71-98(1984) BibTeX

[9]

C. Mani Krishna, Kang G. Shin, Yann-Hang Lee: Optimization Criteria for Checkpoint Placement. Commun. ACM 27(10): 1008-1012(1984) BibTeX

[10]

Guy M. Lohman, John A. Muckstadt: Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating. ACM Trans. Database Syst. 2(3): 209-222(1977) BibTeX

[11]

Raymond A. Lorie: Physical Integrity in a Large Segmented Database. ACM Trans. Database Syst. 2(1): 91-104(1977) BibTeX

[12]

...

[13]

Daniel J. Rosenkrantz: Dynamic Database Dumping. SIGMOD Conference 1978: 3-8 BibTeX

[14]

Asser N. Tantawi, Manfred Ruschitzka: Performance Analysis of Checkpointing Strategies. ACM Trans. Comput. Syst. 2(2): 123-144(1984) BibTeX

Referenced by

1. Kun-Lung Wu, Philip S. Yu, Ming-Syan Chen: Dynamic Finite Versioning: An Effective Versioning Approach to Concurrent Transaction and Query Processing. ICDE 1993: 577-586
2. V. Srinivasan, Michael J. Carey: Compensation-Based On-Line Query Processing. SIGMOD Conference 1992: 331-340
3. V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309