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.
- It makes use of redundant relations to
reduce comunlcation cost;
- 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;
- an efficient algorithm to process fragments is provided;
- 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;
- useless semi-joins are discarded and
"worse" semi-joins are replaced by better ones;
- 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.
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
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
- Wei Sun, Clement T. Yu:
Semantic Query Optimization for Tree and Chain Queries.
IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
- Ophir Frieder, Chaitanya K. Baru:
Site and Query Scheduling Policies in Multicomputer Database Systems.
IEEE Trans. Knowl. Data Eng. 6(4): 609-619(1994)
- Peter Scheuermann, Eugene Inseok Chong:
Role-based Query Processing in Multidatabase Systems.
EDBT 1994: 95-108
- Arbee L. P. Chen:
A Localized Approach to Distributed Query Processing.
EDBT 1990: 188-202
- H. M. Gladney:
Data Replicas in Distributed Information Services.
ACM Trans. Database Syst. 14(1): 75-97(1989)
- Danièle Gardy, Claude Puech:
On the Effects of Join Operations on Relation Sizes.
ACM Trans. Database Syst. 14(4): 574-603(1989)
- Hyuck Yoo, Stéphane Lafortune:
An Intelligent Search Method for Query Optimization by Semijoins.
IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
- Goetz Graefe, Karen Ward:
Dynamic Query Evaluation Plans.
SIGMOD Conference 1989: 358-366
- David A. Bell, D. H. O. Ling, Sally I. McClean:
Pragmatic Estimation of Join Sizes and Attribute Correlations.
ICDE 1989: 76-84
- Fang Li, Lawrence V. Saxton:
Two-Way Join Optimization in Partitioned Database Systems.
ICDT 1988: 191-204
- 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
- Hyunchul Kang, Nick Roussopoulos:
Using 2-way Semijoins in Distributed Query Processing.
ICDE 1987: 644-651
- Arie Segev:
Optimization of Join Operations in Horizontally Partitioned Database Systems.
ACM Trans. Database Syst. 11(1): 48-80(1986)
- Bezalel Gavish, Arie Segev:
Set Query Optimization in Distributed Database Systems.
ACM Trans. Database Syst. 11(3): 265-293(1986)
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Distributed Queries.
VLDB 1986: 149-159
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Local Queries.
SIGMOD Conference 1986: 84-95
- Michael J. Carey, Hongjun Lu:
Load Balancing in a Locally Distributed Database System.
SIGMOD Conference 1986: 108-119
- 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
- Marjorie Templeton, David Brill, Arbee L. P. Chen, Son Dao, Eric Lund:
Mermaid - Experiences with Network Operation.
ICDE 1986: 292-300
- Clement T. Yu, C. H. Chen:
Adaptive Information System Design: One Query at a Time.
SIGMOD Conference 1985: 280-290
- Clement T. Yu, C. C. Chang:
Distributed Query Processing.
ACM Comput. Surv. 16(4): 399-433(1984)
- Matthias Jarke, Jürgen Koch:
Query Optimization in Database Systems.
ACM Comput. Surv. 16(2): 111-152(1984)
- 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
- Arbee L. P. Chen, Victor O. K. Li:
Optimizing Star Queries in a Distributed Database System.
VLDB 1984: 429-438
- Giovanni Maria Sacco:
Distributed Query Evaluation in Local Area Networks.
ICDE 1984: 510-516
- David Brill, Marjorie Templeton, Clement T. Yu:
Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems.
ICDE 1984: 211-218
- Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen:
File Allocation in Distributed Databases with Interaction between Files.
VLDB 1983: 248-259
- 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