Serialization graph algorithms for multiversion concurrency control

ABSTRACT

We propose a new algorithmic framework for database concurrency control using multiple versions of data items and a serialization graph of the transactions as a synchronization technique, which generalizes all concurrency control methods known so far. This class of algorithms, called MVSGA for Multi Version Serialization Graph set of Algorithms, works by monitoring the acyclicity of the serialization graph which has nodes corresponding to transactions and arcs corresponding to read-from and other transaction positioning decisions made by the scheduler. For each of the major known schedulers we give examples of MVSGA schedulers that cover them. We propose a criterion for optimality among MVSGA schedulers Choice of versions to read from and relative positioning of transactions in the serialization graph should be done in a way that leaves the largest flexibility possible for future choices. This flexibility is measured as the number of pairs of nodes in the serialization graph that remain incomparable. Unfortunately, enforcing this criterion turns out to be NP-complete, so we describe an MVSGA scheduler based on a heuristic that approximates the optimal.

REFERENCES

• ACL-85: Rakesh Agrawal , Michael J. Carey , Miron Livny, Models for studying concurrency control performance: alternatives and implications, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.108-121, May 1985, Austin, Texas, United States
• An-88: E Anagnostou, "Aspects of Database Concurrency Control Performance", M Eng Thesis, Department of Computer Engineering, Umv of Patras, Greece, /988
• BBG-86: C Been, P A Bernstem, and N Goodman, "A model for Concurrency m Nested Transaction Systems", Techmcal Report TR-86-03, School of Information Technology, Wang Institute of Graduate Studms, March 1986
• BEHR-80: R Bayer, E Elhardt, H Heller and A Relser, "D~stnbuted Concurrenc:~ Control m Database Systems~, Proc of the 6th Int'l Conf on Very Large Data Bases (VLDB), pp 275-284, October 1980
• BG-83: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• BHG-87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• BSW-79: P A Bernstem, D W Shtpman and S W Wong, "Formal Aspects of Senahzabdlty m Database Concurrency Control", IEEE Transactions on Software Engmeenng, SE-5(3), pp 203-215, May 1979
• HP-85: Thanasis Hadzilacos , Christos H. Papadimitriou, Algorithmic aspects of multiversion concurrency control, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.96-104, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325417]
• HP-86: Thanasis Hadzilacos , Christos H Papadimitriou, Algorithmic aspects of multiversion concurrency control, Journal of Computer and System Sciences, v.33 n.2, p.297-310, Oct. 1986 [doi>10.1016/0022-0000(86)90022-X]
• HY-86: Thanasis Hadzilacos , Mihalis Yannakakis, Deleting completed transactions, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.43-46, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15402]
• KP-79: H T Kung and C H Papadlmltnou, "An Optlmahty Theor~ of Database Concurrency Control", Acts Informatlca 19(1), pp 1-11, 1983
• LW-84: Ming-Yee Lai , W. Kevin Wilkinson, Distributed Transaction Management in Jasmin, Proceedings of the 10th International Conference on Very Large Data Bases, p.466-470, August 27-31, 1984
• MKM-84: Shojiro Muro , Tiko Kameda , Toshimi Minoura, Multi-version concurrency control scheme for a database system, Journal of Computer and System Sciences, v.29 n.2, p.207-224, Oct. 1984 [doi>10.1016/0022-0000(84)90031-X]
• Pa-79: 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]
• Pa-86: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• PBR-77: C H Papadlmltrmu, P A Bernstem and J B Rothme, "Some Computatmnal Problems Related to Database Concurrency Control", Proc of the Conf on Theoretical Computer Scmnce, Umv of Waterloo, pp 275-282, 1977
• PK-84: Christos H. Papadimitriou , Paris C. Kanellakis, On Concurrency Control by Multiple Versions, ACM Transactions on Database Systems (TODS), v.9 n.1, p.89-99, March 1984 [doi>10.1145/348.318588]
• Re-78: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• ST-87: R. Sun , G. Thomas, Performance results on multiversion timestamp concurrency control with predeclared writesets, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.177-184, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28678]
• We-85: William E. Weihl, Distributed version management for read-only actions (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.122-135, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323607]