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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
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
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]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:32 2009