Conflict Serializability in DBMS

Last Updated on October 31, 2023 by Ankit Kochar

A schedule is considered conflict serializable if it can be transformed from a non-serial schedule into a serial schedule by interchanging its non-conflicting operations.

Conflicting Operations

The two operations become conflicting if all conditions satisfy.

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

Conflicting Pair

Read [i] (x)   -    Read [j] (x) - non conflict    read-read operation.
Read [i] (x)   -    Write [j] (x) -  conflict           read-write operation.
Write [i] (x)   -    Read [j] (x) -  conflict            write-read operation.
Write [i] (x)   -    Write [j] (x) - conflict            write-write operation.

Where I and j denote two different transactions Ti and Tj.

Checking Whether a Schedule is Conflict Serializable Or Not

To determine whether a given non-serial schedule is conflict serializable, perform the following steps:

Step 1: We will find and list all of the operations that are in conflict.

Step 2: Then we will draw one node for each transaction in a precedence graph.

Step 3: After that, we will draw an edge from Ti to Tj for each conflict pair, so that if Xi (V) and Yj (V) form a conflict pair, draw an edge from Ti to Tj.
This ensured that Ti is executed before Tj.

Step 4: At the end, we will check the graph to see if any cycles have formed. If no cycles are found, the schedule is conflict serializable; otherwise, it is not.

Example to Check Whether the Schedule is Conflict Serialzabile or Not:

In this example we will check schedule is conflict serializable or not.

Step 1: We will find and list all of the operations that are in conflict.

Conflict Pair

1. Read [3] (x) – Write [1] (x)
2. Read [2] (y) – Write [3] (y)
3. Read [2] (z) – Write [1] (z)
4. Write [2] (z) – Read [1] (z)
5. Write [2] (z) – Write [1] (z)

Where I and j denote two different transactions Ti and Tj.

Step 2: We will create a precedence graph.
Here in this example, we have 3 transactions in this schedule. So we will create 3 nodes.

Step 3: We will draw an edge from Ti to Tj for each conflict pair.

1. Read [3] (x) – Write [1] (x)
   We will draw an edge from T[3] to T[1] for this conflict pair.

2. Read [2] (y) – Write [3] (y)
   We will draw an edge from T[2] to T[3] for this conflict pair.

3. Read [2] (z) – Write [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1].

4. Write [2] (z) – Read [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1]. But we already drew an edge from T[2] to T[1] in conflict pair 3. so we will not draw an edge again.

5. Write [2] (z) – Write [1] (z)
   For this conflict pair, we will draw an edge from T[2] to T[1]. But we already drew an edge from T[2] to T[1] in conflict pair 3. so we will not draw an edge again.

Step 4: Now we will check the graph to see if any cycles or loops have formed. Here in this example, we can not find out any cycles or loops. So this schedule is conflict serializable.

Conflict Equivalent

In the conflict equivalent, one can be transformed into another by swapping non-conflicting operations. In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).

Two schedules are said to be conflict equivalent if and only if they satisfy the following conditions:

1. They both have the same transaction set.
2. If each conflict operation pair is ordered in the same way.

Example of Conflict equivalent:
In the given example, S2 is conflict equivalent to S1 (S1 can be converted to S2 by swapping non-conflicting operations).

Step 1: We will make a list of all conflict pairs and non-conflict pairs.

Conflict pairs

R(A)        W(A)
W(A)        R(A)
W(A)        W(A)

Non-conflict pairs

R(A)        R(A)
R(B)        R(A)
W(B)        R(A)
R(B)        W(A)
W(A)        W(B)

Step 2: We will find the element in S1 which has no similar sequence order to S2. In this example, R(B) element in transaction 1 has no similar sequence.
So we will swape the adjacent non-conflict pair R(B)-W(A).

Adjacent non-conflict pair

After swapping of non-conflict operation

Step 3: Here still we have R(B) element which has no similar order to S2. So we will swape the adjacent non-conflict pair R(B)-R(A).

Adjacent non-conflict pair

After swapping of non-conflict operation

Now, S1 becomes conflict serializable.

Conclusion
Conflict serializability is a crucial concept in database management systems (DBMS) that ensures the consistency and correctness of concurrent transactions. It allows multiple transactions to execute in parallel while maintaining the same final state as if they had been executed one after the other in a serial manner. Understanding conflict serializability is essential for DBMS designers, administrators, and developers to create efficient and reliable database systems.

FAQs related to Conflict Serializability

Here are some of the FAQs related to Conflict Serializability:

1. What are conflicting operations in a schedule?
Conflicting operations in a schedule are those that involve the same data item and at least one of them is a write operation. Conflicts can arise when multiple transactions attempt to read and write to the same data simultaneously.

2. Why is conflict serializability important in DBMS?
Conflict serializability is important because it guarantees the correctness and consistency of concurrent transactions in a database. It ensures that no matter how transactions are interleaved, the final state of the database will be equivalent to some serial execution of those transactions.

3. How is conflict serializability determined?
Conflict serializability can be determined using techniques such as the precedence graph or the serializability matrix. If there are no cycles in the precedence graph or the serializability matrix, the schedule is considered conflict serializable.

4. What is the difference between conflict serializability and view serializability?
Conflict serializability focuses on the avoidance of conflicts between transactions (e.g., read-write or write-write conflicts). View serializability, on the other hand, considers the consistency of transaction results from the perspective of their read and write sets. Conflict serializability is a stricter criterion than view serializability.

5. Can a non-serializable schedule be made conflict serializable?
Yes, a non-serializable schedule can be transformed into a conflict serializable schedule by swapping non-conflicting operations. This process, known as schedule rewriting or serialization, ensures that transactions execute in a way that preserves the final database state.

6. What are the benefits of achieving conflict serializability in a DBMS?
Achieving conflict serializability ensures data integrity, consistency, and correctness in a multi-user DBMS environment. It allows for concurrent execution of transactions while maintaining the illusion that they are executed sequentially, improving system performance and responsiveness.