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

Distributed Query Processing.

Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
@article{DBLP:journals/csur/YuC84,
  author    = {Clement T. Yu and
               C. C. Chang},
  title     = {Distributed Query Processing},
  journal   = {ACM Comput. Surv.},
  volume    = {16},
  number    = {4},
  year      = {1984},
  pages     = {399-433},
  ee        = {db/journals/csur/YuC84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper, various techniques for optimizing queries in distributed databases are preeented. Although no attempt is made to cover all proposed algorithms on this topic, quite a few ideas extracted from existing algorithms are outlined. It is hoped that large-scale experiments will be conducted to verify the usefulness of these ideas and that they will be integrated to construct a powerful algorithm for distributed query processing.

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

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library


References

[Adiba et al. 1978]
Michel E. Adiba, Jean-Claude Chupin, Robert Demolombe, Georges Gardarin, Jean Le Bihan: Issues in Distributed Data Base Management Systems: A Technical Overview. VLDB 1978: 89-110 BibTeX
[Apers et al. 1983]
Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983) BibTeX
[Babb 1979]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[Baldissera et al. 1979]
...
[Beeri et al. 1981]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[Beeri et al. 1983]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) BibTeX
[Bernstein and Chiu 1981]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[Bernstein and Goodman 1979]
...
[Bernstein and Goodman 1981]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[Bernstein et al. 1981]
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
[Black and Luk 1982]
...
[Ceri and Pelagatti 1984]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[Chandy 1977]
K. Mani Chandy: Models of Distributed Systems. VLDB 1977: 105-120 BibTeX
[Chang 1982a]
Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61 BibTeX
[Chang 1982b]
...
[Chen and Li 1983]
...
[Cheung 1981]
...
[Chiu 1980]
...
[Chiu and Ho 1980]
D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX
[Codd 1970]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Codd 1972]
E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX
[Date 1977]
C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977
BibTeX
[Epstein and Stonebraker 1980]
Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101 BibTeX
[Epstein et al. 1978]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
[Fagin et al. 1980]
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX
[Goodman and Shmueli 1982a]
Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX
[Goodman and Shmueli 1982b]
Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54 BibTeX
[Goodman and Shmueli 1983]
Nathan Goodman, Oded Shmueli: Syntactic Characterization of Tree Database Schemas. J. ACM 30(4): 767-786(1983) BibTeX
[Goodman et al. 1979]
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
[Gouda and Dayal 1981]
Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175 BibTeX
[Graham 1979]
...
[Griffiths Selinger et al. 1979]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Hevner 1980]
...
[Hevner and Yao 1979]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[Jarke and Koch 1983]
Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206 BibTeX
[Jarke and Schmidt 1982]
Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264 BibTeX
[Kambayashi 1981]
...
[Kambayashi and Yoshikawa 1983]
Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67 BibTeX
[Kambayashi et al. 1982]
Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160 BibTeX
[Kerschberg et al. 1980]
...
[Kim 1982]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[King 1982]
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX
[Krishnamurthy and Morgan 1984]
Ravi Krishnamurthy, Stephen P. Morgan: Distributed Query Optimization: An Engineering Approach. ICDE 1984: 220-227 BibTeX
[Kung and Lehman 1980]
H. T. Kung, Philip L. Lehman: Systolic (VLSI) Arrays for Relational Database Operations. SIGMOD Conference 1980: 105-116 BibTeX
[Luk and Black 1981]
...
[Luk and Luk 1980]
...
[Reiner 1982]
David S. Reiner: Letter from the Guest Editor. IEEE Database Eng. Bull. 5(3): 1(1982) BibTeX
[Rothnie adn Goodman 1977a]
James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 BibTeX
[Rothnie and Goodman 1977b]
James B. Rothnie Jr., Nathan Goodman: An Overview of the Preliminary Design of SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 39-57 BibTeX
[Rothnie et al. 1980]
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
[Sacco 1984]
Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516 BibTeX
[Stonebraker et al. 1982]
Michael Stonebraker, John Woodfill, Jeff Ranstrom, Marguerite C. Murphy, Joseph Kalash, Michael J. Carey, Kenneth Arnold: Performance Analysis of Distributed Data Base Systems. IEEE Database Eng. Bull. 5(4): 58-65(1982) BibTeX
[Ullman 1980]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX
[Wah and Lien 1984]
Benjamin W. Wah, Yao-Nan Lien: The File-Assignment and Query-Processing Problems in Local Multiaccess Networks. ICDE 1984: 228-235 BibTeX
[Williams et al. 1981]
R. Williams, Dean Daniels, Laura M. Haas, George Lapis, Bruce G. Lindsay, Pui Ng, Ron Obermarck, Patricia G. Selinger, Adrian Walker, Paul F. Wilms, Robert A. Yost: R*: An Overview of the Architecture. JCDKB 1982: 1-27 BibTeX
[Wong 1977]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[Wong 1981]
Eugene Wong: Dynamic Re-Materialization: Processing Distributed Queries Using Redundant Data. Berkeley Workshop 1981: 3-13 BibTeX
[Wong and Katz 1983]
Eugene Wong, Randy H. Katz: Distributing A Database for Parallelism. SIGMOD Conference 1983: 23-29 BibTeX
[Wong and Youssefi 1976]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[Yao 1977]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[Yu and Ozsoyoglu 1979]
...
[Yu et al. 1979]
Clement T. Yu, Z. Meral Özsoyoglu, K. Lam: Optimization of Distributed Tree Queries. J. Comput. Syst. Sci. 29(3): 409-445(1984) BibTeX
[Yu et al. 1982a]
Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390 BibTeX
[Yu et al. 1982b]
...
[Yu et al. 1983]
Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39 BibTeX
[Yu et al. 1984a]
...
[Yu et al. 1984b]
...

Referenced by

  1. Hubert Naacke, Georges Gardarin, Anthony Tomasic: Leveraging Mediator Cost Models with Heterogeneous Data Sources. ICDE 1998: 351-360
  2. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
  3. Chihping Wang, Ming-Syan Chen: On the Complexity of Distributed Query Optimization. IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
  4. Chengwen Liu, Hao Chen, Warren Krueger: A Distributed Query Processing Strategy Using Placement Dependency. ICDE 1996: 477-484
  5. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
  6. Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
  7. Zhe Li, Kenneth A. Ross: PERF Join: An Alternative to Two-way Semijoin and Bloomjoin. CIKM 1995: 137-144
  8. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  9. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  10. Wei Sun, Mark Allen Weiss: An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities. IEEE Trans. Knowl. Data Eng. 6(6): 997-1001(1994)
  11. 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)
  12. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
  13. P. E. Drenick, E. J. Smith: Stochastic Query Optimization in Distributed Databases. ACM Trans. Database Syst. 18(2): 262-288(1993)
  14. 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)
  15. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  16. Wei Sun, Yibei Ling, Naphtali Rishe, Yi Deng: An Instant and Accurate Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conference 1993: 79-88
  17. Rex Blankinship, Alan R. Hevner, S. Bing Yao: An Iterative Method for Distributed Database Design. VLDB 1991: 389-400
  18. Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58
  19. Amit P. Sheth, James A. Larson: Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Comput. Surv. 22(3): 183-236(1990)
  20. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  21. J. T. Park, Toby J. Teorey: A Knowledge/Based Approach to Multiple Query Processing. DASFAA 1989: 133-140
  22. Yasushi Kiyoki, Takahiro Kurosawa, Peng Liu, Kazuhiko Kato, Takashi Masuda: Implementation and Experiments of an Extensible Parallel Processing System Supporting User Defined Database Operations. DASFAA 1989: 266-273
  23. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
  24. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
  25. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
  26. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
  27. Mark Blakey: Basis of a Partially Informed Distributed Database. VLDB 1987: 381-388
  28. Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180
  29. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
  30. Bezalel Gavish, Arie Segev: Set Query Optimization in Distributed Database Systems. ACM Trans. Database Syst. 11(3): 265-293(1986)
  31. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
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:54:44 2009