B.1 Multivalued Dependencies 3 ·Difference rule.Ifa→→B holds,anda→y holds,then o→→B-y holds anda→yy-B holds. Let us apply our rules to the following example.Let R=(A,B,C,G.H.I) with the following set of dependencies D given: A→→B B→→H1 CG→H We list several members of D+here: ·A→CGHI:Since A→B,the complementation rule(rule4)implies that A→→R-B-AR-B-A=CGHI,s0A→→CGHI. 。A→→Hl:Since A→B and B→→Hl,the multivalued transitivity rule(rule 6)implies that A→→HI-B.Since H-B=HI,A→→Hl. .B-H:To show this fact,we need to apply the coalescence rule (rule 8). B→→HI holds.Since HC HI and CG→H and CGnHI=O,we satisfy the statement of the coalescence rule,with a being B,B being HI,being CG,and y being H.We conclude that BH. ·A→→CG:We already know that A→→CGHI and A→HL.By the difference rule,A→→CGHI-HI.Since CGHI-HI=CG,A→→CG. B.1.2 Dependency Preservation The question of dependency preservation when we have multivalued dependen- cies is not as simple as it is when we have only functional dependencies. A decomposition of schema R into schemas R1,R2,...,R is a dependency- preserving decomposition with respect to a set D of functional and multivalued dependencies if,for every set of relationsr(R1).r2(R2)....,rn(R)such that for all i,ri satisfies D:(the restriction of D to R),there exists a relationr(R)that satisfies D and for which ri nIg(r)for all i. Let us apply the 4NF decomposition algorithm of Figure 8.16 to the schema R=(A,B,C,G,H,I)with D={A→yB,B→→Hl,CG→H.We shall then test the resulting decomposition for dependency preservation.We first need to compute the closure of D.The nontrivial dependencies in closure include all the dependencies in D,and the multivalued dependency A->HI,as we saw in Section B.1.1. R is not in 4NF.Observe that AB is not trivial,yet A is not a superkey. Using AB in the first iteration of the while loop,we replace R with two schemas,(A,B)and (A,C.G.H.1).It is easy to see that (A,B)is in 4NF since all multivalued dependencies that hold on (A,B)are trivial.However,the schema (A.C,G.H.I)is not in 4NF.Applying the multivalued dependency CG-HB.1 Multivalued Dependencies 3 • Difference rule. If →→ holds, and →→ holds, then →→ − holds and →→ − holds. Let us apply our rules to the following example. Let R = (A, B,C, G, H, I) with the following set of dependencies D given: A →→ B B →→ HI CG → H We list several members of D+ here: • A →→ CGHI: Since A →→ B, the complementation rule (rule 4) implies that A →→ R − B − A. R − B − A = CGHI, so A →→ CGHI. • A →→ HI: Since A →→ B and B →→ HI, the multivalued transitivity rule (rule 6) implies that A →→ HI − B. Since HI − B = HI, A →→ HI. • B → H: To show this fact, we need to apply the coalescence rule (rule 8). B →→ HI holds. Since H ⊆ HI and CG → H and CG ∩ HI = ∅, we satisfy the statement of the coalescence rule, with being B, being HI, being CG, and being H. We conclude that B → H. • A →→ CG: We already know that A →→CGHI and A →→ HI. By the difference rule, A →→ CGHI − HI. Since CGHI − HI = CG, A →→ CG. B.1.2 Dependency Preservation The question of dependency preservation when we have multivalued dependencies is not as simple as it is when we have only functional dependencies. A decomposition of schema R into schemas R1, R2,..., Rn is a dependencypreserving decomposition with respect to a set D of functional and multivalued dependencies if, for every set of relations r1(R1),r2(R2),...,rn(Rn) such that for all i, ri satisfies Di (the restriction of D to Ri), there exists a relation r(R) that satisfies D and for which ri = Ri(r) for all i. Let us apply the 4NF decomposition algorithm of Figure 8.16 to the schema R = (A, B,C, G, H, I) with D = {A →→ B, B →→ HI, CG → H}. We shall then test the resulting decomposition for dependency preservation. We first need to compute the closure of D. The nontrivial dependencies in closure include all the dependencies in D, and the multivalued dependency A →→ HI, as we saw in Section B.1.1. R is not in 4NF. Observe that A →→ B is not trivial, yet A is not a superkey. Using A →→ B in the first iteration of the while loop, we replace R with two schemas, (A, B) and (A,C, G, H, I). It is easy to see that (A, B) is in 4NF since all multivalued dependencies that hold on (A, B) are trivial. However, the schema (A,C, G, H, I) is not in 4NF. Applying the multivalued dependency CG→→H