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

Maximal Concurrency by Locking.

Georg Lausen, Eljas Soisalon-Soininen, Peter Widmayer: Maximal Concurrency by Locking. PODS 1984: 38-44
@inproceedings{DBLP:conf/pods/LausenSW84,
  author    = {Georg Lausen and
               Eljas Soisalon-Soininen and
               Peter Widmayer},
  title     = {Maximal Concurrency by Locking},
  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     = {38-44},
  ee        = {http://doi.acm.org/10.1145/588011.588018, db/conf/pods/LausenSW84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The purpose of a database concurrency control mechanism is to control a transaction system in such a way that only serializable executions of transactions are possible; that is, safety is enforced. Locking is an appropriate means to achieve safety. In this paper the following problem is considered:

Can the set of all serializable schedules (in the sense of conflict-preserving serializability) of a transaction system be defined by locking, i.e., can maximal concurrency be achieved by locking?

An efficient algorithm exists for the problem in the case of two-transaction systems, but in general the problem is NP-complete. In the case in which maximal concurrency indeed is achievable by locking a locking policy realizing maximal concurrency can be constructed efficiently. Finally, an easy-to-test sufficient condition under which maximal concurrency is achieved by locking is discussed.

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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... 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]
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
[2]
Witold Lipski Jr., Christos H. Papadimitriou: A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems. J. Algorithms 2(3): 211-226(1981) BibTeX
[3]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[4]
Christos H. Papadimitriou: A theorem in database concurrency control. J. ACM 29(4): 998-1006(1982) BibTeX
[5]
Christos H. Papadimitriou: Concurrency Control by Locking. SIAM J. Comput. 12(2): 215-226(1983) BibTeX
[6]
...
[7]
Eljas Soisalon-Soininen, Derick Wood: Optimal Algorithms to Compute the Closure of a Set of Iso-Rectangles. J. Algorithms 5(2): 199-214(1984) BibTeX
[8]
Mihalis Yannakakis: Issues of Correctness in Database Concurrency Control by Locking. STOC 1981: 363-367 BibTeX
[9]
Mihalis Yannakakis: Freedom from Deadlock of Safe Locking Policies. SIAM J. Comput. 11(2): 391-408(1982) BibTeX
[10]
Mihalis Yannakakis: A Theory of Safe Locking Policies in Database Systems. J. ACM 29(3): 718-740(1982) 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
    Contents
  2. Georg Lausen, Eljas Soisalon-Soininen, Peter Widmayer: Pre-Analysis Locking: A Safe and Deadlock Free Locking Policy. VLDB 1985: 270-281
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:44 2009