What is the graph-based locking technique? Explain.

Concept

A graph-based locking protocol imposes a partial order on database items and represents that order as a directed acyclic graph (DAG). An edge from item Qᵢ to item Qⱼ means that a transaction needing both items must lock Qᵢ before Qⱼ.

The fixed acyclic order prevents transactions from forming a circular wait. The tree protocol is the standard simple form of this technique.

Application

1. Represent every lockable data item as a node. Direct each edge from a predecessor item to an item that may be locked after it.

2. Under the tree protocol, a transaction may lock any node as its first lock. After that, it may lock a node only while it holds a lock on that node’s parent.

3. A transaction may unlock an item at any time, but it cannot lock that same item again later. Therefore, unlocking can begin before all locks have been acquired, unlike two-phase locking.

4. Because every acquisition follows an acyclic parent-to-child order, the resulting schedules are conflict-serializable and circular wait—and hence deadlock under this protocol—cannot occur.

Cross-check and limitations

• Deadlock freedom follows from the DAG: a wait cycle would require a cycle in the prescribed lock order.

• Early unlocking can improve concurrency, but the protocol requires advance knowledge of the data-access order.

• The basic tree protocol does not by itself guarantee recoverability or freedom from cascading rollbacks, so a practical system needs appropriate recovery or commit rules.

Thus, graph-based locking controls concurrent access by forcing lock acquisition to follow an acyclic dependency order; the tree protocol is its common example.