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 -