Define schedule and serializability. How can you test the serializability?

This answer is restricted. Please login to view the answer of this question.

Login Now


A series of operations from one transaction to another transaction is known as a schedule. It is used to preserve the order of the operation in each individual transaction.


The serializability of schedules is used to find non-serial schedules that allow the transaction to execute concurrently without interfering with one another.

It identifies which schedules are correct when executions of the transaction have to interleave their operations.

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 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.
If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

  Loading . . .