Join Strategies on Multi-Dimensional C1ustered Relations

For the last years we have developed relational database systems like GRACE and FDS-R(Functional Disk with Relational database engine)in which the relational algebraic operations were based on dynamic clustering algorithms. Performance evaluations of FDS-R and other works showed that the dynamic clustering algorithm was a good solution for very large unstructured relations. Concerning the relational algebraic operations on structured relations, recent researches exemplified by the Predicate-tree, the Superjoin Algorithm and the DYOP are based on multidimensional clustered relations. The first two are based on hashing, and the last, on a grid-partitioned relation. Anyway, all them are based on structures that partition the relation based on the relation space, not the attribute values. These kind of partitioning are obviously easy to be handled for join operations because the generated partitions are naturally disjoint concerning the discriminate attributes. However they are not conceivable in real applications since the methods based on hashing are not order-preserving and the ones based on grid-partitions show low load-factor for reasonable number of discriminate attributes. Here we present some join strategies for KD-tree indexed relations. As a multidimensional clustering method, KD-tree presents the desired characteristics of order preserving and high load-factor. However, the KD-tree generates partitions that are not disjoint concerning the value of discriminate attributes, which makes the operations on them difficult. In what follows we recall some strategies we have proposed to deal with this difficulty and previously introduced in. Some analysis and evaluations demonstrate the effectiveness of the join strategies for KD-tree indexed relations.