Context-specific synchronization for atomic data types in object-based databases

Reviewer: William Campbell McGee

The concurrency control protocol described in this paper is an extension of that described by Weihl [1]. The purpose of Weihl's work was to study the interaction between concurrency control and recovery. Recovery was recognized by including abort and commit events in the computational model, and by deriving the conditions that transaction operation conflict relations must satisfy in order for system operation to be correct under two commonly-used database updating protocols: update in place (UIP), in which database updates occur at the time transactions request them, and deferred update (DU), in which updates occur at a transaction commit time. Weihl noted in passing that other updating protocols that place fewer constraints on concurrency control might be possible. This paper proposes such a protocol. It is a hybrid protocol, which permits operations that commute under either of the UIP and DU protocols to be excluded from the transaction operation conflict relation; this results in a larger class of correct transaction histories than results from the use of the UIP or DU protocol alone. For added concurrency, this protocol uses the ordered shared locks described by Agrawal and El Abbadi [2]. This is a generalization of two-phase locking in which exclusive locks are replaced by ordered shared locks, and operations by different transactions on the same object are executed in the same order that ordered shared locks on the object are acquired. Various degrees of permissivity are possible, the most permissive of which recognizes the entire class of conflict-preserving serializable histories. The paper shows how progressively greater concurrency is achieved starting with the UIP and DU protocols separately, then using the hybrid protocol with standard two-phase locking, and finally using the hybrid protocol with ordered shared locks. The hybrid protocol has several problems, including circularity in determining conflicts (the response of an operation must be known before the transaction's view can be determined, but the response of the operation depends on the transaction's view); the potential for deadlock in satisfying the requirement that a transaction may not release locks as long as it is waiting for another transaction to release a lock; and the additional complexity of combining the UIP and DU protocols. (A transaction's view of the database reflects not only its own processing and that of already committed transactions, but the processing of uncommitted transactions as well. ) Various implementation solutions to these problems are discussed. The paper is carefully written, but the exposition is not as lucid as that in the two papers on which it is based. Readers unfamiliar with these papers may wish to read them first.