Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB
M.A.W. Houtsma, Annita N. Wilschut, Jan Flokstra · University of Twente Research Information · 1992
This paper describes an experimental performance study of the parallel computation of transitive closure operations on a parallel database system. This work brings two research efforts together. The first is the development of an efficient execution strategy for the parallel computation of path problems, called the Disconnection Set Approach. The second is the development and implementation of a parallel, main-memory DBMS, called PRISMA/DB. Here, we report on the implementation of the disconnection set approach on PRISMA/DB, showing how the latter's design allowed us to easily extend the functionality of the system. It is shown that the parallel implementation of the disconnection set approach yields good performance characteristics, and that linear speedup with respect to a special purpose single processor algorithm is achieved. Finally, we describe a number of experiments that show to what extent data fragmentation issues influence the performance of the disconnection set approach. 1...