Semi-Join Algorithms for Multiprocessor Systems.

Patrick Valduriez: Semi-Join Algorithms for Multiprocessor Systems. SIGMOD Conference 1982: 225-233

@inproceedings{DBLP:conf/sigmod/Valduriez82,
  author    = {Patrick Valduriez},
  editor    = {Mario Schkolnick},
  title     = {Semi-Join Algorithms for Multiprocessor Systems},
  booktitle = {Proceedings of the 1982 ACM SIGMOD International Conference on
               Management of Data, Orlando, Florida, June 2-4, 1982},
  publisher = {ACM Press},
  year      = {1982},
  pages     = {225-233},
  ee        = {http://doi.acm.org/10.1145/582353.582396, db/conf/sigmod/Valduriez82.html},
  crossref  = {DBLP:conf/sigmod/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Semi-join is a relational operator that decreases the cost of processing queries involving binary operations. This is accomplished by initially selecting the data relevant to answer the queries and thereby reducing the size of the operand relations. This paper presents and analyzes algorithms for computing semi-joins in a multiprocessor database machine. First, an architecture model of a multiprocessor system is described, The model incorporates I-O, CPU and messages transmission cost parameters to enable the evaluation of these algorithms in terms of their execution costs. Then two equi-semi-join algorithms are presented and compared and one inequi-semi-join algorithm is proposed. The execution cost of these algorithms are generally lineary proportional to the size of the operand and result relations and inversely proportional to the number of processors. Then, the method by joining two relations and the method by joining their semi-joins are compared. Finally it is shown that the method using semi-joins is generally better.

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

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 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

BibTeX

Printed Edition

Mario Schkolnick (Ed.): Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, Orlando, Florida, June 2-4, 1982. ACM Press 1982 BibTeX
Contents

Online Edition: ACM Digital Library

References

[BERN79a]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BERN79b]: ...
[BERN79c]: ...
[BABB79]: Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[BORA80]: ...
[BORA81]: Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Performance evaluation of four assiciative disk designs. Inf. Syst. 7(1): 53-64(1982) BibTeX
[CHIU80]: D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178 BibTeX
[DEWI79]: David J. DeWitt: Query Execution in DIRECT. SIGMOD Conference 1979: 13-22 BibTeX
[FAUD80]: ...
[GARD81]: ...
[LEBI80]: Jean Le Bihan, Christian Esculier, Gérard Le Lann, Witold Litwin, Georges Gardarin, S. Sedillort, L. Treille: SIRIUS: A French Nationwide Project on Distributed Data Bases. VLDB 1980: 75-85 BibTeX
[OZKA77]: Esen A. Ozkarahan, Stewart A. Schuster, Kenneth C. Sevcik: Performance Evaluation of a Relational Associative Processor. ACM Trans. Database Syst. 2(2): 175-195(1977) BibTeX
[ROTH80]: James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, Terry A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[VALD81a]: ...
[VALD81b]: Patrick Valduriez, Georges Gardarin: Multiprocessor Join Algorithms of Relations. JCDKB 1982: 219-236 BibTeX

Referenced by

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
Tinghe Fei, Chaitanya K. Baru, Stanley Y. W. Su: SM3: A Dynamically Partitionable Multicomputer System with Switchable Main Memory Modules. ICDE 1984: 42-49
Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]