DBMS Notes

Serializability And Its Types

  • As we know some non-serial schedule are also consistent and behave like serial schedules
  • To check whether the given non-serial schedule is serial or not, the concept of Serializability is used.

According to Serializability 

“If a given non-serial schedule of ‘n’ transactions is equivalent to some serial schedule of ‘n’ transactions, then it is called as a serializable schedule”.

Example

Suppose there are 3 transactions (T1,T2,T3) where T1 execute first and then T2 and T3 then serial schedule will  contain the following series of transaction execution

T1→T2→T3

Non-serial must contains a series where any transaction cannot repeat itself just like the above serial schedule but position of transaction can be inter-change. So Non-serial will be one of the following if it is serializable.

  • T1→T2 →T3
  • T1→T3 →T2
  • T2→T1 →T3
  • T2→T3 →T1
  • T3→T1 →T2
  • T3→T2 →T1

If a schedule contains the series of transaction where transctions are repeating like T1→T2 →T1 →T3 where T1 repeating then that series will not be serial.

Types of Serializability

Serializability is mainly of two types

1. Conflict Serializability

Conflict serializability is used to check whether the given Non-serial schedule is Serial or not.

Testing of of conflict serializability

  • In conflict serializability, by using conflicting pairs we draw a precedence graph from given schedule.
  • If derived precedence graph from schedule holds no loop then that schedule will be a serial schedule.

Keep in mind a serial schedule will always be

  • Consistant
  • Serializable or serial

Let explain with example

Example 01: Check given schedule is serializable or not?

Solution:

  • R(x) means Read operation on data “x”
  • W(y) means Write operation on data “y”
  • So, x,y is data and R,W are read and write operations

First find the precedence graph from above schedule.  To draw a precedence graph,

  • Taking all transactions as edge.
  • Check conflict pairs in other transactions and draw edge.

Steps to draw precedence graph

At time1, R(x) of T1 exist, as conflict of R(x) is W(x). so Check W(x) in T2 and T3. As No W(x) exist in T2 and T3, after time1. So, No edge is draw from T1 to T2 or T3.

At time2, R(y) of T3 exist, as conflict of R(y) is W(y). so Check W(y) in T2 and T1. As No W(y) exist in T2 and T1, after time2. So, No edge is draw from T3 to T1 or T2.

At time3, R(x) of T3 exist, as conflict of R(x) is W(x). so Check W(x) in T2 and T1. As W(x) exist in T1 , after time3. So, an edge is draw from T3 to T1.

At time4, R(y) of T2 exist, as conflict of R(y) is W(y). so Check W(y) in T1 and T3. As W(y) exist in T3 , after time4. So, an edge is draw from T2 to T3.

At time5, R(z) of T2 exist, as conflict of R(z) is W(z). So Check W(z) in T3 and T1, after time5. As an W(z) exist in T1, after time5. So, an edge is draw from T2 to T1.

At time6, W(y) of T3 exist, as conflict of W(y) is R(y) and W(y). so Check R(y) and  W(y) in T2 and T1, after time6. As No R(y) and W(y) exist in T2 and T1 , after time6. So, No edge is draw from T3 to T1 or T2.

At time7, W(z) of T2 exist, as conflict of W(z) is R(z) and W(z). so Check W(z) and R(z) in T1 and T3, after time7. As an W(z) exist in T1 , after time7. So, an edge is draw from T2 to T1. This edge is already exist.

At time8, time9, time10, operation of T1 R(z), W(x), W(z) are executed respectively. Because after time8, no operation of T2 and T3 are exists.

After all time execution, the following precedence graph will draw.

If precedence graph is has no loop or acyclic graph the given schedule will be

  • Conflict serilizable
  • Serilizable/serial
  • Consistant

Order or sequence of transaction execution will be derived through Topological Sort method

According to Topological Sort Method, select the vertex first which has lowest in-degree So,

In above example sequence will be T2 → T3 → T1.

Possible Sequence

  • If there are N transcations then possible sequence will be N!.
  • So for 3 transactions there can be 3!= 3*2*1 = 6 sequence .

Possible 6 sequence of 3 transactions are given below

  • T1→T2 →T3
  • T1→T3 →T2
  • T2→T1 →T3
  • T2→T3 →T1
  • T3→T1 →T2
  • T3→T2 →T1

2. View Serializibility

Why View Serializibility is used?

As we know if there is no loop in graph then it will be conflict serilizable but if there is a loop in the graph then it may or may not be a serilizable  which will be check through View Serializibility.

Method of view serializabitlity still are comming soon…..

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest