Expected Size of the Natural Join

Author:Yang, Donlin, Department of Computer ScienceUniversity of Virginia

The primary cost in processing relational database queries is the cost of joining two or more relations. In order to develop more efficient join algorithms or to optimize query strategies at run time. we must be able to accurately compute the expected size of a join relation. In [6], Rosenthal derives the expected join size formula in terms of the sizes of the join domain and source relations. However. his proof process requires two stringent conditions. First, the distributions of the join attribute values in source relations must be independent and second. at least one of the distributions must be uniform. In this paper, We show that Rosenthal's expression is still valid under much more general conditions through the use of an exact join size formula.
Note: Abstract extracted from PDF file via OCR

All rights reserved (no additional license for public reuse)
Source Citation:

Yang, Donlin. "Expected Size of the Natural Join." University of Virginia Dept. of Computer Science Tech Report (1985).

University of Virginia, Department of Computer Science
Published Date: