in Databases retagged ago by
2,812 views
6 votes
6 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
in Databases retagged ago by
by
2.8k views

1 comment

previous year GATE 2007 question!!!
0
0

3 Answers

2 votes
2 votes
Best answer

$\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_2(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

selected by

1 comment

in S2 r2(x) and w1(x)
0
0
2 votes
2 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)
2 votes
2 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
Answer:

Related questions