GATE Question
Question: Consider the following schedules involving two transactions. Which one of the following statements is true? [GATE 2007]
S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y) W1(X)
S2: R1(X) R2(X) R2(Y) W2(Y) R1(Y) W1(X)
- Both S1 and S2 are conflict serializable
- Only S1 is conflict serializable
- Only S2 is conflict serializable
- None
Solution: Two transactions of given schedules are:
T1: R1(X) R1(Y) W1(X)
T2: R2(X) R2(Y) W2(Y)
Let us first check serializability of S1:
S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y) W1(X)
To convert it to a serial schedule, we have to swap non-conflicting operations so that S1 becomes equivalent to serial schedule T1->T2 or T2->T1. In this case, to convert it to a serial schedule, we must have to swap R2(X) and W1(X) but they are conflicting. So S1 can’t be converted to a serial schedule.
Now, let us check serializability of S2:
S2: R1(X) R2(X) R2(Y) W2(Y) R1(Y) W1(X)
Swapping non conflicting operations R1(X) and R2(X) of S2, we get
S2’: R2(X) R1(X) R2(Y) W2(Y) R1(Y) W1(X)
Again, swapping non conflicting operations R1(X) and R2(Y) of S2’, we get
S2’’: R2(X) R2(Y) R1(X) W2(Y) R1(Y) W1(X)
Again, swapping non conflicting operations R1(X) and W2(Y) of S2’’, we get
S2’’’: R2(X) R2(Y) W2(Y) R1(X) R1(Y) W1(X)
which is equivalent to a serial schedule T2->T1.
So, correct option is C. Only S2 is conflict serializable.
Conflict Serializability in DBMS
As discussed in Concurrency control, serial schedules have less resource utilization and low throughput. To improve it, two or more transactions are run concurrently. However, concurrency of transactions may lead to inconsistency in the database. To avoid this, we need to check whether these concurrent schedules are serializable or not.