article

Free access

Multiversion concurrency control—theory and algorithms

Editor: Robert W. Taylor Authors:

Philip A. Bernstein,

Nathan GoodmanAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 8, Issue 4

Pages 465 - 483

https://doi.org/10.1145/319996.319998

Published: 01 December 1983 Publication History

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., 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]

BAYER, H., SELLER, H., AND REISER A. Parallelism and recovery in database systems. A CM Trans. Database Syst. 5, 2 (June 1980), 139-156.

Digital Library

[3]

BEnNSTEIN, P. A., AND GOODMAN, N. Concurrency control in distributed database systems. ACM Comput. Surv. 13, 2 (June 1981), 185-221.

Digital Library

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

Digital Library

[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.)

Digital Library

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

Digital Library

[7]

DUBOURDIEU, D.J. Implementation of distributed transactions, in Proc. 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, pp. 81-94.

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

Digital Library

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

Digital Library

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

Digital Library

[11]

HOLT, R.C. Some deadlock properties of computer systems. ACM Comput. Surv. 4, 3 (Sept. 1972), 179-196.

Digital Library

[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]

LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558-565.

Digital Library

[14]

PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct~ 1979), 631-653.

Digital Library

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

Digital Library

[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]

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.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

Cited By

Salunke SOuda A(2024)A Performance Benchmark for the PostgreSQL and MySQL DatabasesFuture Internet10.3390/fi1610038216:10(382)Online publication date: 19-Oct-2024
https://doi.org/10.3390/fi16100382
Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Hamada NSaito KKawashima H(2024)Qobra: Accelerating Transactional Serializability Verifier by Quantum AnnealingJournal of Information Processing10.2197/ipsjjip.32.101332(1013-1022)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.1013
Show More Cited By

Index Terms

Multiversion concurrency control—theory and algorithms
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

Rethinking serializable multiversion concurrency control

Multi-versioned database systems have the potential to significantly increase the amount of concurrency in transaction processing because they can avoid read-write conflicts. Unfortunately, the increase in concurrency usually comes at the cost of ...
Multiversion Cautious Schedulers for Database Concurrency Control

Let MC stand for a class of logs (i.e. sequences of read/write steps of transactions) that are serializable when multiple versions of the data items are maintained. The multiversion cautious scheduler, MCS(MC) which is introduced, outputs a sequence ...
Real-time optimistic concurrency control protocol with dynamic adjustment of serialization order
RTAS '95: Proceedings of the Real-Time Technology and Applications Symposium

Proposes a new real-time optimistic protocol. By using a dynamic adjustment of the serialization order by backward-adjusting the non-serious conflicting transactions before the committing transactions, many unnecessary restarts can be eliminated. In the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 8, Issue 4

Dec. 1983

184 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/319996

Editor:
Robert W. Taylor
IBM Research Lab, San Jose, CA

Issue’s Table of Contents

Copyright © 1983 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1983

Published in TODS Volume 8, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

transaction processing

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

324
Total Citations
View Citations
3,196
Total Downloads

Downloads (Last 12 months)462
Downloads (Last 6 weeks)47

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Salunke SOuda A(2024)A Performance Benchmark for the PostgreSQL and MySQL DatabasesFuture Internet10.3390/fi1610038216:10(382)Online publication date: 19-Oct-2024
https://doi.org/10.3390/fi16100382
Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Hamada NSaito KKawashima H(2024)Qobra: Accelerating Transactional Serializability Verifier by Quantum AnnealingJournal of Information Processing10.2197/ipsjjip.32.101332(1013-1022)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.1013
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Semenova SKo SLiu YZiarek LDantu K(2024)A Comprehensive Study of Systems Challenges in Visual Simultaneous Localization and Mapping SystemsACM Transactions on Embedded Computing Systems10.1145/367731724:1(1-31)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3677317
Vandevoort BKetsman BNeven F(2024)When View- and Conflict-Robustness Coincide for Multiversion Concurrency ControlProceedings of the ACM on Management of Data10.1145/36515922:2(1-16)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651592
Blelloch GWei YLee IChabbi MSteuwer M(2024)VERLIB: Concurrent Versioned PointersProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638501(200-214)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638501
Cui ZDou WGao YWang DSong JZheng YWang TYang RXu KHu YWei JHuang TRoychoudhury APaiva AAbreu RStorey M(2024)Understanding Transaction Bugs in Database SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639207(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639207
Che YCheng DWang XWang R(2024)Opca: Enabling Optimistic Concurrent Access for Multiple Users in Oblivious Data StorageIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.344162335:11(1891-1903)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TPDS.2024.3441623
Kida AKawashima H(2024)Accelerating BFT Database with Transaction Reconstruction2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW63119.2024.00061(232-241)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPSW63119.2024.00061
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents