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

Maurice A.W. Houtsma, Annita N. Wilschut, Jan Flokstra

Research output: Contribution to conferencePaperpeer-review

62 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages206-217
Number of pages12
Publication statusPublished - Aug 1993
Event19th International Conference on Very Large Data Bases, VLDB 1993 - Dublin, Ireland
Duration: 24 Aug 199327 Aug 1993
Conference number: 19

Conference

Conference19th International Conference on Very Large Data Bases, VLDB 1993
Abbreviated titleVLDB
Country/TerritoryIreland
CityDublin
Period24/08/9327/08/93

Keywords

  • DB-PDB: PARALLEL DATABASES

Fingerprint

Dive into the research topics of 'Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithms on PRISMA/DB'. Together they form a unique fingerprint.

Cite this