# Precedence Graph For Testing Conflict Serializability

Precedence Graph(serialization graph)
It is a directed graph G with set of nodes N (T1, T2, T3, …, Tn) and set of directed edges E (E1, E2, …, Em).
Algorithm for construction of Precedence Graph:

• Create Nodes in the precedence graph equal to the number of transactions in the schedule S.
• Create directed edge from Ti to Tj as Ti -> Tj if one of the following condition is true.(conflict operations).
1. Read-Write Conflict:Create a directed edge Ti -> Tj if Tj reads data item (e.g. X) written by Ti.
2. Write-Read Conflict:Create a directed edge Ti -> Tj if Tj writes into data item (e.g. X) after it has been read by Ti.
3. Write-Write Conflict:Create a directed edge Ti -> Tj if Tj writes into data item (e.g. X) after it has been written by Ti.
• The Schedule S is serializable if there is no cycle in the precedence graph.
• Example: R1(X),R2(Y),R2(Y),W2(X),W3(Y),R1(X) • First draw all the transactions in the precedence graph • Check if there is a Tj that reads an item after  Ti writes it.
• T1 reads X after it has been written by T2, so there is a directed edge from T2 -> T1 • Check if there is a Tj that write an item after Ti reads it.
• T2 writes X after T1 reads it, so there is a directed edge from T1 -> T2
• T3 writes Y after T2 reads it, so there is a directed edge from T2 -> T3 • Check if there is a Tj that writes an item after  Ti writes it.
• not in this case. So above graph is the final graph.
• Above graph is cyclic as there is a cycle between T1 and T2, and therefore it is not conflict serializable.