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:
“Bourbons the only drink. You can take all that champagne stuff and pour it down the English Channel. Well, why wait 80 years before you can drink the stuff? Great vineyards, huge barrels aging forever, poor little old monks running around testing it, just so some woman in Tulsa, Oklahoma can say it tickles her nose.”
—John Michael Hayes (b.1919)
“Let not England forget her precedence of teaching nations how to live.”
—John Milton (16081674)
“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 (19111980)