
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 eventstate 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