ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Algorithmic Aspects of Multiversion Concurrency Control.

Thanasis Hadzilacos, Christos H. Papadimitriou: Algorithmic Aspects of Multiversion Concurrency Control. PODS 1985: 96-104
@inproceedings{DBLP:conf/pods/HadzilacosP85,
  author    = {Thanasis Hadzilacos and
               Christos H. Papadimitriou},
  title     = {Algorithmic Aspects of Multiversion Concurrency Control},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {96-104},
  ee        = {http://doi.acm.org/10.1145/325405.325417, db/conf/pods/HadzilacosP85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Multiversion schedulers are now a widely accepted method for enhancing the performance of the concurrency control component of a database. In this paper we introduce a new notion of multiversion serializability (MVSR) based on conflicts (MVCSR), and discuss and its relation with the well known single version conflict serializability (CSR). On-line schedulable (OLS) subsets of MVSR were defined in [PK]. We prove here that it is NP-complete to decide whether a set of schedules is OLS. We next introduce the concept of maximal OLS sets, aand show that no efficient scheduler can be designed that recognizes maximal subsets of the MVSR or MVCSR schedules. Finally, a general framework for algorithms based on MVCSR is presented.

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


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

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

References

[BHR]
Rudolf Bayer, Hans Heller, Angelika Reiser: Parallelism and Recovery in Database Systems. ACM Trans. Database Syst. 5(2): 139-156(1980) BibTeX
[BG]
Philip A. Bernstein, Nathan Goodman: Multiversion Concurrency Control - Theory and Algorithms. ACM Trans. Database Syst. 8(4): 465-483(1983) BibTeX
[HY]
...
[IK]
...
[Pa1]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[Pa2]
...
[PK]
Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. ACM Trans. Database Syst. 9(1): 89-99(1984) BibTeX
[SB]
...
[SR]
Richard Edwin Stearns, Daniel J. Rosenkrantz: Distributed Database Concurrency Controls Using Before-Values. SIGMOD Conference 1981: 74-83 BibTeX
[Ya]
Mihalis Yannakakis: Issues of Correctness in Database Concurrency Control by Locking. STOC 1981: 363-367 BibTeX

Referenced by

  1. Paul M. Bober, Michael J. Carey: Multiversion Query Locking. VLDB 1992: 497-510
  2. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  3. Thanasis Hadzilacos: Serialization Graph Algorithms for Multiversion Concurrency Control. PODS 1988: 135-141
  4. Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Serializability with Constraints. ACM Trans. Database Syst. 12(3): 429-452(1987)
  5. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  6. Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:46 2009