zbMATH — the first resource for mathematics

Parallel processing for the full reduction of a chain query in distributed databases. (English) Zbl 0780.68028
Summary: The paper extends the results of P. A. Bernstein and N. Goodman [SIAM J. Comput. 10, No. 4, 751-771 (1981; Zbl 0469.68090)], P. A. Bernstein and D. W. Chiu [J. Assoc. Comput Mach. 28. No. 1, 25-40 (1981; Zbl 0454.68126)] and 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.
68P15 Database theory
68W15 Distributed algorithms
Full Text: DOI