Conflict Serializability in DBMS

Conflicting Operations

Conflicting operations are performed concurrently on the same data or resource. Conflicting operations’ execution order affects the final outcome. In other words, when two or more operations are performed on the same data or resource, and the order in which they are executed changes the final result, those operations are called conflicting.

For example, imagine two users are trying to update the same field in a database at the same time. If they both update the field with different values and the system does not account for this, it can lead to conflicts. In this case, the operations of updating the same field in the database are conflicting.

Also see, Recursive Relationship in DBMS

How to Check If A Schedule is Conflict Serializable?

To check if a schedule is conflict serializable, you can follow the below steps:

1. Draw a precedence graph for the given schedule. The nodes in the graph show transactions. The edges in the graph represent conflicts between the transactions.
Precedence Graph: It is a directed graph that is used in DBMS. It is used to check whether a set of transactions is conflict serializable. It represents all the dependencies between transactions. It helps to identify any conflicts that may arise due to the concurrent execution of transactions.
Suppose there is a schedule that has three transactions:

T1: R(P) W(P)
T2: W(Y) W(X)
T3: R(Y) W(X)

So its precedence graph will be:

2. Check if there are any cycles in the precedence graph. If there are no cycles, the schedule is conflict serializable.
 

3. If any cycles are there in the precedence graph, the schedule can or cannot be conflict serializable. To check if the schedule is conflict serializable, apply the following test:

1. Pick any of the cycles in the graph.
    
2. Label each edge in the cycle with some direction, either "same" or "opposite". An edge is labeled "same" if it represents a conflict between two transactions that occur in the same order in the cycle. An edge is labeled "opposite" if it represents a conflict between two transactions that occur in the opposite order in the cycle.
    
3. If all edges in the cycle are labeled "same", the schedule is conflict serializable. If any edge is labeled "opposite", the schedule is not conflict serializable.
    
4. Repeat steps a-c for all cycles in the graph. If all cycles pass the test, the schedule is conflict serializable. If any cycle fails the test, the schedule is not conflict serializable.
    

By following the above steps, you can check if a given schedule is a conflict serializable or not.

Let us understand conflict serializability with the help of an example.

Example to Understand Conflict Serializability

Let's consider an example of two transactions, T1 and T2, that are working on a bank account balance.

Transaction T1 transfers $200 from account P to account Q. 

Transaction T2 transfers $100 from account Q to account P.

If these transactions, T1 and T2, execute concurrently, they can cause a conflict because they both involve updating the duplicate two accounts.

To ensure the conflict serializability, we need to check whether the order of execution of these transactions, T1 and T2 affects the final outcome. 

We can represent these transactions as a precedence graph, as shown below:

T1: R(P) W(P) R(Q) W(Q)
T2: R(Q) W(Q) R(P) W(P)

On the above-mentioned transactions, different operations are performed, such as R(read) and W(write). We can find the conflict serializability by checking the conflicts between operations.

Each node represents a transaction in this graph. Each edge indicates a conflict between two transactions. In this case, there are two edges, indicating that T1 and T2 conflict with each other.

We can see that the graph has a cycle (T1 → T2 → T1). It indicates that the transactions are not conflict serializable. To ensure conflict serializability, one of the transactions should be aborted, or their order must be rearranged to eliminate the cycle.

For example, we can execute T1 first and then T2 or vice-versa. Both orders will result in the same final account balances and will be conflict serializable.

Therefore, conflict serializability ensures that all the transactions are executed in a way that produces the same outcome as a serial execution of the transactions, regardless of their order of execution.

Conflict Equivalent

Conflict serializability ensures a smooth flow of database operations, but there's another concept closely related to it: conflict equivalence. Imagine two different ways to make the same sandwich with the same ingredients – maybe one person spreads the mayo before adding the cheese, while the other does it the other way around. As long as they don't try to grab the same ingredient at the same time, the outcome (the delicious sandwich) will be the same.

In the world of databases, two schedules (sequences of database operations) are considered conflict equivalent if they involve the same set of transactions and maintain the order of conflicting operations. Here are some examples:

Example 1: Simple Swap

Schedule 1:

• Transaction 1 (T1): Read (A)
• Transaction 2 (T2): Write (A)

Schedule 2 (conflict equivalent):

• Transaction 2 (T2): Write (A)
• Transaction 1 (T1): Read (A)

In both schedules, T1 reads the value of A before T2 writes a new value. The order of the conflicting operations (read and write on A) remains the same, even though their order is swapped.

Example 2: Swapping Non-Conflicting Operations

Schedule 1:

• Transaction 1 (T1): Read (A)
• Transaction 2 (T2): Read (B)
• Transaction 1 (T1): Write (A)

Schedule 2 (conflict equivalent):

• Transaction 2 (T2): Read (B)
• Transaction 1 (T1): Read (A)
• Transaction 1 (T1): Write (A)

Here, both transactions access different data items (A and B) initially. Swapping the read operations (T2's read of B and T1's read of A) doesn't cause any conflicts because they don't interact with each other. The conflicting operation (T1's write on A) remains at the end in both schedules.

Example 3: Multiple Conflicts, Same Order

Schedule 1:

• Transaction 1 (T1): Read (A)
• Transaction 2 (T2): Write (A)
• Transaction 1 (T1): Write (B)
• Transaction 3 (T3): Read (B)

Schedule 2 (conflict equivalent):

• Transaction 2 (T2): Write (A)
• Transaction 1 (T1): Read (A)
• Transaction 3 (T3): Read (B)
• Transaction 1 (T1): Write (B)

This example involves two conflicts: T1 and T2 on A, and T1 and T3 on B. Even though the order of non-conflicting operations is changed, the order of conflicting operations (read/write on A and B) remains the same in both schedules.

What is Schedule in DBMS?

A schedule in DBMS indicates a sequence of transactions that are executed on a database. A schedule is essentially a timeline. It specifies the order in which different transactions are read from and written to the database. 

There are different types of schedules in DBMS:

A schedule is represented graphically using a Gantt chart. In a Gantt chart, each transaction is represented by a horizontal bar. This horizontal bar indicates the time during which the transaction is active. A schedule can be categorized as serial or concurrent. It depends on whether transactions are executing one at a time or multiple transactions are executing simultaneously.

It is very important to make sure that a schedule is correct. A schedule in DBMS is considered correct only if it produces the same result as if the transactions were executed in some serial order. This property is also known as the serializability of a schedule. This is because the concurrent execution of transactions can lead to several problems. The problems can be lost updates, dirty reads, and inconsistent results if not appropriately managed. Hence, it's important to use proper concurrency control techniques.

These techniques are locking and timestamp ordering. These techniques help to make sure that transactions are executed correctly and safely.

Question: Consider the following schedules involving two transactions. Which one of the following statements is true?

S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y) W1(X) 
S2: R1(X) R2(X) R2(Y) W2(Y) R1(Y) W1(X) 

• Both S1 and S2 are conflict serializable
• Only S1 is conflict serializable
• Only S2 is conflict serializable
• None

Answer-: Schedule S1: This schedule is conflict serializable. If you draw a precedence graph for it, you'll see there are no circular dependencies.

Schedule S2: This schedule is not conflict serializable. In this case, the operations R2(X) and W1(X) conflict, creating a circular dependency in the precedence graph.

So, the correct answer is: Only S1 is conflict serializable.

Advantages of Conflict Serializability 

The following are the advantages of conflict serializability in DBMS:

• It helps to ensure that the database remains consistent even when multiple transactions access and modify the same data.
   
• It allows multiple transactions to execute simultaneously without interfering with each other. This simultaneous execution improves system performance.
   
• It ensures the database is always available to users, even during peak activity times.
   
• It allows the database to scale to handle increasing volumes of data and users.

Disadvantages of Conflict Serializability

The following are the disadvantages of conflict serializability in DBMS:

• Implementing conflict serializability requires additional processing overhead, which can slow down the system's performance.
   
• It can lead to deadlocks when multiple transactions wait for each other to release resources. This process can result in system failures.
   
• It requires a complex algorithm to check whether transactions are serializable or not. This can be difficult to implement and maintain in large systems.

Must Recommended Topic, Schema in DBMS

Frequently Asked Questions

What is conflict serializability in DBMS?

A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting operations while maintaining transaction order.

How to check if a schedule is serializable or not?

To check serializability, construct a precedence graph (serializability graph). If the graph has no cycles, the schedule is conflict-serializable; otherwise, it's not.

What is the difference between view and conflict in DBMS?

Conflict Serializability ensures a schedule can be converted into a serial schedule by swapping non-conflicting operations. View Serializability ensures the same final output but allows more schedules, even if not conflict-serializable.

Conclusion

This article delves into the concept of conflict serializability in DBMS. We have also discussed the schedule and an example to understand conflict serializability in DBMS. Additionally, we explored the advantages and disadvantages associated with conflict serializability in DBMS. You can check out our other blogs to enhance your knowledge:

• Interview Questions on Database
   
• Joins in DBMS
   
• Data abstraction in DBMS
   
• Introduction to Scheduling in DBMS
   
• Apache Spark
   
• Joins in dbms
   

To practice and improve yourself in the interview, you can also check out Top 100 SQL problems, Interview experience, Coding interview questions, and the Ultimate guide path for interviews.