1. We will need to compute all the multivalued dependencies that are logically implied by a given set of multivalued dependencies.
- Let D denote a set of functional and multivalued dependencies.
- The closure D+ of D is the set of all functional and multivalued dependencies logically implied by D.
- We can compute D+ from D using the formal definitions, but it is easier to use a set of inference rules.
2. The following set of inference rules is sound and complete. The rst three rules are Armstrong's axioms from Chapter 5.
(a) Reexivity rule: if is a set of attributes and β ∈α , then α→ β holds.
(b) Augmentation rule: if α→ β holds, and γis a set of attributes, then γα→ γβholds.
(c) Transitivity rule: if α→ β holds, and β→ γ holds, then α→ γ holds.
(d) Complementation rule: if α→→ β holds, then α→→ R- α- βholds.
(e) Multivalued augmentation rule: if α→→ β holds, and γ ∈ R and δ ∈ γ , then γα→→ δβ holds.
(f) Multivalued transitivity rule: if α→→ β holds, and β→→ γ holds, then α→→ γ- β holds.
(g) Replication rule: if α→ β holds, then α→→ β.
(h) Coalescence rule: if α→→ β holds, and γ ∈ β , and there is a γ such that γ∈ R and γ ∩ β= Ф, and δ→ γ, then α→ γ holds.
3. An example of multivalued transitivity rule is as follows. loan# →→ cname and cname →→ {cname, caddress}.
Thus we have loan# →→ caddress, where caddress = {cname, caddress}-cname.
An example of coalescence rule is as follows. If we have student name →→ {bank, account}, and student_id → bank,
then we have student name → bank.
4. Let's do an example:
- Let R = (A,B,C, G,H, I) be a relation schema.
- Suppose A →→BC holds.
- The de nition of multivalued dependencies implies that if t1[A] = t2[A], then there exists tuples t3 and t4 such that:
t1[A] = t2[A] = t3[A] = t4[A]
t3[BC] = t1[BC]
t3[GHI] = t2[GHI]
t4[GHI] = t1[GHI]
t4[BC] = t2[BC]
- The complementation rule states that if A →→ BC then A →→ GHI.
- Tuples t3 and t4 satisfy A →→ GHI if we simply change the subscripts.
5. We can simplify calculating D+, the closure of D by using the following rules, derivable from the previous ones:
- Multivalued union rule: if α→→ β holds and α→→ γ holds, then α→→ βγ holds.
- Intersection rule: if α→→ β holds and α→→ γ holds, then α→→ β∩ γ holds.
- Difference rule: if α→→ β holds and α→→ γ holds, then α→→ β- γholds then α→→ γ- βholds.
6. An example will help:
Let R = (A,B,C, G,H, I) with the set of dependencies:
A →→ B
B →→ HI
CG→H
We list some members of D+:
- A →→ CGHI: since A →→ B, complementation rule implies that A →→ R-B-A, and R-B-A = CGHI.
- A →→HI: Since A →→ B and B →→ HI, multivalued transitivity rule implies that A →→ HI-B.
- B → H: coalescence rule can be applied. B →→ HI holds, H ∈ HI and CG→→H and CG ∩ HI = Ф ,
so we can satisfy the coalescence rule with being B, being HI, being CG, and being H. We conclude that B → H.
- A →→ CG: now we know that A →→CGHI and A →→ HI. By the difference rule, A →→ CGHI - HI = CG.