Serialization Graph Algorithms for Multiversion Concurrency Control.

@inproceedings{DBLP:conf/pods/Hadzilacos88,
  author    = {Thanasis Hadzilacos},
  title     = {Serialization Graph Algorithms for Multiversion Concurrency Control},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {135-141},
  ee        = {http://doi.acm.org/10.1145/308386.308426, db/conf/pods/Hadzilacos88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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

Copyright © 1988 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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ACL-85]

Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121 BibTeX

[An-88]

...

[BBG-86]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX

[BEHR-80]

Rudolf Bayer, Klaus Elhardt, Hans Heller, Angelika Reiser: Distributed Concurrency Control in Database Systems. VLDB 1980: 275-284 BibTeX

[BG-83]

Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX

[BHG-87]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[BSW-79]

Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) BibTeX

[HP-85]

Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104 BibTeX

[HP-86]

Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. J. Comput. Syst. Sci. 33(2): 297-310(1986) BibTeX

[HY-86]

Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46 BibTeX

[KP-79]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19: 1-11(1983) BibTeX

[LW-84]

Ming-Yee Lai, W. Kevin Wilkinson: Distributed Transaction Management in Jasmin. VLDB 1984: 466-470 BibTeX

[MKM-84]

Shojiro Muro, Tiko Kameda, Toshimi Minoura: Multi-version Concurrency Control Scheme for a Database System. J. Comput. Syst. Sci. 29(2): 207-224(1984) BibTeX

[Ps-79]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[Pa-86]

...

[PBR-77]

...

[PK-84]

Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984) BibTeX

[Re-78]

...

[ST-87]

Rong Sun, Gomer Thomas: Performance Results in Multiversion Timestamp Concurrency Control with Predeclared Writesets. PODS 1987: 177-184 BibTeX

[We-85]

William E. Weihl: Distributed Version Management for Read-Only Actions (Extended Abstract). PODC 1985: 122-135 BibTeX

Referenced by

1. Tadeusz Morzy: The Correctness of Concurrency Control for Multiversion Database Systems with Limited Number of Versions. ICDE 1993: 595-604