Databases Reference
In-Depth Information
So the rules are reasonable. But what's more important is that they're both
sound
and
complete
. Soundness
and completeness are concepts frequently encountered in connection with formal systems in general.
In the formal
system under consideration here, this is what they mean:
Completeness:
If an FD
f
is implied by the ones in the given set
F
, then it can be derived from the ones in
F
by means of the rules. (To repeat, to say some FD
f
is implied by the FDs in some set
F
is to say that if the
FDs in
F
hold, then
f
holds too.)
Soundness:
If an FD
f
isn't implied by the ones in the given set
F
, then it can't be derived from the ones in
F
by means of the rules.
1
The rules thus form what's called an
axiomatization
for FDs. As a consequence, they can be used to derive
what's called the
closure
F
+
of any given set
F
of FDs. Here's a definition:
Definition:
Let
F
be a set of FDs. Then the
closure
F
+
of
F
is the set of all FDs implied by those in
F
.
What's more, the derivation process can be
mechanized
; that is, Armstrong's rules can be incorporated into
(e.g.) a design tool that, given a set
F
of FDs that hold in some relvar
R
, will be able to compute the closure
F
+
of
that set
F
, or in other words the complete set of all FDs that hold in that relvar. The significance of this fact should
be obvious.
ADDITIONAL RULES
Several additional inference rules can be derived from the original three, the following among them. Such
additional rules can be used to simplify the practical task of computing
F
+
from
F
. Here are some examples:
4.
X
→
X
(“self determination”).
5.
If
X
→
Y
and
X
→
Z
, then
X
→
YZ
(“union”).
6.
If
X
→
Y
and
Z
→
W
, then
XZ
→
YW
(“composition”).
If
X
→
YZ
, then
X
→
Y
and
X
→
Z
(“decomposition”).
2
7.
In the next section, I'll show how these four rules can be derived from the original three. First, however, let
me give a couple of examples to show how the rules (original and/or additional) can be used. By way of a first
example, suppose we're given a relvar
R
with attributes
A
,
B
,
C
,
D
,
E
,
F
, and we're told the following FDs hold in
that relvar:
1
If you have a background in logic, you might like the following characterization: Soundness means all theorems are tautologies; completeness
means all tautologies are theorems. Or more intuitively (and with acknowledgments to Hugh Darwen): Soundness means if you can prove it, it's
true; completeness means if it's true, you can prove it.
2
Two points: First, don't confuse this kind of decomposition with nonloss decomposition as discussed at length elsewhere in this topic. Second,
observe that composition and decomposition as here defined aren't quite inverses of each other; to be specific, the inverse of decomposition is
that special case of composition in which
Z
is replaced by
X
and
W
is replaced by
Z
.
