On the power of safe locking

AbstractThe purpose of a database concurrency control is to allow only serializable executions of transactions, that is, to enforce safety. We study the properties of locking as a means to achieve safety. We consider the problem of whether it is possible to disallow by locking all nonserializable executions (or schedules) of a transaction system without disallowing any serializable schedule, that is, of whether the set of all serializable schedules (in the sense of conflict-preserving serializability) can be defined by locking. We present an efficient algorithm for deciding this problem for 2-transaction systems. Moreover, if the set of conflict-serializable schedules can be defined by locking, a corresponding deadlock-free locked transaction system can be constructed efficiently. For the case of an arbitrary number of transactions, we show that the conflict-serializable schedules can be defined by locking if this holds for all pairs of transactions and a certain “minimal” locked transaction system exists and is safe. Moreover, we introduce restrictions on locking which allow necessary and sufficient conditions