The GATE Grind

GATE 2021 CS – Question 42

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

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?

  1. $S_1$ is conflict serializable, and $S_2$ is not conflict serializable.
  2. $S_1$ is not conflict serializable, and $S_2$ is conflict serializable.
  3. Both $S_1$ and $S_2$ are conflict serializable.
  4. Neither $S_1$ nor $S_2$ is conflict serializable.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $S_1$ is not conflict serializable, and $S_2$ is conflict serializable.

Explanation

In $S_1$: r1(y) before w2(y) gives T1->T2, and r2(x) before w1(x) gives T2->T1, a cycle. In $S_2$: r1(y) comes after w2(y) giving T2->T1, and r2(x) before w1(x) also gives T2->T1, no cycle.