CS245  Winter 2000

Assignment 5
due in class on Thursday February 10


PROBLEM 1

Do Problem 6.1.4 from textbook.

PROBLEM 2

Do Problem 6.1.6 part (a) and (b) only, from textbook.

PROBLEM 3

Do Problem 7.2.6 part (b) from textbook.

PROBLEM 4

Do Problem 7.4.1 parts (c), (d), (f), (h) from textbook.

PROBLEM 5

Suppose you have 2 relations, R(A, B, C) and S(B, C, D, E).

You have a clustered unique (no duplicate keys) B+-tree index on
attribute A for relation R.
Assume this index is kept entirely in memory (i.e., you do not need
to read it from disk).

For relation S, you have two indices:
* a non-clustered non-unique B+-tree index for attribute B
* a clustered non-unique B+-tree index for attribute C

Furthermore, assume that these two indices are kept in memory (i.e. you
do not need to read them from disk). Also, assume that all of the tuples
of S that agree on attribute C are stored in sequentially adjacent blocks
on disk (that is, if more than one block is needed to store all of the tuples
with some value of C, then these blocks will be sequentially located on
the disk).

Other relevant data:
* 500 tuples of R are stored per block on disk.
* T(R) = 500,000 (number of tuples of R)

* 100 tuples of S are stored per block on disk.
* T(S) = 100,000 (number of tuples of S)
* V(S,B)= 40,000 (image size of attribute B in S)
* V(S,C)= 40 (image size of attribute C in S)

You want to execute the following query:

SELECT *
FROM R, S
WHERE (R.B=S.B) AND (R.C=S.C)

We present you with two query plans:

Plan 1:

For every block B of R, retrieved using the clustered index on A for R
    For every tuple r of B
         Use the index on B for S to retrieve all
             of the tuples s of S such that s.B=r.B
             For each of these tuples s, if s.C=r.C, output r.A, r.B, r.C,
                                                            s.B, s.C, s.D, s.E


Plan 2:

For every block B of R, retrieved using the clustered index on A for R
    For every tuple r of B
         Use the index on C for S to retrieve all
             of the tuples s of S such that s.C=r.C
             For each of these tuples s, if s.B=r.B, output r.A, r.B, r.C,
                                                            s.B, s.C, s.D, s.E

You should analyze each of these plans carefully in terms of
their behavior regarding accesses to disk.  Your analysis should consider
the behavior both in terms of the number of I/Os, as well as the total
access time.  Explain which of the plans is therefore better under what
circumstances.  Be sure to include in your analysis what accesses to 
disk are sequential accesses and which ones are random accesses.

* Now consider what happens if instead V(S,C) = 500.  Will one plan perform 
better than the other?

* Instead of using the V-function to do your estimate, assume that the
number of tuples  returned is proportional to the size of the domain
of an attribute.  Let DOM(S,B) = 1000, and DOM(S,C) = 100.  Re-calculate
your estimates.

END OF HOMEWORK 5