Conflict Serializability in DBMS

Facebooktwitterredditpinterestlinkedinmailby feather

Conflict Serializability

A schedule is said to be conflict serializable if it can transform into a serial schedule after swapping of non-conflicting operations. It is a type of serializability that can be used to check whether the non-serial schedule is conflict serializable or not.

Conflicting operations

The two operations are called conflicting operations, if all the following three conditions are satisfied:

  • Both the operation belongs to separate transactions.
  • Both works on the same data item.
  • At least one of them contains one write operation.

Note: Conflict pairs for the same data item are:
Read-Write
Write-Write
Write-Read

Conflict Equivalent Schedule

Two schedules are called as a conflict equivalent schedule if one schedule can be transformed into another schedule by swapping non-conflicting operations.

Example of conflict serializability:

Schedule S2 (Non-Serial Schedule):

Time Transaction T1 Transaction T2 Transaction T3
t1 Read(X)    
t2     Read(Y)
t3     Read(X)
t4   Read(Y)  
t5   Read(Z)  
t6     Write(Y)
t7   Write(Z)  
t8 Read(Z)    
t9 Write(X)    
t10 Write(Z)    

Precedence graph for schedule S2:

In the above schedule, there are three transactions: T1, T2, and T3. So, the precedence graph contains three vertices.

Precedence graph for schedule S2:

To draw the edges between these nodes or vertices, follow the below steps:

Step1: At time t1, there is no conflicting operation for read(X) of Transaction T1.
Step2: At time t2, there is no conflicting operation for read(Y) of Transaction T3.
Step3: At time t3, there exists a conflicting operation Write(X) in transaction T1 for read(X) of Transaction T3. So, draw an edge from T3→T1.

edges between these nodes or vertices

Step4: At time t4, there exists a conflicting operation Write(Y) in transaction T3 for read(Y) of Transaction T2. So, draw an edge from T2→T3.

Step5: At time t5, there exists a conflicting operation Write (Z) in transaction T1 for read (Z) of Transaction T2. So, draw an edge from T2→T1.

exists a conflicting operation

Step6: At time t6, there is no conflicting operation for Write(Y) of Transaction T3.
Step7: At time t7, there exists a conflicting operation Write (Z) in transaction T1 for Write (Z) of Transaction T2. So, draw an edge from T2→T1, but it is already drawn.

After all the steps, the precedence graph will be ready, and it does not contain any cycle or loop, so the above schedule S2 is conflict serializable. And it is equivalent to a serial schedule. Above schedule S2 is transformed into the serial schedule by using the following steps:

Step1: Check the vertex in the precedence graph where indegree=0. So, take the vertex T2 from the graph and remove it from the graph.

Check the vertex in the precedence graph

Step 2: Again check the vertex in the left precedence graph where indegree=0. So, take the vertex T3 from the graph and remove it from the graph. And draw the edge from T2→T3.

graph and remove it from the graph

Step3: And at last, take the vertex T1 and connect with T3.

vertex T1 and connect with T3

Precedence graph equivalent to schedule S2

Precedence graph equivalent

Schedule S2 (Serial Schedule):

Time Transaction T1 Transaction T2 Transaction T3
t1   Read(Y)  
t2   Read(Z)  
t3   Write(Z)  
t4     Read(Y)
t5     Read(X)
t6     Write(Y)
t7 Read(X)    
t8 Read(Z)    
t9 Write(X)    
t10 Write(Z)    

Schedule S3 (Non-Serial Schedule):

Time Transaction T1 Transaction T2
t1 Read(X)  
t2    Read(X)
t3   Read (Y)
t4   Write(Y)
t5 Read(Y)  
t6 Write(X)  

To convert this schedule into a serial schedule, swap the non- conflicting operations of T1 and T2.

Time Transaction T1 Transaction T2
t1    Read(X)
t2   Read (Y)
t3   Write(Y)
t4 Read(X)  
t5 Read(Y)  
t6 Write(X)  

Then, finally get a serial schedule after swapping all the non-conflicting operations, so this schedule is conflict serializable.

Facebooktwitterredditpinterestlinkedinmailby feather