10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
413
replace the second Path relation by NewPath. Note that if the shortest path
from u to v has length k, then we can break this path into a head of length
⌊k/2⌋at the beginning and a tail of length ⌈k/2⌉at the end. The tail will not
be discovered until the round ⌈k/2⌉, whereupon it appears in NewPath, while
the head will surely be discovered at that round (if k is even) or before (if k
is odd), and will thus be in Path for the next join with NewPath. Thus, the
following seminaive version of recursive doubling will work.
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 Path.X, NewPath.Y
FROM Path, NewPath
WHERE NewPath.X = Path.Y;
10.8.8
Smart Transitive Closure
There is a variant of recursive doubling, called smart transitive closure, that
avoids discovering the same path more than once. Every path of length greater
than 1 can be broken into a head whose length is a power of 2, followed by a
tail whose length is no greater than the length of the head.
Example 10.32 : A path of length 13 has a head consisting of the ﬁrst 8 arcs,
followed by a tail consisting of the last 5 arcs. A path of length 2 is a head of
length 1 followed by a tail of length 1. Note that 1 is a power of 2 (the 0th
power), and the tail will be as long as the head whenever the path itself has a
length that is a power of 2.
✷
To implement smart transitive closure in SQL, we introduce a relation
Q(X, Y ) whose function after the ith round is to hold all pairs of nodes (x, y)
such that the shortest path from x to y has length exactly 2i. Also, after the
ith round, Path(x, y) will be true if the shortest path from x to y is of length
at most 2i+1 −1.
Note that this interpretation of Path is slightly diﬀerent
from the interpretation of Path in the simple recursive-doubling method given
in Section 10.8.7.
Initially, set both Q and Path to be copies of the relation Arc. After the
ith round, assume that Q and Path have the contents described in the previous
paragraph. Note that for the round i = 1, the initial values of Q and Path
initially satisfy the conditions as described for i = 0. On the (i + 1)st round,
we do the following:
