Testing of Serializability in DBMS

by

Testing of Serializability

The Serializability of a schedule is tested using a Serialization graph.

Assume a schedule S1. For S1, a graph called Precedence Graph is constructed. This graph consists of a pair G = (V, E), where E is a set of the edges, and V is a set of all vertices. All the transactions participating in the schedule are stored in the vertices. The set of edges is used to contain all edges Ti ->Tj for which one of the three conditions holds:

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

Schedule S Precedence Graph

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

 

Explanation

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 S1

This graph contains a cycle which is why it is not serializable.

Explanation

Read(A): In T4, no subsequent writes to A, so no new edges
Read(C): In T4, no subsequent writes to C, so no new edges
Write(A): A is subsequently read by T5, so add edge T4 → T5
Read(B): In T5, no subsequent writes to B, so no new edges
Write(C): C is subsequently read by T6, so add edge T4 → T6
Write(B): A is subsequently read by T6, so add edge T5 → T6
Write(C): In T6, no subsequent reads to C, so no new edges
Write(A): In T5, no subsequent reads to A, so no new edges
Write(B): In T6, no subsequent reads to B, so no new edges

 

Precedence Graph S2

S2 is not cyclic, which is why it is serializable.