GATE CSE 2020 | Question: 37

Question

Consider a schedule of transactions $T_1$ and $T_2$:

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & RA & & & RC & & WD & & WB & \text{Commit} &  \\ \hline T_2  & & RB & WB & & RD & &  WC & & & \text{Commit} \\ \hline \end{array}$

Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the above schedule?

• A. $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 &  & & & RA & RC & WD & WB & & \text{Commit} &  \\ \hline T_2  & RB & WB & RD & & & & & WC &  & \text{Commit} \\ \hline \end{array} \\$
• B. $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 & RA & RC &WD &WB & &  &  & & \text{Commit} &  \\ \hline T_2  & &  & & &RB & WB & RD& WC &  & \text{Commit} \\ \hline \end{array} \\$
• C. $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 &  RA & RC & WD &  &  &  & WB & & \text{Commit} &  \\ \hline T_2  &  &  & & RB & WB  & RD & & WC &  & \text{Commit} \\ \hline \end{array} \\$
• D. $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T_1 &  & & &  & RA & RC & WD & WB & \text{Commit} &  \\ \hline T_2  & RB & WB & RD & WC & & & &  &  & \text{Commit} \\ \hline \end{array}$

Comments

Can anyone explain how option C is not the answer? Dependency graphs of both A and C seem equivalent to that of the given schedule.

---

Similar question:

https://gateoverflow.in/3374/gate2008-it-63

---

In option C, we clearly see that there is swapping in conflict operations i.e. w1(D) and r2(D)

Answer 1

If you draw the dependency graph, you'll notice that there is a cycle. Hence Option (D) and Option (B) are straightaway False. 

Now in Option (C), there is a swapping operation of conflicting operations $W_1(D)$ and $R_2(D)$. Hence it's False as well.

Hence, Option(A) is the answer

Comments

@d3ba, @immanujs, @srestha, @Arjun

Can you please explain how the answer is option A. I am unable to understand how conflicting operations in option A and the question matches.

If we go by checking only conflict types (i.e R-W,W-R and W-W) without considering the variables on which they are conflicting then it matches with the order present in option B. Please help.

Thank you

Edit- I have understood the procedure of solving this problem 

---

I guess, there is a swapping operation of conflicting operations R1(c) and W2(C) not for W1(D) and R2(D) in option D

---

I think best way to tackle this problem is check conflicting pairs, they shouldn’t swap in conflict equivalent schedule.

---

@Pratik2404 thanks

Answer 2

A schedule $T_1$ is said to be conflict equivalent to another schedule if we can obtain $T2$ from $T1$ by swapping non-conflicting instructions.

$T1$	$RA$			$RC$		$WD$		$WB$	$COMMIT$
$T2$		$RB$	$WB$		$RD$		$WC$			$COMMIT$

---

A. let us try to get option $A$ by swapping non-conflicting instructions

$T1$	$RA$			$RC$		$WD$		$WB$	$COMMIT$
$T2$		$RB$	$WB$		$RD$		$WC$			$COMMIT$

We can swap $RA$ with $RB$

$T1$		$RA$		$RC$		$WD$		$WB$	$COMMIT$
$T2$	$RB$		$WB$		$RD$		$WC$			$COMMIT$

We can swap $RA$ with $WB$

$T1$			$RA$	$RC$		$WD$		$WB$	$COMMIT$
$T2$	$RB$	$WB$			$RD$		$WC$			$COMMIT$

We can swap $RC$ with $RD$ 

$T1$			$RA$		$RC$	$WD$		$WB$	$COMMIT$
$T2$	$RB$	$WB$		$RD$			$WC$			$COMMIT$

We can swap $RA$ with $RD$ 

$T1$				$RA$	$RC$	$WD$		$WB$	$COMMIT$
$T2$	$RB$	$WB$	$RD$				$WC$			$COMMIT$

 We can swap $WB$ with $WC$ 

$T1$				$RA$	$RC$	$WD$	$WB$		$COMMIT$
$T2$	$RB$	$WB$	$RD$					$WC$		$COMMIT$

$\therefore$ we have obtained schedule given in $A$ from schedule given in question , hence it is correct answer.

---

B.

$T1$	$RA$	$RC$	$WD$	$WB$					$COMMIT$
$T2$					$RB$	$WB$	$RD$	$WC$		$COMMIT$

 In question there was conflict from $R_2B \rightarrow W_1B$ but in this option the conflict is swapped i.e. $W_1B \rightarrow R_2B$

Hence it is incorrect.

---

C

$T1$	$RA$	$RC$	$WD$				$WB$		$COMMIT$
$T2$				$RB$	$WB$	$RD$		$WC$		$COMMIT$

 

 In question there was conflict from $R_2D \rightarrow W_1D$ but in this option the conflict is swapped i.e. $W_1D \rightarrow R_2D$

Hence it is incorrect.

---

D.

$T1$					$RA$	$RC$	$WD$	$WB$	$COMMIT$
$T2$	$RB$	$WB$	$RD$	$WC$						$COMMIT$

 In question there was conflict from $R_1C \rightarrow W_2C$ but in this option the conflict is swapped i.e. $W_2C \rightarrow R_1C$

Hence it is incorrect.

 

Answer 3

Two schedules are said to be conflict equivalent if the conflicting actions are similar in both of them

Conflicting condition:  (i) Two operations should be from different transactions

                                                     (ii) one of them must be write

                                                     (iii) both the operation should act on same data item

Here in the schedule given in question conflicting operations are :---

RC1 ---WC2  ,   RD2 ---WD1 ,    RB2 --- WB1 ,   WB2 ----WB1

In option( A) we can see that conflicting operations are similar to that of the schedule given in question. Ans; (A)

In option (B)  for example one of the conflicting operation WD1 --> RD2   Therefore can't be the answer.

In option (C) for example one of the conflicting operation WD1 --> RD2    Therefore can't be the answer.

In option (D) for example one of the conflicting operation WC2 --> RC1    Therefore can't be the answer.

Comments

I think this is sure shot method. Thanks @Srinivas_Reddy_Kotla Sir

Answer 4

Ans will be A)

If we draw graph only A) is conflict equivalent to the given question