Conflict Serializability | Practice Problems

Conflict Serializability-

 

Before you go through this article, make sure that you have gone through the previous article on Conflict Serializability.

 

We have discussed-

• The concept of serializability helps to identify the correct non-serial schedules that will maintain the consistency of the database.
• There are two types of serializability-

 

 

In this article, we will discuss practice problems based on conflict serializability.

 

PRACTICE PROBLEMS BASED ON CONFLICT SERIALIZABILITY-

 

Problem-01:

 

Check whether the given schedule S is conflict serializable or not-

S : R₁(A) , R₂(A) , R₁(B) , R₂(B) , R₃(B) , W₁(A) , W₂(B)

 

Solution-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

• R₂(A) , W₁(A)              (T₂ → T₁)
• R₁(B) , W₂(B)              (T₁ → T₂)
• R₃(B) , W₂(B)              (T₃ → T₂)

 

Step-02:

 

Draw the precedence graph-

 

 

• Clearly, there exists a cycle in the precedence graph.
• Therefore, the given schedule S is not conflict serializable.

 

Problem-02:

 

Check whether the given schedule S is conflict serializable and recoverable or not-

 

 

Solution-

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

• R₂(X) , W₃(X)              (T₂ → T₃)
• R₂(X) , W₁(X)              (T₂ → T₁)
• W₃(X) , W₁(X)             (T₃ → T₁)
• W₃(X) , R₄(X)              (T₃ → T₄)
• W₁(X) , R₄(X)              (T₁ → T₄)
• W₂(Y) , R₄(Y)              (T₂ → T₄)

 

Step-02:

 

Draw the precedence graph-

 

 

• Clearly, there exists no cycle in the precedence graph.
• Therefore, the given schedule S is conflict serializable.

 

Checking Whether S is Recoverable Or Not-

 

• Conflict serializable schedules are always recoverable.
• Therefore, the given schedule S is recoverable.

 

Alternatively,

• There exists no dirty read operation.
• This is because all the transactions which update the values commits immediately.
• Therefore, the given schedule S is recoverable.
• Also, S is a Cascadeless Schedule.

 

Problem-03:

 

Check whether the given schedule S is conflict serializable or not. If yes, then determine all the possible serialized schedules-

 

 

Solution-

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

• R₄(A) , W₂(A)              (T₄ → T₂)
• R₃(A) , W₂(A)              (T₃ → T₂)
• W₁(B) , R₃(B)              (T₁ → T₃)
• W₁(B) , W₂(B)             (T₁ → T₂)
• R₃(B) , W₂(B)              (T₃ → T₂)

 

Step-02:

 

Draw the precedence graph-

 

 

• Clearly, there exists no cycle in the precedence graph.
• Therefore, the given schedule S is conflict serializable.

 

Finding the Serialized Schedules-

 

• All the possible topological orderings of the above precedence graph will be the possible serialized schedules.
• The topological orderings can be found by performing the Topological Sort of the above precedence graph.

 

After performing the topological sort, the possible serialized schedules are-

1. T₁ → T₃ → T₄ → T₂
2. T₁ → T₄ → T₃ → T₂
3. T₄ → T₁ → T₃ → T₂

 

Problem-04:

 

Determine all the possible serialized schedules for the given schedule-

 

 

Solution-

 

The given schedule S can be rewritten as-

 

 

This is because we are only concerned about the read and write operations taking place on the database.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

List all the conflicting operations and determine the dependency between the transactions-

• R₁(A) , W₂(A)              (T₁ → T₂)
• R₂(A) , W₁(A)              (T₂ → T₁)
• W₂(A) , W₁(A)             (T₂ → T₁)
• R₂(B) , W₁(B)              (T₂ → T₁)
• R₁(B) , W₂(B)              (T₁ → T₂)
• W₁(B) , W₂(B)             (T₁ → T₂)

 

Step-02:

 

Draw the precedence graph-

 

 

• Clearly, there exists a cycle in the precedence graph.
• Therefore, the given schedule S is not conflict serializable.
• Thus, Number of possible serialized schedules = 0.

 

Next Article- View Serializability in DBMS

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.