Precedence graph


A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.
The precedence graph for a schedule S contains:

Example 1

Example 2

A precedence graph of the schedule D, with 3 transactions. As there is a cycle through the committed transactions T1 and T2, this schedule is not Conflict serializable.
Notice, that the commit of Transaction 2 does not have any meaning regarding the creation of a precedence graph.

Testing Serializability with Precedence Graph

Algorithm to test Conflict Serializability of a Schedule S along with an example schedule.

  1. For each transaction Tx participating in schedule S, create a node labeled Ti in the precedence graph. Thus the precedence graph contains T1, T2, T3.
  2. For each case in S where Tj executes a read_item after Ti executes a write_item, create an edge 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 Tj executes a write_item after Ti executes a read_item, create an edge in the precedence graph. This results in a directed edge from T1 to T2 before T2 having W.
  4. For each case in S where Tj executes a write_item after Ti executes a write_item, create an edge in the precedence graph. This results in directed edges from T2 to T1, T2 to T3 and T1 to T3.
  5. The schedule S is serializable if and only if the precedence graph has no cycles. As T1 and T2 constitute a cycle, the above example is not serializable.