OPTIMIZING JOINS BETWEEN 2 FRAGMENTED RELATIONS ON A BROADCAST LOCAL-NETWORK

The problem of joining two fragmented relations on a broadcast network is dealt with. Multiple copies of a fragment are used to increase parallelism and reduce transmission cost. A bipartite graph model is used to represent the pairs of fragments from the two relations which need to be joined. We are interested in minimizing total transmission cost needed to compute a distributed join between two fragmented relations. This join problem is formulated as a linear integer program. Two heuristics are developed for the general two-way join problem. When the corresponding join graph is restricted to tree structure, an optimal algorithm can be developed. Computational experiments are performed to analyze the performances of these heuristics.
Publisher
PERGAMON-ELSEVIER SCIENCE LTD
Issue Date
1991
Language
ENG
Keywords

DISTRIBUTED DATABASES; OPTIMIZATION; SYSTEMS

Citation

INFORMATION SYSTEMS, v.16, no.2, pp.185 - 198

ISSN
0306-4379
DOI
10.1016/0306-4379(91)90014-Z
URI
http://hdl.handle.net/10203/4891
Appears in Collection
KGSM-Journal Papers(저널논문)
  • Hit : 388
  • Download : 8
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 4 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0