Distributed Transitive Closure Computations: The Disconnected Set Approach

摘要

The recursion process of transitive closure is addressed. To gain speedup inprocessing for efficient computation, distributed (parallel) computation is considered. A disconnection set approach which fragments the data beforehand according to rules stemming from the application domain is introduced. It is applicable to several queries based on transitive closure such as connectivity, shortest path, and bill of materials. It can be generalized to work for other application domains. Example illustrations are given and the reformulation into independent subqueries is proved sound and complete. Relational algebra programs for actual computation are presented. Preliminary simulations which show that the approach leads to a speedup which is almost proportional to the number of processors without significant overhead are included.