Download free books at BookBooN.com
An Introduction to Relational Database Theory
199
Database Design I: Projection-Join Normalization
Now we must look at the circumstances under which Step 5 is needed, and why an FD is inevitably lost
in that step.
FD Loss Sometimes Inevitable
Consider the relvar WXYZ with attributes W, X, Y, and Z. Assume that {{W,X} ĺ {Y,Z}, {Y} ĺ {X}} is a
minimal cover for WXYZ. Then {W,X} and {W,Y} are both keys of WXYZ (exercise: prove that claim), and
WXYZ is not in BCNF because the determinant {Y} is not a superkey. Date’s procedure (Steps 1 to 4)
yields the BCNF relvar XY with key {Y} but retains the non-BCNF relvar WXYZ. In Step 5 we decompose
WXYZ into WXZ and XY, now both in BCNF, but then we lose the FD {W,X} ĺ {Y}. We will need to
declare a constraint to the effect that {W,X} is a key of WXZ JOIN XY.
For a realistic example exhibiting this phenomenon, consider payments made against bank accounts by
use of debit cards. Payments are identified within a particular account by transaction numbers, so
payments by debit card might be recorded in a relvar with attributes Account#, Transaction#,
Card#, Payee, and Amount. {Account#, Transaction#} is a key for this relvar but so is
{Transaction#, Card#
} because we have {Card#} ĺ {Account#}. (There might be several
distinct cards for the same account: for example, if it is a joint account.)
In general, if A, B, C, and D are subsets of the heading of relvar r and FDs ABĺCD and CĺB hold in r,
then AB and AC are both keys of r. If each attribute of r appears in exactly one of A, B, C, and D, A and
B are each nonempty, and either C or D is nonempty, then
(a) C, a proper subkey, is the determinant of a nontrivial FD and r is therefore not in BCNF.
(b) Steps 1 to 4 will not result in a BCNF decomposition of r.
(c) The nontrivial FD ABĺCD is lost in the decomposition resulting from Step 5.
One might even question the claim that Steps 1 to 4 guarantee to preserve FDs. Consider the relvar SCF
with attributes S, C, and F, standing for student, course, and faculty as before. This time, however we have
the FD {S}
ĺ {F} in addition to {C} ĺ {F}. Our minimal cover is therefore {{S} ĺ {F}, {C} ĺ {F}},
from which we can conclude that {S,C} ĺ {F} holds in SCF and {S,C} is a key of SCF (exercise: prove
this). Application of Step 2 yields relvars SF and CF and Step 4 yields SC. Have we lost the FD
{S,C} ĺ {F}, which, although not present in the given minimal cover, is a consequence of that cover? In
one sense, no, because it holds in JOIN{SF, CF, SC}, but the fact remains that the decomposition allows
a student to be enrolled on a course offered by a faculty other than the student’s faculty unless some
constraint is declared to make that impossible. With relvar SCF that was not possible. If we consider
UNION{JOIN{SC,SF}, JOIN{SC,CF}} we can discover a sense in which that FD has indeed been lost,
for that can yield a relation in which it does not hold. As with the 6NF decomposition of
WIFE_OF_HENRY_VIII we have a situation where a constraint implied by the very structure of a relvar
has to be stated explicitly when a decomposition is taken.