Conflict Serializability in DBMS

What are the conflicting operations? 

Two operations are said to be conflicting if both are different operations fighting for the same data item in which at least one is write operation

Examples for conflicting and no conflicting operations

• (R1 (A), W2 (A)): Conflicting because R1 and W2 are different operations fighting for the same data item A and one is a write operation
• (W1 (A), W2 (A)) and (W1 (A), R2 (A)): Conflicting because both are different operations and fighting for the same data item A involving at least one write operation
• (R1 (A), W2 (B)): Non conflicting because these R1 and W2 are different operations and are accessing different data items A and B respectively
• (W1 (A), W2 (B)): Non-conflicting because W1 and W2 are different operations accessing different data items A and B.

Checking whether a given schedule is conflict serializable or not

Consider the following schedule:

S1: R1 (A), W1 (A), R2 (A), W2 (A), R1 (B), W1 (B), R2 (B), W2 (B)

If i and j are two operations in a transaction and i< j (i.e. i is executed before j), the same order will follow in the schedule as well. Using this property, we can get two transactions of schedule S1 as:
T1: R1 (A), W1 (A), R1 (B), W1 (B)
T2: R2 (A), W2 (A), R2 (B), W2 (B)

T1->T2 or T2->T1 are possible serial schedules

• Interchanging R2 (A) and R1 (B) non-conflicting operations in S1, the schedule becomes,

S11: R1 (A), W1 (A), R1 (B), W2 (A), R2 (A), W1 (B), R2 (B), W2 (B)

• In the same way, interchanging W2 (A) and W1 (B) non-conflicting operations in S11, the schedule becomes,

S12: R1 (A), W1 (A), R1 (B), W1 (B), R2 (A), W2 (A), R2 (B), W2 (B)

• S12 is a serial schedule in which all operations of T1 are performed before starting any operation of T2. Since S1 has been transformed into a serial schedule S12 by interchanging non-conflicting operations of its or , S1 is conflict serializable.

Let us take another Schedule:

S2: R2 (A), W2 (A), R1 (A), W1 (A), R1 (B), W1 (B), R2 (B), W2 (B)

The two transactions are:

T1: R1 (A), W1 (A), R1 (B), W1 (B)

T2: R2 (A), W2 (A), R2 (B), W2 (B)

T1->T2 or T2->T1 are possible serial schedules.

• Original Schedule is:

S2: R2 (A), W2 (A), R1 (A), W1 (A), R1 (B), W1 (B), R2 (B), W2 (B)

• Interchanging R1 (A) and R2 (B) non-conflicting operations in S2, the schedule becomes,

S21: R2 (A), W2 (A), R2 (B), W1 (A), R1 (B), W1 (B), R1 (A), W2 (B)

• In the same way, interchanging W1 (A) and W2 (B) non-conflicting operations in S21, the schedule becomes,

S22: R2 (A), W2 (A), R2 (B), W2 (B), R1 (B), W1 (B), R1 (A), W1 (A)

• In schedule S22, even though all operations of T2 are performed first, but the operations of T1 are not in order (the 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 into another by swapping non-conflicting operations. In the example discussed above, S11 is a 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.