|
|
|
@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}
}
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.
