edited by
6,535 views
30 votes
30 votes

Consider two transactions $T_1$ and $T_2$, and four schedules $S_1, S_2, S_3, S_4$,  of  $T_1$  and  $T_2$ as given below:

$T_1: R_1[x]W_1[x]W_1[y]$

$T_2: R_2[x]R_2[y]W_2[y]$

$S_1: R_1[x]R_2[x]R_2[y] W_1[x] W_1[y] W_2[y]$

$S_2: R_1[x]R_2[x]R_2[y] W_1[x] W_2[y] W_1[y]$

$S_3: R_1[x]W_1[x]R_2[x] W_1[y] R_2[y] W_2[y]$

$S_4: R_2[x]R_2[y]R_1[x] W_1[x] W_1[y] W_2[y]$

Which of the above schedules are conflict-serializable?

  1. $S_1 \text{ and } S_2$
  2. $S_2 \text{ and } S_3$
  3. $S_3$ only
  4. $S_4$ only
edited by

2 Answers

Best answer
32 votes
32 votes

The answer is B.

  • S1 has a cycle from $T1\to T2$ and $T2 \to T1.$
  • S2-- It is uni-directional and has only $T2\to T1.$
  • S3-- It is uni-directional and has only $T1\to T2.$
  • S4-- same as S1.

A schedule is conflict serializable if there is no cycle in the directed graph made by the schedules.

In the schedules we check for RW, WR, WW conflicts between the schedules and only these conflicts contribute in the edges of the graph.

edited by
Answer:

Related questions

61 votes
61 votes
6 answers
1