Distributed transitive closure computations: the disconnection set approach
M.A.W. Houtsma, Peter M. G. Apers, Stefano Ceri · University of Twente Research Information · 1990
This paper deals with one of the most common and important types of recursion: transitive closure. Since many real world problems reduce to generalized transitive closure computations, efficient computation is essential. To gain a significant speedup in processing, we consider distributed (i.e. parallel) computation. Partial support from NFI, a Dutch research fund, and from the LOGIDATA+ project of C.N.R Italy y Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands z Computer Science Department, University of Twente x Dipartimento di Matematica,Universita' di Modena By fragmenting the data beforehand according to rules stemming from the application domain, queries can be split into several independent subqueries. These subqueries are computed in parallel on only a part of the data and are more specialized in the sense that extra selections are applied on each fragment. The disconnection set approach introduced in this paper...