Precedence graph

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

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 examples

Example 1

Example 2

${\displaystyle S={\begin{bmatrix}T1&T2\\R(A)&R(A)\\A=A*5&R(B)\\W(A)&B=B+A\\R(B)&W(B)\\B=B*10&\\W(B)&\\\end{bmatrix}}}$

Example 2

${\displaystyle D=R1(A)}$ ${\displaystyle R2(B)}$ ${\displaystyle W2(A)}$ ${\displaystyle Com.2}$ ${\displaystyle W1(A)}$ ${\displaystyle Com.1}$ ${\displaystyle W3(A)}$ ${\displaystyle 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. Notice, that the commit of Transaction 2 does not have any meaning regarding the creation of a precedence graph.

Testing Serializability with Precedence Graph

Testing Serializability Example

Algorithm to test Conflict Serializability of a Schedule S along with an example schedule.

${\displaystyle S={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\\end{bmatrix}}}$

or

${\displaystyle S=R1(A)}$ ${\displaystyle W2(A)}$ ${\displaystyle Com.2}$ ${\displaystyle W1(A)}$ ${\displaystyle Com.1}$ ${\displaystyle W3(A)}$ ${\displaystyle Com.3}$

1. For each transaction T_x participating in schedule S, create a node labeled T_i in the precedence graph. Thus the precedence graph contains T₁, T₂, T₃.
2. For each case in S where T_j executes a read_item(X) after T_i executes a write_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_j executes a write_item(X) after T_i executes a read_item(X), create an edge (T_i → T_j) in the precedence graph. This results in a directed edge from T₁ to T₂ (as T₁ has R(A) before T₂ having W(A)).
4. For each case in S where T_j executes a write_item(X) after T_i 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 serializable if and only if the precedence graph has no cycles. As T₁ and T₂ constitute a cycle, the above example is not (conflict) serializable.

References

1. "Precedence graph test for conflict-serializability".

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.