Databases Reference
In-Depth Information
The projection on {S,J,T} is of course identical to the original relvar!—in other words, it's an
identity
projection
(see the section immediately following this one), and there isn't much decomposition, as such,
going on here.
There doesn't actually seem to be much point in maintaining the second relvar (i.e., the projection on {T,J})
as well as the original one, unless we want to be able to say that, e.g., Professor Black teaches Physics
without there existing, at the same time, some student who's actually being taught by Professor Black. If we
don't want this ability, we probably won't want to maintain that second relvar. Thus, the decomposition
produced by the 3NF isn't necessarily a
recommended
one—but, to repeat, it's one in which all relvars are in
3NF and all FDs are preserved.
I'll leave it as an exercise (Exercise 6.3) to show what happens when the 3NF procedure is applied to relvars
RX1, RX2, and RX3. Meanwhile, I'd like to close this section with a few words regarding BCNF. First, we can
add another (fifth) step to the 3NF procedure, as follows:
5.
Let
Z
be an element of
S
such that the projection
P
of relvar
R
on the attributes of
Z
is not in BCNF; let
X
→
Y
be an element of
C
(i.e., an FD) that holds in
P
; and let
X
not be a superkey for
P
. Replace
Z
in
S
by (a) the
union of
X
and
Y
and (b) the difference
Z
-
Y
between
Z
and
Y
(in that order). Perform this step for each
distinct
Z
and each distinct
X
.
Now, the 3NF procedure applied to relvar SJT produced a set
S
consisting of the headings {T,J} and {S,J,T}.
The projection of SJT on {T,J} is in BCNF, but the (identity) projection of SJT on {S,J,T} isn't, because the FD {T}
→ {J} holds in this latter projection and {T} isn't a superkey. Applying Step 5, therefore, we delete the heading
{S,J,T} and insert (a) the union of {T} and {J}—but this insertion has no effect, since that union is already an
element of
S
—and (b) the difference between {S,J,T} and {J}, in that order. Thus,
S
winds up with the following
headings as elements:
{ S , T }
{ T , J }
These are the headings of a set of BCNF relvars into which SJT can be nonloss decomposed (the keys for
those relvars are {S,T} and {T}, respectively). As you can see, therefore, adding Step 5 to the 3NF procedure
converts it into a BCNF procedure, though without any guarantee that FDs will be preserved. (In fact, of course, it's
impossible to provide any such guarantee, since we already know that BCNF and FD preservation can be conflicting
objectives.) However, any FDs lost are ones that
can't
be preserved without violating BCNF.
Actually we can simplify matters somewhat and go straight to BCNF—i.e., bypassing 3NF—as follows (the
input is as for the 3NF procedure; i.e., it consists of a relvar
R
and an irreducible cover
C
for the FDs that hold in
R
):
1.
Initialize
S
to contain just the heading of
R
.
2.
(
Same as Step 2 of the 3NF procedure.
) Let
X
be the left side (the determinant) of some FD in
C
; let the
complete set of FDs in
C
with left side
X
be
X
→
Y1
, ...,
X
→
Yn
; and let the union of
Y1
, ...
Yn
be
Y
. Add the
union of
X
and
Y
to
S
. Perform this step for each distinct
X
.
3.
Let
Z
be an element of
S
such that the projection
P
of
R
on the attributes of
Z
is not in BCNF; let
X
→
Y
be
an FD of
C
that holds in
P
; and let
X
not be a superkey for
P
. Replace
Z
in
S
by (a) the union of
X
and
Y
and
(b) the difference
Z
-
Y
between
Z
and
Y
(in that order). Perform this step for each distinct
Z
and each
distinct
X
.
