GATE CS 2012 Q.27 (CS Q.27): Transactions, Serializability and Concurrency Control

Consider the following transactions with data items $P$ and $Q$ initialized to zero:

$T_1$ :
read ( $P$ );
read ( $Q$ );
if $P = 0$ then $Q := Q + 1$ ;
write ( $Q$ ).

$T_2$ :
read ( $Q$ );
read ( $P$ );
if $Q = 0$ then $P := P + 1$ ;
write ( $P$ ).

Any non-serial interleaving of $T_1$ and $T_2$ for concurrent execution leads to

a serializable schedule

a schedule that is not conflict serializable

a conflict serializable schedule

a schedule for which a precedence graph cannot be drawn

Official answer and solution

Solution

Trace conflicting read/write operations on data items P and Q across all possible non-serial interleavings of transactions T1 and T2.

Because $T_1$ begins by reading $P$ before $T_2$ writes $P$ , the conflict $R_1(P) < W_2(P)$ introduces a directed edge $T_1 \to T_2$ in the serialization (precedence) graph.
Concurrently, because $T_2$ reads $Q$ before $T_1$ writes $Q$ , the conflict $R_2(Q) < W_1(Q)$ introduces a reverse directed edge $T_2 \to T_1$ in the precedence graph.

Thus, both directed edges $T_1 \to T_2$ and $T_2 \to T_1$ are present, forming a directed cycle in the precedence graph.
A schedule is conflict serializable if and only if its precedence graph contains no directed cycles. Since a cycle is unavoidably created in every non-serial interleaving, any non-serial execution leads to a schedule that is not conflict serializable.

Final answer

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.