1. We saw that BC-schema was in BCNF, but still was not an ideal design as it su ered from repetition of information. We had the multivalued dependency cname →→ street ccity, but no non-trivial functional dependencies.

2. We can use the given multivalued dependencies to improve the database design by decomposing it into fourth normal form.

3. A relation schema R is in 4NF with respect to a set D of functional and multivalued dependencies if for all multivalued dependencies in D+ of the form →→ β , where α ∈ R and β ∈ R, at least one of the following hold:

• α →→ β is a trivial multivalued dependency.
• α is a superkey for schema R.

4. A database design is in 4NF if each member of the set of relation schemas is in 4NF.

5. The de nition of 4NF di ers from the BCNF de nition only in the use of multivalued dependencies.

• Every 4NF schema is also in BCNF.
• To see why, note that if a schema is not in BCNF, there is a non-trivial functional dependency → βholding on R, where is not a superkey.
• Since → β implies →→ β, by the replication rule, R cannot be in 4NF.

6. We have an algorithm similar to the BCNF algorithm for decomposing a schema into 4NF:

result := -R},
done := false,
compute D+,
while (not done) do
if (there is a schema Ri in result
that is not in 4NF)
then begin
let →→ β be a nontrivial multivalued
dependency that holds on Ri such that
→Ri is not in D+, and
α ∩ β =Φ,,
result = (result - Ri) ∪ (Ri - β ) ∪ ( α, β),
end
else done = true,

7. If we apply this algorithm to BC-schema:

• cname → loan# is a nontrivial multivalued dependency and cname is not a superkey for the schema.
• We then replace BC-schema by two schemas:
  Cust-loan-schema=(cname, loan#)
  Customer-schema=(cname, street, ccity)
• These two schemas are in 4NF.

8. We can show that our algorithm generates only lossless-join decompositions.

• Let R be a relation schema and D a set of functional and multivalued dependencies on R.
• Let R1 and R2 form a decomposition of R.
• This decomposition is lossless-join if and only if at least one of the following multivalued dependencies
  is in D+:
  R1 ∩ R2 → R1
  R1 ∩ R2 → R2
• We saw similar criteria for functional dependencies.
• This says that for every lossless-join decomposition of R into two schemas R1 and R2, one of the two
  above dependencies must hold.
• You can see, by inspecting the algorithm, that this must be the case for every decomposition.

9. Dependency preservation is not as simple to determine as with functional dependencies.

• Let R be a relation schema.
• Let R1,R2, : : :Rn be a decomposition of R.
• Let D be the set of functional and multivalued dependencies holding on R.
• The restriction of D to Ri is the set Di consisting of:
  - All functional dependencies in D+ that include only attributes of Ri.
  - All multivalued dependencies of the form →→ β∩ Ri where α ∈ Ri and →→ β is in D+.
• A decomposition of schema R is dependency preserving with respect to a set D of functional andmultivalued dependencies if for every set of relations r1(R1), r2(R2), ...rn(Rn) such that for all i, ri satisfies Di, there exists a relation r(R) that satis es D and for which ri = â…¡Ri(r) for all i.

Figure 7.9: Projection of relation r onto a 4NF decomposition of R.

10. What does this formal statement say? It says that a decomposition is dependency preserving if for every set of relations on the decomposition schema satisfying only the restrictions on D there exists a relation r on the entire schema R that the decomposed schemas can be derived from, and that r also satis es the functional and multivalued dependencies.

11. We'll do an example using our decomposition algorithm and check the result for dependency preservation.

• Let R = (A,B,C, G,H, I).
• Let D be
  A→→B
  B→→HI
  CG→→H
• R is not in 4NF, as we have A → B and A is not a superkey.
• The algorithm causes us to decompose using this dependency into
  R1 = (A,B)
  R2 = (A,C, G,H, I)
• R1 is now in 4NF, but R2 is not.
• Applying the multivalued dependency CG →→ H (how did we get this?), our algorithm then decomposes
  R2 into
  R3 = (C, G,H)
  R4 = (A,C, G, I)
• R3 is now in 4NF, but R4 is not.
• Why? As A →→ HI is in D+ (why?) then the restriction of this dependency to R4 gives us A →→ I.
• Applying this dependency in our algorithm nally decomposes R4 into
  R5 = (A, I)
  R6 = (A,C,G)
• The algorithm terminates, and our decomposition is R1,R3,R5 and R6.

12. Let's analyze the result.

• This decomposition is not dependency preserving as it fails to preserve B →→ HI.
• Figure 7.9 (textbook 6.14) shows four relations that may result from projecting a relation onto the four schemas of our decomposition.
• The restriction of D to (A,B) is A →→B and some trivial dependencies.
• We can see that r1 satis es A →→ B as there are no pairs with the same A value.
• Also, r2 satis es all functional and multivalued dependencies since no two tuples have the same value on any attribute.
• We can say the same for r3 and r4.
• So our decomposed version satis es all the dependencies in the restriction of D.
• However, there is no relation r on (A,B,C, G,H, I) that satis es D and decomposes into r1, r2, r3 and r4.
• Figure 7.10 (textbook 6.15) shows r = r1 ∝r2 ∝r3 ∝r4.

Figure 7.10: A relation r(R) that does not satisfy B →→ HI.

• 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.

13. We have seen that if we are given a set of functional and multivalued dependencies, it is best to nd a database design that meets the three criteria:

• 4NF.
• Dependency Preservation.
• Lossless-join.

14. If we only have functional dependencies, the rst criteria is just BCNF.

15. We cannot always meet all three criteria. When this occurs, we compromise on 4NF, and accept BCNF, or even 3NF if necessary, to ensure dependency preservation.