In:
ACM Transactions on Database Systems, Association for Computing Machinery (ACM), Vol. 16, No. 2 ( 1991-05), p. 279-308
Abstract:
Consider the class of distributed database systems consisting of a set of nodes connected by a high bandwidth network. Each node consists of a processor, a random access memory, and a slower but much larger memory such as a disk. There is no shared memory among the nodes. The data are horizontally partitioned often using a hash function. Such a description characterizes many parallel or distributed database systems that have recently been proposed, both commercial and academic. We study the optimization problem that arises when the query processor must repartition the relations and intermediate results participating in a multijoin query. Using estimates of the sizes of intermediate relations, we show (1) optimum solutions for closed chain queries; (2) the NP-completeness of the optimization problem for star, tree, and general graph queries; and (3) effective heuristics for these hard cases. Our general approach and many of our results extend to other attribute partitioning schemes, for example, sort-partitioning on attributes, and to partitioned object databases.
Type of Medium:
Online Resource
ISSN:
0362-5915
,
1557-4644
DOI:
10.1145/114325.103713
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1991
detail.hit.zdb_id:
196155-X
detail.hit.zdb_id:
2006335-0
Bookmarklink