Computing the Closure of Attributes

Computing the Closure of Attributes

Before proceeding to other rules, we shall give a general principle from which all rules follow. Assume {A1, A2,. . . ,An} is a set of attributes and S  is a set of FD's. The closure of {A1, A2, . . . ,An} under the FD's in S is the set of attributes B such that every relation that satisfies all the FD's in set  S also satisfies A1, A2, . . . An → B. That is, A1, A2, . . . An → B follows from the FD's of S. We denote the closure of a set of attributes A1A2....An by {A1, A2,. . . ,An}+.

the trivial-dependency rule

To make the discussion of computing closures simpler, we shall allow trivial FD's, so A1, A2,. . . ,An are always in {A1, A2, . . . ,An}+.

Figure (b) demonstrates the closure process. Starting with the given set of attributes, we frequently expand the set by adding the right sides of FD's as soon as we have included their left sides. Ultimately, we cannot expand the set any more, and the resulting set is the closure. The following steps are a more detailed rendition of the algorithm for computing the closure of a set of attributes {A1, A2,. . .,An} with respect to a set of FD's.

1. Let X be a set of attributes that ultimately will become the closure. First, we initialize X to be {A1, A2, . . . ,An}.

2. Now, we repeatedly search for some FD B1B2... Bm → C such that all of B1, B2,. . . , Bm are in the set of attributes X, but C is not. We then add C to the set X.

3. Repeat step 2 as many times as necessary until no more attributes can be added to X. Since X can only grow, and the number of attributes of any relation schema must be finite, eventually nothing more can be added to X.

4. The set X, after no more attributes can be added to it, is the correct value of {A1, A2, .. . ,An}+.

Example (a) : Let us consider a relation with attributes A, B, C, D, E, and F. Suppose that this relation has the FD's AB → C, BC → AD, D → E, and CF → B. What is the closure of {A,B}, that is, {A,B}+?
Computing the closure of a Set of attributes

We start with X = {A, B}. First, notice that both attributes on the left side of FD AB → C are in X, so we may add the attribute C, which is on the right side of that FD. Thus,  after one iteration of step 2, X becomes {A,B,C}.

Next, we see that the left, side of BC → AD is now contained in X, so we may add to X the attributes A and D. A is already there, but D is not, so X next  becomes {A, B, C, D}. At this point, we may use the FD D → E to add E to X, which is now {A, B, C, D, E}. No more changes to X are possible. ln particular, the FD CF → B can not be used, because its left side never becomes contained in X. Thus, {A, B}+ = {A,B, C, D, E}.

If we know how to compute the closure of any set of attributes, then we can test whether any given FD A1A2An → B follows from a set of FDs S. First compute {A1, A2,. . . ,An}+ using the set of FDs S. If B is in {A1, A2, . . . . ,An}+, then A1A2.. . An → B does follow from S, and if B is not in  {A1, A2, .,,, An}+, then this FD does not follow from S. More generally, a FD with a set of attributes on the right can be tested if we remember that  this FD is a shorthand for a set of FD's. Thus, A1A2. . .An → B1B2. . .Bm follows from set of FD's S if and only if all of B1,B2, ...,Bm are in {A1,A2,...,.An}+.
 
Example (b) : Consider the relation and FD's of Example (a). Suppose we wish to test whether AB → D follows from these FD's. We compute {A, B}+, which is {A, B, C, D, E}, as we saw in that example. Since D is a member of the closure, we conclude that AB → D does follow.

On the other hand, consider the FD D → A. To test whether this FD follows from the given FD's, first compute {D}+. To do so, we start with X = {D}.  We can use the FD D → E to add E to the set X. However, then we are stuck. We cannot find any other FD whose left side is contained in X = {D, E}, so {D}+ = {D, E}. Since A is not a member of {D, E}, we conclude that D → A does not follow.



Tags