Functional Dependencies

Armstrong Axioms and Inference Rules

Three primary axioms - reflexivity, augmentation and transitivity - are sound and complete, meaning they derive every dependency that follows and none that does not. Three secondary rules make proofs shorter.

On this page (16)

Concept

Armstrong axioms are a set of inference rules for deriving new functional dependencies from known ones. They matter because they are sound and complete.

Property	Meaning
Sound	Every dependency derived is genuinely true. The rules never invent a false one.
Complete	Every dependency that logically follows can be derived. Nothing true is unreachable.

Together these two properties mean the axioms are exactly right — no more and no less powerful than logical implication itself.

The three primary axioms

1. Reflexivity

  If  Y is a subset of X   then   X -> Y

  { roll_no, name } -> roll_no
  { A, B, C } -> { A, B }
  X -> X

  This generates the TRIVIAL dependencies. It needs no
  input dependencies at all, which is why it is the only
  axiom that can start a derivation from nothing.

2. Augmentation

  If  X -> Y   then   X Z -> Y Z    for any Z

  Given   roll_no -> name
  then    { roll_no, course_code } -> { name, course_code }

  Adding the same attributes to both sides preserves truth.
  Intuition: if X already pins down Y, then knowing X and
  something extra still pins down Y and that extra thing.

3. Transitivity

  If  X -> Y  and  Y -> Z   then   X -> Z

  roll_no   -> dept_code
  dept_code -> dept_head
  ---------------------------
  roll_no   -> dept_head

  This is the rule that creates transitive dependencies,
  and therefore the rule 3NF is designed around.

The three secondary rules

These are derived from the primary three. They save time, and the derivations themselves are examinable.

4. Union

  If  X -> Y  and  X -> Z   then   X -> Y Z

  DERIVATION
    1  X -> Y            given
    2  X -> Z            given
    3  X X -> X Y        augment 1 with X   (X X is just X)
    4  X -> X Y          simplify
    5  X Y -> Y Z        augment 2 with Y
    6  X -> Y Z          transitivity on 4 and 5

5. Decomposition

  If  X -> Y Z   then   X -> Y  and  X -> Z

  DERIVATION
    1  X -> Y Z          given
    2  Y Z -> Y          reflexivity
    3  X -> Y            transitivity on 1 and 2
       and likewise for Z

  Union and decomposition are inverses. Together they mean
  the RIGHT hand side of a dependency can always be split
  or combined freely - a fact used constantly in Phase 8.

  WARNING: this freedom applies to the RIGHT side only.
  X Y -> Z does NOT give X -> Z. The left side cannot be
  split, and assuming otherwise is the classic error.

6. Pseudo transitivity

  If  X -> Y  and  W Y -> Z   then   W X -> Z

  DERIVATION
    1  X -> Y            given
    2  W Y -> Z          given
    3  W X -> W Y        augment 1 with W
    4  W X -> Z          transitivity on 3 and 2

The complete summary

#	Rule	Statement	Type
1	Reflexivity	Y subset of X gives X -> Y	Primary
2	Augmentation	X -> Y gives XZ -> YZ	Primary
3	Transitivity	X -> Y, Y -> Z gives X -> Z	Primary
4	Union	X -> Y, X -> Z gives X -> YZ	Secondary
5	Decomposition	X -> YZ gives X -> Y and X -> Z	Secondary
6	Pseudo transitivity	X -> Y, WY -> Z gives WX -> Z	Secondary

Worked derivation

  Given  F = { A -> B, B C -> D, A -> C }
  Prove  A -> D

    1  A -> B            given
    2  A -> C            given
    3  A -> B C          union of 1 and 2
    4  B C -> D          given
    5  A -> D            transitivity on 3 and 4

  CHECK WITH CLOSURE
    A+ : { A }
         A -> B    add B    { A, B }
         A -> C    add C    { A, B, C }
         B C -> D  add D    { A, B, C, D }
    A+ = { A, B, C, D }, and D is in it.  Confirmed.

Closure and the axioms always agree, because the axioms are complete. In an exam, use closure to find the answer quickly and the axioms to write the proof when one is demanded.

F plus — the closure of a dependency set

F+ is the set of all dependencies derivable from F. It is usually enormous, so it is never written out. When a question asks whether a dependency is in F+, compute a closure instead — that is exactly what the shortcut is for.

Common mistakes

Splitting the left hand side. X Y -> Z does not give X -> Z. Decomposition works on the right only.
Augmenting only one side. The same Z must be added to both.
Using transitivity when the middle sets do not match. X -> Y and Z -> W combine only if Y contains Z, and then via pseudo transitivity.
Confusing sound and complete. Sound means nothing false is produced; complete means nothing true is missed.
Trying to enumerate F plus. It grows exponentially. Use closure.

Exam and interview questions

State the three primary Armstrong axioms with an example of each.
What do sound and complete mean, and why do both matter?
Derive the union rule from the primary axioms.
Derive the decomposition rule from the primary axioms.
Why can the right hand side be split but not the left?

Practice

Given F = { A -> B C, C D -> E, B -> D }, prove A -> E using the axioms, then confirm with closure.
Derive pseudo transitivity from the primary axioms.
Show that A B -> C does not imply A -> C, using a two tuple counterexample.
Given F = { A -> B, B -> C }, list five dependencies in F plus.

Conclusion

Reflexivity, augmentation and transitivity are sound and complete; union, decomposition and pseudo transitivity are convenient shortcuts derived from them. Use closure to get answers fast, and the axioms when a written proof is required — and never split a left hand side.

Topics #Advanced #DBMS #Functional Dependency #Interview #Placement

Written by Lorens Mishra

Default administrator account created by the installer.