Safe Locking Policies for Dynamic Databases

Vinay K. Chaudhri and Vassos Hadzilacos

Yannakakis showed that a locking policy is not safe if and only if it allows a canonical nonserializable schedule of transactions in which all transactions except one are executed serially \cite{Yannakakis-JACM-82}. In the present paper, we study the generalization of this result to a dynamic database, that is, a database that may undergo insertions and deletions of entities. We illustrate the utility of this generalization by applying it to obtain correctness proofs of three locking policies that handle dynamic databases.