Show that the relation schemas produced by Algorithm 15.4 are in 3NF.

What will be an ideal response?

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
superkey of R, and (b) A is not a prime attribute. But according to step 2 of the
algorithm, R i will contain a set of attributes X union A 1 union A 2 union ... union A n ,
where X -> A i for i=1, 2, ..., n, implying that X is a key of R i and the A i are the only
non-prime attributes of R i . Hence, if an FD Y -> A holds in R i where A is non-prime and
Y is not a superkey of R i , Y must be a proper subset of X (otherwise Y would contain X
and hence be a superkey). If both Y -> A and X -> A hold and Y is a proper subset of X,
this contradicts that X -> A is a FD in a minimal set of FDs that is input to the algorithm,
since removing an attribute from X leaves a valid FD, thus violating one of the
minimality conditions. This produces a contradiction of our assumptions. Hence, R i must
be in 3NF.