Journal of the ACM Bibliography

Shinichi Morishita. Avoiding Cartesian products for multiple joins. Journal of the ACM, 44(1):57-85, January 1997. [BibTeX entry]

Computing the natural join of a set of relations is an important operational in relational database systems. The ordering of joins determines to a large extent the computation time of the join. Since the number of possible orderings could be very large, query optimizers first reduce the search space by using various heuristics and then try to select an optimal ordering of joins. Avoiding Cartesian products is a common heuristic for reducing the search space, but it cannot guarantee optimal ordering in its search space, because the cheapest Cartesian-product-free (CPF, for short) ordering could be significantly worse than an optimal non-CPF ordering by a factor of an arbitrarily large number. In this paper, we use programs consisting of joins, semijoins, and projections for computing the join of some relations, and we introduce a novel algorithm that derives programs from CPF orderings of joins. We show that there exists a CPF ordering from which our algorithm derives a program whose cost is within a constant factor of the cost of an optimal ordering. Thus, our result demonstrates the effectiveness of avoiding Cartesian products as a heuristic for restricting the search space of orderings of joins.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in: Shinichi Morishita. Avoiding cartesian products in programs for multiple joins. In Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 368-379, San Diego, California, 2-4 June 1992.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sequencing and scheduling; H.2.4 [Database Management]: Systems -- query processing; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search -- plan execution, formation generation

General Terms: Algorithms, Database Theory, Languages

Additional Key Words and Phrases: Cartesian product, database scheme, join expression tree, join strategy, optimality, semijoin

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database