Closure of a Set of Functional Dependencies

Posted By on October 7, 2014


Download PDF
Third Normal Form (3NF)
Other Functional Dependencies

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 .
Third Normal Form (3NF)
Other Functional Dependencies

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com