Databases Reference

In-Depth Information

Chapter 7

F D A x i o m a t i z a t i o n

[The] true and solid and living axioms

—Francis Bacon:
The New Organon

I've touched on the point several times already that some FDs imply others; now it's time to get more specific. First

of all, however, I need to introduce some notation—notation that (a) reduces the number of keystrokes required in

formal proofs and the like and (b) can also help, sometimes, to see the forest as well as the trees, as it were.

As you might recall, the statement of Heath's Theorem in Chapter 5 included the following sentence:
Let XY

denote the union of X and Y, and similarly for XZ.
The notation I want to introduce is basically just an extension of

this simple idea (it's a trifle illogical, but it's very convenient). To be specific, the notation uses expressions of the

form
XY
to mean:

The union of {
X
} and {
Y
}, if
X
and
Y
denote individual attributes (i.e., are individual attribute names)

The union of
X
and
Y
, if
X
and
Y
denote sets of attributes (i.e., are sets of attribute names)

It also allows {
X
} to be abbreviated to just
X
(e.g., in an FD) if
X
denotes an individual attribute.
Note:
For

convenience, I'll refer to this notation from this point forward as
Heath notation
.

ARMSTRONG'S AXIOMS

We've seen that, formally speaking, an FD is just an expression of the form
X
→
Y
, where
X
and
Y
are sets (actually

sets of attribute names, but from a formal point of view it really doesn't matter what the sets consist of). Now,

suppose we're given some set (
F
, say) of FDs. Then we can apply certain formal
rules of inference
to derive further

FDs from the ones in
F
—FDs that are
implied
by the ones in
F
, meaning that if the ones in
F
hold in some relvar
R
,

then the derived ones do so too. The rules in question were first stated by Armstrong in 1974 and for that reason are

usually referred to as
Armstrong's inference rules
or (more commonly)
Armstrong's axioms
. They can be stated in a

variety of equivalent ways, of which the following is perhaps the simplest:

1.

If
Y
is a subset of
X
, then
X
→
Y
(“reflexivity”).

2.

If
X
→
Y
, then
XZ
→
YZ
(“augmentation”).

3.

If
X
→
Y
and
Y
→
Z
, then
X
→
Z
(“transitivity”).

Observe that these rules are intuitively reasonable, given the intended interpretation of an FD. That is, since

we know what FDs “mean,” we can easily see that, e.g., if the FDs
X
→
Y
and
Y
→
Z
both hold in relvar
R
, then the

FD
X
→
Z
must do so too.
Note:
The suppliers relvar S illustrates this particular rule—the FDs {SNO} → {CITY}

and {CITY} → {STATUS} both hold in that relvar, and therefore the FD {SNO} → {STATUS} does so, too.