Inference Rule

 

Inference Rule (IR):

• The Armstrong's axioms are the basic inference rule.
• Armstrong's axioms are used to conclude functional dependencies on a relational database.
• The inference rule is a type of assertion. It can apply to a set of FD(functional dependency) to derive other FD.
• Using the inference rule, we can derive additional functional dependency from the initial set.

The Functional dependency has 6 types of inference rule:

1. Reflexive Rule (IR₁)

In the reflexive rule, if Y is a subset of X, then X determines Y.

1. If X ⊇ Y then X  →    Y  

Example:

1. X = {a, b, c, d, e}  
2. Y = {a, b, c}  

2. Augmentation Rule (IR₂)

The augmentation is also called as a partial dependency. In augmentation, if X determines Y, then XZ determines YZ for any Z.

1. If X    →  Y then XZ   →   YZ   

Example:

1. For R(ABCD),  if A   →   B then AC  →   BC  

3. Transitive Rule (IR₃)

In the transitive rule, if X determines Y and Y determine Z, then X must also determine Z.

1. If X   →   Y and Y  →  Z then X  →   Z    

4. Union Rule (IR₄)

Union rule says, if X determines Y and X determines Z, then X must also determine Y and Z.

1. If X    →  Y and X   →  Z then X  →    YZ     

Proof:

1. X → Y (given)
2. X → Z (given)
3. X → XY (using IR₂ on 1 by augmentation with X. Where XX = X)
4. XY → YZ (using IR₂ on 2 by augmentation with Y)
5. X → YZ (using IR₃ on 3 and 4)

5. Decomposition Rule (IR₅)

Decomposition rule is also known as project rule. It is the reverse of union rule.

This Rule says, if X determines Y and Z, then X determines Y and X determines Z separately.

1. If X   →   YZ then X   →   Y and X  →    Z   

Proof:

1. X → YZ (given)
2. YZ → Y (using IR₁ Rule)
3. X → Y (using IR₃ on 1 and 2)

6. Pseudo transitive Rule (IR₆)

In Pseudo transitive Rule, if X determines Y and YZ determines W, then XZ determines W.

1. If X   →   Y and YZ   →   W then XZ   →   W   

Proof:

1. X → Y (given)
2. WY → Z (given)
3. WX → WY (using IR₂ on 1 by augmenting with W)
4. WX → Z (using IR₃ on 3 and 2)