GATE CS 2014 Set 3 Q.39 (CS Q.29): Transactions, Serializability and Concurrency Control

Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.

T1: r1(X); r1(Z); w1(X); w1(Z)
T2: r2(Y); r2(Z); w2(Z)
T3: r3(Y); r3(X); w3(Y)

S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)

Which one of the following statements about the schedules is TRUE?

Only S1 is conflict-serializable.

Only S2 is conflict-serializable.

Both S1 and S2 are conflict-serializable.

Neither S1 nor S2 is conflict-serializable.

Official answer and solution

Solution

Construct the precedence (serialization) graph for each schedule and check for directed cycles.

Transactions:
- $T_1: r_1(X); r_1(Z); w_1(X); w_1(Z)$
- $T_2: r_2(Y); r_2(Z); w_2(Z)$
- $T_3: r_3(Y); r_3(X); w_3(Y)$
Precedence Graph for Schedule $S_1$ :
$S_1 = r_1(X); r_3(Y); r_3(X); r_2(Y); r_2(Z); w_3(Y); w_2(Z); r_1(Z); w_1(X); w_1(Z)$
- On item $X$ : $r_3(X)$ occurs before $w_1(X) \implies T_3 \to T_1$ .
- On item $Y$ : $r_2(Y)$ occurs before $w_3(Y) \implies T_2 \to T_3$ .
- On item $Z$ : $w_2(Z)$ occurs before $r_1(Z)$ and $w_1(Z) \implies T_2 \to T_1$ .
  The edges are $T_2 \to T_3$ , $T_3 \to T_1$ , and $T_2 \to T_1$ . This directed graph is acyclic (topological ordering: $T_2, T_3, T_1$ ).
  Hence, $S_1$ is conflict-serializable.
Precedence Graph for Schedule $S_2$ :
$S_2 = r_1(X); r_3(Y); r_2(Y); r_3(X); r_1(Z); r_2(Z); w_3(Y); w_1(X); w_2(Z); w_1(Z)$
- On item $Z$ $Z$ :
  - $r_1(Z)$ occurs before $w_2(Z) \implies T_1 \to T_2$ .
  - $w_2(Z)$ occurs before $w_1(Z) \implies T_2 \to T_1$ .
    This creates a direct 2-cycle: $T_1 \to T_2 \to T_1$ .
    Because the precedence graph contains a cycle, $S_2$ is NOT conflict-serializable.
Therefore, only $S_1$ is conflict-serializable (option A).

Final answer

Common trap

Missing the conflict between r1(Z) and w2(Z) that creates an edge T1 -> T2 in S2.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.