**Precedence Graph(serialization graph)**

It is a directed graph G with set of nodes N (T_{1}, T_{2}, T_{3}, …, T_{n}) and set of directed edges E (E_{1}, E_{2}, …, E_{m}).

**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 T_{i}to T_{j}as T_{i}-> T_{j}if one of the following condition is true.(conflict operations).**Read-Write Conflict:**Create a directed edge T_{i}-> T_{j}if T_{j}reads data item (e.g. X) written by T_{i}.**Write-Read Conflict:**Create a directed edge T_{i}-> T_{j}if T_{j}writes into data item (e.g. X) after it has been read by T_{i}.**Write-Write Conflict:**Create a directed edge T_{i}-> T_{j}if T_{j}writes into data item (e.g. X) after it has been written by T_{i}.

**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.