Databases Reference
In-Depth Information
previous section, in relvar RX3, where the FDs {CLASS} → {CITY} and {CITY} → {STATUS} both held and so
the FD {CLASS} → {STATUS} held as well.
So some FDs imply others. Given a set
F
of FDs, then, we can sensibly talk about a
cover
for
F
. Here's the
definition:
Definition:
A
cover
for a set
F
of FDs is a set
C
of FDs such that every FD in
F
is implied by the FDs in
C
.
As a trivial example, let
F
be the set:
{
X
→
Y
,
Y
→
Z
,
X
→
Z
}
Then the following are both covers for
F
:
{
X
→
Y
,
Y
→
Z
}
{
X
→
Y
,
Y
→
Z
,
X
→
Z
}
This example illustrates two points: First, covers aren't unique, in general; second, any set of FDs is
certainly a cover for itself, because among other things every FD implies itself. A third and more important point is
the following: Enforcing the FDs in a cover
C
for a given set
F
will “automatically” enforce those in that set
F
.
Thus, given some set
F
of FDs that need to be enforced, it's sufficient to find some cover
C
for
F
and enforce the
FDs in
C
instead. (In particular, it's sufficient to enforce the FDs in an
irreducible
cover for
F
, as will quickly
become clear.)
Now I can define what it means for a cover to be irreducible:
Definition:
A cover
C
for a set
F
of FDs is
irreducible
if and only if it possesses all of the following
properties:
1.
Singleton dependant:
Every FD in
C
has just one attribute on the right side.
2.
Irreducible determinant:
Every FD in
C
is itself irreducible.
Note:
I'm being a trifle sloppy here.
Recall from Chapters 4 and 5 that FD irreducibility is defined only with respect to some relvar─but I
haven't said anything here about the FDs in
F
as holding in any relvar, and there's thus no context
that would allow us to talk legitimately about FDs being irreducible. What I mean, however, is that
no attribute can be discarded from the left side without losing the property that
C
is a cover for
F
.
3.
No redundant FDs:
No FD can be discarded from
C
without losing the property that
C
is a cover
for
F
.
The obvious question arises: Given some specific set of FDs, how can we find an irreducible cover for that
set? I'll answer this question properly in the next chapter. For now, let me just give an example—namely, an
irreducible cover for the FDs that hold in our usual suppliers relvar S:
{ SNO }
→
{ SNAME }
{ SNO }
→
{ CITY }
{ CITY }
→
{ STATUS }
