Related Searches
Definitions
Nearby Words
Precedence Graphs
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
| 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.
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
Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)
This article is licensed under the GNU Free Documentation License.
Last updated on Sunday August 17, 2008 at 07:29:40 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation
This article is licensed under the GNU Free Documentation License.
Last updated on Sunday August 17, 2008 at 07:29:40 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation
Related Articles
|
|
|
|
|
|
|
|
|
|
HighBeam Research, Inc. © Copyright 2009.
Copyright © 2013 Dictionary.com, LLC. All rights reserved.
