Skip Navigation

The Computer Journal 1996 39(8):675-687; doi:10.1093/comjnl/39.8.675
© 1996 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Morrissey, J. M.
Right arrow Articles by Bealor, W. T.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Minimizing Data Transfers in Distributed Query Processing: A Comparative Study and Evaluation

J. M. Morrissey * and W. T. Bealor *

School of Computer Science, University of Windsor, 401 Sunset, Windsor, Ontario, Canada N9B 3P4. Email: joan{at}cs.uwindsor.ca

A new heuristic, called Algorithm W, is presented as a method for efficiently generating cost-effective semijoin schedules for distributed query processing. It uses the concepts of profit, marginal profit and gain to determine a sequence of semijoins to minimize the total volume of data transferred over the network. Reducers, which are small in size and highly selective are constructed and applied in a cost-effective way. We show that in most cases the heuristic has complexity O(nm). However, static strategies, such as Algorithm W rely on accurate estimates to function properly. If the estimates are incorrect then the strategy may be less than optimal. Dynamic strategies, where the schedule of operations is monitored and modified during execution, are proposed as a solution to this problem. We propose two new dynamic heuristics: Algorithm D1 has minimal overheads and does not require schedule modification; Algorithm D2 is a more sophisticated dynamic strategy that has a ‘look ahead’ phase to determine the ‘best’ starting point for the optimization and it permits schedule modifications. We evaluate the performance of the heuristics and test the hypothesis that a dynamic strategy allows for better estimates and improved schedules.

Received November 27, 1995. revised November 22, 1996.

* School of Computer Science, University of Windsor, 401 Sunset, Windsor, Ontario, Canada N9B 3P4 Email: joan{at}cs.uwindsor.ca


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.