Closure of a Set of Functional Dependencies

1. We need to consider all functional dependencies that hold. Given a set F of functional dependencies, we can prove that certain other ones also hold. We say these ones are logically implied by F.
2. Suppose we are given a relation scheme R=(A,B,C,G,H,I), and the set of functional dependencies:

    A    B 
   
   		 		 		 		 A    C 
   
   		 		 		 		 CG    H 
   
   		 		 		 		 CG    I 
   
   		 		 		 		 B    H 
   
   

   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 A, they must also have the same value on H, and we can say that A H .

4. The closure of a set F of functional dependencies is the set of all functional dependencies logically implied by F.
5. We denote the closure of F 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 F 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.)