Testing Serializability With Precedence Graph
The drawing sequence for the precedence graph:-
- 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
- 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.
- 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.
- 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.
- 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:
“Now I see that going out into the testing ground of men it is the tongue and not the deed that wins the day.”
—Sophocles (497–406/5 B.C.)
“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)