# Closure of a Set of Functional Dependencies

Posted By on October 7, 2014

## 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 .

#### Posted by Akash Kurup

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

Website: http://world4engineers.com