Parallel processing for the full reduction of a chain query in distributed databases

A semijoin is a relational operator which reduces a relation by selecting a set of tuples that match one or more tuples of another relation in the joining domains. Most of the queries can be evaluated by using semijoins. For the class of tree queries, there exists sequences of semijoins that "fully reduce" the database. Those sequences delimit the exact portions of the database needed to answer the query. Such sequences are called full reducers. This paper extends the results of Bernstein and Goodman [P. A. Bernstein and N. Goodman. SIAM J. Comput. 10(4), 751-771 (1981)], Bernstein and Chiu [P. A. Bernstein and D. W. Chiu, J. ACM 28(1), 25-40 (1981)] and Ullman [J. D. Ullman. Principles of Relational Databases (1988)], by constructing a parallel algorithm for a subset of tree queries, called chain queries. An efficient parallel algorithm for the construction of full reducers for chain queries is presented and analyzed. We claim that the full reduction of a chain query can be done in parallel by executing only 2n - 2 semijoins in the time required for an n - 1 semijoins evaluation using 4 processors