Concurrency Control in Graph Protocols by Using Edge Locks.

Gael N. Buckley, Abraham Silberschatz: Concurrency Control in Graph Protocols by Using Edge Locks. PODS 1984: 45-50

@inproceedings{DBLP:conf/pods/BuckleyS84,
  author    = {Gael N. Buckley and
               Abraham Silberschatz},
  title     = {Concurrency Control in Graph Protocols by Using Edge Locks},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {45-50},
  ee        = {http://doi.acm.org/10.1145/588011.588019, db/conf/pods/BuckleyS84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A large number of locking protocols use precedence relations among data items to ensure the serializability of the database system. These protocols have extended the semantics of the exclusive lock from prohibiting access to a data item to prohibiting access to an entire subgraph. In this paper we argue that combining the use of exclusive locks for these different purposes is ill conceived. We present a general theory on how these two distinct functions can be separated into the traditional locks operating on the individual data items, and a corresponding set operating on the edges of graph. This is illustrated by a general transformation from a given graph protocol to the new edge protocol which preserves the major properties of the original protocol. We then give a characterization for a large class of edge lock protocols within a database system, which includes most previous locking protocols defined on databases organized as graphs. We show how this separation increases concurrency, and generalizes previously unrelated concepts, such as using deadlock avoidance locks in general locking protocols.

Copyright © 1984 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 Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]: ...
[2]: 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
[3]: Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317 BibTeX
[4]: Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) BibTeX
[5]: Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[6]: Henry F. Korth: Deadlock Freedom Using Edge Locks. ACM Trans. Database Syst. 7(4): 632-652(1982) BibTeX
[7]: Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX
[8]: Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) BibTeX
[9]: Mihalis Yannakakis: Freedom from Deadlock of Safe Locking Policies. SIAM J. Comput. 11(2): 391-408(1982) BibTeX

Referenced by

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

BibTeX

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