Transactions and serializability: GATE CS question with solution

Method: check serializability separately, then check recoverability, cascadelessness and strictness from their definitions.

Conflict serializability. Conflicting pairs (same item, different transactions, at least one write):

• $w_1(X)$ before $r_2(X)$, $r_1(X)$ and $w_1(X)$ before $w_2(X)$: edge $T_1\to T_2$.
• $w_1(Y)$ before $r_2(Y)$: edge $T_1\to T_2$.

No edge goes from $T_2$ to $T_1$, so the precedence graph is acyclic and $S$ is equivalent to $T_1{T}_2$. (a) is true.

Recoverable. A schedule is recoverable if every transaction commits only after every transaction it read from has committed. $T_2$ reads $X$ (and later $Y$) written by $T_1$, and $c_1$ comes before $c_2$. (b) is true.

Cascadeless. A transaction may read a value written by another transaction only after that writer commits. $r_2(X)$ reads $T_1$'s value of $X$ while $T_1$ is still active. Had $T_1$ aborted at that point, $T_2$ would have to be rolled back too. (c) is false.

Strict. After a transaction writes an item, no other transaction may read or write that item until the writer commits or aborts. Strict implies cascadeless, so (d) is false as well.

Trap. A dirty read alone does not make a schedule unrecoverable; what matters is the commit order of reader and writer. Here the writer commits first, so the schedule is recoverable but still exposed to cascading aborts.

What was tested: the chain strict ⊂ cascadeless ⊂ recoverable, and that serializability is a separate question from recoverability.