Maximal concurrency locking

Abstract

The purpose of a database concurrency control mechanism is to control a transaction system in such a way that only serializable executions of transactions are possible; that is, safety is enforced. Locking is an appropriate means to achieve safety. In this paper the following problem is considered: Can the set of all serializable schedules (in the sense of conflict-preserving serializability) of a transaction system be defined by locking, i.e., can maximal concurrency be achieved by locking? An efficient algorithm exists for the problem in the case of two-transaction systems, but in general the problem is NP-complete. In the case in which maximal concurrency indeed is achievable by locking a locking policy realizing maximal concurrency can be constructed efficiently. Finally, an easy-totest sufficient condition under which maximal concurrency is achieved by locking is discussed.