ACM SIGMOD Anthology TODS dblp.uni-trier.de

Optimization of Join Operations in Horizontally Partitioned Database Systems.

Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
@article{DBLP:journals/tods/Segev86,
  author    = {Arie Segev},
  title     = {Optimization of Join Operations in Horizontally Partitioned Database
               Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {11},
  number    = {1},
  year      = {1986},
  pages     = {48-80},
  ee        = {http://doi.acm.org/10.1145/5236.5241, db/journals/tods/Segev86.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper analyzes the problem of joining two horizontally partitioned relations in a distributed database system. Two types of semijoin strategies are introduced, local and remote. Local semijoins are performed at the site of the restricted relation (or fragment), and remote semijoins can be performed at an arbitrary site. A mathematical model of a semijoin strategy for the case of remote semijoins is developed, and lower bounding and heuristic procedures are proposed. The results of computational experiments are reported. The experiments include an analysis of the heuristics' performance relative to the lower bounds, sensitivity analysis, and error analysis. These results reveal a good performance of the heuristic procedures, and demonstrate the benefit of using semijoin operations to reduce the size of fragments prior to their transmission. The algorithms for the case of remote semijoins were found to be superior to the algorithms for the case of local semijoins. In addition, we found that the estimation accuracy of the selectivity factors has a significant effect on the incurred communication cost.

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]
...
[2]
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
[3]
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
[4]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[5]
Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61 BibTeX
[6]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[7]
...
[8]
...
[9]
Dean Daniels, Patricia G. Selinger, Laura M. Haas, Bruce G. Lindsay, C. Mohan, Adrian Walker, Paul F. Wilms: An Introduction to Distributed Query Compilation in R*. DDB 1982: 291-309 BibTeX
[10]
C. J. Date: An Introduction to Database Systems, 3rd Edition. Addison-Wesley 1981
BibTeX
[11]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
[12]
...
[13]
...
[14]
...
[15]
...
[16]
...
[17]
...
[18]
...
[19]
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
[20]
...
[21]
...
[22]
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
[23]
Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
BibTeX
[24]
...
[25]
...
[26]
Richard Peebles, Eric G. Manning: A Computer Architecture for Large (Distributed) Data Bases. VLDB 1975: 405-427 BibTeX
[27]
...
[28]
...
[29]
...
[30]
...
[31]
...
[32]
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX
[33]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX
[34]
...
[35]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[36]
Eugene Wong: Retrieving Dispersed Data from SDD-1: A System for Distributed Databases. Berkeley Workshop 1977: 217-235 BibTeX
[37]
Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39 BibTeX

Referenced by

  1. Chengwen Liu, Hao Chen, Warren Krueger: A Distributed Query Processing Strategy Using Placement Dependency. ICDE 1996: 477-484
  2. Zhe Li, Kenneth A. Ross: PERF Join: An Alternative to Two-way Semijoin and Bloomjoin. CIKM 1995: 137-144
  3. Won S. Lee, Phillip C.-Y. Sheu: An Object-Oriented Query Evaluation Scheme for Logical Databases in Massively Parallel Environment. IEEE Trans. Knowl. Data Eng. 6(1): 181-187(1994)
  4. 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)
  5. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  6. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  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. Fang Li, Lawrence V. Saxton: Two-Way Join Optimization in Partitioned Database Systems. ICDT 1988: 191-204
  9. Bezalel Gavish, Arie Segev: Set Query Optimization in Distributed Database Systems. ACM Trans. Database Syst. 11(3): 265-293(1986)
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