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

Schedule $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)$.

List conflicting pairs (same item, different transactions, at least one write), in schedule order:
- On $x$: $R_4(x),R_2(x),R_3(x)$ all come before $W_2(x)$: $T_4\to T_2$ and $T_3\to T_2$.
- On $y$: $R_1(y),W_1(y)$ come before $W_3(y)$: $T_1\to T_3$. $W_1(y)$ and $W_3(y)$ come before $R_4(y)$: $T_1\to T_4$ and $T_3\to T_4$.

Edges: $T_1\to T_3$, $T_1\to T_4$, $T_3\to T_4$, $T_3\to T_2$, $T_4\to T_2$. The only topological order is
$$T_1\to T_3\to T_4\to T_2:\text{ option (A)}.$$

More Transactions and Concurrency Control questions

All Transactions and Concurrency Control questions →