Databases Reference
In-Depth Information
7.
If
X
→
YZ
, then
X
→
Y
and
X
→
Z
(“decomposition”).
Proof:
X
→
YZ
(given) and
YZ
→
Y
by reflexivity; hence
X
→
Y
by transitivity (and likewise for
X
→
Z
).
ANOTHER KIND OF CLOSURE
To recap, the closure
F
+
of a set
F
of FDs is the set of all FDs implied by those in
F
. Now, in principle we could
compute
F
+
from
F
by repeatedly applying Armstrong's rules (and/or rules derived therefrom) until they stop
producing new FDs. In practice, however, there's little need to compute
F
+
per se (which is just as well, perhaps,
since the procedure just outlined is hardly very efficient). But now I want to show how we can compute a certain
subset of
F
+
: namely, that subset consisting of all FDs with a given determinant. More precisely, I'll show how,
given a heading
H
, a subset
Z
of
H
, and a set
F
of FDs with respect to
H
, we can compute what's called the
closure
Z
+
of
Z
under
F
. Here's a definition:
Definition:
Let
H
be a heading, let
F
be a set of FDs with respect to
H
, and let
Z
be a subset of
H
. Then
the
closure
Z
+
of
Z
under
F
is the maximal subset
C
of
H
such that
Z
→
C
is implied by the FDs in
F
.
By the way, note that we now have two kinds of closure (try not to confuse them!): closure of a set of FDs,
and closure of a set of attributes under a set of FDs.
4
Note too that we use the same “superscript plus” notation for
both.
Here then is a simple pseudocode algorithm for computing the closure
Z
+
of
Z
under
F:
Z
+
:=
Z
;
do “forever” ;
for each FD
X
→
Y
in
F
do ;
if
X
is a subset of
Z
+
then replace
Z
+
by the union of
Z
+
and
Y
;
end ;
if
Z
+
did not change on this iteration
then quit ;
/* computation complete */
end ;
Let's do an example. Suppose the given heading is
ABCDEG
and we want to compute the closure
AB
+
of the
set of attributes
AB
under the following set
F
of FDs:
A
→
BC
E
→
CG
B
→
E
CD
→
EG
Let's now step through the algorithm:
First of all, we initialize the result
AB
+
to the set of attributes
AB
.
1.
4
Not to mention the kind of closure that applies to the operators of the relational algebra.
