
492
Bancilhon
and
Ramakrishnan
There are a total of
(h'
up>down
+ 1) steps. In addition, we set up D E
1
new
subqueries at Step i. In fact, we may set up new subqueries even when the pre-
vious steps generate no new paths, since this is done for i = 1 to h'
up
.
The paths with a segment of length i in up are computed by the following
join:
up. s
g.
down
The join at Step i is computed in 3 stages. For a given start node (in up),
we find all paths starting from one of its children and having a segment of
length i - 1 in up (and in down). We do this by simply using the paths we
found in Steps 1 through i
—
1 (i.e., in the partial results for s
g
compute ...