A '''precedence graph''', also named '''conflict graph'''<ref>{{Cite web|url=http://math.cmu.edu/~bkell/21110-2010s/conflict-graphs.html|title = 21-110: Conflict graphs}}</ref> and '''serializability graph''', is used in the context of concurrency control in databases.<ref>{{cite web|url=http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/7-serializability/graph-conflict.html |title=Precedence graph test for conflict-serializability}}</ref> It is the directed graph representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions. A schedule is ''conflict-serializable'' if and only if its precedence graph of ''committed transactions'' is ''acyclic''.
The precedence graph for a schedule S contains: * A node for each committed transaction in S * An arc from T<sub>i</sub> to T<sub>j</sub> if an action of T<sub>i</sub> precedes and conflicts with one of T<sub>j</sub>'s actions. That is the actions belong to different transactions, at least one of the actions is a write operation, and the actions access the same object (read or write). Cycles of committed transactions can be prevented by aborting an ''undecided'' (neither committed, nor aborted) transaction on each cycle in the precedence graph of all the transactions, which can otherwise turn into a cycle of committed transactions (and a committed transaction cannot be aborted). One transaction aborted per cycle is both required and sufficient in number to break and eliminate the cycle (more aborts are possible, and can happen under some mechanisms, but are unnecessary for serializability). The probability of cycle generation is typically low, but, nevertheless, such a situation is carefully handled, typically with a considerable amount of overhead, since correctness is involved. Transactions aborted due to serializability violation prevention are ''restarted'' and executed again immediately.
==Precedence graph examples==
===Example 1=== :<math>S = \begin{bmatrix} T1 & T2 \\ R(A) & R(A) \\ A=A*5 & R(B) \\ W(A) & B=B+A \\ R(B) & W(B) \\ B=B*10 & \\ W(B) & \\
\end{bmatrix}</math>
===Example 2=== :'''<math>D = R1(A)</math> <math>R2(B)</math> <math>W2(A)</math> <math> Com.2</math> <math> W1(A)</math> <math> Com.1</math> <math> W3(A)</math> <math> Com.3 </math>'''
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.
=== Example 3 === thumb|Testing Serializability Example Algorithm to test ''Conflict Serializability'' of a Schedule S along with an example schedule.
<math>S = \begin{bmatrix} T1 & T2 & T3 \\ R(A) & & \\ & W(A) & \\ & Com. & \\ W(A) & & \\ Com. & & \\ & & W(A)\\ & & Com.\\ \end{bmatrix}</math>
:or
'''<math>S = R1(A)</math> <math>W2(A)</math> <math> Com.2</math> <math> W1(A)</math> <math> Com.1</math> <math> W3(A)</math> <math> Com.3 </math>'''
# For each transaction T<sub>x</sub> participating in schedule S, create a node labeled T<sub>i</sub> in the precedence graph. Thus the precedence graph contains T<sub>1</sub>, T<sub>2</sub>, T<sub>3</sub>. # For each case in S where T<sub>j</sub> executes a ''read_item''(X) after T<sub>i</sub> executes a ''write_item''(X), create an edge (T<sub>i</sub> → T<sub>j</sub>) in the precedence graph. This occurs nowhere in the above example, as there is no read after write. # For each case in S where T<sub>j</sub> executes a ''write_item''(X) after T<sub>i</sub> executes a ''read_item''(X), create an edge (T<sub>i</sub> → T<sub>j</sub>) in the precedence graph. This results in a directed edge from T<sub>1</sub> to T<sub>2</sub> (as T<sub>1</sub> has ''R(A)'' before T<sub>2</sub> having ''W(A)''). # For each case in S where T<sub>j</sub> executes a ''write_item''(X) after T<sub>i</sub> executes a ''write_item''(X), create an edge (T<sub>i</sub> → T<sub>j</sub>) in the precedence graph. This results in directed edges from T<sub>2</sub> to T<sub>1</sub>, T<sub>2</sub> to T<sub>3</sub> and T<sub>1</sub> to T<sub>3</sub>. # The schedule S is serializable if and only if the precedence graph has no cycles. As T<sub>1</sub> and T<sub>2</sub> constitute a cycle, the above example is not (conflict) serializable.
==References== {{Reflist}}
==External links== * [http://portal.acm.org/citation.cfm?id=1202608&dl=GUIDE&coll=GUIDE&CFID=9802819&CFTOKEN=82728908 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 System Concepts (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.
Category:Database management systems