ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Query Processing for Distributed Databases Using Generalized Semi-Joins.

Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160
@inproceedings{DBLP:conf/sigmod/KambayashiYY82,
  author    = {Yahiko Kambayashi and
               Masatoshi Yoshikawa and
               Shuzo Yajima},
  editor    = {Mario Schkolnick},
  title     = {Query Processing for Distributed Databases Using Generalized
               Semi-Joins},
  booktitle = {Proceedings of the 1982 ACM SIGMOD International Conference on
               Management of Data, Orlando, Florida, June 2-4, 1982},
  publisher = {ACM Press},
  year      = {1982},
  pages     = {151-160},
  ee        = {http://doi.acm.org/10.1145/582353.582381, db/conf/sigmod/KambayashiYY82.html},
  crossref  = {DBLP:conf/sigmod/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In distributed database systems, the cost to process a query is mainly determined by the amount of communication. Semi-join is a very useful tool to reduce the cost of joins in such systems. There are, however, queries called cyclic ones which cannot be processed by semi-joins only. In this paper the concept of generalized semi-joins is introduced to solve such a problem. To handle an arbitrary cyclic query, first a spanning tree is selected in the corresponding query graph and then generalized semi-joins are applied in the order determined by the tree. Processing of cyclic queries, however, requires more communication cost than processing of tree queries, since in the former case we need to transmit attribute values which are not required in the latter case. A procedure to reduce the communication cost of such additional data is developed, which will make the generalized semi-join based procedures practical.

Copyright © 1982 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 ...

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

Printed Edition

Mario Schkolnick (Ed.): Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, Orlando, Florida, June 2-4, 1982. ACM Press 1982 BibTeX
Contents

Online Edition: ACM Digital Library

References

[AHO-H74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[ATZEP8203]
Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX
[BEERF8105]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[BERNC8101]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BERNG7912]
...
[BERNG8111]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[BERNG8112]
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX
[BLASE77]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[HEVNY7905]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[KAMB 8109]
...
[MERRK8109]
T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498 BibTeX
[ROTHB8003]
James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, Terry A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[ROTHG7710]
James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 BibTeX
[WONG 7705]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[YU--07911]
...

Referenced by

  1. Chihping Wang, Ming-Syan Chen: On the Complexity of Distributed Query Optimization. IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
  2. Ming-Syan Chen, Philip S. Yu: A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 6(1): 152-165(1994)
  3. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
  4. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  5. Ming-Syan Chen, Philip S. Yu: Combining Join and Semi-Join Operations for Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993)
  6. A. Y. Lu, Phillip C.-Y. Sheu: Processing of Multiple Queries in Distributed Databases. ICDE 1991: 42-49
  7. Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58
  8. Y. C. Tay: Attribute Agreement. PODS 1989: 110-119
  9. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
  10. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
  11. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
  12. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  13. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  14. Masatoshi Yoshikawa, Yahiko Kambayashi: Processing Inequality Queries Based on Generalized Semi-Joins. VLDB 1984: 416-428
  15. Ravi Krishnamurthy, Stephen P. Morgan: Distributed Query Optimization: An Engineering Approach. ICDE 1984: 220-227
  16. Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:31 2009