Parallelism and Recovery in Database Systems.

Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980)
  author    = {Rudolf Bayer and
               Hans Heller and
               Angelika Reiser},
  title     = {Parallelism and Recovery in Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {2},
  year      = {1980},
  pages     = {139-156},
  ee        = {, db/journals/tods/BayerHR80.html},
  bibsource = {DBLP,}


In this paper a new method to increase parallelism in database systems is described. Use is made of the fact that for recovery reasons, we often have two values for one object in the database - the new one and the old one. Introduced and discussed in detail is a certain scheme by which readers and writers may work simultaneously on the same object. It is proved that transactions executed according to this scheme have the correct effect; i.e., consistency is preserved. Several variations of the basic scheme which are suitable depending on the degree of parallelism required, are described.

Copyright © 1980 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
Rudolf Bayer: Integrity, Concurrency, and Recovery in Databases. ECI 1976: 79-106 BibTeX
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
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
Raymond A. Lorie: Physical Integrity in a Large Segmented Database. ACM Trans. Database Syst. 2(1): 91-104(1977) BibTeX
Brian Randell: Reliable Computing Systems. Advanced Course: Operating Systems 1978: 282-391 BibTeX
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
Gunter Schlageter: Process Synchronization in Database Systems. ACM Trans. Database Syst. 3(3): 248-271(1978) BibTeX
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

Referenced by

  1. Shalab Goel, Bharat K. Bhargava, Sanjay Kumar Madria: An Adaptable Constrained Locking Protocol for High Data Contention Environments. DASFAA 1999: 321-328
  2. H. V. Jagadish, Inderpal Singh Mumick, Michael Rabinovich: Asynchronous Version Advancement in a Distributed Three-Version Database. ICDE 1998: 424-435
  3. Paul M. Bober, Michael J. Carey: Indexing for Multiversion Locking: Alternatives and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 9(1): 68-84(1997)
  4. Dallan Quass, Jennifer Widom: On-Line Warehouse View Maintenance. SIGMOD Conference 1997: 393-404
  5. H. V. Jagadish, Inderpal Singh Mumick, Michael Rabinovich: Scalable Versioning in Distributed Databases with Commuting Updates. ICDE 1997: 520-531
  6. Arif Merchant, Kun-Lung Wu, Philip S. Yu, Ming-Syan Chen: Performance Analysis of Dynamic Finite Versioning Schemes: Storage Cost vs. Obsolescence. IEEE Trans. Knowl. Data Eng. 8(6): 985-1001(1996)
  7. Ahmad R. Hadaegh, Ken Barker: Value-serializability and an Architecture for Managing Transactions in Multiversion Objectbase Systems. ADBIS 1996: 126-133
  8. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers, Lijing Lin: Ordered Shared Locks for Real-Time Databases. VLDB J. 4(1): 87-126(1995)
  9. Paul Ammann, Sushil Jajodia, Padmaja Mavuluri: On-The-Fly Reading of Entire Databases. IEEE Trans. Knowl. Data Eng. 7(5): 834-838(1995)
  10. Paul M. Bober, Michael J. Carey: Indexing Alternatives for Multiversion Locking. EDBT 1994: 145-158
  11. F. Bukhari, Sylvia L. Osborn: Two Fully Distributed Concurrency Control Algorithms. IEEE Trans. Knowl. Data Eng. 5(5): 872-881(1993)
  12. 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
  13. Tadeusz Morzy: The Correctness of Concurrency Control for Multiversion Database Systems with Limited Number of Versions. ICDE 1993: 595-604
  14. Sang Hyuk Son, Spiros Kouloumbis: A Token-Based Synchronization Scheme Using Epsilon-Serializability and Its Performance for Real-Time Distributed Database Systems. DASFAA 1993: 235-242
  15. H. V. Jagadish, Oded Shmueli: Proclamation-Based Model for Cooperating Transactions. VLDB 1992: 265-276
  16. C. Mohan, Hamid Pirahesh, Raymond A. Lorie: Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions. SIGMOD Conference 1992: 124-133
  17. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: Using Delayed Commitment in Locking Protocols for Real-Time Databases. SIGMOD Conference 1992: 104-113
  18. Divyakant Agrawal, Amr El Abbadi, Richard Jeffers: An Approach to Eliminate Transaction Blocking in Locking Protocols. PODS 1992: 223-235
  19. Paul M. Bober, Michael J. Carey: On Mixing Queries and Transactions via Multiversion Locking. ICDE 1992: 535-545
  20. Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991)
  21. Partha Dasgupta, Zvi M. Kedem: The Five Color Concurrency Control Protocol: Non-Two-Phase Locking in General Databases. ACM Trans. Database Syst. 15(2): 281-307(1990)
  22. Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989)
  23. Jerre D. Noe, David B. Wagner: Measured Performance of Time Interval Concurrency Control Techniques. VLDB 1987: 359-367
  24. Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129
  25. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
  26. Meichun Hsu, Arvola Chan: Partitioned Two-Phase Locking. ACM Trans. Database Syst. 11(4): 431-446(1986)
  27. Rudolf Bayer: Consistency of Transactions and Random Batch. ACM Trans. Database Syst. 11(4): 397-404(1986)
  28. Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46
  29. Georg Lausen, Eljas Soisalon-Soininen, Peter Widmayer: Towards Online Schedulers Based on Pre-Analysis Locking. ICDT 1986: 242-259
  30. Calton Pu: On-the-Fly, Incremental, Consistent Reading of Entire Databases. VLDB 1985: 369-375
  31. Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104
  32. Marco A. Casanova, Arnaldo V. Moura, Luiz Tucherman: On the Correctness of a Local Storage Subsystem. PODS 1985: 123-134
  33. Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984)
  34. Klaus Elhardt, Rudolf Bayer: A Database Cache for High Performance and Fast Restart in Database Systems. ACM Trans. Database Syst. 9(4): 503-525(1984)
  35. Peter Dadam, Vincent Y. Lum, H.-D. Werner: Integration of Time Versions into a Relational Database System. VLDB 1984: 509-522
  36. Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118
  37. Haran Boral, Israel Gold: Towards A Self-Adapting Centralized Concurrency Control Algorithm. SIGMOD Conference 1984: 18-32
  38. M. Dennis Mickunas, Pankaj Jalote, Roy H. Campbell: The Delay/Re-Read Protocol for Concurrency Control in Databases. ICDE 1984: 307-314
  39. Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983)
  40. Peter Peinl, Andreas Reuter: Empirical Comparison of Database Concurrency Schemes. VLDB 1983: 97-108
  41. Werner Kießling, G. Landherr: A Quantitative Comparison of Lockprotocols for Centralized Databases. VLDB 1983: 120-130
  42. Michael J. Carey: An Abstract Model of Database Concurrency Control Algorithms. SIGMOD Conference 1983: 97-107
  43. Meichun Hsu, Stuart E. Madnick: Hierarchical Database Decomposition - A Technique for Database Concurrency Control. PODS 1983: 182-191
  44. Michael J. Carey: Granularity Hierarchies in Concurrency Control. PODS 1983: 156-165
  45. Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Distributed Concurrency Control (Invited Paper). VLDB 1982: 62-76
  46. Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191
  47. Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92
  48. Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82
  49. Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981)
  50. Michael L. Brodie: On Modelling Behavioural Semantics of Databases. VLDB 1981: 32-42
  51. Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83
  52. Rudolf Bayer, Klaus Elhardt, Hans Heller, Angelika Reiser: Distributed Concurrency Control in Database Systems. VLDB 1980: 275-284
  53. Joachim W. Schmidt: Parallel Processing of Relations: A Single-Assignment Approach. VLDB 1979: 398-408
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:38:43 2008