3,048 views

Consider following schedules involving two transactions:

$S_{1}: \: r_{1}(X);r_{1}(Y);r_{2}(X);r_{2}(Y);w_{2}(Y);w_{1}(X)$

$S_{2}: \: r_{1}(X);r_{2}(X);r_{2}(Y);w_{2}(Y);r_{1}(Y);w_{1}(X)$

Which of the following statement is true?

1. Both $S_1$ and $S_2$ are conflict serializable.
2. $S_1$ is conflict serializable and $S_2$ is not conflict serializable
3. $S_1$ is not conflict serializable and $S_2$ is conflict serializable
4. Both $S_1$  and $S_2$ are not conflict serializable

1 comment

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

In S2: r2(X) followed by w1(X) will give edge from 2 to 1 hence option 3 should be correct.
Yes option 3
ya i have done a mistake. corrected it now in the answer. Thanks for pointing out

Option 3

Option B is correct.

The precedence graph for schedule S1 contains a cycle T1-T2-T1, while the schedule S2 has no cycle.
by