Precedence Graph - Testing Serializability With Precedence Graph

Testing Serializability With Precedence Graph

The drawing sequence for the precedence graph:-

1. For each transaction T_i participating in schedule S, create a node labelled T_i in the precedence graph. So the precedence graph contains T₁, T₂, T₃
2. For each case in S where T_j executes a read_item(X) after T_i executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. This occurs nowhere in the above example, as there is no read after write.
3. For each case in S where T_j executes a write_item(X) after T_i executes a read_item(X), create an edge (T_i --> T_j) in the precedence graph. This will bring to front a directed graph from T₁ to T₂.
4. For each case in S where T_j executes a write_item(X) after T_i executes a write_item(X), create an edge (T_i --> T_j) in the precedence graph. It creates a directed graph from T₂ to T₁, T₁ to T₃, and T₂ to T₃.
5. The schedule S is serializable if the precedence graph has no cycles. As T₁ and T₂ constitute a bicycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods.