Precedence graph

A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.

The precedence graph for a schedule S contains:

• A node for each committed transaction in S
• An arc from T_i to T_j if an action of T_i precedes and conflicts with one of T_j's actions.

Precedence graph example

$D={\begin{bmatrix}T1&T2&T3\\&R(B)&\\R(C)&W(A)&\\W(C)&\\R(D)&&\\&&W(B)\\W(D)&&W(A)\\&\\\end{bmatrix}}$

or

$D=R1(A)$ $R2(B)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

A precedence graph of the schedule D, with 3 transactions. As there is a cycle (of length 2; with two edges) through the committed transactions T1 and T2, this schedule (history) is not Conflict serializable.

Testing Serializability with Precedence Graph

The drawing sequence for the precedence graph:-

1. For each transaction T_i participating in schedule S, create a node labelled T_i in the precedence graph. So the precedence graph contains T₁, T₂, T₃
2. For each case in S where T_i executes a write_item(X) then T_j executes a read_item(X), create an edge (T_i --> T_j) in the precedence graph. This occurs nowhere in the above example, as there is no read after write.
3. For each case in S where T_i executes a read_item(X) then T_j executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. This results in a directed edge from T₁ to T₂.
4. For each case in S where T_i executes a write_item(X) then T_j executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. This results in directed edges from T₂ to T₁, T₁ to T₃, and T₂ to T₃.
5. The schedule S is conflict serializable if the precedence graph has no cycles. As T₁ and T₂ constitute a cycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods.

External links

• The Fundamentals of Database Systems, 5th Edition the use of precedence graphs is discussed in chapter 17, as they relate to tests for conflict serializability.
• Abraham Silberschatz, Henry Korth, and S. Sudarshan. 2005. Database Systems Concepts (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.