%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "morishita1997.ltx",
%%%     date      = "28 March 1997",
%%%     time      = "15:15:52 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "60750 119 518 4307",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{Morishita1997}

\title{Avoiding {Cartesian} Products for Multiple Joins}

\author{Shinichi Morishita}

\Pages{57--85}

\Month{January}

\Year{1997}

\Volume{44}

\Number{1}

\maketitle

\begin{abstract}

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 \emph{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.

\end{abstract}

\begin{categories}

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

\end{categories}

\begin{terms}

Algorithms, Database Theory, Languages

\end{terms}

\begin{keywords}

Cartesian product, database scheme, join expression tree, join strategy,
  optimality, semijoin

\end{keywords}

\end{document}
