patternMinor
Can you reduce a precedence graph or do *all* relevant nodes need to be connected
Viewed 0 times
cannodesgraphyouallneedreducerelevantconnectedprecedence
Problem
Let's say we have the following simple transaction-schedule:
T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.
My question is: is it also necessary to draw an arrow from T1 to T3? T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.
On the other hand, T1 -> T2 -> T3 implies T1 -> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?
If the answer to the above question is yes, here is a follow up - consider the following schedule:
In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?
T1 | T2 | T3
-----+------+-----
w(x)| |
| w(x) |
| | w(x)T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.
My question is: is it also necessary to draw an arrow from T1 to T3? T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.
On the other hand, T1 -> T2 -> T3 implies T1 -> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?
If the answer to the above question is yes, here is a follow up - consider the following schedule:
T1 | T2 | T3
-----+------+-----
w(x)| |
w(y)| |
| w(x) |
| w(z) |
| | w(y)
| | w(z)In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?
Solution
Yes it is necessary.
According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$ is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation in $T_j$.
It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $T_2$ and $T_3$.
So an edge $T_1 \longrightarrow T_3$ is necessary because w(x) in $T_1$ and w(x) in $T_3$ are two conflicting¹ operations.
For this schedule there will be three edges in the precedence graph:$T_1 \longrightarrow T_2$, $T_1 \longrightarrow T_3$ and $T_2 \longrightarrow T_3$.
1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.
According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$ is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation in $T_j$.
It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $T_2$ and $T_3$.
T1 | T2 | T3
-----+------+-----
w(x)| |
| w(x) |
| | w(x)So an edge $T_1 \longrightarrow T_3$ is necessary because w(x) in $T_1$ and w(x) in $T_3$ are two conflicting¹ operations.
T1 | T2 | T3
-----+------+-----
w(x)| |
w(y)| |
| w(x) |
| w(z) |
| | w(y)
| | w(z)For this schedule there will be three edges in the precedence graph:$T_1 \longrightarrow T_2$, $T_1 \longrightarrow T_3$ and $T_2 \longrightarrow T_3$.
1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.
Code Snippets
T1 | T2 | T3
-----+------+-----
w(x)| |
| w(x) |
| | w(x)T1 | T2 | T3
-----+------+-----
w(x)| |
w(y)| |
| w(x) |
| w(z) |
| | w(y)
| | w(z)Context
StackExchange Computer Science Q#23047, answer score: 4
Revisions (0)
No revisions yet.