GATE CSE 2024 | Set 1 | Question: 36

Question

​​​​Consider the following read-write schedule $\text{S}$ over three transactions $T_{1}, T_{2}$, and $T_{3}$, where the subscripts in the schedule indicate transaction IDs:

$S: r_{1}(z) ; w_{1}(z) ; r_{2}(x) ; r_{3}(y) ; w_{3}(y) ; r_{2}(y) ; w_{2}(x) ; w_{2}(y) ;$

Which of the following transaction schedules is/are conflict equivalent to $\text{S}$?

• A. $T_{1} T_{2} T_{3}$
• B. $T_{1} T_{3} T_{2}$
• C. $T_{3} T_{2} T_{1}$
• D. $T_{3} T_{1} T_{2}$

Comments

When you draw a timeline table for this you will observe that transaction T1 doesn't matter where you put only there will be dependency between T2 and T3 and then play according to it.

Answer 1

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

The corresponding polygraph for the given transaction. it has three conflict pairs as $T_3\rightarrow T_2$ as $r_3(y)\rightarrow w_2(y),w_3(y)\rightarrow r_2(y),w_3(y)\rightarrow w_2(y)$.
Because the graph is acyclic it is CSS and its corresponding conflict equal schedule is based on the topological order of the given graph.

Therefore it's correct TS sequences are:

1. $T_1,T_3,T_2$
2. $T_3,T_1,T_2$
3. $T_3,T_2,T_1$

Option $(B, C, D)$ are correct.

Comments

The graph is correct but the sequences should be like _T3_T2_.in one of the underscore places we can have T1 and leave the others.
So, the correct options are B, C, and D.

Please correct me if I'm wrong.

---

Also,if anyone is wondering, CSS stands for Conflict Serializable Schedule.