Conceptual level concurrency control of relational update transactions (Q1186426)

The authors present a theoretical approach to the problem of using semantic information (that goes beyond simple commutativity of updates) to increase the concurrency of transactions. A transaction is viewed as a sequence of insertions, deletions or modifications, forming a semantic unit. This model allows both to increase concurrency and to extract internal parallelism from transactions. Both static serializability testing and dynamic scheduling of transactions are investigated, in the frame of a notion of serializability of a schedule that is defined entirely semantically. Static serializability testing is shown to be NP- complete, but an infinite sequence of increasingly powerful polynomial- time testing algorithms, which approximate exact serializability testing, is given. For less powerful transactions (where no modifications appear) efficient exact serializability testing algorithms are shown to exist. The authors also study how more concurrency in schedules can be gained if the concurrency control problem is considered in the presence of constraint information (functional dependencies). The dynamic scheduler is a nonlocking scheduling algorithm based on serializability graph testing; it generates a larger class of correct schedules than that generated when only conflicts between pairs of updates are considered.