A parallel strategy for transitive closure using double hash-based clustering

Abstract

We present a parallel algorithm to compute the transitive closure of a relation. The transitive closure operation has been recognized as an important extension of the relational algebra. The importance of the performance problem brought by its evaluation brings one to consider parallel execution strategies. Such strategies constitute one of the keys to efficiency in a very large data base environment. The innovative aspects of the presented algorithm concern: 1) the possibility of working with a reasonable amount of memory space without creating extra Inputs/Outputs; 2) the use of on-disk clustering accomplished by double hashing; and 3) the parallelization of the transitive closure operation. The processing time is reduced by a factor of p, where p is the number of processors allocated for the operation. Communication times remain limited; a cyclic organization eliminates the need for serialization of transfers. The evaluation in a shared nothing architecture, shows the benefits of the proposed parallel transitive algorithm. Permission to copy kbilhout VW all or par1 of thi material i5 oranted provided that the copies arc not maclc OIcli~trihuted ~‘oIt direct commercial advantage. the VLDH copy I-ight notice‘ and the title of the publication and it Jarc appmr. ;~nd notice k gi\cn that copying is hq pcmmi~sion of the Vcr! Large Data Haw Endowment. To copy othcrwisc. or IO rcpuhlish. rccttlirc :I fee and/or special permission from the Endowrncnt.