10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
411
followed all paths of length up to d+1, and will therefore discover no new Path
facts on the last round. At that point, we know we can stop.
As for rechability, we can use seminaive evaluation to speed up the join at
each round. A fact Path(v, u) that was discovered more than one round ago
will already have been joined with every useful Arc(u, w) fact, and therefore will
not add any new Path facts at the current round. Therefore, we can implement
linear TC by the following seminaive algorithm.
The improved algorithm uses the relation Path(X, Y ) as well as a relation
NewPath(X, Y ), which contains all and only the Path facts that have been
discovered at the previous round. Initially, we set NewPath to be Arc, while
Path is empty. We repeat the following steps until at some round, NewPath is
a subset of Path.
1. Insert each node in NewPath into Path. If no change to Path occurs, then
we have discovered all Path facts, and the iteration ends.
2. Otherwise, compute a new value for relation NewPath(X, Y ) by setting
it to be the result of the following query:
SELECT DISTINCT NewPath.X, Arc.Y
FROM NewPath, Arc
WHERE Arc.X = NewPath.Y;
10.8.7
Transitive Closure by Recursive Doubling
Interestingly, the transitive closure can be computed much faster in parallel
than can strict reachability or linear transitive closure. By a recursive-doubling
technique, we can double the length of paths we know about in a single round.
Thus, on a graph of diameter d, we need only log2 d rounds, rather than d
rounds. If d = 6, the diﬀerence is not important, but if d = 1000, log2 d is
about 10, so there is a hundredfold reduction in the number of rounds.
The simplest recursive-doubling approach is to start with relation Path(X, Y )
equal to the arc relation Arc(X, Y ). Suppose that after i rounds, Path(X, Y )
contains all pairs (x, y) such that there is a path from x to y of length at most
2i. Then if we join Path with itself at the next round, we shall discover all those
pairs (x, y) such that there is a path from x to y of length at most 2×2i = 2i+1.
The recursive-doubling query in SQL is
SELECT DISTINCT p1.X, p2.Y
FROM Path p1, Path p2
WHERE p1.Y = p2.X;
After computing this query, we get all pairs connected by a path of length
between 2 and 2i+1, assuming Path contains pairs connected by paths of length
between 1 and 2i. If we take the union of the result of this query with the Arc
relation itself, then we get all paths of length between 1 and 2i+1 and can use the
