IAE Academy

GATE 2025 CS2 Q.53: solution and answer

GATE 2025 · CS2Q.53 · 2 marks · MSQ

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

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

GATE 2025 CS2 question 53: Two boxes listing the transactions.Tap to open full size
Figure from the GATE 2025 CS2 paper. It is part of the question.
Figure description

Two boxes listing the transactions. Box 'Transaction T1' lists in order: R1(X), W1(Y), R1(X), W1(X), COMMIT(T1). Box 'Transaction T2' lists in order: W2(X), W2(Y), COMMIT(T2).

  1. (A)

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

  2. (B)

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

  3. (C)

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

  4. (D)

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

Answer and solution

ANSWER

Only schedule (B) is conflict serializable, equivalent to the serial order T2 then T1.

Official answer: BSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. Method: draw the precedence graph. Add an edge when an operation of comes before a conflicting operation of on the same item (different transactions, same item, at least one a write). A schedule is conflict serializable exactly when this graph has no cycle.

  2. (A) comes before , giving . comes before the second , giving . The graph has a cycle, so (A) is not conflict serializable.

  3. (B) precedes , so . precedes , so . precedes , so . Every conflicting pair gives an edge and there is no edge, so the graph is acyclic. The schedule is equivalent to the serial order . (B) is conflict serializable.

  4. (C) comes before , giving . comes before the second , giving . The graph has a cycle, so (C) is not conflict serializable.

  5. (D) precedes , giving . precedes , giving . The graph has a cycle, so (D) is not conflict serializable.

  6. Only (B) is conflict serializable.

KEY IDEA

Build the precedence graph from conflicting operations (same item, different transactions, at least one write). The schedule is conflict serializable exactly when the graph has no cycle.

WATCH OUT FOR

Looking only at the first conflict between the transactions and missing the opposite-direction edge from a later operation, such as the second R1(X) after W2(X) in (A) and (C), or W1(Y) before W2(Y) in (D).

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 9 Transactions questions, with notes

More Transactions questions