|
|
|
@inproceedings{DBLP:conf/vldb/Chang82,
author = {Jo-Mei Chang},
title = {A Heuristic Approach to Distributed Query Processing},
booktitle = {Eigth International Conference on Very Large Data Bases, September
8-10, 1982, Mexico City, Mexico, Proceedings},
publisher = {Morgan Kaufmann},
year = {1982},
isbn = {0-934613-14-1},
pages = {54-61},
ee = {db/conf/vldb/Chang82.html},
crossref = {DBLP:conf/vldb/82},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
In a distributed database environment, finding the optimal strategy which fully reduces all relations referenced by a general tree query, may take exponential time. Furthermore, since reduced relations are to be moved to the final site, the optimal strategy which fully reduces all relations does not give an optimal solution to the problem of minimizing the total transmission cost. For a general query, even with only one join attribute, the problem of finding an optimal strategy to reduce the total data transmission cost has been shown to be NP-hard.
In this paper, a heuristic approach is taken to the distributed query processing problem. Different cost benefit functions are defined based on the nature of the relations involved in the semijoin. The proposed algorithm will produce a sequence of cost beneficial semijoin operations to reduce the total data transmission cost involved in answering a general query. For each join attribute, a two phase reduction process is used. The order in which the semijoins are performed is controlled by the projected size of the join attribute. This algorithm produces optimal sequence of semijoins for simple queries. For general queries, The experimental results, obtained by simulation, indicate a substantial improvement over the SDD-1 query processing algorithm.
Copyright © 1982 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
