DBMS Serializability

DBMS Serializability

Serializability is the classical concurrency scheme. It ensures that a schedule for executing concurrent transactions is equivalent to one that executes the transactions serially in some order. When multiple transactions are running concurrently then there is a possibility that the database may be left in an inconsistent state. Serializability is a concept that helps us to check which schedules are serializable.

Serializable schedule

A serializable schedule always leaves the database in consistent state. A serial schedule is always a serializable schedule because in serial schedule, a transaction only starts when the other transaction finished execution. However a non-serial schedule needs to be checked for Serializability. A non-serial schedule of n number of transactions is said to be serializable schedule, if it is equivalent to the serial schedule of those n transactions.

There are two types of Serializability:

1. Conflict Serializability

2. View Serializability

1. Conflict Serializability:

Conflict Serializability is one of the type of Serializability, which can be used to check whether a non-serial schedule is conflict serializable or not.

A schedule is called conflict serializable if we can convert it into a serial schedule after swapping its non-conflicting operations.

Conflicting operations

Two operations are said to be in conflict, if they satisfy all the following three conditions:

1. Both the operations should belong to different transactions.
2. Both the operations are working on same data item.
3. At least one of the operation is a write operation.

Example : Operation W(X) of transaction T1 and operation R(X) of transaction T2 are conflicting operations, because they satisfy all the three conditions mentioned above. They belong to different transactions, they are working on same data item X, one of the operation in write operation.

Two schedules are said to be conflict Equivalent if one schedule can be converted into other schedule after swapping non-conflicting operations. If a schedule is conflict Equivalent to its serial schedule then it is called Conflict Serializable schedule.

Example of Conflict Serializability

Consider this schedule:

To convert this schedule into a serial schedule we must have to swap the R(A) operation of transaction T2 with the W(A) operation of transaction T1. However we cannot swap these two operations because they are conflicting operations, thus we can say that this given schedule is not Conflict Serializable.

Another Example:

Swapping non-conflicting operations:

1. swapping R(A) of T1 and R(A) of T2

2. swapping R(A) of T1 and R(B) of T2

3. swapping R(A) of T1 and W(B) of T2.

After doing above swappings, the schedule is

This is a serial schedule after swapping all the non-conflicting operations so the given schedule is Conflict Serializable.

2. View Serializability

View Serializability is a process to find out that a given schedule is view serializable or not. A given schedule is view serializable, if the given schedule is View Equivalent to its serial schedule.

View Equivalent

Two schedules T1 and T2 are said to be view equivalent, if they satisfy all the following conditions:

1. Initial Read: Initial read of each data item in transactions must match in both schedules. For example, if transaction T1 reads a data item X before transaction T2 in schedule S1 then in schedule S2, T1 should read X before T2.

2. Final Write: Final write operations on each data item must match in both the schedules. For example, a data item X is last written by Transaction T1 in schedule S1 then in S2, the last write operation on X should be performed by the transaction T1.

3. Update Read: If in schedule S1, the transaction T1 is reading a data item updated by T2 then in schedule S2, T1 should read the value after the write operation of T2 on same data item. For example, In schedule S1, T1 performs a read operation on X after the write operation on X by T2 then in S2, T1 should read the X after T2 performs write on X.

View Serializable

If a schedule is view equivalent to its serial schedule then the given schedule is said to be View Serializable.

Example:

Now check the three conditions of view serializability:

Initial Read

In schedule S1, transaction T1 first reads the data item X. In S2 also transaction T1 first reads the data item X.

Check for Y in schedule S1, transaction T1 first reads the data item Y. In S2 also the first read operation on Y is performed by T1.

For both data items X & Y, the initial read condition is satisfied in S1 & S2.

Final Write

In schedule S1, the final write operation on X is done by transaction T2. In S2 also transaction T2 performs the final write on X.

Checking for Y in schedule S1, the final write operation on Y is done by transaction T2. In schedule S2, final write on Y is done by T2.

For both data items X & Y, the final write condition is satisfied in S1 & S2.

Update Read

In S1, transaction T2 reads the value of X, written by T1. In S2, the same transaction T2 reads the X after it is written by T1.

In S1, transaction T2 reads the value of Y, written by T1. In S2, the same transaction T2 reads the value of Y after it is updated by T1.

The update read condition is also satisfied for both the schedules.

Since all the three conditions that checks whether the two schedules are view equivalent are satisfied in this example, which means S1 and S2 are view equivalent.