Conflict Serializability in DBMS

A schedule in DBMS is the sequence of transactions in the order of their execution. You can learn more about schedules and serializable schedules in DBMS here.

Serializability of non-serial schedules are of two types - conflict serializability and view serializability. Conflict Serializability in DBMS checks if a non-serial schedule is conflict serializable or not. View Serializability checks if a schedule is view serializable or not. If a schedule is a view equivalent to a Serial Schedule, it is said to be view serializable.

What is Conflict Serializability in DBMS?

Conflict Serializability checks if a non-serial schedule is conflict serializable or not. A non-serial schedule is conflict serializable if it can convert into a serial schedule by swapping its non-conflicting operations.

Conflicting Operations

A pair of operations are said to be conflicting operations if they follow the set of conditions given below:

• Each operation is a part of different transactions.
• Both operations are performed on the same data item.
• One of the performed must be a write operation.

Let's consider two different transactions, $T_i$ and $T_j$. Then considering the above conditions, the following table follows:

Example

Let's see an example based on the following schedule.

In the above schedule, we can notice that:

• W1(A) and R2(A) are part of different transactions.
• Both apply to the same data item, i.e., A.
• W1(A) is a write operation.

W1(A) and R2(A) are conflicting operations as they satisfy all the above conditions.

Similarly, W1(A) and W2(A) are conflicting operations as they are part of different transactions working on the same data item, and one of them is the write operation.

W1(A) and W2(B) are non-conflicting operations as they work on different data items and thus do not satisfy all the given conditions.

R1(A) and R2(A) are non-conflicting operations as none of them is a write operation and thus does not satisfy the third condition.

W1(A) and R1(A) are non-conflicting as they belong to the same transactions and thus do not satisfy the first condition.

Conflict Equivalent

If a schedule gets converted into another schedule by swapping the non-conflicting operations, they are said to be conflict equivalent schedules.

Checking Whether a Schedule is Conflict Serializable Or Not

A non-serial schedule gets checked for conflict serializability using the following steps:

1. Figure out all the conflicting operations and enlist them.
2. Create a precedence graph. For every transaction in the schedule, draw a node in the precedence graph.
3. If Xi(A) and Yj(A) represent a conflict pair, then draw an edge from Ti to Tj for each conflict pair. The precedence graph ensures that Ti gets executed before Tj.
4. The next step involves checking for any cycle formed in the graph. A schedule is a conflict serializable if there is no cycle present.

Example

Example 1: The above example has a pair of conflicting operations. The transaction drawn on a precedence graph makes a cycle. Thus the schedule is not conflict serializable.

Example 2:

The above example has only one conflict pair. Drawing the transaction on a graph does not produce a cycle. Thus it is conflict serializable.

Example 3:

The above example has a pair of conflicting operations. Unlike Example 1, the transaction drawn on a precedence graph does not make a cycle. Thus the schedule is conflict serializable.

Let's try another method to check the conflict serializability of the schedule. We will check if the schedule is conflict serializable or not by converting it to a serial schedule by swapping the non-conflicting operations.

Example 4: Let's see it with an example.

We can convert the above schedule into a serial schedule by swapping the operation R2(A) of transaction 2 with the W1(A) operation of transaction 1. However, the two operations are conflicting operations. Thus, they cannot get swapped to convert the non-serial schedule to a serial schedule. So, the above schedule is not conflict serializable.

Example 5: Let's take another example to understand it better.

We can check whether a non-serial schedule is conflict serializable or not if it can convert into a serial schedule by swapping its non-conflicting operations. Let's start by swapping the non-conflicting operations.

• Swapping of R(A) of Transaction 1 and R(A) of Transaction 2 converts the schedule to:

• Swapping of R(A) of Transaction 1 and R(B) of Transaction 2 converts the schedule to:

• Swapping of R(A) of Transaction 1 and W(B) of Transaction 2 converts the schedule to:

The swapping of all the non-conflicting operations gives us a serial schedule. Thus, we can say that the above schedule is conflict serializable.

Read More:

• What is Transaction in DBMS?.