ACM SIGMOD Anthology TODS dblp.uni-trier.de

A State Transition Model for Distributed Query Processing.

Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
@article{DBLP:journals/tods/LafortuneW86,
  author    = {St{\'e}phane Lafortune and
               Eugene Wong},
  title     = {A State Transition Model for Distributed Query Processing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {3},
  year      = {1986},
  pages     = {294-322},
  ee        = {http://doi.acm.org/10.1145/6314.6460, db/journals/tods/LafortuneW86.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A state transition model for the optimization of query processing in a distributed database system is presented. The problem is parametrized by means of a state describing the amount of processing that has been performed at each site where the database is located. A state transition occurs each time a new join or semijoin is executed. Dynamic programming is used to compute recursively the costs of the states and the globally optimal solution, taking into account communication and local processing costs. The state transition model is general enough to account for the possibility of parallel processing among the various sites, as well as for redundancy in the database. The model also permits significant reductions of the necessary computations by taking advantage of simple additivity and site-uniformity properties of a cost model, and of clever strategies that improve on the basic dynamic programming algorithm.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
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
[2]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[3]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[4]
Philip A. Bernstein, Nathan Goodman: The power of inequality semijoins. Inf. Syst. 6(4): 255-265(1981) BibTeX
[5]
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
[6]
...
[7]
Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304 BibTeX
[8]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[9]
Arbee L. P. Chen, Victor O. K. Li: Optimizing Star Queries in a Distributed Database System. VLDB 1984: 429-438 BibTeX
[10]
Dah-Ming W. Chiu, Philip A. Bernstein, Yu-Chi Ho: Optimizing Chain Queries in a Distributed Database System. SIAM J. Comput. 13(1): 116-134(1984) BibTeX
[11]
D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX
[12]
Wesley W. Chu, Paul Hurley: Optimal Query Processing for Distributed Database Systems. IEEE Trans. Computers 31(9): 835-850(1982) BibTeX
[13]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
[14]
Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982) BibTeX
[15]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[16]
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX
[17]
...
[18]
...
[19]
...
[20]
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX
[21]
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
[22]
Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX
[23]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[24]
Eugene Wong: Dynamic Rematerialization: Processing Distributed Queries Using Redundant Data. IEEE Trans. Software Eng. 9(3): 228-232(1983) BibTeX
[25]
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX
[26]
...
[27]
Clement T. Yu, Z. Meral Özsoyoglu, K. Lam: Optimization of Distributed Tree Queries. J. Comput. Syst. Sci. 29(3): 409-445(1984) 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. Gautam Bhargava, Piyush Goel, Balakrishna R. Iyer: Hypergraph Based Reorderings of Outer Join Queries with Complex Predicates. SIGMOD Conference 1995: 304-315
  3. 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)
  4. Chung-Min Chen, Nick Roussopoulos: The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching. EDBT 1994: 323-336
  5. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  6. P. E. Drenick, E. J. Smith: Stochastic Query Optimization in Distributed Databases. ACM Trans. Database Syst. 18(2): 262-288(1993)
  7. Jörg Liebeherr, Edward Omiecinski, Ian F. Akyildiz: The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 510-522(1993)
  8. 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)
  9. Arun N. Swami, Balakrishna R. Iyer: A Polynomial Time Algorithm for Optimizing Join Queries. ICDE 1993: 345-354
  10. Peter Bodorik, J. Spruce Riordon, James S. Pyra: Deciding on Correct Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 4(3): 253-265(1992)
  11. Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58
  12. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
  13. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:59 2008