Closure of a Set of Functional Dependencies

1. We need to consider all functional dependencies that hold. Given a set of functional dependencies, we can prove that certain other ones also hold. We say these ones are logically implied by .

2. Suppose we are given a relation scheme , and the set of functional dependencies:

   

   Then the functional dependency is logically implied.

3. To see why, let and be tuples such that

   

   As we are given A B , it follows that we must also have

   

   Further, since we also have B H , we must also have

   

   Thus, whenever two tuples have the same value on , they must also have the same value on , and we can say that A H .

4. The closure of a set of functional dependencies is the set of all functional dependencies logically implied by .

5. We denote the closure of by .

6. To compute , we can use some rules of inference called Armstrong's Axioms:
   • Reflexivity rule: if is a set of attributes and , then holds.
   • Augmentation rule: if holds, and is a set of attributes, then holds.
   • Transitivity rule: if holds, and holds, then holds.
7. These rules are sound because they do not generate any incorrect functional dependencies. They are also complete as they generate all of .

8. To make life easier we can use some additional rules, derivable from Armstrong's Axioms:
   • Union rule: if and , then holds.
   • Decomposition rule: if holds, then and both hold.

   • Pseudotransitivity rule: if holds, and holds, then holds.
9. Applying these rules to the scheme and set mentioned above, we can derive the following:
   • A H, as we saw by the transitivity rule.
   • CG HI by the union rule.
   • AG I by several steps:
     • Note that A C holds.
     • Then AG CG , by the augmentation rule.
     • Now by transitivity, AG I .
     (You might notice that this is actually pseudotransivity if done in one step.)