3,234 views

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

1 comment

previous year GATE 2007 question!!!

3 Answers

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_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

by

1 comment

in S2 r2(x) and w1(x)

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.

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:

7 votes
2 answers
1
12 votes
2 answers
2
4 votes
2 answers
3
9 votes
4 answers
4
3,814 views