ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Non-Two-Phase Locking Protocol for Concurrency Control in General Databases.

Partha Dasgupta, Zvi M. Kedem: A Non-Two-Phase Locking Protocol for Concurrency Control in General Databases. VLDB 1983: 92-94
@inproceedings{DBLP:conf/vldb/DasguptaK83,
  author    = {Partha Dasgupta and
               Zvi M. Kedem},
  editor    = {Mario Schkolnick and
               Costantino Thanos},
  title     = {A Non-Two-Phase Locking Protocol for Concurrency Control in General
               Databases},
  booktitle = {9th International Conference on Very Large Data Bases, October
               31 - November 2, 1983, Florence, Italy, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1983},
  isbn      = {0-934613-15-X},
  pages     = {92-94},
  ee        = {db/conf/vldb/DasguptaK83.html},
  crossref  = {DBLP:conf/vldb/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A database is viewed as a collection of data objects which can be read or written by concurrent transactions. Interleaving of updates can leave the database in an inconsistent state. A sufficient condition to guarantee consistency of the database is serializability of the actions (reads or writes) performed by the transactions on the data items, that is, the interleaved execution of the transactions should be equivalent to some serial execution of the transaction [1,2,7]. Here we will assume serializability as the criterion of correctness.

The 2-phase locking protocol is a well known protocol which procedures serializable logs (Eswaran[4]. In database concurrency control we re not interested in all possible serializable logs. We are interested in logs which maximize allowable concurency. However 2-phase locking does far scoring high in this criterion. There are serializable logs, allowing far more concurrency than any 2-phase locked log.

To achieve greater concurrency, we need to have more information about transaction behavior. One approach is to structure the database as a DAG (directed acyclic graph) (Kedem[5]). In this case non-2-phase bevaior is attainable, and due to exploitation of the structure of the database to constrain transaction behavior it appears to provide higher concurrency. Another approach is to know in advance the readset and writeset of the transactions. This approach has been used for deadlock avoidance but not for geining on concurrency [1]. Knowing the exact readset (or writeset) of a transaction is not always feasible, however a superset of the readset (or writeset) can be statistically determined. We will assume this strategy and demonstrate how this information can be used to achieve higher concurrency.

Copyright © 1983 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Mario Schkolnick, Costantino Thanos (Eds.): 9th International Conference on Very Large Data Bases, October 31 - November 2, 1983, Florence, Italy, Proceedings. Morgan Kaufmann 1983, ISBN 0-934613-15-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Christos H. Papadimitriou, Paris C. Kanellakis: On Concurrency Control by Multiple Versions. PODS 1982: 76-82 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:57 2010 by Michael Ley (ley@uni-trier.de)