Precedence graph
From Wikipedia, the free encyclopedia
A precedence graph, also named conflict graph and serializability graph, is used in the study of database theory within the realm of computer science.
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.
[edit] Precedence graph example
| Time | T1 | T2 | T3 |
|---|---|---|---|
| 1 | read(A) | ||
| 2 | write(A) | ||
| 3 | Commit | ||
| 4 | write(A) | ||
| 5 | Commit | ||
| 6 | write(A) | ||
| 7 | Commit |
A precedence graph of 3 transactions. As there is a cycle, this schedule (history) is not Conflict serializable.
[edit] 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.
- basic precedence graph generator by Laurens Stötzel, University of Duisburg-Essen, Germany
 |
This database-related article is a stub. You can help Wikipedia by expanding it. |
