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 }