/    /  DBMS – Armstrong Axioms

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