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

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

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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

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

Paul M. Bober, Michael J. Carey: Multiversion Query Locking. VLDB 1992: 497-510
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Thanasis Hadzilacos: Serialization Graph Algorithms for Multiversion Concurrency Control. PODS 1988: 135-141
Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Serializability with Constraints. ACM Trans. Database Syst. 12(3): 429-452(1987)
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
Thanasis Hadzilacos, Mihalis Yannakakis: Deleting Completed Transactions. PODS 1986: 43-46

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]