[Solved]: Can you reduce a precedence graph or do *all* relevant nodes need to be connected

Problem Detail: 

Let's say we have the following simple transaction-schedule:

 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?

Asked By : Timon Knigge

Answered By : tanmoy

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$.

 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23047