Dark Mode

3,173 views

8 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?

- $S_1$ is conflict serializable, and $S_2$ is not conflict serializable
- $S_1$ is not conflict serializable, and $S_2$ is conflict serializable
- Both $S_1$ and $S_2$ are conflict serializable
- Niether $S_1$ nor $S_2$ is conflict serializable

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

3 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$

- $r_1(y)\rightarrow w_2(y)$
- $r_2(x)\rightarrow w_1(x)$

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

- $r_2(x)\rightarrow w_1(x)$
- $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.

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)

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)