Néron model: Difference between revisions
Jump to navigation
Jump to search
Deltahedron (talk | contribs) |
en>R.e.b. Expanding article |
||
Line 1: | Line 1: | ||
A '''precedence graph''', also named '''conflict graph''' and '''[[serializability]] graph''', is used in the context of [[concurrency control]] in [[database]]s. | |||
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 [[Schedule (computer science)#Conflicting actions|conflicts]] with one of T<sub>j</sub>'s actions. | |||
==Precedence graph example== | |||
[[Image:Precedence graph.svg|200px|right]] | |||
:<math>D = \begin{bmatrix} | |||
T1 & T2 & T3 \\ | |||
R(A) & & \\ | |||
& W(A) & \\ | |||
& Com. & \\ | |||
W(A) & & \\ | |||
Com. & & \\ | |||
& & W(A)\\ | |||
& & Com.\\ | |||
\end{bmatrix}</math> | |||
or | |||
:'''<math>D = 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>''' | |||
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 (computer science)|schedule]] (history) is ''not'' [[Serializability#View and conflict serializability|Conflict serializable]]. | |||
==Testing Serializability with Precedence Graph== | |||
The drawing sequence for the precedence graph:- | |||
# For each transaction T<sub>i</sub> participating in schedule S, create a node labelled T<sub>i</sub> in the precedence graph. So the precedence graph contains T<sub>1</sub>, T<sub>2</sub>, T<sub>3</sub> | |||
# For each case in S where T<sub>i</sub> executes a write_item(X) then T<sub>j</sub> executes a read_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>i</sub> executes a read_item(X) then T<sub>j</sub> executes a write_item(X), create an edge (T<sub>i</sub> --> T<sub>j</sub>) in the precedence graph. This will bring to front a directed graph from T<sub>1</sub> to T<sub>2</sub>. | |||
# For each case in S where T<sub>i</sub> executes a write_item(X) then T<sub>j</sub> executes a write_item(X), create an edge (T<sub>i</sub> --> T<sub>j</sub>) in the precedence graph. It creates a directed graph from T<sub>2</sub> to T<sub>1</sub>, T<sub>1</sub> to T<sub>3</sub>, and T<sub>2</sub> to T<sub>3</sub>. | |||
# The schedule S is serializable if the precedence graph has no cycles. As T<sub>1</sub> and T<sub>2</sub> constitute a bicycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods. | |||
==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 [[serializability#View and conflict serializability|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. | |||
[[Category:Database management systems]] | |||
[[el:Γράφος Σειριοποιησιμότητας]] | |||
[[ru:Граф предшествования]] |
Revision as of 20:43, 15 August 2013
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
or
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.
Testing Serializability with Precedence Graph
The drawing sequence for the precedence graph:-
- For each transaction Ti participating in schedule S, create a node labelled Ti in the precedence graph. So the precedence graph contains T1, T2, T3
- For each case in S where Ti executes a write_item(X) then Tj executes a read_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 Ti executes a read_item(X) then Tj executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. This will bring to front a directed graph from T1 to T2.
- For each case in S where Ti executes a write_item(X) then Tj executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. It creates a directed graph from T2 to T1, T1 to T3, and T2 to T3.
- The schedule S is serializable if the precedence graph has no cycles. As T1 and T2 constitute a bicycle, then we cannot declare S as serializable or not and serializability has to be checked using other methods.
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.