Precedence graph
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
![](../I/m/Precedence_graph.svg.png)
or
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
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 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.
- 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 results in a directed edge from T1 to T2.
- 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. This results in directed edges from T2 to T1, T1 to T3, and T2 to T3.
- The schedule S is conflict 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
- The Fundamentals of Database Systems, 5th Edition the use of precedence graphs is discussed in chapter 17, as they relate to tests for conflict serializability.
- Abraham Silberschatz, Henry Korth, and S. Sudarshan. 2005. Database Systems Concepts (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.
This article is issued from Wikipedia - version of the 10/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.