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 : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)

 

Solution-

 

Step-01:

 

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

  • R2(A) , W1(A)              (T2 → T1)
  • R1(B) , W2(B)              (T1 → T2)
  • R3(B) , W2(B)              (T3 → T2)

 

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-

  • R2(X) , W3(X)              (T2 → T3)
  • R2(X) , W1(X)              (T2 → T1)
  • W3(X) , W1(X)             (T3 → T1)
  • W3(X) , R4(X)              (T3 → T4)
  • W1(X) , R4(X)              (T1 → T4)
  • W2(Y) , R4(Y)              (T2 → T4)

 

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-

  • R4(A) , W2(A)              (T4 → T2)
  • R3(A) , W2(A)              (T3 → T2)
  • W1(B) , R3(B)              (T1 → T3)
  • W1(B) , W2(B)             (T1 → T2)
  • R3(B) , W2(B)              (T3 → T2)

 

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. T1 → T3 → T4 → T2
  2. T1 → T4 → T3 → T2
  3. T4 → T1 → T3 → T2

 

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-

  • R1(A) , W2(A)              (T1 → T2)
  • R2(A) , W1(A)              (T2 → T1)
  • W2(A) , W1(A)             (T2 → T1)
  • R2(B) , W1(B)              (T2 → T1)
  • R1(B) , W2(B)              (T1 → T2)
  • W1(B) , W2(B)             (T1 → T2)

 

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.

Summary
Conflict Serializability | Practice Problems
Article Name
Conflict Serializability | Practice Problems
Description
Practice Problems based on Conflict Serializability and How to check whether a given schedule is conflict serializable or not. Serializability in DBMS is a concept that helps to identify the correct non-serial schedules that will maintain the consistency of the database.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-