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)} \)

Hint:

To check conflict serializability, construct a precedence graph and verify the presence of cycles.

Answer 1

The Correct Option is B

A schedule is conflict serializable if we can obtain a conflict-equivalent serial schedule by swapping non-conflicting operations.

To check conflict serializability, we construct the precedence graph:

Step 1: Identify Conflicting Operations

• \( W2(X) \) and \( R1(X) \) conflict because both involve the data item \( X \), with one performing a write and the other a read.
• \( W2(Y) \) and \( W1(Y) \) conflict because both involve the data item \( Y \), with one performing a write and the other a write.
• \( W1(X) \) and \( R1(X) \) conflict because both involve the data item \( X \), with one performing a write and the other a read.

Step 2: Construct Precedence Graph

• If there is a cycle in the graph, the schedule is not conflict serializable. This means it’s impossible to reorder operations to make it serial.
• If no cycles exist in the graph, the schedule is conflict serializable. In this case, the schedule can be transformed into a serial one without violating dependencies.

After analyzing the given options, only Option (B) follows a conflict-equivalent serial schedule, making it conflict serializable. This means that by rearranging operations that do not conflict, the schedule in Option (B) can be made into a serial schedule without creating any inconsistency or dependency violations.