TY - Generic
T1 - Parallel transitive closure computations using topological sort
T2 - Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991
Y1 - 1991
A1 - Hua, K. A.
A1 - Sridhar Hannenhalli
KW - Computer science
KW - Concurrent computing
KW - data partitioning
KW - Database systems
KW - database theory
KW - deductive databases
KW - File systems
KW - horizontal partitioning
KW - joins
KW - local data fragments
KW - message passing multiprocessor system
KW - Multiprocessing systems
KW - Parallel algorithms
KW - PARALLEL PROCESSING
KW - parallel programming
KW - parallel transitive closure
KW - processing nodes
KW - relation tuples
KW - Relational databases
KW - sorting
KW - topological sort
AB - Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm
JA - Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991
PB - IEEE
SN - 0-8186-2295-4
ER -