Let a relation R have some functional dependencies F specified. The closure of F (usually written as F+) is the set of all functional dependencies that may be logically derived from F. Often F is the set of most obvious and important functional dependencies and F+, the closure, is the set of all the functional dependencies including F and those that can be deduced from F. The closure is important and may, for example, be needed in finding one or more candidate keys of the relation.

For example, the student relation has the following functional dependencies

sno -> sname cno -> cname sno -> address cno -> instructor instructor -> office

Let these dependencies be denoted by F. The closure of F, denoted by F+, includes F and all functional dependencies that are implied by F.

To determine F+, we need rules for deriving all functional dependencies that are implied by F. A set of rules that may be used to infer additional dependencies was proposed by Armstrong in 1974. These rules (or axioms) are a complete set of rules in that all possible functional dependencies may be derived from them. The rules are:

1. Reflexivity Rule --- If X is a set of attributes and Y is a subset of X, then X -> Y holds.

   The reflexivity rule is the most simple (almost trivial) rule. It states that each subset of X is functionally dependent on X.

2. Augmentation Rule --- If X -> Y holds and W is a set of attributes, then WX -> WY holds.

   The augmentation rule is also quite simple. It states that if Y is determined by X then a set of attributes W and Y together will be determined by W and X together. Note that we use the notation WX to mean the collection of all attributes in W and X and write WX rather than the more conventional (W, X) for convenience.

3. Transitivity Rule --- If X -> Y and Y -> Z hold, then X -> Z holds.

   The transitivity rule is perhaps the most important one. It states that if X functionally determines Y and Y functionally determines Z then X functionally determines Z.

These rules are called Armstrong's Axioms.

Further axioms may be derived from the above although the above three axioms are sound and complete in that they do not generate any incorrect functional dependencies (soundness) and they do generate all possible functional dependencies that can be inferred from F (completeness). For proof of soundness and completeness of Armstrong's Axioms, the reader is referred to Ullman (Vol 1, page 387). The most important additional axioms are:

1. Union Rule --- If X -> Y and X -> Z hold, then X -> YZ holds.

2. Decomposition Rule --- If X -> YZ holds, then so do X -> Y and X -> Z.

3. Pseudotransitivity Rule --- If X -> Y and WY -> Z hold then so does WX -> Z.

Based on the above axioms and the functional dependencies specified for relation student, we may write a large number of functional dependencies. Some of these are:

(sno, cno) -> sno (Rule 1)
(sno, cno) -> cno (Rule 1)
(sno, cno) -> (sname, cname) (Rule 2)
cno -> office (Rule 3)
sno -> (sname, address) (Union Rule)
etc.

Often a very large list of dependencies can be derived from a given set F since Rule 1 itself will lead to a large number of dependencies. Since we have seven attributes (sno, sname, address, cno, cname, instructor, office), there are 128 (that is, 2^7) subsets of these attributes. These 128 subsets could form 128 values of X in functional dependencies of the type X -> Y. Of course, each value of X will then be associated with a number of values for Y ( Y being a subset of X) leading to several thousand dependencies. These large number of dependencies are not particularly helpful in achieving our aim of normalizing relations.

Although we could follow the present procedure and compute the closure of F to find all the functional dependencies, the computation requires exponential time and the list of dependencies is often very large and therefore not very useful. There are two possible approaches that can be taken to avoid dealing with the large number of dependencies in the closure. One is to deal with one attribute or a set of attributes at a time and find its closure (i.e. all functional dependencies relating to them). The aim of this exercise is to find what attributes depend on a given set of attributes and therefore ought to be together. The other approach is to find the minimal covers. We will discuss both approaches briefly.

As noted earlier, we need not deal with the large number of dependencies that might arise in a closure since often one is only interested in determining closure of a set of attributes given a set of functional dependencies. Closure of a set of attributes X is all the attributes that are functionally dependent on X given some functional dependencies F while the closure of F was all functional dependencies that are implied by F. Computing the closure of a set of attributes is a much simpler task if we are dealing with a small number of attributes. We will denote the closure of a set of attributes X given F by X+.

An algorithm to determine the closure:

Step 1 Let X^c <- X
Step 2 Let the next dependency be A -> B. If A is in X^c and B is not, X^c <- X^c + B.
Step 3 Continue step 2 until no new attributes can be added to X^c.

The result of the algorithm is X^c that is equal to X+.

The above algorithm may also be used to remove redundant dependencies. For example, to check if X -> A is redundant, we find closure of X without using X -> A. If A is in X^c, we can eliminate X -> A as redundant.

Consider the following relation

student(sno, sname, cno, cname).

We wish to determine the closure of (sno, cno). We have the following functional dependencies.

sno -> sname
cno -> cname

We apply the above algorithm using X^c as the place holder for all the attributes that have been found to be dependent on X so far.

Step 1 --- X^c <- X, that is, X^c <- (sno, cno)
Step 2 --- Consider sno -> sname, since sno is in X^c and sname is not, we have
X^c <- (sno, cno) + sname
Step 3 --- Consider cno -> cname, since cno is in X^c and cname is not, we have
X^c <- (sno, cno, sname) + cname
Step 4 --- Again, consider sno -> sname but this does not change X^c.
Step 5 --- Again, consider cno -> cname but this does not change X^c.

Therefore X+ = X^c = (sno, cno, sname, cname).

This shows that all the attributes in the relation student (sno, cno, sname, cname) are dependent on (sno, cno) and therefore (sno, cno) is a candidate key of the present relation. In this case, it is the only candidate key.

Similarly we may wish to investigate the closure of (sname, cname). We will find that the closure of (sname, cname) is only (sname, cname). Therefore these two attributes together cannot form the key of the above relation.

We define some further concepts about functional dependencies:

Copyright © 1996 Gopal Gupta. All rights reserved.

Back Contents Next