Armstrong Axioms

The following is the set of rules which is used to generate F+  from F.

• Reflexivity Rule : 

α  → β holds if α is a set of attributes and β ⊆ α.        

• Augmentation Rule :

γα  →  αβ holds if γ is a set of attributes α  → β holds.                

• Transitivity Rule :

 If α  → γ holds, then  α  → β  and  β → γ  holds. 

• Union Rule :

If α  → β  γ  holds. then  α  → β   and  α → γ  holds.

• Decomposition Rule :

 If  α  → βγ holds, then α → β  and α  → γ holds.

• Pseudo Transitivity Rule :

If α  → β is true and so is γβ → δ, then αγ  → δ  holds.

Example-1     

Let   S = (A, B, C, G, H, I)                                                            

F =  [ A → B,  A → C,  CG → H, CG → I,  B → H ] 

Find the additional FDs which are in F+.

Output :

1. a) A → H         Transitivity Rule     A → B,   B → H
2. b) CG → HI       Union Rule            CG ↜ H, CG → I
3. c) AG → I        Pseudo transitivity Rule    A →C, CG → I

Note : Here, Pseudo Transitivity Rule is the combination of Augmentation and Transitivity Rule.

Closure of Attribute Sets :

Consider some set of attributes (S). The set of attributes T, which can be derived from S, is said to be ‘Closure of attribute set’.

Example-9 :     

Let   S = (A, B, C, G, H, I)                                                                            

F =  [ A → B,  A → C,  CG → H, CG → I,  B →H ]

Find the Closure of Attribute set to AG.

Output :   (AG)+ → ABG → ABCG → ABCGH → ABCGHI

i.e., (AG)+→ ABCGHI 

Reference Link

Armstrong Axioms