A dynamic tree-locking protocol

The tree-locking protocol proposed by Silberschatz and Kedem⁵ guarantees transaction schedules that are both serializable and deadlock-free. The tree-locking protocol assumes the existence of a partial order defined over all of the objects in a database. Requiring all transactions to be tree-locked with respect to this single partial order limits the degree of concurrency obtainable in a database system by increasing the potential for conflict between transactions. In this paper we define a new locking protocol that is derived from the tree-locking protocol, but allows a changing set of partial orders to be defined over the objects in a database. We call this protocol dynamic tree-locking.