Introduces the connectivity index, an access structure for the efficient evaluation of traversal-recursive queries. Unlike conventional bottom-up evaluation techniques that require the creation of temporary files and scanning of the relations many times in computing the relational operators, the new access strategy requires only a single-pass scan of the index file. The proposed scheme is illustrated using examples. Algorithms for the maintenance of the index structure are presented.>

Two relational join strategies, broadcast-based join and bucket-based join, have been recently proposed for the hypercube interconnection topology. The first strategy, however, incurs many unnecessary comparisons of pairs of tuples of the two relations. Although the second technique compares only tuples of the relevant buckets, it may suffer from potential load imbalance, which is most critical to the performance of a shared-nothing system. To address these issues, a join algorithm for hypercube computers which includes dynamic load balancing capabilities to minimize the effect of skewness in tuple distribution is proposed. Simulation results indicate that the scheme provides significant improvement over the bucket-based join strategy. In fact, the technique is consistently superior even when the skew condition is very mild.>