The GATE Grind

GATE 2022 CS – Question 39

Databases · Transactions and Concurrency Control · 2 marks · Multiple choice

Let $R_i(z)$ and $W_i(z)$ denote read and write operations on a data element $z$ by a transaction $T_i$, respectively. Consider the schedule $S$ with four transactions.
$S: R_4(x)R_2(x)R_3(x)R_1(y)W_1(y)W_2(x)W_3(y)R_4(y)$
Which one of the following serial schedules is conflict equivalent to $S$?

  1. $T_1\to T_3\to T_4\to T_2$
  2. $T_1\to T_4\to T_3\to T_2$
  3. $T_4\to T_1\to T_3\to T_2$
  4. $T_3\to T_1\to T_4\to T_2$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $T_1\to T_3\to T_4\to T_2$

Explanation

On x, $R_4$ and $R_3$ precede $W_2$, giving $T_4\to T_2$ and $T_3\to T_2$. On y, $W_1\to W_3$, $W_1\to R_4$ and $W_3\to R_4$ give $T_1\to T_3\to T_4$. The only topological order is $T_1\to T_3\to T_4\to T_2$.