Databases Reference
In-Depth Information
{ { SNO , SNAME } , { SNO , STATUS } , { SNAME , CITY } }
{ { CITY , SNO } , { CITY , STATUS , SNAME } }
(Contrast the examples following the previous definition.) So now, at last, we know precisely what it means for a
given relvar to be subject to a given JD─and it's immediate that relvar
R
can be nonloss decomposed into its
projections on
X1
, ...,
Xn
if and only if
it's subject to the JD
{
X1
,...,
Xn
}.
FIFTH NORMAL FORM
Now, when we were talking about FDs and BCNF, we got into a discussion of
trivial FDs
and
FD irreducibility
and
FDs implied by keys
and various related matters. As I'm sure you'd expect by now, analogous concepts arise in
connection with JDs and 5NF also─but the details are a little trickier. Well, the concept of a JD being trivial is
actually quite straightforward:
Definition:
Let
{
X1
,...,
Xn
} be a JD,
J
say, with respect to heading
H
. Then
J
is
trivial
if and only if it's
satisfied by every relation with heading
H
.
From this definition, it's easy to prove the following result:
Theorem:
Let
{
X1
,...,
Xn
} be a JD,
J
say, with respect to heading
H
. Then
J
is
trivial
if and only if some
Xi
(1 ≤
i
≤
n
) is equal to
H
(because every relation with heading
H
necessarily satisfies every JD with respect
to
H
that's of the form
{...,
H
,...}).
We can regard this theorem as an
operational
(or “syntactic”) definition, inasmuch as it provides an effective
test that can easily be applied in practice. (By contrast, the formal or “semantic” definition isn't much use in the
practical problem of determining whether or not a given JD is trivial.)
I'll defer discussion of
JD irreducibility
to the next chapter; before then I want to explain what it means for a
JD to be implied by keys.
Definition:
Let relvar
R
have heading
H
and let
{
X1
,...,
Xn
} be a JD,
J
say, with respect to
H
. Then
J
is
implied by the keys
of
R
if and only if every relation
r
that satisfies
R
's key constraints also satisfies
J
.
This definition requires some elaboration. First of all, to say some relation satisfies some key constraint is to
say it satisfies the applicable uniqueness requirement; and if it satisfies the uniqueness requirement for the attributes
that constitute some key, it certainly satisfies the uniqueness requirement for every superset of that set of attributes
(just so long as that superset is a subset of the pertinent heading, of course)─in other words, for every corresponding
superkey. Thus, the phrase “satisfies
R
's key constraints” in the definition could be replaced by the phrase “satisfies
R
's superkey constraints” without making any significant difference. Likewise, the concept “implied by keys” could
just as well be “implied by superkeys,” again without making any significant difference.
Second, what happens if the JD
J
mentioned in the definition is trivial? Well, in that case, by definition,
J
is
satisfied by every relation
r
with heading
H
, and so
J
is certainly satisfied by every relation
r
that satisfies
R
's key
constraints a fortiori. So trivial JDs are always “implied by keys,” trivially.
Third, then, suppose
J
is nontrivial. How do we determine whether some nontrivial JD is implied by the keys
of some relvar? This question does have a satisfactory answer, but it's a trifle complicated, and for that reason I'll
defer it to the next section. Before then, I want to give a definition of 5NF and say a little about that definition.
