Conflict Serializability | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

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. But concurrency of transactions may lead to inconsistency in database. To avoid this, we need to check whether these concurrent schedules are serializable or not.

Conflict Serializable: A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

Conflicting operations: Two operations are said to be conflicting if all conditions satisfy: 

• They belong to different transactions
• They operate on the same data item
• At Least one of them is a write operation

Example:

• Conflicting operations pair (R1(A), W2(A)) because they belong to two different transactions on same data item A and one of them is write operation.
• Similarly, (W1(A), W2(A)) and (W1(A), R2(A)) pairs are also conflicting.
• On the other hand, (R1(A), W2(B)) pair is non-conflicting because they operate on different data item.
• Similarly, ((W1(A), W2(B)) pair is non-conflicting.

Consider the following schedule:
S1: R₁(A), W₁(A), R₂(A), W₂(A), R₁(B), W₁(B), R₂(B), W₂(B)
If O_i and O_j are two operations in a transaction and O_i< O_j (O_i is executed before O_j), same order will follow in the schedule as well. Using this property, we can get two transactions of schedule S1 as:
T1: R₁(A), W₁(A), R₁(B), W₁(B)
T2: R₂(A), W₂(A), R₂(B), W₂(B)

1. Possible Serial Schedules are: T1 → T2 or T2 → T1 
Swapping non-conflicting operations R₂(A) and R₁(B) in S1, the schedule becomes,
S11: R₁(A), W₁(A), R₁(B), W₂(A), R₂(A), W₁(B), R₂(B), W₂(B)
Similarly, swapping non-conflicting operations W₂(A) and W₁(B) in S11, the schedule becomes,
S12: R₁(A), W₁(A), R₁(B), W₁(B), R₂(A), W₂(A), R₂(B), W₂(B)
S12 is a serial schedule in which all operations of T1 are performed before starting any operation of T2. Since S has been transformed into a serial schedule S12 by swapping non-conflicting operations of S1, S1 is conflict serializable.
Let us take another Schedule:
S2: R₂(A), W₂(A), R₁(A), W₁(A), R₁(B), W₁(B), R₂(B), W₂(B)
Two transactions will be:  
T1: R₁(A), W₁(A), R₁(B), W₁(B)
T2: R₂(A), W₂(A), R₂(B), W₂(B)
2. Possible Serial Schedules are: T1 → T2 or T2 → T1 
Original Schedule is: 
S2: R₂(A), W₂(A), R₁(A), W₁(A), R₁(B), W₁(B), R₂(B), W₂(B)
Swapping non-conflicting operations R1(A) and R2(B) in S2, the schedule becomes,
S21: R₂(A), W₂(A), R₂(B), W₁(A), R₁(B), W₁(B), R₁(A), W₂(B)
Similarly, swapping non-conflicting operations W₁(A) and W₂(B) in S21, the schedule becomes,  
S22: R₂(A), W₂(A), R₂(B), W₂(B), R₁(B), W₁(B), R₁(A), W₁(A)
In schedule S22, all operations of T2 are performed first, but operations of T1 are not in order (order should be R1(A), W1(A), R1(B), W1(B)). So S2 is not conflict serializable.

Conflict Equivalent: Two schedules are said to be conflict equivalent when one can be transformed to another by swapping non-conflicting operations. In the example discussed above, S11 is conflict equivalent to S1 (S1 can be converted to S11 by swapping non-conflicting operations). Similarly, S11 is conflict equivalent to S12 and so on.

Note 1: Although S2 is not conflict serializable, but still it is conflict equivalent to S21 and S21 because S2 can be converted to S21 and S22 by swapping non-conflicting operations.

Note 2: The schedule which is conflict serializable is always conflict equivalent to one of the serial schedule. S1 schedule discussed above (which is conflict serializable) is equivalent to serial schedule (T1->T2).

Question: Consider the following schedules involving two transactions. Which one of the following statement is true?    [GATE 2007]
S1: R₁(X) R₁(Y) R₂(X) R₂(Y) W₂(Y) W₁(X)
S2: R₁(X) R₂(X) R₂(Y) W₂(Y) R₁(Y) W₁(X)
(a) Both S1 and S2 are conflict serializable
(b) Only S1 is conflict serializable
(c) Only S2 is conflict serializable
(d) None
Ans: (c)
Solution: Two transactions of given schedules are:
T1: R₁(X) R₁(Y) W₁(X)
T2: R₂(X) R₂(Y) W₂(Y)
Let us first check serializability of S1:
S1: R₁(X) R₁(Y) R₂(X) R₂(Y) W₂(Y) W₁(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 R₂(X) and W₁(X) but they are conflicting. So S1 can’t be converted to a serial schedule.
Now, let us check serializability of S2:
S2: R₁(X) R₂(X) R₂(Y) W₂(Y) R₁(Y) W₁(X)
Swapping non conflicting operations R₁(X) and R₂(X) of S2, we get
S2’: R₂(X) R₁(X) R₂(Y) W₂(Y) R₁(Y) W₁(X)
Again, swapping non conflicting operations R₁(X) and R₂(Y) of S2’, we get
S2’’: R₂(X) R₂(Y) R₁(X) W₂(Y) R₁(Y) W₁(X)
Again, swapping non conflicting operations R₁(X) and W₂(Y) of S2’’, we get
S2’’’: R₂(X) R₂(Y) W₂(Y) R₁(X) R₁(Y) W₁(X)
which is equivalent to a serial schedule T2 → T1.
So, correct option is C. Only S2 is conflict serializable.