recategorized
3,825 views
1 votes
1 votes

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
recategorized

7 Answers

0 votes
0 votes

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

0 votes
0 votes
Option B is correct.

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

Related questions

1 votes
1 votes
3 answers
4
go_editor asked Jan 31, 2017
8,521 views
If following sequence of keys are inserted in a B+ tree with K(=3) pointers:8, 5, 1, 7, 3, 12, 9, 6Which of the following shall be correct B+ tree?