Synchronization in Nested Transactions

Database systems take advantage of concurrent activities in order to offerbetter throughput and response time for programs accessing the shared data. Inspite of employing concurrency, database systems offer a a programmingenvironment where the applications programmer is not required to write programsthat have to synchronize to each other. The scheduler is the database systemcomponent that manages the concurrent accesses. The execution of applicationprograms as seen by the scheduler is called a transaction. The schedulerensures that, in spite of the possible interleaving of accesses, the effects ofthe transactions will appear atomic to each other. The scheduler does this byfollowing a concurrency control protocol. Transaction atomicity in terms ofconcurrency control issues is know as {\\it serializability}. Most of theschedulers ensures conflict serializability, by basing their decisions on aconflict or commutativity based predicate defined on the atomic operationsinvoked by the transactions. Conflict and commutativity predicates capture thenotion of a potential interference between transactions. Traditionalserializability theory deals with ``flat\'\' transactions, i.e., transactionsthat can only call atomic database operations.This dissertation presents two contributions in the area of serializability ofa special type of transaction called nested transactions. Nested transactionsmainly differ from traditional or \"flat\" transactions in the sense that theyoffer concurrency control within transactions by serializing subtransactions,i.e., transactions can call other transactions. There exists two components ina nested transaction execution. The first component is the hierarchy oftransactions and the second is the level of the atomic database accessesoperations. Our first contribution is a theoretical framework where theserializability of nested transactions can be formally proven. Such frameworkcan be used whenever serializability is based on a conflict predicate at thelevel of the atomic database access operations. The second contribution is thespecification of protocols that can be used in schedulers coping with nestedtransactions. The protocols are novel in the sense that they can use semanticinformation of the programs associated to the hierarchy of transactions inorder to enhance concurrency. We present formal correctness proofs of theproposed protocols.