Concurrency control algorithms for multiversion database systems

ABSTRACT

Concurrency control is the activity of synchronizing operations issued by concurrently executing programs on a shared database. The goal is to produce an execution that has the same effect as a serial (noninterleaved) one. In a multiversion database system, each write on a data item produces a new copy (or version) of that data item. This paper presents a theory for analyzing the correctness of concurrency control algorithms for multiversion database systems. We use the theory to analyze some new algorithms and some previously published ones.

REFERENCES

• 1: Bayer, R., E. Elhardt, H. Heller, and A. Reiser, "Distributed Concurrency Control in Database Systems," Proc. Sixth Int'l Conf. on Very Large Data Bases, IEEE, N.Y., 1980, pp. 275-284.
• 2: R. Bayer , H. Heller , A. Reiser, Parallelism and recovery in database systems, ACM Transactions on Database Systems (TODS), v.5 n.2, p.139-156, June 1980 [doi>10.1145/320141.320146]
• 3: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 4: Bernstein, P.A., D.W. Shipman, and W.S. Wong, "Formal Aspects of Serializability in Database Concurrency Control," IEEE Trans. on Software Eng. SE-5, 3 (May 1979), pp. 203-215.
• 5: Marco Antonio Casanova, Concurrency Control Problem for Database Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 6: Arvola Chan , Stephen Fox , Wen-Te K. Lin , Anil Nori , Daniel R. Ries, The implementation of an integrated concurrency control and recovery scheme, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582386]
• 7: DuBourdieu, D.J., "Implementation of Distributed Transactions," Proc. 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 81-94.
• 8: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 9: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
• 12: King, P.F. and Collmeyer, A.J. "Database Sharing—An Efficient Mechanism for Supporting Concurrent Processes," Proc. 1974 NCC, AFIPS Press, Montvale, New Jersey, 1974.
• 13: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 14: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 15: Papadimitriou, C.H., Bernstein, P.A., and Rothnie, J.B., Jr., "Some Computational Problems Related to Database Concurrency Control," Proc. Conf. on Theoretical Computer Science, waterloo, ontario, August, 1977.
• 16: Christos H. Papadimitriou , Paris C. Kanellakis, On concurrency control by multiple versions, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588125]
• 17: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 18: Abraham Silberschatz, A multi-version concurrency scheme with no rollbacks, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.216-223, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806700]
• 19: Stearns, R.E., P.N. Lewis II, and D.J. Rosenkrantz, "Concurrency Controls for Dat-base Systems," Proc. 17th Symp. On Foundations of Conjurer Science, IEEE, N.Y., 1976, pp. 19-32.
• 20: Richard E. Stearns , Daniel J. Rosenkrantz, Distributed database concurrency controls using before-values, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582330]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Management, Performance, Theory