Data fragmentation for parallel transitive closure strategies

Maurice A.W. Houtsma, Peter M.G. Apers, Gideon L.V. Schipper

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
62 Downloads (Pure)


A topic that is currently inspiring a lot of research is parallel (distributed) computation of transitive closure queries. In [lo] the disconnection set approach has been introduced as an effective strategy for such a computation. It involves reformulating a transitive closure query on a relation into a number of transitive closure queries on smaller fragments; these queries can then execute independently on the fragments, without need for communication and without computing the same tuples at more than one processor. Now that effective strategies as just mentioned have been developed, the next problem is that of developing adequate data fragmentation strategies for these approaches. This is a dificult problem, but of paramount importance to the success of these approaches. We discuss the issues that influence data fragmentation. We present a number of algorithms, each focusing on one of the important issues. We discuss the pros and cons of the algorithms, and we give some results of applying the algorithms to different types of graphs. This last aspect shows to what respect the algorithms indeed conform to the goals we set out.
Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Data Engineering (ICDE 1993)
Place of PublicationLos Alamitos, CA
Number of pages10
ISBN (Print)0-8186-3570-3
Publication statusPublished - Apr 1993
Event9th International Conference on Data Engineering, ICDE 1993 - Vienna, Austria
Duration: 19 Apr 199323 Apr 1993
Conference number: 9


Conference9th International Conference on Data Engineering, ICDE 1993
Abbreviated titleICDE




Dive into the research topics of 'Data fragmentation for parallel transitive closure strategies'. Together they form a unique fingerprint.

Cite this