Conflict Serializability in DBMS

Conflict Serializability in DBMS

 

In this article, we will learn about Conflict Serializability in DBMS.

  • Serial schedules will have less performance because it cannot allow multiple transactions run concurrently, hence to improve the performance we need to execute multiple transactions at the same time
  • But sometimes because of the concurrency of transactions database may become inconsistent like when two or more transactions try to access the same data item
  • Hence to avoid this we need to verify whether these concurrent schedules are serializable or not
Conflict Serializability in DBMS

Conflict serializable:

 Whenever a schedule can be transformed into a serial schedule by swapping the non-conflicting operations then it is called conflict serializable schedule.

 

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, interchainging 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.

 

Note 1: Although S2 is not conflict serializable, 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).