Develop cost functions for the PROJECT, UNION, INTERSECTION, SET DIFFERENCE, and CARTESIAN PRODUCT algorithms discussed in section 19.4.

Question

What will be an ideal response?

Answer 1

Assume relations R and S are stored in b R and b S disk blocks, respectively. Also, assume
that the file resulting from the operation is stored in b RESULT disk blocks (if the size
cannot be otherwise determined).
PROJECT operation: if includes a key of R, then the cost is 2*b R since the
read–in and write–out files have the same size, which is the size of R itself; if list> does not include a key of R, then we must sort the intermediate result file before
eliminating duplicates, which costs another scan; thus the latter cost is 3*b R +
k*b R *log 2 b R (assuming PROJECT is implemented by sort and eliminate duplicates).
SET OPERATIONS (UNION, DIFFERENCE, INTERSECTION): According to the algorithms
where the usual sort and scan/merge of each table is done, the cost of any of these is:
k*[(b R *log 2 b R ) + (b S *log 2 b S )] + b R + b S + b RESULT
CARTESIAN PRODUCT: The join selectivity of Cartesian product is js = 1, and the typical
way of doing it is the nested loop method, since there are no conditions to match. We first
assume two memory buffers; the other quantities are as discussed for the JOIN analysis
in Section 18.2.3. We get:
J1: C R X S = b R + (b R *b S ) + (|R|*|S|)/bfr RS
Next, suppose we have n B memory buffers, as in Section 16.1.2. Assume file R is
smaller and is used in the outer loop. We get:
J1': C R X S = b R + ceiling(b R /(n B - 1)) * b S )+ (|R|*|S|)/bfr RS , which is better than
J1, per its middle term.