GATE CS 2014 Set 2 Q29 — Transactions and Concurrency Control

To determine the properties of the schedule $S$, we analyze it for conflict-serializability and recoverability.

1. Conflict Serializability

We construct the precedence graph by identifying conflicting operations (two operations by different transactions on the same data item, where at least one is a write):

• $R_2(X)$ and $W_3(X) \implies T_2 \to T_3$
• $R_2(X)$ and $W_1(X) \implies T_2 \to T_1$
• $W_3(X)$ and $W_1(X) \implies T_3 \to T_1$
• $W_1(X)$ and $R_4(X) \implies T_1 \to T_4$
• $W_2(Y)$ and $R_4(Y) \implies T_2 \to T_4$

The directed edges in the precedence graph are:

$$\text{Edges} = \{T_2 \to T_3,\ T_2 \to T_1,\ T_3 \to T_1,\ T_1 \to T_4,\ T_2 \to T_4\}$$

Since there are no cycles in this precedence graph, the schedule $S$ is conflict-serializable. A valid serial order is $T_2 \to T_3 \to T_1 \to T_4$.

2. Recoverability

A schedule is recoverable if, for every transaction $T_j$ that reads a data item written by $T_i$, the commit operation of $T_i$ occurs before the commit operation of $T_j$ ($C_i < C_j$).

Let's check the read-from relations in $S$:

1. $T_4$ reads $X$ written by $T_1$:
   • $T_1$ commits before $T_4$ ($C_1 < C_4$). This condition is satisfied.
2. $T_4$ reads $Y$ written by $T_2$:
   • $T_2$ commits before $T_4$ ($C_2 < C_4$). This condition is satisfied.

Since all read-from dependencies satisfy the commit order requirement, the schedule is recoverable.

Conclusion

The schedule $S$ is both conflict-serializable and recoverable.