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))