Databases Reference
In-Depth Information
{ QTY }
→
{ QTY }
{ }
→
{ }
4.2 Yes, it is (“whenever two tuples agree on
X
, they also agree on
Y
” implies a comparison between the
projections of the tuples in question on the attributes of
X
and
Y
).
4.3
No answer provided.
4.4
First of all, here are the two definitions, numbered for purposes of subsequent reference:
1.
Relvar
R
is in 2NF if and only if, for every key
K
of
R
and every nonkey attribute
A
of
R
, the FD
K
→ {
A
}
is irreducible.
2.
Relvar
R
is in 2NF if and only if, for every nontrivial FD
X
→
Y
that holds in
R
, at least one of the
following is true: (a)
X
is a superkey; (b)
Y
is a subkey; (c)
X
is not a subkey.
Now, Definition 2 says
R
isn't
in 2NF if and only if there exists a nontrivial FD
X
→
Y
that holds in
R
such
that
X
isn't a superkey and
Y
isn't a subkey and
X
is a subkey. But if
X
is a subkey and not a superkey, it must be a
proper
subkey; thus, Definition 2 effectively says
R
isn't in 2NF if and only if there exists a nontrivial FD
X
→
Y
that holds in
R
such that
X
is a proper subkey and
Y
isn't a subkey. So let
K
be a key that includes
X
as a proper
subkey. Then the FD
K
→
Y
holds in
R
and is reducible, whence it follows that the FD
K
→ {
A
} holds in
R
and is
reducible for every attribute
A
contained in
Y
. So Definition 2 implies Definition 1. Following this argument in the
reverse direction will likewise show that Definition 1 implies Definition 2.
4.5
Consider the following argument.
Let relvar
R
not be in 2NF. Then there must be some key
K
of
R
and some nonkey attribute
A
of
R
such that
the FD
K
→ {
A
} (which holds in
R
, necessarily) is reducible─meaning some attribute can be dropped from
K
, yielding
K′
say, such that the FD
K′
→ {
A
} still holds. Hence
K
must be composite.
This argument appears to show that the answer to the exercise must be
yes
─i.e., if a relvar isn't in 2NF, it
must have a composite key. But the argument is incorrect! Here's a counterexample. Let USA be a binary relvar
with
attributes COUNTRY and STATE; the predicate is
STATE is part of COUNTRY
, but COUNTRY is the
United States in every tuple. Now, {STATE} is the sole key for this relvar, and the FD {STATE} → {COUNTRY}
thus certainly holds. However, the FD {} → {COUNTRY} clearly holds as well (see the answer to Exercise 4.10
below); the FD {STATE} → {COUNTRY} is thus reducible, and so the relvar isn't in 2NF, and yet the key
{STATE} isn't composite.
4.6 No! By way of a counterexample, consider relvar USA from the answer to the previous exercise. That relvar
is subject to the FD {} → {COUNTRY}, which is neither trivial nor an arrow out of a superkey, and so the relvar
isn't in BCNF. (In fact, of course, it isn't even in 2NF, as we saw in the answer to the previous exercise.) It follows
that the relvar can be nonloss decomposed into its two unary projections on {COUNTRY} and {STATE},
respectively. (Note that the corresponding join, needed to reconstruct the original relvar, is in fact a cartesian
product.)
