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

This paper is one of the first to discuss actual implementation of and eqerimentation with parallel transitive closure operations on a full-fledged relational database system. It brings two research efforts together;
the development of an eficient execution strategy for parallel computation of path problems, called Disconnection Set Approach, and the development
and implementation of a parallel, main-memory DBMS, called PRISMA/DB. First, we report on the implementation of the disconnection set approach on PRISMA/DB, showing how the latter’s design allowed us to easily exend the functionality of the system. Second, we investigate the disconnection set approach’s parallel behavior and performance by means of extensive
experimentation.
It is shown that the parallel implementation of the disconnection set approach yields very good performance characteristics, and that (super)linear speedup
w.r.t. a special implementation of semi-naive is achieved for regular, so-called linear fragmentations. We also present a number of experiments that show
to what extent data fragmentation issues influence the performance. Finally, we discuss the speedup and benefits to be achieved for arbitrary fragmentations.