Precedence Graph - Testing Serializability With Precedence Graph

Testing Serializability With Precedence Graph

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 Tj executes a read_item(X) after Ti executes a write_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 Tj executes a write_item(X) after Ti executes a read_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 Tj executes a write_item(X) after Ti 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 bicycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods.

Read more about this topic:  Precedence Graph

Famous quotes containing the words testing, precedence and/or graph:

    “Today so much rebellion is aimless and demoralizing precisely because children have no values to challenge. Teenage rebellion is a testing process in which young people try out various values in order to make them their own. But during those years of trial, error, embarrassment, a child needs family standards to fall back on, reliable habits of thought and feeling that provide security and protection.”
    —Neil Kurshan (20th century)

    “What is line? It is life. A line must live at each point along its course in such a way that the artist’s presence makes itself felt above that of the model.... With the writer, line takes precedence over form and content. It runs through the words he assembles. It strikes a continuous note unperceived by ear or eye. It is, in a way, the soul’s style, and if the line ceases to have a life of its own, if it only describes an arabesque, the soul is missing and the writing dies.”
    —Jean Cocteau (1889–1963)

    “When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
    —Marshall McLuhan (1911–1980)