Chapter 15: Database Design Theory: Normalization Algorithms
1
CHAPTER 15: Database Design Theory: Normalization Algorithms
Answers to Selected Exercises
15.17 – Show that the relation schemas produced by Algorithm 15.4 are in 3NF.
Answer:
We give a proof by contradiction. Suppose that one of the relations R i resulting from
Algorithm 15.1 is not in 3NF. Then a FD Y -> A holds R i in where: (a) Y is not a
15.18 – Show that, if the matrix S resulting from Algorithm 15.3 does not have a row
that is all “a” symbols, then projecting S on the decomposition and joining it back will always
produce at least one spurious tuple.
Answer:
The matrix S initially has one row for each relation R i in the decomposition, with “a”
symbols under the columns for the attributes in R i . Since we never change an “a” symbol
15.19 – Show that the relation schemas produced by Algorithm 15.5 are in BCNF.
Chapter 15: Database Design Theory: Normalization Algorithms
3
(c) Consider the decomposition of REFRIG into D={R1(M,Y,P), R2(M,MP,C)}. Is this
decomposition lossless? Show why. (You may consult the test under Property LJ1 in
Section 15.2.4)
Answers:
(a)
– {M} IS NOT a candidate key since it does not functionally determine attributes Y or P.
– {M, Y} IS a candidate key since it functionally determines the remaining attributes P, MP,
(b)
REFRIG is not in 2NF, due to the partial dependency {M, Y} MP (since {M} MP
(c)