View Serializability in DBMS
View Serializability
It is a type of serializability that can be used to check whether the given schedule is view serializable or not. A schedule called as a view serializable if it is view equivalent to a serial schedule.
View Equivalent
Two schedules S1 and S2 are said to be view equivalent if both satisfy the following conditions:
1. Initial read
An initial read of the data item in both the schedule must be same. For example, lets two schedule S1 and S2. If transaction T1 reads the data item A in schedule S1, then in schedule S2 transaction T1 also reads A.
Schedule S1:
Time | Transaction T1 | Transaction T2 |
t1 | Read(X) | |
t2 | Write(X) |
Schedule S2:
Time | Transaction T1 | Transaction T2 |
t1 | Write(X) | |
t2 | Read(X) |
Above two schedules, S1 and S2 are view equivalent, because initial read instruction in S1 is done by T1 transaction and in schedule S2 is also done by transaction T2.
2. Updated Read
In schedule S1, if the transaction Ti is reading the data item A which is updated by transaction Tj, then in schedule S2 also, Ti should read data item A which is updated by Tj.
Schedule S1:
Time | Transaction T1 | Transaction T2 |
t1 | Write(X) | |
t2 | Read(X) |
Schedule S2:
Time | Transaction T1 | Transaction T2 |
t1 | Write(X) | |
t2 | Read(X) |
Above two schedules S1 and S2 are view equivalent because in schedule S1 transaction
T2 reads the data item A which is updated by T1 and in schedule S2 T2 also reads
the data item A which is updated by T1.
3. Final write
The final write operation on each data item in both the schedule must be same. In a schedule S1, if a transaction T1 updates data item A at last then in schedule S2, final writes operations should also be done by T1 transaction.
Schedule S1:
Time | Transaction T1 | Transaction T2 | Transaction T3 |
t1 | Write(X) | ||
t2 | Read(X) | ||
t3 | Write(X) |
Schedule S2:
Time | Transaction T1 | Transaction T2 | Transaction T3 |
t1 | Write(X) | ||
t2 | Read(X) | ||
t3 | Write(X) |
Above two schedules, S1 and S2 are view equivalent because final write operation in schedule S1 is done by T1 and in S2, T1 also does the final write operation.
View Serializable
A schedule is said to be a view serializable if that schedule is view equivalent to a serial schedule.
View Serializable example
Schedule S1 (Non-Serial Schedule):
Time | Transaction T1 | Transaction T2 |
t1 | Read(X) | |
t2 | Write(X) | |
t3 | Read(X) | |
t4 | Write(X) | |
t5 | Read(Y) | |
t6 | Write(Y) | |
t7 | Read(Y) | |
t8 | Write(Y) |
Schedule S2 (Serial Schedule):
Time | Transaction T1 | Transaction T2 |
t1 | Read(X) | |
t2 | Write(X) | |
t3 | Read(Y) | |
t4 | Write(Y) | |
t5 | Read(X) | |
t6 | Write(X) | |
t7 | Read(Y) | |
t8 | Write(Y) |
Note: S2 is the serial schedule of S1. If we can prove that both the schedule are view equivalent, then we can say that S1 schedule is a view serializable schedule.
Now, check the three conditions of view serializability for this example:
1. Initial Read
In
S1 schedule, T1 transaction first reads the data item X. In Schedule S2 also
transaction T1 first reads the data item X.
Now, check for Y. In schedule S1, T1 transaction first reads the data item Y.
In schedule S2 also the first read operation on data item Y is performed by T1.
We checked for both data items X and Y, and the initial read condition
is satisfied in schedule S1 & S2.
2. Updated Read
In
Schedule S1, transaction T2 reads the value of X, which is written by transaction
T1. In Schedule S2, the same transaction T2 reads the data item X after T1
updates it.
Now check for Y. In Schedule S1, transaction T2 reads the value of Y, which is
written by T1. In S2, the same transaction T2 reads the value of data item Y
after T1 writes it.
The update read condition is also
satisfied for both the schedules S1 and S2.
3. Final Write
In
schedule S1, the final write operation
on data item X is done by transaction T2. In schedule S2 also transaction T2
performs the final write operation on X.
Now, check for data item Y. In schedule S1, the final write operation on Y is done
by T2 transaction. In schedule S2, a final write operation on Y is done by T2.
We checked for both data items X and Y, and the final write condition
is also satisfied for both the schedule S1 & S2.
Conclusion: Hence, all the three conditions are satisfied in this example, which means Schedule S1 and S2 are view equivalent. Also, it is proved that schedule S2 is the serial schedule of S1. Thus we can say that the S1 schedule is a view serializable schedule.