CSE444 Final
			       Answers
			    December, 2001


1.
a.

CREATE TABLE Property (
   name CHAR(10) PRIMARY KEY,
   city VARCHAR(30)
);

CREATE TABLE Policy (
   pid CHAR(10) PRIMARY KEY,
   premium INT,
   startyear INT,
   endyear INT,
   preimium INT,
   covers CHAR(10) REFERENCES Property(name)
);

CREATE TABLE Claim (
   cid CHAR(10) PRIMARY KEY,
   amount INT,
   year INT,
   for CHAR(10) REFERENCES Policy(pid)
);


b.

SELECT DISTINCT x1.cid
FROM Claim x1, Policy y1, Property p, Claim x2, Policy y2
WHERE x1.for = y1.pid AND y1.covers=p.name AND
      p.name = y2.covers AND y2.pid = x2.for AND
      x2.pid = "03492" AND x1.year = x2.year


c.

SELECT year, count(*), sum(amount)
FROM   Claim
GROUP BY year

d.

SELECT DISTINCT Policy.pid
FROM Policy, Claim
GROUP BY Policy.pid, Claim.year
HAVING sum(Claim.amount) > 10*Policy.premium



2.

a.  Let M be the memory size

    In step 1 we generate the max number of B-buckets, i.e. M (it
    never hurts to have more).

    In step 2 we need to store in memory one bucket from R (we favor R
    over S since R is smaller) and use the remaining memory (if any)
    to partition U into buckets on the C attribute.  The expected size
    of a bucket from R is: B(R)/M.  Hence the maximum number of
    C-buckets we can create during step 2, and, consequently, step 3 is:

             M - B(R)/M

    In step 4 we need to be able to hold a bucket from T in main
    memory (we favor T over U since T is smaller).  The expected size
    of a bucket from T is:

             B(T) /  (M - B(R)/M)

    This has to be < M.  We solve this inequation:


             B(T) /  (M - B(R)/M)  <=   M

             B(T)   <=   M*M  -  B(R)

	     B(R) + B(T)  <=  M*M

	     10000 + 30000  <= M*M

             40000 <= M*M

             200 <= M

    We need at least M = 200 for this plan to work.

b. 200

c. R: 50  and S: 100

d. 150

e   U:  266    T: 200


3. a

i yes

ii yes

iii no:

R     A | B | C
     -----------
      1 | 2 | 3

S     A | B | C
     -----------
      1 | 2 | 3
      1 | 4 | 5


iv yes

v no: take R as above and:

T     C | D
     ------
      3 | 4
      3 | 5


b

i. yes

ii. yes

iii. no: same counterexample as in a

iv. yes

v. yes

4.

Subquery	Size		Cost		Optimal plan
================================================================
RS		1k		0
----------------------------------------------------------------
RT		3k		0
----------------------------------------------------------------
RU		2k		0
----------------------------------------------------------------
ST		1.2k		0
----------------------------------------------------------------
SU		0.8k		0
----------------------------------------------------------------
TU		2.4k		0
----------------------------------------------------------------
RST		6k		1k		(RS)T
----------------------------------------------------------------
RSU		4k		0.8k		(SU)R
----------------------------------------------------------------
RTU		12k		2k		(RU)T
----------------------------------------------------------------
STU		4.8k		0.8k		(SU)T
----------------------------------------------------------------
RSTU		24k		2.2k		(RU)(ST)
----------------------------------------------------------------

5.

a

<START CKPT T1>
<START CKPT T2,T3>
<START CKPT T4,T5>

b

X4 = 8,  6   (final value: 6)
X5 = 7

c.  Up to the second START CKPT