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
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
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - 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