Multiversion concurrency control—theory and algorithms

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. 1 BAYER, R., ELHARDT, E., HELLER, H., AND REISER, A. Distributed concurrency control in database systems. In Proc. 6th Int. Conf. Very Large Data Bases (Montreal, Oct. 1-3, 1980) ACM, New York, 1980, pp. 275-284.
2. 2 BAYER, H., SELLER, H., AND REISER A. Parallelism and recovery in database systems. A CM Trans. Database Syst. 5, 2 (June 1980), 139-156.
3. 3 BEnNSTEIN, P. A., AND GOODMAN, N. Concurrency control in distributed database systems. ACM Comput. Surv. 13, 2 (June 1981), 185-221.
4. 4 BERNSTEX~, P. A., SHIPMAN, D. W., AND WONt, W. S. Formal aspects of serializability in database concurrency control. IEEE Trans. Softw. Eng. SE-5, 3 (May 1979), 203-215.
5. 5 CASANOVA, M.A. The Concurrency Control Problem of Database Systems. Lecture Notes in Computer Science, vol. 116, Springer-Verlag, New York, 1981. (Originally published as Tech. Rep. TR-17-79, Center for Research in Computing Technology, Harvard University, 1979.)
6. 6 CHAN, A., Fox, S., LIN, W. T. K., Nora, A., AND RIES, D.R. The implementation of an integrated concurrency control and recovery scheme. In Proc. 1982 ACM SIGMOD Conf. Management of Data (Orlando, Fla., June 2-4, 1982), M. Schkolnick, Ed., ACM, New York, 1982, pp. 184-191.
7. 7 DUBOURDIEU, D.J. Implementation of distributed transactions, in Proc. 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 81-94.
8. 8 ESWARAN, K. P., GRAY, J. N., LORX~., R. A., AND TnAmER, I.L. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633.
9. 9 GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP.Completeness, W. H. Freeman and Company, San Francisco, 1979.
10. 10 GRAY, J.N. Notes on database operating systems. In Operating Systems: An Advanced Course, Lecture Notes in Computer Science, vol. 60, Springer-Vedag, New York, 1978, pp. 393-481.
11. 11 HOLT, R.C. Some deadlock properties of computer systems. ACM Comput. Surv. 4, 3 (Sept. 1972), 179-196.
12. 12 KINc, P. F., ANl) COLLMEYER, A.J. Database sharing--an efficient mechanism for supporting concurrent processes. In Proc. 1974 NCC, AFIPS Press, Montvale, N.J., 1974.
13. 13 LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.
14. 14 PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct~ 1979), 631-653.
15. 15 PAPADIMITRIOU, C. H., AND KANELLAKIS, P.C. On concurrency control by multiple versions. In Proc. ACM Syrup. Principles of Database Systems (Los Angeles, March 29-31, 1982), ACM, New York, 1982, pp. 76-82.
16. 16 PAPADIMITRIOU, C. H., BERNSTEIN, P. A., AND ROTHNIE, J. B., JR. Some computational problems related to database concurrency control. In Proc. Conf. Theoretical Computer Science, (Waterloo, Ontario, Aug. 1977).
17. 17 REEl), D. Naming and synchronization in a decentralized computer system. Tech. Rep. MIT/ LCS/TR-205, Dept. Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Sept. 1978.
18. 18 ROSENKRANTZ, D. J., STEARNS, R. E., AND LEWIS, P. M., II System level concurrency control for distributed database systems. ACM Trans. Database Syst. 3, 2 (June 1978), 178-198.
19. 19 SILBERSCHATZ, A. A multi-version concurrency control scheme with no rollbacks. In Proc. ACM SIGACT-SIGOPS Syrup. Principles of Distributed Computing (Ottawa, Canada, Aug. 18-20, 1982), ACM, New York, 1982, pp. 216-223.
20. 20 STEARNS, R. E., AND ROSENKRANTZ, D. J. Distributed database concurrency controls using before-values. In Proc. 198I ACM SIGMOD Conf. Management of Data, ACM, New York, 1981, pp. 74-83.
21. 21 STEARNS, R. E., LEWIS, p. M., II, AND ROSENKRANTZ, D.J. Concurrency controls for database systems. In Proc. 17th Syrup. Foundations of Computer Science, IEEE, New York, 1976, pp. 19-32.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines