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