Serialization

 

Serializability

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. A serializable schedule is the one that always leaves the database in consistent state.

What is a 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. A serial schedule doesn’t allow concurrency, only one transaction executes at a time and the other starts when the already running transaction finished.

Types of Serializability 

There are two types of Serializability.

 1.         Conflict Serializability

 2.         View Serializability

 Conflict Serializability

 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 operations is a write operation

 View Serializability

 View Serializability is a process to find out that a given schedule is view serializable or not.

 To check whether a given schedule is view serializable, we need to check whether the given schedule is View Equivalent to its serial schedule

 Testing of Serializability

 Serialization Graph is used to test the Serializability of a schedule.

 Assume a schedule S. For S, we construct a graph known as precedence graph. This graph has a pair G = (V, E), where V consists a set of vertices, and E consists a set of edges. The set of vertices is used to contain all the transactions participating in the schedule. The set of edges is used to contain all edges Ti ->Tj for which one of the three conditions holds:

 Create a node Ti → Tj if Ti executes write (Q) before Tj executes read (Q).

 Create a node Ti → Tj if Ti executes read (Q) before Tj executes write (Q).

Create a node Ti → Tj if Ti executes write (Q) before Tj executes write (Q).

If a precedence graph contains a single edge Ti → Tj, then all the instructions of Ti are executed before the first instruction of Tj is executed. If a precedence graph for schedule S contains a cycle, then S is non-serializable. If the precedence graph has no cycle, then S is known as serializable.

 

 

 

Read(A): In T1, no subsequent writes to A, so no new edges

Read(B): In T2, no subsequent writes to B, so no new edges

Read(C): In T3, no subsequent writes to C, so no new edges

Write(B): B is subsequently read by T3, so add edge T2 → T3

Write(C): C is subsequently read by T1, so add edge T3 → T1

 Write(A): A is subsequently read by T2, so add edge T1 → T2

 Write(A): In T2, no subsequent reads to A, so no new edges

 Write(C): In T1, no subsequent reads to C, so no new edges

 Write(B): In T3, no subsequent reads to B, so no new edges 

Precedence graph for schedule S1:

 

 

View Serializability

• A schedule will view serializable if it is view equivalent to a serial schedule.
• If a schedule is conflict serializable, then it will be view serializable.
• The view serializable which does not conflict serializable contains blind writes.

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 schedule 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.

Above two schedules are view equivalent because Initial read operation in S1 is done by T1 and in S2 it is also done by T1.

2. Updated Read

In schedule S1, if Ti is reading A which is updated by Tj 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

Example:

Schedule S

With 3 transactions, the total number of possible schedule

1.     = 3! = 6  

2.     S1 = <T1 T2 T3>  

3.     S2 = <T1 T3 T2>  

4.     S3 = <T2 T3 T1>  

5.     S4 = <T2 T1 T3>  

6.     S5 = <T3 T1 T2>  

7.     S6 = <T3 T2 T1>  

Taking first schedule S1:

ex