retagged by
5,420 views
9 votes
9 votes

Let $r_i(z)$ and $w_i(z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_i$. Consider the following two schedules.

  • $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 one of the following options is correct?

  1. $S_1$ is conflict serializable, and $S_2$ is not conflict serializable
  2. $S_1$ is not conflict serializable, and $S_2$ is conflict serializable
  3. Both $S_1$ and $S_2$ are conflict serializable
  4. Niether $S_1$ nor $S_2$ is conflict serializable
retagged by

3 Answers

Best answer
6 votes
6 votes

$\begin{array}{c|c} \hline 
\bf{T_1} & \bf{T_2} \\ \hline
r_1(x)\\
r_1(y) \\
&r_2(x)\\
&r_2(y) \\
&w_2(y) \\
w_1(x) \\ \hline
\end{array}$

Here $r_1(y)$ and $w_2(y)$ are conflicting pairs, giving $T_1\rightarrow T_2$ and $r_2(x)$ and $w_1(x)$ giving $T_2\rightarrow T_1$, so the schedule is not conflict serializable.


$\begin{array}{c|c} \hline 
\bf{T_1} & \bf{T_2} \\ \hline
r_1(x)\\
&r_2(x)\\
&r_2(y) \\
&w_2(y)\\
r_1(y)\\
w_1(x) \\ \hline
\end{array}$

Here $r_2(x)$ and $w_1(x)$ are conflicting pairs giving $T_2\rightarrow T_1$, and $w_2(y)$ and $r_1(y)$ also giving $T_2\rightarrow T_1$, therefore this schedule is conflict serializable.

Correct Option B

edited by
5 votes
5 votes

A schedule $S$ is CSS if their precedence graph is acyclic. A precedence graph can have cycle iff:

  • either read-write conflict
  • either write-read conflict
  • either write-write conflict.

Precedence graph of schedule $S_1$: following conflicts resent in schedule $S_1$

  1. $r_1(y)\rightarrow w_2(y)$
  2. $r_2(x)\rightarrow w_1(x)$

Precedence graph of schedule $S_2$: Following conflicts present in schedule $S_2$

  1. $r_2(x)\rightarrow w_1(x)$
  2. $w_2(y)\rightarrow r_1(y)$

It is clearly visible that $S_1$ having a cycle so it’s not CSS whereas $S_2$ is acyclic graph, it’s CSS.

Option $B$ is correct.

 

 

edited by
3 votes
3 votes
In Schedule 1: R1(y) is conflicting with W2(y) therefore in the precedence graph there will be edge from T1->T2.Also,R2(x) is conflicting with W1(x) therefore there will be edge from T2->T1.

Precedence graph of S1 is having cycle hence S1 is not conflict serializable.

In Schedule 2: R2(x) is conflicting with W1(x) therefore there will be edge from T2->T1 in precedence graph.W2(y) is conflicting with R1(y) therefore edge T2->T1.

Precedence graph of S2 is not having any cycle hence S2 is conflict serializable.

Answer is : (B)
Answer:

Related questions