Locking based on a pairwise decomposition of a transaction system

Locking is a synchronization primitive used in database systems to guarantee correctness of a concurrent execution of a set of user transactions accessing the database. The way locking is used should not restrict potential concurrency more than necessary. Thus, there is the problem how to insert lock and unlock operations into the transactions. This paper surveys work on locking, which is based on a pairwise decomposition of the transaction system. Such a decomposition supports the application of two-dimensional geometric techniques, which have truned out to be very helpful in designing locking algorithms.