Implementation and Performance Evaluation of a Parallel Transitive ClosureAlgorithm on PRISMA/DB

摘要

The paper describes an experimental performance study of the parallel computationof transitive closure operations on a parallel database system. The 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 data base management system (DBMS), called PRISMA/DB. The paper reports on the implementation of the disconnection set approach on PRISMA/DB, showing how the latter's design allows one 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, it describes a number of experiments that show to what extent data fragmentation issues influence the performance of the disconnection set approach.