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 precedens graph for a schedule S contains:
- A node for each commited 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 | R(A) | ||
| 2 | W(A) | ||
| 3 | Commit | ||
| 4 | W(A) | ||
| 5 | Commit | ||
| 6 | W(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.
