Parallel hierarchical evaluation of transitive closure queries

Houtsma, M.A.W. and Cacace, F. and Ceri, S. (1991) Parallel hierarchical evaluation of transitive closure queries. In: First International Conference on Parallel and Distributed Information Systems, Miami Beach Florida, 1991, 4-6 Dec. 1991, Miami Beach, FL.

Preview

PDF
623Kb

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
Item Type:	Conference or Workshop Item
Copyright:	©1991 IEEE
Research Group:	Information Systems (IS) Databases (DB)
Link to this item:	http://purl.utwente.nl/publications/19243
Official URL:	http://dx.doi.org/10.1109/PDIS.1991.183080
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 119766