GATE CSE 2025 Set 2 Q53

Question

Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?
A) R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1)
B) W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)
C) R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2)
D) W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)

Accepted Answer

Official answer: B) W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1). Explanation: To determine whether a schedule is conflict serializable, we construct the precedence (serializability) graph for each schedule: 1. Option (A): R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1) - R1(X) occurs before W2(X) T1 T2 - W2(X) occurs before R1(X) and W1(X) T2 T1 - There is a cycle (T1 T2 T1), so the schedule is not conflict serializable. 2. Option (B): W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1) - W2(X) occurs before R1(X) and W1(X) T2 T1 - W2(Y) occurs before W1(Y) T2 T1 - There is no conflicting pair where T1 precedes T2. The graph has only the edge T2 T1, which is acyclic. Thus, this schedule is conflict serializable. 3. Option (C): R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2) - R1(X) occurs before W2(X) T1 T2 - W2(X) occurs before R1(X) and W1(X) T2 T1 - There is a cycle (T1 T2 T1), so the schedule is not conflict serializable. 4. Option (D): W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1) - W2(X) occurs before R1(X) and W1(X) T2 T1 - W1(Y) occurs before W2(Y) T1 T2 - There is a cycle (T1 T2 T1), so the schedule is not conflict serializable. Hence, only option (B) is conflict serializable.

Answer

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

Answer

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

Answer

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

Answer

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

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

Step-by-step verified solution

Check you can still solve Transactions and Concurrency Control under a clock

More from GATE CSE 2025 Set 2

More on Transactions 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?

Step-by-step verified solution

Check you can still solve Transactions and Concurrency Control under a clock

More from GATE CSE 2025 Set 2

More on Transactions 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?

Step-by-step verified solution

Check you can still solve Transactions and Concurrency Control under a clock

More from GATE CSE 2025 Set 2

More on Transactions and Concurrency Control

Share this solution

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

Step-by-step verified solution

Check you can still solve Transactions and Concurrency Control under a clock

More from GATE CSE 2025 Set 2

More on Transactions and Concurrency Control

Share this solution