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

Question

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?

Answer 1

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.

Answer 2

Whether it is necessary to include the edge $T_1 \to T_3$ depends upon how you plan to use the graph and what properties you want it to have.

In many applications, it is not necessary to include the edge $T_1 \to T_3$, since it is already implied by other edges. For instance, the set of schedules that are consistent with this graph (i.e., the set of topological sorts of the graph) will be the same whether you use a dag $G$, the transitive reduction of $G$, or the transitive closure of $G$.

The answer might depend upon what your definition of a "precedence graph" is. If you are using the phrase informally, then it is up to you to define what graph you want to use. On the other hand, if you are using "precedence graph" as a formally defined term, as defined "in the concurrency control literature", that definition states that you should include an edge from $u$ to $v$ if (1) $u$ must precede $v$, and (2) $u$ conflicts with $v$. Thus, if $T_1$ conflicts with $T_3$, then you should include the edge $T_1 \to T_3$ (assuming you want to use that definition); if it doesn't conflict, don't include that edge. In your example, it does conflict, so yes, you must include the edge $T_1 \to T_3$ if you want to use that definition of precedence graph.