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-

• W₁(B) , W₂(B)              (T₁ → T₂)
• W₁(B) , W₃(B)              (T₁ → T₃)
• W₁(B) , W₄(B)              (T₁ → T₄)
• W₂(B) , W₃(B)              (T₂ → T₃)
• W₂(B) , W₄(B)              (T₂ → T₄)
• W₃(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.
• 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-

• R₁(A) , W₃(A)              (T₁ → T₃)
• R₂(A) , W₃(A)              (T₂ → T₃)
• R₂(A) , W₁(A)              (T₂ → T₁)
• W₃(A) , W₁(A)             (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.

 

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 W₃ (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-

• 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₁)

 

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 : R₁(A) , W₂(A) , R₃(A) , W₁(A) , W₃(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-

• R₁(A) , W₂(A)              (T₁ → T₂)
• R₁(A) , W₃(A)              (T₁ → T₃)
• W₂(A) , R₃(A)              (T₂ → T₃)
• W₂(A) , W₁(A)             (T₂ → T₁)
• W₂(A) , W₃(A)             (T₂ → T₃)
• R₃(A) , W₁(A)              (T₃ → T₁)
• W₁(A) , W₃(A)             (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.

 

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 W₂ (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.

Schedules in DBMS-

 

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

 

We have discussed-

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

 

 

In this article, we will discuss about View Serializability.

 

View Serializability-

 

If a given schedule is found to be view equivalent to some serial schedule, then it is called as a view serializable schedule.

 

Also read- Schedules in DBMS

 

View Equivalent Schedules-

 

Consider two schedules S1 and S2 each consisting of two transactions T1 and T2.

Schedules S1 and S2 are called view equivalent if the following three conditions hold true for them-

 

Condition-01:

 

For each data item X, if transaction T_i reads X from the database initially in schedule S1, then in schedule S2 also, T_i must perform the initial read of X from the database.

 

Thumb Rule “Initial readers must be same for all the data items”.

 

Condition-02:

 

If transaction T_i reads a data item that has been updated by the transaction T_j in schedule S1, then in schedule S2 also, transaction T_i must read the same data item that has been updated by the transaction T_j.

 

Thumb Rule “Write-read sequence must be same.”.

 

Condition-03:

 

For each data item X, if X has been updated at last by transaction T_i in schedule S1, then in schedule S2 also, X must be updated at last by transaction T_i.

 

Thumb Rule “Final writers must be same for all the data items”.

 

Checking Whether a Schedule is View Serializable Or Not-

 

Method-01:

 

Check whether the given schedule is conflict serializable or not.

• If the given schedule is conflict serializable, then it is surely view serializable. Stop and report your answer.
• If the given schedule is not conflict serializable, then it may or may not be view serializable. Go and check using other methods.

 

Thumb Rules All conflict serializable schedules are view serializable. All view serializable schedules may or may not be conflict serializable.

 

Method-02:

 

Check if there exists any blind write operation.

(Writing without reading is called as a blind write).

• If there does not exist any blind write, then the schedule is surely not view serializable. Stop and report your answer.
• If there exists any blind write, then the schedule may or may not be view serializable. Go and check using other methods.

 

Thumb Rule No blind write means not a view serializable schedule.

 

Method-03:

 

In this method, try finding a view equivalent serial schedule.

• By using the above three conditions, write all the dependencies.
• Then, draw a graph using those dependencies.
• If there exists no cycle in the graph, then the schedule is view serializable otherwise not.

 

Next Article- Practice Problems On View Serializability

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

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.

Schedules in DBMS-

 

Before you go through this article, make sure that you have gone through the previous article on Schedules in DBMS.

 

We have discussed-

• A schedule is the order in which the operations of multiple transactions appear for execution.
• Serial schedules are always consistent.
• Non-serial schedules are not always consistent.

 

In DBMS, schedules may be classified as-

 

 

In this article, we will discuss about Serializability in DBMS.

 

Serializability in DBMS-

 

• Some non-serial schedules may lead to inconsistency of the database.
• Serializability is a concept that helps to identify which non-serial schedules are correct and will maintain the consistency of the database.

 

Serializable Schedules-

 

If a given non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’ transactions, then it is called as a serializable schedule.

 

Characteristics-

 

Serializable schedules behave exactly same as serial schedules.

Thus, serializable schedules are always-

• Consistent
• Recoverable
• Casacadeless
• Strict

 

Serial Schedules Vs Serializable Schedules-

 

Serial Schedules	Serializable Schedules
No concurrency is allowed. Thus, all the transactions necessarily execute serially one after the other.	Concurrency is allowed. Thus, multiple transactions can execute concurrently.
Serial schedules lead to less resource utilization and CPU throughput.	Serializable schedules improve both resource utilization and CPU throughput.
Serial Schedules are less efficient as compared to serializable schedules. (due to above reason)	Serializable Schedules are always better than serial schedules. (due to above reason)

 

Types of Serializability-

 

Serializability is mainly of two types-

 

 

1. Conflict Serializability
2. View Serializability

 

In this article, we will discuss about Conflict Serializability.

Learn about View Serializability.

 

Conflict Serializability-

 

If a given non-serial schedule can be converted into a serial schedule by swapping its non-conflicting operations, then it is called as a conflict serializable schedule.

 

Conflicting Operations-

 

Two operations are called as conflicting operations if all the following conditions hold true for them-

• Both the operations belong to different transactions
• Both the operations are on the same data item
• At least one of the two operations is a write operation

 

Example-

 

Consider the following schedule-

 

 

In this schedule,

• W1 (A) and R2 (A) are called as conflicting operations.
• This is because all the above conditions hold true for them.

 

Checking Whether a Schedule is Conflict Serializable Or Not-

 

Follow the following steps to check whether a given non-serial schedule is conflict serializable or not-

 

Step-01:

 

Find and list all the conflicting operations.

 

Step-02:

 

Start creating a precedence graph by drawing one node for each transaction.

 

Step-03:

 

• Draw an edge for each conflict pair such that if X_i (V) and Y_j (V) forms a conflict pair then draw an edge from T_i to T_j.
• This ensures that T_i gets executed before T_j.

 

Step-04:

 

• Check if there is any cycle formed in the graph.
• If there is no cycle found, then the schedule is conflict serializable otherwise not.

 

NOTE-

 

• By performing the Topological Sort of the Directed Acyclic Graph so obtained, the corresponding serial schedule(s) can be found.
• Such schedules can be more than 1.

 

Next Article- Practice Problems On Conflict Serializability

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.