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 b X4 = 8, 6 (final value: 6) X5 = 7 c. Up to the second START CKPT