Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems.

Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175

@inproceedings{DBLP:conf/sigmod/GoudaD81,
  author    = {Mohamed G. Gouda and
               Umeshwar Dayal},
  editor    = {Y. Edmund Lien},
  title     = {Optimal Semijoin Schedules For Query Processing in Local Distributed
               Database Systems},
  booktitle = {Proceedings of the 1981 ACM SIGMOD International Conference on
               Management of Data, Ann Arbor, Michigan, April 29 - May 1, 1981},
  publisher = {ACM Press},
  year      = {1981},
  pages     = {164-175},
  ee        = {http://doi.acm.org/10.1145/582318.582344, db/conf/sigmod/GoudaD81.html},
  crossref  = {DBLP:conf/sigmod/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Semijoin strategies are a technique for query processing in distributed database systems. In the past, methodologies for constructing minimum communication-cost strategies for solving tree queries have been developed. These assume point-to-point communication and ignore local processing costs and the limited communication capacity of the system. In this paper, query processing in bus or loop systems is considered. The definition of strategy is extended to allow for broadcast mode of communication. We then address the problem of finding the minimum response-time schedule for executing a given strategy in an m-bus system taking into account local processing and system capacity. It is shown that the problem is computationally intractable for general tree queries, even in a l-bus system, and for special classes of tree queries in an m-bus system. However, there is a polynomial-time algorithm for simple queries in a l-bus system.

Copyright © 1981 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Y. Edmund Lien (Ed.): Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, April 29 - May 1, 1981. ACM Press 1981

Contents

Online Edition: ACM Digital Library

References

[BC 81]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)
[Ch 80]: D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178
[GJ 79]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[GS 78]: ...
[He 80]: ...
[HY 79]: Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979)
[Me 76]: Robert Metcalfe, David Boggs: Ethernet: Distributed Packet Switching for Local Computer Networks. Commun. ACM 19(7): 395-404(1976)
[MP 77]: ...
[Wo 77]: Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235