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.[69] 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:

  1. First of all, we initialize the result AB+ to the set of attributes AB.

  2. We now go round the inner loop four times, once for each of the given FDs. On the first iteration (for the FD A → BC), we find that the determinant A is indeed a subset of AB+ as computed thus far, so we add attributes (B and) C to the result. AB+ is now the set ABC.

  3. On the second iteration (for the FD E → CG), we find that the determinant E is not a subset of the result as computed so far, which thus remains unchanged.

  4. On the third iteration (for the FD B → E), we add E to AB+, which thus now has the value ABCE.

  5. On the fourth iteration (for the FD CD → EG), AB+ remains unchanged.

  6. Now we go round the inner loop four times again. On the first iteration, the result remains unchanged; on the second, it expands to ABCEG; on the third and fourth, it remains unchanged.

  7. Now we go round the inner loop four times again. The result remains unchanged, and so the whole process terminates, with AB+ = ABCEG.

Well, I hope you can see from this example that computing Z+ given H, F, and Z is essentially straightforward. And the important thing is this: Given some set F of FDs (with respect to some heading H), we can easily tell whether some specific FD X → Y (with respect to that same heading H) is implied by F, because it will be so if and only if Y is a subset of the closure X+ of X under F. In other words, we now have a simple way of determining whether a given FD X → Y is in the closure F+ of F without actually having to compute F+.

It also follows from the definition (of closure of a set of attributes) that the superkeys for a relvar R are precisely those subsets SK of the heading of R such that the closure SK+ of SK—under the pertinent set of FDs—is the entire heading of R.


[69] Not to mention the kind of closure that applies to the operators of the relational algebra.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.216.2.66