Serializability in DBMS

3.6K

What is serializability?

Serializability is the concurrency scheme. It ensures that a schedule for executing concurrent transactions is equivalent to one that executes the transactions serially in some order. It assumes that all accesses to the database are done using read and write operations.

In simple words ,we can say that we try to find the clone of a parallel transaction ,that is in serial schedule.

Types of Serializability in DBMS

There are two types of Serializability

1. Conflict Serializability
2. View Serializability

In the DBMS Schedules, we learned that there are two types of schedules – Serial & Non-Serial. A Serial schedule doesn’t support concurrent execution of transactions while a non-serial schedule supports concurrency. A non-serial schedule may leave the database in an inconsistent state so we need to check these non-serial schedules for Serializability.

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 the same data item.
3. At least one of the operations is a write operation.

Let’s see some examples to understand this:

Example 1: 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 the same data item X, one of the operations in write operation.

Example 2: Similarly Operations W(X) of T1 and W(X) of T2 are conflicting operations.

Example 3: Operations W(X) of T1 and W(Y) of T2 are non-conflicting operations because both the write operations are not working on same data item so these operations don’t satisfy the second condition.

Example 4: Similarly R(X) of T1 and R(X) of T2 are non-conflicting operations because none of them is write operation.

Example 5: Similarly W(X) of T1 and R(X) of T1 are non-conflicting operations because both the operations belong to the same transaction T1.

Conflict Serializable check

Lets check whether a schedule is conflict serializable or not. If a schedule is conflict Equivalent to its serial schedule then it is called Conflict Serializable schedule. Lets take few examples of schedules.

Example of Conflict Serializability

Lets consider this schedule:

T1         T2
-----     ------
R(A)
R(B)
          R(A)
          R(B)
          W(B)
W(A)

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.

Lets take another example:

T1         T2
-----     ------
R(A)
          R(A)
          R(B)
          W(B)
R(B)
W(A)

Lets swap non-conflicting operations:

After swapping R(A) of T1 and R(A) of T2 we get:

T1         T2
-----     ------
          R(A)
R(A)
          R(B)
          W(B)
R(B)
W(A)

After swapping R(A) of T1 and R(B) of T2 we get:

T1         T2
-----     ------
          R(A)
          R(B)
R(A) 
          W(B)
R(B)
W(A)

After swapping R(A) of T1 and W(B) of T2 we get:

T1         T2
-----     ------
          R(A)
          R(B)
          W(B)
R(A)         
R(B)
W(A)

We finally got a serial schedule after swapping all the non-conflicting operations so we can say that the given schedule is Conflict Serializable.

View Equivalent

Two schedules S1 and S2 are said to be view equivalent if they satisfy the following conditions:

1. Initial Read

An initial read of both schedules must be the same. Suppose two schedules S1 and S2. In schedule S1, if a transaction T1 is reading the data item A, then in S2, transaction T1 should also read A.

2. Updated Read

If Ti is reading A which is updated by Tj in S1 then in S2 also Ti should read A which is updated by Tj. 

Above two schedules are not view equal because, in S1, T3 is reading A updated by T2 and in S2, T3 is reading A updated by T1.

3. Final Write

A final write must be the same between both the schedules. In schedule S1, if a transaction T1 updates A at last then in S2, final writes operations should also be done by T1.

Above two schedules is view equal because Final write operation in S1 is done by T3 and in S2, the final write operation is also done by T3.

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.	Serializable Schedules are always better than serial schedules.