Parallel hierarchical evaluation of transitive closure queries

Maurice A.W. Houtsma, Filippo Cacace, Stefano Ceri

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

82 Downloads (Pure)

Abstract

Presents a new approach to parallel computation of transitive closure queries using a semantic data fragmentation. Tuples of a large base relation denote edges in a graph, which models a transportation network. A fragmentation algorithm is proposed which produces a partitioning of the base relation into several fragments such that any fragment corresponds to a subgraph. One fragment, called high-speed fragment, collects all edges which guarantee maximum speed. Thus, the fragmentation algorithm induces a hierarchical relationship between the high-speed fragment and all other fragments. With this fragmentation, any query about paths connecting two nodes can be answered by using just the fragments in which nodes are located and the high-speed fragment. In general, if each fragment is managed by a distinguished processor, then the query can be answered by three processors working in parallel. This schema can be applied recursively to generate an arbitrary number of hierarchical levels
Original languageEnglish
Title of host publicationProceedings of the 1st International Conference on Parallel and Distributed Information Systems (PDIS 1991)
Place of PublicationLos Alamitos
PublisherIEEE
Pages130-137
Number of pages8
ISBN (Print)0-8186-2295-4
DOIs
Publication statusPublished - Dec 1991
Event1st International Conference on Parallel and Distributed Information Systems (PDIS 1991) - Miami Beach, Florida, USA
Duration: 4 Dec 19916 Dec 1991

Conference

Conference1st International Conference on Parallel and Distributed Information Systems (PDIS 1991)
Period4/12/916/12/91
Other4-6 Dec. 1991

Keywords

  • DB-PDB: PARALLEL DATABASES

Fingerprint

Dive into the research topics of 'Parallel hierarchical evaluation of transitive closure queries'. Together they form a unique fingerprint.

Cite this