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. That is the actions belong to different transactions, at least one of the actions is a write operation, and the actions access the same object (read or write).

Precedence graph examples

Example 1

:$S = \begin 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$

Example 2

:$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.
Notice, that the commit of Transaction 2 does not have any meaning regarding the creation of a precedence graph.

Testing Serializability with Precedence Graph

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

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

:or

$S = R1(A)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

# 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₃.
# 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.
# 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)'').
# 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₃.
# 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

{{Reflist

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 System Concepts (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.

Database management systems

el:Γράφος Σειριοποιησιμότητας
ru:Граф предшествования