Appendix B Advanced Relational Database Design r1:A B a1 b1 a2 b1 T2:CGH c181h1 c2&2h2 r3:A1 a111 a212 r4: ACG a1c181 a2C282 Figure B.1 Projection of relation r onto a 4NF decomposition of R. (which follows from the given functional dependency CG->H by the replication rule),we replace(A,C,G,H.,I)with the two schemas(C,G,H)and (A,C,G,I). Schema(C,G,H)is in 4NF,but schema(A,C,G,I)is not.To see that(A,C,G,I) is not in4NF,we note that since A→→HI is in D+,A→→I is in the restriction of D to(A,C,G,I).Thus,in a third iteration of the while loop,we replace(A,C,G,I) with two schemas (A.1)and (A.C.G).The algorithm then terminates and the resulting 4NF decomposition is {(A,B).(C.G.H),(A,I),(A,C,G)}. This 4NF decomposition is not dependency preserving,since it fails to preserve the multivalued dependency BHI.Consider Figure B.1,which shows the four relations that may result from the projection of a relation on(A,B.C,G,H,I) onto the four schemas of our decomposition.The restriction of D to (A,B)is A>B and some trivial dependencies.It is easy to see that ri satisfies AB, because there is no pair of tuples with the same A value.Observe that r2 satisfies all functional and multivalued dependencies,since no two tuples in r2 have the same value on any attribute.A similar statement can be made for r3 and r4. Therefore,the decomposed version of our database satisfies all the dependencies in the restriction of D.However,there is no relation r on (A,B,C,G,H,I)that satisfies D and decomposes into ri.r2,r3,and r4.Figure B.2 shows the relation r=rh凶r2r3r4.Relation r does not satisfy B→→Hl.Any relation s containing r and satisfying B>HI must include the tuple(a2,b1,c2,82,hi,i1). However,IcGH (s)includes a tuple (c2.82.h)that is not in r2.Thus,our decomposition fails to detect a violation of BHI. We have seen that,if we are given a set of multivalued and functional depen- dencies,it is advantageous to find a database design that meets the three criteria of4 Appendix B Advanced Relational Database Design r1 : A B 1 b1 2 b a a a a a a 1 r2 : C G H c1 g1 h1 c2 g2 h2 r3 : A I 1 1 2 2 r4 : A C G 1 c1 g1 2 c2 g2 i i Figure B.1 Projection of relation r onto a 4NF decomposition of R. (which follows from the given functional dependency CG → H by the replication rule), we replace (A,C, G, H, I) with the two schemas (C, G, H) and (A,C, G, I). Schema (C, G, H) is in 4NF, but schema (A,C, G, I) is not. To see that (A,C, G, I) is not in 4NF, we note that since A →→ HI is in D+, A →→ I is in the restriction of D to (A,C, G, I). Thus, in a third iteration of the while loop, we replace (A,C, G, I) with two schemas (A, I) and (A,C, G). The algorithm then terminates and the resulting 4NF decomposition is {(A, B), (C, G, H), (A, I), (A,C, G)}. This 4NFdecomposition is not dependency preserving, since it fails to preserve the multivalued dependency B →→ H I. Consider Figure B.1, which shows the four relations that may result from the projection of a relation on (A, B,C, G, H, I) onto the four schemas of our decomposition. The restriction of D to (A, B) is A →→ B and some trivial dependencies. It is easy to see that r1 satisfies A →→ B, because there is no pair of tuples with the same A value. Observe that r2 satisfies all functional and multivalued dependencies, since no two tuples in r2 have the same value on any attribute. A similar statement can be made for r3 and r4. Therefore, the decomposed version of our database satisfies all the dependencies in the restriction of D. However, there is no relation r on (A, B,C, G, H, I) that satisfies D and decomposes into r1,r2,r3, and r4. Figure B.2 shows the relation r = r1 ✶ r2 ✶ r3 ✶ r4. Relation r does not satisfy B →→ HI. Any relation s containing r and satisfying B →→ HI must include the tuple (a2, b1, c2, g2, h1, i1). However, CGH (s) includes a tuple (c2, g2, h1) that is not in r2. Thus, our decomposition fails to detect a violation of B →→ HI. We have seen that, if we are given a set of multivalued and functional depen￾dencies, it is advantageous to find a database design that meets the three criteria of