Serializability in DBMS

Serializability in DBMS

Serializability is the concept in a transaction that helps to identify which non-serial schedule is correct and will maintain the database consistency. It relates to the isolation property of transaction in the database.

Serializability is the concurrency scheme where the execution of concurrent transactions is equivalent to the transactions which execute serially.

Serializable Schedule

A serial schedule is always a serializable schedule because any transaction only starts its execution when another transaction has already completed its execution. However, a non-serial schedule of transactions needs to be checked for Serializability.

Note: If a schedule of concurrent ‘n' transactions can be converted into an equivalent serial schedule. Then we can say that the schedule is serializable. And this property is known as serializability.

Testing of Serializability

To test the serializability of a schedule, we can use the serialization graph.

Suppose, a schedule S. For schedule S, construct a graph called as a precedence graph. It has a pair G = (V, E), where E consists of a set of edges, and V consists of a set of vertices. The set of vertices contain all the transactions participating in the S schedule. The set of edges contains all edges Ti ->Tj for which one of the following three conditions satisfy:

1. Create a node Ti ? Tj if Ti transaction executes write (Q) before Tj transaction executes read (Q).
2. Create a node Ti ? Tj if Ti transaction executes read (Q) before Tj transaction executes write (Q).
3. Create a node Ti ? Tj if Ti transaction executes write (Q) before Tj transaction executes write (Q).

Schedule S:

Time	Transaction T1	Transaction T2
t1	Read(A)
t2	A=A+50
t3	Write(A)
t4		Read(A)
t5		A+A+100
t6		Write(A)

Precedence graph of Schedule S

In above precedence graph of schedule S, contains two vertices T1 and T2, and a single edge T1? T2, because all the instructions of T1 are executed before the first instruction of T2 is executed.

If a precedence graph for any schedule contains a cycle, then that schedule is non-serializable. If the precedence graph has no cycle, then the schedule is serializable.
So, schedule S is serializable (i.e., serial schedule) because the precedence graph has no cycle.

Schedule S1:

Time	Transaction T1	Transaction T2
t1	Read(A)
t2		Read(A)
t3		Write(A)
t4	A=A+50
t5	Write(A)

Precedence graph of Schedule S1

In above precedence graph of schedule S1, contains two vertices T1 and T2, and edges T1? T2 and T2? T1. In this Schedule S1, operations of T1 and T2 transaction are present in an interleaved manner.
The precedence graph contains a cycle, that’s why schedule S1 is non-serializable.

Types of Serializability

1. Conflict Serializability
2. View Serializability

Related Posts:

• DBMS Data Independence: Logical and Physical
• Hashing in DBMS: Static and Dynamic
• Aggregate Functions in DBMS
• Concurrency Control Protocols
• View Serializability in DBMS
• Conflict Serializability in DBMS
• DBMS Schedule
• Concurrent Execution of Transaction
• ACID Properties in DBMS
• States of Transaction in DBMS
• What is Transaction in DBMS