Accession Number : ADA187033
Title : Nested Transactions, Conflict-Based Locking, and Dynamic Atomicity.
Descriptive Note : Technical rept.,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Personal Author(s) : Fekete, Alan ; Lynch, Nancy ; Merritt, Michael ; Weihl, William
PDF Url : ADA187033
Report Date : Sep 1987
Pagination or Media Count : 57
Abstract : In this paper examines some concurrency control algorithms for nested transaction systems. A simple local property called dynamic atomicity is defined for data objects in such a system, and we show that all the executions of a system are serially correct (despite concurrency and transaction aborts) provided each data object is dynamic atomic. This result is applied to give a correctness proof for a new algorithm, called Conflict Based Locking, for managing data in a nested transaction system. The algorithm uses a table specifying which operations may not proceed concurrently to determine when an operation may be granted a lock on an object. The algorithm is an extension of a general conflict-based locking protocol introduced by Weihl for transaction systems without nesting. It is also similar to Moss' algorithm, which uses read- and write- locks and a stack of versions of each object to ensure the serializability and recoverability of transactions accessing the data. We show that objects implemented using Moss' algorithm of the new Conflict-Based Locking algorithm are dynamic atomic. Thus it follows that if each object in a nested transaction system uses either Moss' algorithm or the new Conflict-Based Locking algorithm, then all executions of the system will be serially correct.
Descriptors : *ALGORITHMS, *DATA MANAGEMENT, CONTROL, DATA BASES, SEMANTICS, INPUT OUTPUT PROCESSING, SERIAL PROCESSORS
Subject Categories : Computer Systems
Distribution Statement : APPROVED FOR PUBLIC RELEASE