DBMS Conflict Serializability

In the DBMS Schedules guide, we learned that there are two types of schedules – Serial & Non-Serial. A Serial schedule doesn’t support concurrent execution of transactions while a non-serial schedule supports concurrency. We also learned in Serializability tutorial that a non-serial schedule may leave the database in inconsistent state so we need to check these non-serial schedules for the Serializability.

Conflict Serializability is one of the type of Serializability, which can be used to check whether a non-serial schedule is conflict serializable or not.

What is Conflict Serializability?

A schedule is called conflict serializable if we can convert it into a serial schedule after swapping its non-conflicting operations.

Conflicting operations

Two operations are said to be in conflict, if they satisfy all the following three conditions:

1. Both the operations should belong to different transactions.
2. Both the operations are working on same data item.
3. At least one of the operation is a write operation.

Lets see some examples to understand this:
Example 1: Operation W(X) of transaction T1 and operation R(X) of transaction T2 are conflicting operations, because they satisfy all the three conditions mentioned above. They belong to different transactions, they are working on same data item X, one of the operation in write operation.

Example 2: Similarly Operations W(X) of T1 and W(X) of T2 are conflicting operations.

Example 3: Operations W(X) of T1 and W(Y) of T2 are non-conflicting operations because both the write operations are not working on same data item so these operations don’t satisfy the second condition.

Example 4: Similarly R(X) of T1 and R(X) of T2 are non-conflicting operations because none of them is write operation.

Example 5: Similarly W(X) of T1 and R(X) of T1 are non-conflicting operations because both the operations belong to same transaction T1.

Conflict Equivalent Schedules

Two schedules are said to be conflict Equivalent if one schedule can be converted into other schedule after swapping non-conflicting operations.

Conflict Serializable check

Lets check whether a schedule is conflict serializable or not. If a schedule is conflict Equivalent to its serial schedule then it is called Conflict Serializable schedule. Lets take few examples of schedules.

Example of Conflict Serializability

Lets consider this schedule:

T1         T2
-----     ------
R(A)
R(B)
          R(A)
          R(B)
          W(B)
W(A)

To convert this schedule into a serial schedule we must have to swap the R(A) operation of transaction T2 with the W(A) operation of transaction T1. However we cannot swap these two operations because they are conflicting operations, thus we can say that this given schedule is not Conflict Serializable.

Lets take another example:

T1         T2
-----     ------
R(A)
          R(A)
          R(B)
          W(B)
R(B)
W(A)

Lets swap non-conflicting operations:

After swapping R(A) of T1 and R(A) of T2 we get:

T1         T2
-----     ------
          R(A)
R(A)
          R(B)
          W(B)
R(B)
W(A)

After swapping R(A) of T1 and R(B) of T2 we get:

T1         T2
-----     ------
          R(A)
          R(B)
R(A) 
          W(B)
R(B)
W(A)

After swapping R(A) of T1 and W(B) of T2 we get:

T1         T2
-----     ------
          R(A)
          R(B)
          W(B)
R(A)         
R(B)
W(A)

We finally got a serial schedule after swapping all the non-conflicting operations so we can say that the given schedule is Conflict Serializable.