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.