ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Optimizing Star Queries in a Distributed Database System.

Arbee L. P. Chen, Victor O. K. Li: Optimizing Star Queries in a Distributed Database System. VLDB 1984: 429-438
@inproceedings{DBLP:conf/vldb/ChenL84,
  author    = {Arbee L. P. Chen and
               Victor O. K. Li},
  editor    = {Umeshwar Dayal and
               Gunter Schlageter and
               Lim Huat Seng},
  title     = {Optimizing Star Queries in a Distributed Database System},
  booktitle = {Tenth International Conference on Very Large Data Bases, August
               27-31, 1984, Singapore, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1984},
  isbn      = {0-934613-16-8},
  pages     = {429-438},
  ee        = {db/conf/vldb/ChenL84.html},
  crossref  = {DBLP:conf/vldb/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. In an earlier paper, we described an approach to obtain the optimal semi-join program for a star query by gradually reducing the search space to a minimal set S without making any assumptions on the file sizes and the semi-join selectivities. In this paper, by making certain assumptions on the file sizes and the semi-join selectivities, the size of S can be reduced to unity, i.e, given a star query, we can directly generate the optimal program. Our assumption on selectivitres is consistent in the sense that we consider the selectivity of a semi-join based on the current database state, i.e., we take into consideration the reduction effects of all prior semi-joins. We have also included an example which compares the performance of existing heuristic algorithms with our proposed optimal algorithm.

Copyright © 1984 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Gunter Schlageter, Lim Huat Seng (Eds.): Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings. Morgan Kaufmann 1984, ISBN 0-934613-16-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
...
[7]
...
[8]
To-Yat Cheung: A Method for Equijoin Queries in Distributed Relational Databases. IEEE Trans. Computers 31(8): 746-751(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
...
[16]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
W. S. Luk, Lydia Luk: Optimizing Semi-Join Programs for Distributed Query Processing. ICOD 1983: 298-316 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:58 2010 by Michael Ley (ley@uni-trier.de)