Precedence Graph For Testing Conflict Serializability | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Precedence Graph For Testing Conflict Serializability in DBMS

Precedence Graph or Serialization Graph is used commonly to test Conflict Serializability of a schedule.
It is a directed Graph (V, E) consisting of a set of nodes V = {T₁, T₂, T₃……….T_n} and a set of directed edges E = {e₁, e₂, e₃………………e_m}.
The graph contains one node for each Transaction T_i. An edge e_i is of the form T_j → T_k where T_j is the starting node of e_i and T_k is the ending node of e_i. An edge e_i is constructed between nodes T_j to T_k if one of the operations in T_j appears in the schedule before some conflicting operation in T_k .

The Algorithm can be written as:

1. Create a node T in the graph for each participating transaction in the schedule.
2. For the conflicting operation read_item(X) and write_item(X) – If a Transaction T_j executes a read_item (X) after T_i executes a write_item (X), draw an edge from T_i to Tj in the graph.
3. For the conflicting operation write_item(X) and read_item(X) – If a Transaction T_j executes a write_item (X) after T_i executes a read_item (X), draw an edge from T_i to Tj in the graph.
4. For the conflicting operation write_item(X) and write_item(X) – If a Transaction T_j executes a write_item (X) after T_i executes a write_item (X), draw an edge from T_i to T_j in the graph.
5. The Schedule S is serializable if there is no cycle in the precedence graph.

If there is no cycle in the precedence graph, it means we can construct a serial schedule S’ which is conflict equivalent to the schedule S.
The serial schedule S’ can be found by Topological Sorting of the acyclic precedence graph. Such schedules can be more than 1.
For example,
Consider the schedule S:
S : r1(x) r1(y) w2(x) w1(x) r2(y)

Creating Precedence graph:

1. Make two nodes corresponding to Transaction T₁ and T₂.
   
2. For the conflicting pair r1(x) w2(x), where r1(x) happens before w2(x), draw an edge from T1 to T2.
   
3. For the conflicting pair w2(x) w1(x), where w2(x) happens before w1(x), draw an edge from T2 to T1.
   Since the graph is cyclic, we can conclude that it is not conflict serializable to any schedule serial schedule.
   Let us try to infer a serial schedule from this graph using topological ordering.
   The edge T1 → T2 tells that T1 should come before T2 in the linear ordering.
   The edge T2 → T1 tells that T2 should come before T1 in the linear ordering.
   So, we can not predict any particular order (when the graph is cyclic). Therefore, no serial schedule can be obtained from this graph.
   Consider the another schedule S1 :
   S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x)
   The graph for this schedule is:Since the graph is acyclic, the schedule is conflict serializable. Performing Topological Sort on this graph would give us a possible serial schedule which is conflict equivalent to schedule S1.
   In Topological Sort, we first select the node with indegree 0, which is T1. This would be followed by T3 and T2.
   So, S1 is conflict serializable since it is conflict equivalent to the serial schedule T1 T3 T2.

Condition of schedules to View-equivalent

Two schedules S1 and S2 are said to be view-equivalent if below conditions are satisfied: 

1. Initial Read
   If a transaction T1 reading data item A from database in S1 then in S2 also T1 should read A from database.
   Transaction T2 is reading A from database. 
2. Updated Read 
   If Ti is reading A which is updated by Tj in S1 then in S2 also Ti should read A which is updated by Tj.
   Above two schedule are not view-equivalent as in S1 : T3 is reading A updated by T2, in S2 T3 is reading A updated by T1. 
3. Final Write operation 
   If a transaction T1 updated A at last in S1, then in S2 also T1 should perform final write operations.
    Above two schedules are not view-equivalent as Final write operation in S1 is done by T1 while in S2 done by T2.

View Serializability: A Schedule is called view serializable if it is view equal to a serial schedule (no overlapping transactions).