In a DBMS, when multiple transactions request locks or compete for data, the system needs a way to track dependencies so it can avoid non‑serializable schedules and deadlocks.
Graph‑based protocols use directed graphs (like wait‑for graphs and precedence graphs) to model which transactions are waiting for which others or which ones must execute before others. These graphs are then analyzed to decide when to allow, block, or abort transactions.
What Is a Graph‑Based Protocol?
A graph‑based protocol is a concurrency‑control method that represents relationships between transactions as nodes and edges in a graph.
Nodes represent transactions.
Edges represent dependencies (waiting or execution order).
The DBMS periodically checks the graph for undesirable patterns (like cycles) and takes action (for example, aborting a transaction) to restore correctness.
Two important kinds of graphs are:
Wait‑for graph (for deadlock detection).
Precedence graph (for checking serializability).
For beginners, the key idea is:
“The system draws a picture of who is waiting for whom, and then uses that picture to decide what to do.”
Wait‑For Graph and Deadlock Detection
A wait‑for graph is used to detect deadlocks in lock‑based systems.
Each node = a transaction waiting for a lock.
An edge = “Transaction is waiting for a resource held by .”
Whenever any transaction waits for a lock that another transaction holds, the DBMS adds an edge to the wait‑for graph.
If the graph develops a cycle, it means there is a deadlock: each transaction in the cycle is waiting for the next one, and none can proceed.
At that point, the DBMS chooses one transaction (often the youngest or the one with the least work) to abort, breaking the cycle and allowing the others to continue.
Why the Wait‑For Graph Matters
It gives a simple, visual way to detect deadlocks.
It allows the system to recover from deadlocks quickly by aborting one victim transaction.
It forms the core of lock‑based deadlock detection in many real‑world DBMS products.
Precedence Graph and Serializability
A precedence graph is used to decide whether a schedule is conflict serializable.
Each node = a transaction.
An edge = “Transaction has a conflicting operation that comes before a conflicting operation of .”
Once the precedence graph is built, the DBMS checks for cycles:
If there is no cycle, the schedule is conflict serializable.
If there is a cycle, the schedule is not conflict serializable and may be rejected or controlled differently.
Why the Precedence Graph Matters
It gives a mechanical way to check serializability without simulating every possible interleaving.
It connects the locking or timestamp decisions to the final correctness of the schedule.
For beginners, it shows that concurrency control is not just about “blocking operations” but about preserving a safe order between transactions.
Summary
Graph‑based protocol in DBMS is a concurrency control technique that uses directed graphs (like wait‑for graphs and precedence graphs) to model dependencies between transactions. The wait‑for graph helps detect and break deadlocks, while the precedence graph helps decide whether a schedule is conflict serializable. By analyzing these graphs, the DBMS can allow safe concurrency, block harmful interference, and quickly recover when problems arise, making graph‑based protocols a powerful tool for ensuring correctness and reliability.