In order to check conflict serializability of graph ,we need to construct precedence graph
Testing for conflict serializability:
Algorithm
1. For each transaction Ti participating in schedule S, create a node labelled Ti in the precedence graph
2. For each case in S where Tj executes a read item(X) after Ti executes a write item(X), create an edge (Ti −→ Tj ) in the precedence graph.
3. For each case in S where Tj executes a write item(X) after Ti executes a write item(X), create an edge (Ti −→ Tj ) in the precedence graph.
4. For each case in S where Tj executes a write item(X) after Ti executes a read item(X), create an edge (Ti −→ Tj ) in the precedence graph.
5. The schedule S is serializable if and only if there is no cycle in the precedence graph.
S1 : r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)
r1(Y) followed by W2(Y) edge from 1 to 2
r2(X) followed by w1(X) edge from 2 to 1
so cycle . S1 is not conflict serializable
S2 : r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)
r2(X) followed by w1(X) edge from 2 to 1
w2(Y) followed by r1(Y) edge from 2 to 1
No cycle . S2 is conflict serializable
S1 is not conflict serializable. S2 is conflict serializable