A Theory of Correct Locking Protocols for Database Systems.

Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: A Theory of Correct Locking Protocols for Database Systems. VLDB 1981: 112-124
  author    = {Donald S. Fussell and
               Zvi M. Kedem and
               Abraham Silberschatz},
  title     = {A Theory of Correct Locking Protocols for Database Systems},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {112-124},
  ee        = {db/conf/vldb/FussellKS81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP,}


In database systems which allow concurrent processing, it is necessary to control the interaction among the concurrent transactions in order to prevent them from destroying the consistency of the database. The most common mechanism proposed to achieve this involves the use of locking and unlocking instrucions to provide controlled access to units of shared data. These instructions are embedded in the transactions according to rules which are called locking protocols. A correct locking protocol assures that the consistency of the database is preserved and that no deadlocks occur to prevent termination of the transactions. In this paper, a theory is developed of how a priori syntactic information about the behavior of the transactions in a system can be used to construct correct protocols. The relationship between the problems of assuring correctness and deadlock-freedom is explored in a unified model which applies to systems which allow only exclusive locks as well as to systems which allow both exclusive and shared access nodes.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

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

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX


Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971) BibTeX
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) BibTeX
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
Zvi M. Kedem, Abraham Silberschatz: Controlling Concurrency Using Locking Protocols (Preliminary Report). FOCS 1979: 274-285 BibTeX
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
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) BibTeX
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock. FOCS 1979: 286-297 BibTeX

Referenced by

  1. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
  2. Jianwen Su: Safety of Non-Well-Locked Trasnaction Systems. PODS 1986: 47-52
  3. Ouri Wolfson, Mihalis Yannakakis: Deadlock-Freedom (and Safety) of Transactions in a Distributed Database. PODS 1985: 105-112
  4. Zvi M. Kedem, C. Mohan, Abraham Silberschatz: An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking Protocols. VLDB 1982: 91-97
  5. Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92
  6. C. Mohan, Donald S. Fussell, Abraham Silberschatz: Compatibility and Commutativity in Non-two-phase Locking Protocols. PODS 1982: 283-292
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:11 2009