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

On the Design of a Query Processing Strategy in a Distributed Database Environment.

Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
@inproceedings{DBLP:conf/sigmod/YuC83,
  author    = {Clement T. Yu and
               C. C. Chang},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {On the Design of a Query Processing Strategy in a Distributed
               Database Environment},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {30-39},
  ee        = {http://doi.acm.org/10.1145/582192.582203, db/conf/sigmod/YuC83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

An algorithm is given to process a given query in a fragmented distributed data base environment. Unlike previoue algorithms, it has the following desired features.
  1. It makes use of redundant relations to reduce comunlcation cost;
  2. a copy of each relation referenced by the query is selected so that the set of relations are contained in the minimum number of sites;
  3. an efficient algorithm to process fragments is provided;
  4. all relations that need not be sent to the assembly site to produce the answer are identified. Thus, unnecessary sending of these relations across sites and processing on these relations, which are common in earlier algorithms, are avoided;
  5. useless semi-joins are discarded and "worse" semi-joins are replaced by better ones;
  6. a process to estimate the cost and the benefit of a semi-join, based on dynamic execution of semi-joins is introduced. It is expected that the new process is more accurate than earlier estimation process.
The algorithm is easy to implement and is operational.

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

David J. DeWitt, Georges Gardarin (Eds.): SIGMOD'83, Proceedings of Annual Meeting, San Jose, California, May 23-26, 1983. ACM Press 1983 BibTeX , SIGMOD Record 13(4)
Contents

Online Edition: ACM Digital Library


References

[AHU]
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
[BFMM]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 BibTeX
[BeCh]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BeGo]
...
[BlLu]
...
[Chan1]
Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61 BibTeX
[Chan2]
...
[Chiu]
...
[ChHo]
D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX
[Codd]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Date]
...
[FaMU]
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
[GoSh]
Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 BibTeX
[Grah]
...
[HeYa]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[Hevn]
...
[KeYa]
...
[Luk1]
...
[Luk2]
...
[SDD1V1]
...
[SDD1V2]
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
[WDHL]
...
[Wong]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[Yao]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[YuOz]
...
[YuLO]
...
[YLCC]
Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390 BibTeX
[YuCC]
...

Referenced by

  1. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  2. Ophir Frieder, Chaitanya K. Baru: Site and Query Scheduling Policies in Multicomputer Database Systems. IEEE Trans. Knowl. Data Eng. 6(4): 609-619(1994)
  3. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
  4. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
  5. H. M. Gladney: Data Replicas in Distributed Information Services. ACM Trans. Database Syst. 14(1): 75-97(1989)
  6. Danièle Gardy, Claude Puech: On the Effects of Join Operations on Relation Sizes. ACM Trans. Database Syst. 14(4): 574-603(1989)
  7. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  8. Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366
  9. David A. Bell, D. H. O. Ling, Sally I. McClean: Pragmatic Estimation of Join Sizes and Attribute Correlations. ICDE 1989: 76-84
  10. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
  11. Ravi Mukkamala, Steven C. Bruell, Roger K. Shultz: A Heuristic Algorithm for Determining a Near-optimal Set of Nodes to Access in a Partially Replicated Distributed Database System. ICDE 1988: 330-336
  12. Hyunchul Kang, Nick Roussopoulos: Using 2-way Semijoins in Distributed Query Processing. ICDE 1987: 644-651
  13. Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
  14. Bezalel Gavish, Arie Segev: Set Query Optimization in Distributed Database Systems. ACM Trans. Database Syst. 11(3): 265-293(1986)
  15. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
  16. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95
  17. Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119
  18. 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
  19. Marjorie Templeton, David Brill, Arbee L. P. Chen, Son Dao, Eric Lund: Mermaid - Experiences with Network Operation. ICDE 1986: 292-300
  20. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
  21. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
  22. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  23. Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415
  24. Arbee L. P. Chen, Victor O. K. Li: Optimizing Star Queries in a Distributed Database System. VLDB 1984: 429-438
  25. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
  26. David Brill, Marjorie Templeton, Clement T. Yu: Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems. ICDE 1984: 211-218
  27. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
  28. Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: Supporting a Semantic Data Model in a Distributed Database System. VLDB 1983: 354-363
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:33 2009