View Serializability in DBMS

Before moving to view serializability, please make sure you have learned serializability, if not please visit the given article

View Serializability is a procedure to check if the given schedule is consistent or not. It is performed only if the given schedule is not conflict-serializable. It is important to check the consistency of the schedule as an inconsistent schedule leads to an inconsistent state of the program which is undesirable.

What is View Serializability?

A system handles multiple transactions running concurrently, there is a possibility that a few of them leave the system databases in an inconsistent state and thus, the system fails. To be aware of such schedules and save the system from failures, we check if schedules are serializable or not. If the given schedule is serializable implies it will never leave the database in an inconsistent state.

Serial schedules are the schedules where no two transactions are executed concurrently. Thus, serial schedules never leave the database in an inconsistent state. If the given schedule is view serializable, then we are sure that it is a consistent schedule or serial schedule.

View Serializability is a process used to check whether the given schedule is view serializable or not. To do so we check if the given schedule is View Equivalent to its serial schedule.

Why do we need to Use View-Serializability?

There is a possibility that even though the schedule does not conflict serializable, it gives a consistent result. This is because conflict serializability is limited to the precedence graph of a schedule. If the precedence graph contains any loops/cycles we cannot predict whether a schedule is consistent or inconsistent.

If its precedence graph doesn't contain any loop/cycle and the given schedule is consistent, but if it contains a loop/cycle then the schedule may or may not be consistent. To figure out the state of the schedule, we use the concept of View-Serializability because we do not want to bind the concept of Serializability only to Conflict with Serializability.

Example

Let us understand View-Serializability with an example of a schedule S~1~.

Checking conflict serializability Precedence Graph of S1:

• R1(X), W2(X) (T1 → T2)
• R2(X), W1(X) (T2 → T1)
• W1(X), W2(X) (T1 → T2)
• R1(Y), W2(Y) (T1 → T2)
• R2(Y), W1(Y) (T2 → T1)
• W1(Y), W2(Y) (T1 → T2)

The conflict precedence graph is as follows:

The above graph contains cycle/loop thus, it is not conflict serializable but by only considering the precedence graph we can't conclude if the given schedule is consistent or not.

In the above example if we swap a few transaction operations, and format the table as follows:

Now the precedence graph is as follows:

The precedence graph doesn't contain any cycle or loop which implies the given schedule is conflict serializable and the result will be the same as that of the first table.

But if the given schedule does not conflict with serializable, then we need to check for View Serializability. If it is view serializable then it is consistent else it is inconsistent. Thus, to address the limitations of conflict serializability, the concept of view-serializability was introduced.

Methods to Check View Serializability

There are two methods to check View Serializability.

Method 1: View Equivalent

If the given schedule is view-equivalent to the serial schedule itself then we can say that the schedule is view-serializable.

To generate the serial schedule of the given schedule, we follow the following steps:

• Take the transaction say Ti that performs any operation first in the schedule. Write all the operations performed by that transaction one after the other in the given schedule.
• Similarly, take another transaction that is performing any operation right after Ti in the given schedule and write all the operations performed by it below transaction Ti on any data item.
• Follow the above steps for all the transactions. The order is very important.

Let us take the example of the table for checking View Serializability.

Let us call this Schedule S1

Also, for the above table the serial schedule is as follows:

Let us call this Schedule S2

As transaction T1 performed the first operation we wrote all of its operations on data item X as well as Y first and then all the operations of T2 are written next.

Two schedules are said to be viewed as equivalent if they satisfy the following three conditions:

Condition 1: Initial Read

Initially if transaction T1 of Schedule S1 reads data item X, then transaction T1 of Schedule S2 must read data item X initially as well.

In the example above, the Initial read is made by the T1 transaction for both the data items X and Y in Schedule S1 and in S2 as well as initial read is made by transaction T1 for both. Thus, the initial read condition is satisfied in S1 and S2 for data items X and Y.

Condition 2: Update Read

If transaction Ti is reading updated data item X by transaction Tj in S1, then in Schedule S2 Ti should read X which is updated by Tj.

The value of X and Y is updated by transaction T1 in schedule S1, which is read by transaction T2. In Schedule S2 the X and Y data items are updated by T1 and are read by T2 as well. Thus, in the above two schedules, the update read condition is also satisfied.

Condition 3: Final Write

If transaction T1 updates data item Y at last in S1, then in S2 also, T1 should perform the final write operation on Y.

The final write for data items X and Y are made by Transaction T2 in Schedule S1. Also, the final write is made by T2 in Schedule S2 in Schedule S1 as well as serial schedule S2. Thus, the condition for the final write is also satisfied.

Result

As all three conditions are satisfied for our schedule S1 and its Serial Schedule S2, they are view equivalent. Thus, we can say that the given schedule S1 is the view-serializable schedule and is consistent.

Method 2: Check the View-Serializability of a Schedule

There's another method to check the view-serializability of a schedule. The first step of this method is the same as the previous method i.e. checking the conflict serializability of the schedule by creating the precedence graph.

Let us take an example of the schedule as follows to check the View Serializability

Writing all the conflicting operations:

• R1(X), W2(X) (T1 → T2)
• R1(X), W3(X) (T1 → T3)
• W2(X), R3(X) (T2 → T3)
• W2(X), W1(X) (T2 → T1)
• W2(X), W3(X) (T2 → T3)
• R3(X), W1(X) (T3 → T1)
• W1(X), W3(X) (T1 → T3)

The precedence graph for the above schedule is as follows:

If the precedence graph doesn't contain a loop/cycle, then it is conflict serializable, and thus concludes that the given schedule is consistent. We are not required to perform the View Serializability test as a conflict serializable schedule is view-serializable as well.

As the above graph contains a loop/cycle, it does not conflict with serializable. Thus we need to perform the following steps -

Next, we will check for blind writes. If the blind writes don't exist, then the schedule is non-view Serializable. We can simply conclude that the given schedule is inconsistent.

If there exist any blind writes in the schedule, then it may or may not be view serializable.

Blind writes: If a write action is performed on a data item by a Transaction (updation), without performing the reading operation then it is known as blind write.

In the above example, transaction T2 contains a blind write, thus we are not sure if the given schedule is view-serializable or not.

Lastly, we will draw a dependency graph for the schedule. Note: The dependency graph is different from the precedence graph.

Steps for dependency graph:

• Firstly, T1 reads X, and T2 first updates X. So, T1 must execute before the T2 operation. (T1 → T2)
• T3 performs the final updation on X thus, T3 must execute after T1 and T2. (T1 → T3 and T2 → T3)
• T2 updates X before T3, so we get the dependency as (T2 → T3)

The dependency graph is formed as follows:

As no cycles exist in the dependency graph for the example we can say that the schedule is view-serializable.

If any cycle/ loop exists then it is not view-serializable and the schedule is inconsistent. If cycle//loop doesn't exist then it is view-serializable.