View Serializability in DBMS | Practice Problems

Database Management System
Spread the love

View Serializability-

 

Before you go through this article, make sure that you have gone through the previous article on View 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 view serializability.

 

Also read- Conflict Serializability

 

PRACTICE PROBLEMS BASED ON VIEW SERIALIZABILITY-

 

Problem-01:

 

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

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

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

  • W1(B) , W2(B)              (T1 → T2)
  • W1(B) , W3(B)              (T1 → T3)
  • W1(B) , W4(B)              (T1 → T4)
  • W2(B) , W3(B)              (T2 → T3)
  • W2(B) , W4(B)              (T2 → T4)
  • W3(B) , W4(B)              (T3 → T4)

 

Step-02:

 

Draw the precedence graph-

 

 

  • Clearly, there exists no cycle in the precedence graph.
  • Therefore, the given schedule S is conflict serializable.
  • Thus, we conclude that the given schedule is also view serializable.

 

Problem-02:

 

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

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

Checking Whether S is Conflict Serializable Or Not-

 

Step-01:

 

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

  • R1(A) , W3(A)              (T1 → T3)
  • R2(A) , W3(A)              (T2 → T3)
  • R2(A) , W1(A)              (T2 → T1)
  • W3(A) , W1(A)             (T3 → T1)

 

Step-02:

 

Draw the precedence graph-

 

 

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

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists a blind write W3 (A) in the given schedule S.
  • Therefore, the given schedule S may or may not be view serializable.

 

Now,

  • To check whether S is view serializable or not, let us use another method.
  • Let us derive the dependencies and then draw a dependency graph.

 

Drawing a Dependency Graph-

 

  • T1 firstly reads A and T3 firstly updates A.
  • So, T1 must execute before T3.
  • Thus, we get the dependency T1 → T3.
  • Final updation on A is made by the transaction T1.
  • So, T1 must execute after all other transactions.
  • Thus, we get the dependency (T2, T3) → T1.
  • There exists no write-read sequence.

 

Now, let us draw a dependency graph using these dependencies-

 

 

  • Clearly, there exists a cycle in the dependency graph.
  • Thus, we conclude that the given schedule S is not view serializable.

 

Problem-03:

 

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

 

 

Solution-

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

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)
  • W1(A) , W2(A)             (T1 → T2)
  • R1(B) , W2(B)              (T1 → T2)
  • R2(B) , W1(B)              (T2 → T1)

 

Step-02:

 

Draw the precedence graph-

 

 

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

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists no blind write in the given schedule S.
  • Therefore, it is surely not view serializable.

 

Alternatively,

  • You could directly declare that the given schedule S is not view serializable.
  • This is because there exists no blind write in the schedule.
  • You need not check for conflict serializability.

 

Problem-04:

 

Check whether the given schedule S is view serializable or not. If yes, then give the serial schedule.

S : R1(A) , W2(A) , R3(A) , W1(A) , W3(A)

 

Solution-

 

For simplicity and better understanding, we can represent the given schedule pictorially as-

 

 

  • We know, if a schedule is conflict serializable, then it is surely view serializable.
  • So, let us check whether the given schedule is conflict serializable or not.

 

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)
  • R1(A) , W3(A)              (T1 → T3)
  • W2(A) , R3(A)              (T2 → T3)
  • W2(A) , W1(A)             (T2 → T1)
  • W2(A) , W3(A)             (T2 → T3)
  • R3(A) , W1(A)              (T3 → T1)
  • W1(A) , W3(A)             (T1 → T3)

 

Step-02:

 

Draw the precedence graph-

 

 

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

 

Now,

  • Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
  • To check whether S is view serializable or not, let us use another method.
  • Let us check for blind writes.

 

Checking for Blind Writes-

 

  • There exists a blind write W2 (A) in the given schedule S.
  • Therefore, the given schedule S may or may not be view serializable.

 

Now,

  • To check whether S is view serializable or not, let us use another method.
  • Let us derive the dependencies and then draw a dependency graph.

 

Drawing a Dependency Graph-

 

  • T1 firstly reads A and T2 firstly updates A.
  • So, T1 must execute before T2.
  • Thus, we get the dependency T1 → T2.
  • Final updation on A is made by the transaction T3.
  • So, T3 must execute after all other transactions.
  • Thus, we get the dependency (T1, T2) → T3.
  • From write-read sequence, we get  the dependency T2 → T3

 

Now, let us draw a dependency graph using these dependencies-

 

 

  • Clearly, there exists no cycle in the dependency graph.
  • Therefore, the given schedule S is view serializable.
  • The serialization order T1 → T2 → T3.

 

Next Article- Recoverable and Irrecoverable Schedules

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
View Serializability in DBMS | Practice Problems
Article Name
View Serializability in DBMS | Practice Problems
Description
Practice Problems based on View Serializability and How to check whether a given schedule is view 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

Spread the love