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.
