A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions.

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178
  author    = {D. M. Chiu and
               Y. C. Ho},
  editor    = {Peter P. Chen and
               R. Clay Sprowls},
  title     = {A Methodology for Interpreting Tree Queries Into Optimal Semi-Join
  booktitle = {Proceedings of the 1980 ACM SIGMOD International Conference on
               Management of Data, Santa Monica, California, May 14-16, 1980},
  publisher = {ACM Press},
  year      = {1980},
  pages     = {169-178},
  ee        = {, db/conf/sigmod/ChiuH80.html},
  crossref  = {DBLP:conf/sigmod/80},
  bibsource = {DBLP,}


In this paper we outline a general methodology illustrated by specific examples for the optimal interpretation of a class of semi-join queries in distributed database systems.

Copyright © 1980 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

Peter P. Chen, R. Clay Sprowls (Eds.): Proceedings of the 1980 ACM SIGMOD International Conference on Management of Data, Santa Monica, California, May 14-16, 1980. ACM Press 1980 BibTeX

Online Edition: ACM Digital Library


Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
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
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions (Abstract). SIGMOD Conference 1978: 39 BibTeX
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

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. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  3. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  4. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  5. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  6. Nick Roussopoulos, Hyunchul Kang: A Pipeline N-way Join Algorithm Based on the 2-way Semijoin Program. IEEE Trans. Knowl. Data Eng. 3(4): 486-495(1991)
  7. Kyung-Chang Kim: Performance of Query Optimization Heuristics in Object-Oriented Databases. DASFAA 1991: 99-108
  8. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
  9. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  10. Hyunchul Kang, Nick Roussopoulos: Using 2-way Semijoins in Distributed Query Processing. ICDE 1987: 644-651
  11. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
  12. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
  13. 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
  14. C. P. Wang, Victor O. K. Li: The Relation-Partitioning Approach to Processing Star Queries in Distributed Databases. ICDE 1986: 21-28
  15. Marjorie Templeton, David Brill, Arbee L. P. Chen, Son Dao, Eric Lund: Mermaid - Experiences with Network Operation. ICDE 1986: 292-300
  16. Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
  17. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  18. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  19. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
  20. Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
  21. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
  22. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
  23. Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61
  24. Patrick Valduriez: Semi-Join Algorithms for Multiprocessor Systems. SIGMOD Conference 1982: 225-233
  25. 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)
  26. Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163
  27. Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:23 2009