Databases Reference
In-Depth Information
key {
A
} considered in isolation. No. 4 would be implied by keys─actually by an individual key─if and only if {
C
}
were a key, but it isn't; what's more, that JD can't possibly hold in
R
, because if it did, then {
C
} would have to be a
key after all (think about it!). As for No. 5, it clearly isn't implied by the keys; it might or might not hold in
R
, but if
it does, then
R
can't be in 5NF.
So what exactly is going on in these examples? Let me try to explain the intuition behind what I've been
saying (you might like to try interpreting what follows in terms of the suppliers relvar S and the JD
{{SNO,SNAME},{SNO,STATUS},{SNAME,CITY}}, under the assumption once again that {SNO} and
{SNAME} are both keys for that relvar):
Let
X1
, ...,
Xn
be subsets of the heading
H
of relvar
R
, such that the union of
X1
, ...,
Xn
is equal to
H
.
Let
J
be the JD
{
X1
,...,
Xn
}, and let
J
be implied by the keys of
R
.
Let
r
be the relation that's the current value of
R
.
Choose, arbitrarily, two distinct elements (components) of the set {
X1
,...,
Xn
}, say
X1
and
X2
.
Let
r1
and
r2
be the projections of
r
on
X1
and
X2
, respectively.
Now, if
X1
and
X2
both include the same key
K
of
R
, then the join
r12
of
r1
and
r2
─whose heading
X12
will
be the union of
X1
and
X2
─will be a strict one to one join, and so
r1
and
r2
can be replaced by
r12
without loss of
information. (At the same time,
X1
and
X2
can be replaced in
J
by
X12
.) Since the original version of
J
was implied
by the keys of
R
, performing such replacements repeatedly will, by definition, eventually yield a relation (a) that's
equal to the original relation
r
, and in particular (b) will therefore have a heading equal to the entire heading
H
.
Let me now point out that everything I've said so far becomes much simpler in the common special case
where the pertinent relvar
R
has just one key
K
. In that case, the JD
{
X1
,...,
Xn
} is implied by keys if and only if
both of the following are true:
a.
Every attribute of
R
is included in at least one of
X1
, ...,
Xn
. (This requirement always applies, of course, in
the general case as well as in this special case.)
b.
The sole key
K
of
R
is included in each of
X1
, ...,
Xn
─in other words, each of
X1
, ...,
Xn
is a superkey.
So if
R
has just one key
K
, then
R
is in 5NF if and only if every component of every JD that holds in
R
includes that
key
K
.
4
(However, please note that─
important!
─I'm assuming here that the only JDs under consideration are ones
that are irreducible with respect to
R
. See Chapter 11.) By way of example, consider the parts relvar P. The only
irreducible JDs
{
X1
,...,
Xn
} that hold in that relvar are such that each
Xi
(
i
= 1, ...,
n
) includes the sole key {PNO}.
Those JDs are clearly all implied by that sole key, therefore, and relvar P is in 5NF. Here's one of the JDs in
question:
{ { PNO , PNAME , COLOR } , { PNO , WEIGHT , CITY } }
4
Note that this isn't the case with relvar S─that relvar is subject to at least one JD for which at least one component fails to include the sole key
{SNO} (viz.,
{{SNO,SNAME,CITY},{CITY,STATUS}}) and so isn't in 5NF.