GATE CS 2025 Set 2 Q.53: Transactions, Serializability and Concurrency Control

Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?

R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1)

W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)

R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2)

W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)

Official answer and solution

Solution

Build the precedence (conflict) graph for each schedule and check whether it is acyclic.

Checking conflicting operations on X and Y in each schedule:

(A): R1(X) precedes W2(X) ( $T_1 \rightarrow T_2$ ), while W2(X) precedes R1(X) and W1(X) ( $T_2 \rightarrow T_1$ ). Cycle $T_1 \leftrightarrow T_2$ (not conflict serializable).
(B): On X, W2(X) precedes R1(X), R1(X), W1(X) ( $T_2 \rightarrow T_1$ ); on Y, W2(Y) precedes W1(Y) ( $T_2 \rightarrow T_1$ ). The precedence graph has only the edge $T_2 \rightarrow T_1$ and no cycle, so (B) is conflict serializable (equivalent to serial schedule $T_2 \rightarrow T_1$ ).
(C): R1(X) precedes W2(X) ( $T_1 \rightarrow T_2$ ), while W2(X) precedes R1(X) and W1(X) ( $T_2 \rightarrow T_1$ ). Cycle $T_1 \leftrightarrow T_2$ .
(D): W2(X) precedes R1(X) ( $T_2 \rightarrow T_1$ ), while W1(Y) precedes W2(Y) ( $T_1 \rightarrow T_2$ ). Cycle $T_1 \leftrightarrow T_2$ .

Final answer

Option (B)

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

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 53 of 65
Section: Computer Science and Information Technology

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