Precedence Graph For Testing Conflict Serializability

Precedence Graph(serialization graph)
It is a directed graph G with set of nodes N (T1, T2, T3, …, Tn) and set of directed edges E (E1, E2, …, Em).
Algorithm for construction of Precedence Graph:

  • Create Nodes in the precedence graph equal to the number of transactions in the schedule S.
  • Create directed edge from Ti to Tj as Ti -> Tj if one of the following condition is true.(conflict operations).
    1. Read-Write Conflict:Create a directed edge Ti -> Tj if Tj reads data item (e.g. X) written by Ti.
    2. Write-Read Conflict:Create a directed edge Ti -> Tj if Tj writes into data item (e.g. X) after it has been read by Ti.
    3. Write-Write Conflict:Create a directed edge Ti -> Tj if Tj writes into data item (e.g. X) after it has been written by Ti.
  • The Schedule S is serializable if there is no cycle in the precedence graph.
  • Example: R1(X),R2(Y),R2(Y),W2(X),W3(Y),R1(X) 
    • First draw all the transactions in the precedence graph
    • Check if there is a Tj that reads an item after  Ti writes it.
      • T1 reads X after it has been written by T2, so there is a directed edge from T2 -> T1
    • Check if there is a Tj that write an item after Ti reads it.
      • T2 writes X after T1 reads it, so there is a directed edge from T1 -> T2
      • T3 writes Y after T2 reads it, so there is a directed edge from T2 -> T3
    • Check if there is a Tj that writes an item after  Ti writes it.
      • not in this case. So above graph is the final graph.
    • Above graph is cyclic as there is a cycle between T1 and T2, and therefore it is not conflict serializable.

Leave a Reply

avatar
  Subscribe  
Notify of