Conflict Serializability in DBMS
FREE
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.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
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, and . Then considering the above conditions, the following table follows:
| Transaction i | Transaction j | IsConflicting |
|---|---|---|
| Readi (X) | Readj (X) | Non-conflicting |
| Readi (X) | Writej (X) | Conflicting |
| Writei (X) | Readj (X) | Conflicting |
| Writei (X) | Writej (X) | Conflicting |
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Example
Let's see an example based on the following schedule.
| Transaction 1 | Transaction 2 |
|---|---|
| R1(A) | W2(B) |
| W1(A) | |
| R2(A) | |
| R1(B) | W2(A) |
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.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Conflict Equivalent
If a schedule gets converted into another schedule by swapping the non-conflicting operations, they are said to be conflict equivalent schedules.
Turn Learning into Career Growth
Checking Whether a Schedule is Conflict Serializable Or Not
A non-serial schedule gets checked for conflict serializability using the following steps:
- Figure out all the conflicting operations and enlist them.
- Create a precedence graph. For every transaction in the schedule, draw a node in the precedence graph.
- 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.
- 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.
| Transaction 1 | Transaction 2 |
|---|---|
| R1(A) | |
| R1(B) | |
| R2(A) | |
| R2(B) | |
| W2(B) | |
| W1(A) |
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.
| Transaction 1 | Transaction 2 |
|---|---|
| R(A) | |
| R(A) | |
| R(B) | |
| W(B) | |
| R(B) | |
| W(A) |
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:
| Transaction 1 | Transaction 2 |
|---|---|
| R(A) | |
| R(A) | |
| R(B) | |
| W(B) | |
| R(B) | |
| W(A) |
- Swapping of R(A) of Transaction 1 and R(B) of Transaction 2 converts the schedule to:
| Transaction 1 | Transaction 2 |
|---|---|
| R(A) | |
| R(B) | |
| R(A) | |
| W(B) | |
| R(B) | |
| W(A) |
- Swapping of R(A) of Transaction 1 and W(B) of Transaction 2 converts the schedule to:
| Transaction 1 | Transaction 2 |
|---|---|
| R(A) | |
| R(B) | |
| W(B) | |
| R(A) | |
| R(B) | |
| W(A) |
The swapping of all the non-conflicting operations gives us a serial schedule. Thus, we can say that the above schedule is conflict serializable.
Conclusion
- Conflict Serializability in DBMS 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.
- Two operations are said to conflict if they are part of different transactions working on the same data item, and one must be a write operation.
- Conflict equivalent schedules can convert from one to another by swapping the non-conflicting operations.
- A schedule is a conflict serializable if no cycle is present in the precedence graph