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:
“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)
“Let not England forget her precedence of teaching nations how to live.”
—John Milton (1608–1674)
“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)