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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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)
[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)
[3]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)
[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)
[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)
[11]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)
[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)
[13]: Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101
[14]: ...
[15]: ...
[16]: Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979)
[17]: ...
[18]: W. S. Luk, Lydia Luk: Optimizing Semi-Join Programs for Distributed Query Processing. ICOD 1983: 298-316
[19]: ...
[20]: Clement T. Yu, K. Lam, C. C. Chang, S. K. Chang: Promising Approach to Distributed Query Processing. Berkeley Workshop 1982: 363-390
[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