Databases Reference
In-Depth Information
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 ).
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
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:
Let's now step through the algorithm:
First of all, we initialize the result AB + to the set of attributes AB .
4 Not to mention the kind of closure that applies to the operators of the relational algebra.
Search WWH ::

Custom Search