Accession Number : ADA132501

Title :   Concurrency Control for Resilient Nested Transactions.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Lynch,Nancy A

PDF Url : ADA132501

Report Date : Feb 1983

Pagination or Media Count : 33

Abstract : A formal framework is developed for providing correctness of algorithms which implement nested transactions. In particular, a simple action tree data structure is defined, which describes the ancestor relationships among executing transactions and also describes the views which different transactions have of the data. A generalization of serializability to the domain of nested transactions with failures is defined. A characterization is given for this generalization of serializability, in terms of absence of cycles in an appropriate dependency relation on transactions. A slightly simplified version of Moss' locking algorithm is presented in detail, and a careful correctness proof is given. The style of correctness proof appears to be quite interesting in its own right. The description of the algorithm, from its initial specification to its detailed implementation, is presented as a series of event-state algebra levels, each of which simulates the previous one in a straightforward way. (Author)

Descriptors :   *Algorithms, *Corrections, *Data bases, *Control theory, Data management, Data processing, Algebra, Trees, Maps, Computer programming, Simulation

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE