1. a. i. NO ii. YES b. i. empty set ii. A->B->C->D->A iii. doesn't exists, since {A,B} intersect {B,C} must also be closed iv. AB->BC, BC->AD, CD->AB, AC->BD, BD->AC, AD->BC v. A->B, B->A, C->A, D->A c. Use B+ = BD, split: ABCD ==> BD + BAC Use C+ = AC, split: BAC ==> AC + BC Final split: ABCD ==> AC + BC + BD d. yes, no, no, no, yes 2. a. SELECT DISTINCT y.cid FROM Claim x, Policy u, Policy v, Claim y WHERE x.pid = u.pid and u.property=v.property and u.year=v.year and y.pid = v.pid b. SELECT u.pid, x.year FROM Claim x, Policy u WHERE x.pid = u.pid GROUP BY u.pid, u.premium, x.year HAVING sum(x.amount) > u.premium c. i. B ii. C iii. B iv. A 3. a. /university/college/department[name/text()="Computer Science"]/student b. let $u := document("file.xml")/university $s := distinct-values($u/college/department/student/text()) for $x in $s return { $x } { count($u/college[department/student/text()=$x]) } c. College(name(key), dean) Department(name(key), collegeName(foreignkey), chair) Student(name(key)) Member(studentName(foreignkey), departmentName(foreignkey)) 4. a. P2, P3. Cannot use a join index for P1 because the index is lost after selection. b. P3 only: use an index scan on R.C and an index scan on S.D c. P1 because it joins smaller tables. d. i. NO: the index join is terrible here ii. YES: the index join makes a single index lookup e. gamma[F, sum(V)](gamma[C, sum(V)](sigma(R)) Join sigma(S)) The inner gamma has only 100 buckets, hence can be done in main memory. The join has a left operand that fits in main memory, and can be done as a nested loop join, then the results piped into the outer gamma operator. This can be implemented as a nested loop too, by reusing the buckets of the first gamma operator. 5. a. exists m. P(pid, m) and C(m, Seattle) b. exists m. exists c. P(pid, m) and C(m, c) and existst oid. OI(oid, pid) and O(oid, c) c. exists m. exists c. P(pid, m) and C(m, c) and forall oid. OI(oid, pid) ==> O(oid, c) d. exists c. C(m,c) and forall pid. (P(pid, m) ==> forall oid. OI(oid, pid) ==> O(pid, c))