Appendix B Advanced Relational Database Design 2.Augmentation rule.If aB holds,and y is a set of attributes,then ya→yβholds. 3.Transitivity rule.Ifa→B holds,.andB→y holds,then o→y holds. 4.Complementation rule..Ifa→→B holds.,then a→yR-B-a holds.. 5.Multivalued augmentation rule..Ifa→B holds,andy≤RandδsY, then yo→8B holds. 6.Multivalued transitivity rule.fa→→B holds,andB→→y holds,then a→→y-B holds. 7.Replication rule.Ifa→B holds,.then a→→B. &.Coalescence rule.Ifa→B holds,,and y B,and there is aδsuch thatδ sR,andδnB=i,andδ→Y,then a→y holds.. The bibliographical notes provide references to proofs that the preceding rules are sound and complete.The following examples provide insight into how the formal proofs proceed. Let R =(A,B,C,G,H,I)be a relation schema.Suppose that ABC holds.The definition of multivalued dependencies implies that,if h[A]=t2[A], then there exist tuples t3 and t4 such that [A]=2[A]=t[A=t4[A] t3[BC]=t[BC] tIGHI=GHI] t[GHI=t[GHI t4[BC]=[BC] The complementation rule states that,if A>BC,then A>GHI.Observe that f3 and t4 satisfy the definition of A>GHI if we simply change the subscripts. We can provide similar justification for rules 5 and 6(see Exercise B.2)using the definition of multivalued dependencies. Rule 7,the replication rule,involves functional and multivalued dependen- cies.Suppose that A-BC holds on R.If h[A]t2[A]and h[BC]t2[BC],then h and t2 themselves serve as the tuples t3 and t4 required by the definition of the multivalued dependency A→→BC. Rule 8,the coalescence rule,is the most difficult of the eight rules to verify (see Exercise B.4). We can simplify the computation of the closure of D by using the following rules,which we can prove using rules 1 to 8(see Exercise B.5): ·Multivalued union rule.fa→B holds,anda→→y holds,then a→→βy holds ·Intersection rule.fa→B holds,,anda→y holds,then o→→Bny holds.2 Appendix B Advanced Relational Database Design 2. Augmentation rule. If → holds, and  is a set of attributes, then  →  holds. 3. Transitivity rule. If → holds, and →  holds, then →  holds. 4. Complementation rule. If →→ holds, then →→ R − − holds. 5. Multivalued augmentation rule. If →→ holds, and  ⊆ R and  ⊆ , then  →→  holds. 6. Multivalued transitivity rule. If →→ holds, and →→  holds, then →→  − holds. 7. Replication rule. If → holds, then →→ . 8. Coalescence rule. If →→ holds, and  ⊆ , and there is a  such that  ⊆ R, and  ∩ = ∅, and  → , then →  holds. The bibliographical notes provide references to proofs that the preceding rules are sound and complete. The following examples provide insight into how the formal proofs proceed. Let R = (A, B,C, G, H, I) be a relation schema. Suppose that A →→ BC holds. The definition of multivalued dependencies implies that, if t1[A] = t2[A], then there exist 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. Observe that t3 and t4 satisfy the definition of A→→GHIif we simply change the subscripts. We can provide similar justification for rules 5 and 6 (see Exercise B.2) using the definition of multivalued dependencies. Rule 7, the replication rule, involves functional and multivalued dependen￾cies. Suppose that A → BC holds on R. If t1[A] = t2[A] and t1[BC] = t2[BC], then t1 and t2 themselves serve as the tuples t3 and t4 required by the definition of the multivalued dependency A →→ BC. Rule 8, the coalescence rule, is the most difficult of the eight rules to verify (see Exercise B.4). We can simplify the computation of the closure of D by using the following rules, which we can prove using rules 1 to 8 (see Exercise B.5): • Multivalued union rule. If →→ holds, and →→  holds, then →→  holds. • Intersection rule. If →→ holds, and →→  holds, then →→ ∩  holds.