A pipeline N-way join algorithm based on the 2-way semijoin program

TitleA pipeline N-way join algorithm based on the 2-way semijoin program
Publication TypeJournal Articles
Year of Publication1991
AuthorsRoussopoulos N, Kang H
JournalIEEE Transactions on Knowledge and Data Engineering
Pagination486 - 495
Date Published1991/12//
ISBN Number1041-4347
Keywords2-way semijoin program, backward size reduction, Bandwidth, Computer networks, Costs, Data communication, data transmission, Database systems, database theory, Delay, distributed databases, distributed query, forward size reduction, intermediate results, Local area networks, network, Parallel algorithms, pipeline N-way join algorithm, pipeline processing, Pipelines, programming theory, Query processing, Relational databases, relational operator, SITES, Workstations

The semijoin has been used as an effective operator in reducing data transmission and processing over a network that allows forward size reduction of relations and intermediate results generated during the processing of a distributed query. The authors propose a relational operator, two-way semijoin, which enhanced the semijoin with backward size reduction capability for more cost-effective query processing. A pipeline N-way join algorithm for joining the reduced relations residing on N sites is introduced. The main advantage of this algorithm is that it eliminates the need for transferring and storing intermediate results among the sites. A set of experiments showing that the proposed algorithm outperforms all known conventional join algorithms that generate intermediate results is included