State all assumptions.

Problem 1. (20 points)

(a)

What is the difference between the SELECT operator in relational algebra and the SELECT keyword in SQL? Do they effectively do the same thing? If not, what is the difference?

(b)

Assume that R(A,B) and S(B,C) are relations. Convert the generalized relational algebra expression below to a corresponding SQL statement:

PROJECT (attribute-list) [ SELECT (condition) [ R NATJOIN S ] ]

Problem 2. (30 points)

(a)  SELECT(P and Q and M)[ R NATJOIN S ]

(b)  SELECT(P or Q)[ R NATJOIN S ]

(c)  PROJECT(E)[ [SELECT(P and Q and M) [R NATJOIN S] ] NATJOIN T ]

where R(A,B,C), S(C,D), and T(D,E,F) are relations,
P is a predicate over D, 
Q is a predicate over B, 
and M is a predicate over C.

Problem 3. (50 points)

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 indexes:

• 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 indexes 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.
• n_R= 750,000 (number of tuples of R)

• 100 tuples of S are stored per block on disk.
• n_S= 250,000 (number of tuples of S)
• V(B,S)= 50,000 (image size of attribute B in S)
• V(C,S)= 50 (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)

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

(a)

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.

(b)

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

(c)

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