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 examples
Example 1
![](../I/m/PrecedenceGraphExample1.jpg)
Example 2
Example 2
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. Notice, that the commit of Transaction 2 does not have any meaning regarding the creation of a precedence graph.
Testing Serializability with Precedence Graph
![](../I/m/Precedence_graph.svg.png)
Testing Serializability Example
Algorithm to test Conflict Serializability of a Schedule S along with an example schedule.
- or
- For each transaction Tx participating in schedule S, create a node labeled Ti in the precedence graph. Thus 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 results in a directed edge from T1 to T2 (as T1 has R(A) before T2 having W(A)).
- 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. This results in directed edges from T2 to T1, T2 to T3 and T1 to T3.
- The schedule S is serializable if and only if the precedence graph has no cycles. As T1 and T2 constitute a cycle, the above example is not (conflict) serializable.
gollark: Except the nearest person to you.
gollark: It's a fun and healthy activity we can all enjoy!
gollark: Hmm, yes, if you *know* that then it's kind of similar to coercion.
gollark: > i shouldn't need to deal with people who live in the time of the old testament properly if they're not willing to catch up to the centuries of science which have undermined their very base belief about the earthYes, and you can ignore them/block them/etc.
gollark: You can blame it on your upbringing and environment and genes or the initial conditions of the universe and the rules for updating it or something like that, but I'm a compatibilist.
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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.