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
.