Databases Reference
In-Depth Information
Fagin's Theorem is the “stronger form of Heath's Theorem” promised in Chapter 5. That is, where Heath's
Theorem gave only a sufficient condition for a relvar to be nonloss decomposable into two projections, Fagin's
Theorem gives both necessary and sufficient conditions. Of course, Fagin's Theorem is “obvious,” given what we
now know about JDs in general; with hindsight, there would never have been any formal need to define MVDs at all
if JDs in general had been defined and properly investigated first. But Fagin's Theorem was proved before JDs in
general had been properly investigated, and it was a new and important result at the time; what's more, it still has
practical significance, inasmuch as MVDs do correspond to a fairly common kind of business rule, whereas the
same can't reasonably be said for “cyclic”
n-
way JDs for
n
> 2 as discussed in Chapters 9 and 10.
FOURTH NORMAL FORM
You won't be surprised to hear there's such a thing as a trivial MVD:
Definition:
Let
X
→→
Y
be an MVD,
M
say, with respect to heading
H
. Then
M
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 theorem (see Exercise 12.7):
Theorem:
Let
X
→→
Y
be an MVD,
M
say, with respect to heading
H
. Then
M
is
trivial
if and only if
either (a)
Y
is a subset of
X
or (b) the union of
X
and
Y
is equal to
H
.
You probably won't be surprised by the next definition, either:
Definition:
Let relvar
R
have heading
H
and let
X
→→
Y
be an MVD,
M
say, with respect to
H
. Then
M
is
implied by the keys
of
R
if and only if every relation
r
that satisfies
R
's key constraints also satisfies
M
.
As with FDs and JDs, “implied by keys” here could just as well be “implied by superkeys” without making
any significant difference. Also, if
M
is trivial, it's satisfied by every relation
r
with heading
H
, and so it's satisfied
by every relation
r
that satisfies
R
's key constraints a fortiori. Thus, trivial MVDs are always “implied by keys,”
trivially. So suppose
M
is nontrivial. Then it's easy to prove the following theorem:
Theorem:
Let
M
be a nontrivial MVD that holds in relvar
R
. Then
M
is
implied by the keys
of
R
if and
only if it reduces to an
FD
out of a superkey of
R
─i.e., the double arrow reduces to a single arrow, as it were,
and the determinant is a superkey.
And now I can define 4NF:
Definition:
Relvar
R
is in
fourth normal form
(4NF) if and only if every MVD of
R
is implied by the keys
of
R
.
However, given the various definitions and theorems already discussed in this section, we can see that the following
“operational” definition is valid too:
Definition:
Relvar
R
is in
fourth normal form
(4NF) if and only for every nontrivial MVD
X
→→
Y
that
holds in
R
,
X
is a superkey for
R
(in other words, every such MVD reduces to “an
FD
out of a superkey”).
