Precedence graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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:

  • A node for each committed transaction in S
  • An arc from Ti to Tj if an action of Ti precedes and conflicts with one of Tj's actions.

Precedence graph example[edit]

Precedence graph.svg
D = \begin{bmatrix}
T1   & T2   & T3  \\
R(A) &      &     \\
     & W(A) &     \\
     & Com. &     \\
W(A) &      &     \\
Com. &      &     \\
     &      & W(A)\\
     &      & Com.\\
\end{bmatrix}

or

D = R1(A) W2(A)  Com.2  W1(A)  Com.1  W3(A)  Com.3

A precedence graph of the schedule D, with 3 transactions. As there is a cycle (of length 2; with two edges) through the committed transactions T1 and T2, this schedule (history) is not Conflict serializable.

Testing Serializability with Precedence Graph[edit]

The drawing sequence for the precedence graph:-

  1. For each transaction Ti participating in schedule S, create a node labelled Ti in the precedence graph. So the precedence graph contains T1, T2, T3
  2. For each case in S where Ti executes a write_item(X) then Tj executes a read_item(X), create an edge (Ti --> Tj) 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 Ti executes a read_item(X) then Tj executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. This will bring to front a directed graph from T1 to T2.
  4. For each case in S where Ti executes a write_item(X) then Tj executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. It creates a directed graph from T2 to T1, T1 to T3, and T2 to T3.
  5. The schedule S is serializable if the precedence graph has no cycles. As T1 and T2 constitute a cycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods.

External links[edit]