next up previous
Next: Closure of Attribute Sets Up: Functional Dependencies Previous: Basic Concepts

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 tex2html_wrap_inline1090 B 
   
   		 		 		 		 A tex2html_wrap_inline1090 C 
   
   		 		 		 		 CG tex2html_wrap_inline1090 H 
   
   		 		 		 		 CG tex2html_wrap_inline1090 I 
   
   		 		 		 		 B tex2html_wrap_inline1090 H 
   
   

   Then the functional dependency tex2html_wrap_inline1194 is logically implied.

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

    tex2html_wrap_inline1200 
   

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

    tex2html_wrap_inline1204 
   

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

    tex2html_wrap_inline1208 
   

   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 tex2html_wrap_inline1090 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 tex2html_wrap_inline1222 .
6. To compute tex2html_wrap_inline1222 , we can use some rules of inference called Armstrong's Axioms:
   • Reflexivity rule: if tex2html_wrap_inline958 is a set of attributes and tex2html_wrap_inline1158 , then tex2html_wrap_inline1058 holds.
   • Augmentation rule: if tex2html_wrap_inline1058 holds, and tex2html_wrap_inline1234 is a set of attributes, then tex2html_wrap_inline1236 holds.
   • Transitivity rule: if tex2html_wrap_inline1058 holds, and tex2html_wrap_inline1240 holds, then tex2html_wrap_inline1242 holds.
7. These rules are sound because they do not generate any incorrect functional dependencies. They are also complete as they generate all of tex2html_wrap_inline1222 .
8. To make life easier we can use some additional rules, derivable from Armstrong's Axioms:
   • Union rule: if tex2html_wrap_inline1058 and tex2html_wrap_inline1242 , then tex2html_wrap_inline1250 holds.
   • Decomposition rule: if tex2html_wrap_inline1250 holds, then tex2html_wrap_inline1058 and tex2html_wrap_inline1242 both hold.
   • Pseudotransitivity rule: if tex2html_wrap_inline1058 holds, and tex2html_wrap_inline1260 holds, then tex2html_wrap_inline1262 holds.
9. Applying these rules to the scheme and set F mentioned above, we can derive the following:
   • A tex2html_wrap_inline1090 H, as we saw by the transitivity rule.
   • CG tex2html_wrap_inline1090 HI by the union rule.
   • AG tex2html_wrap_inline1090 I by several steps:
     • Note that A tex2html_wrap_inline1090 C holds.
     • Then AG tex2html_wrap_inline1090 CG , by the augmentation rule.
     • Now by transitivity, AG tex2html_wrap_inline1090 I .
     (You might notice that this is actually pseudotransivity if done in one step.)

---

next up previous
Next: Closure of Attribute Sets Up: Functional Dependencies Previous: Basic Concepts

Osmar Zaiane
Tue Jun 9 15:12:55 PDT 1998