Home » DBMS

Armstrong's Axioms in Functional Dependency | DBMS

In this tutorial, we are going to learn about Armstrong's Axiom in Function Dependency in Database Management System.
Submitted by Anushree Goswami, on August 13, 2019

Armstrong axioms are a complete set of inference rules or axioms, introduced and developed by William W. Armstrong in 1974. The inference rules are sound which is used to test logical inferences of functional dependencies. The axiom which also refers to as sound is used to infer all the functional dependencies on a relational database. The Axioms are a set of rules, that when applied to a specific set, generates a closure of functional dependencies.

Armstrong's Axioms has two different set of rules,

  1. Axioms or primary rules
    1. Axiom of Reflexivity
    2. Axiom of Augmentation
    3. Axiom of Transitivity
  2. Additional rules or Secondary rules
    1. Union
    2. Composition
    3. Decomposition
    4. Pseudo Transitivity

1) Axioms or primary rules

Let suppose T (k) with the set of attributes k be a relation scheme. Subsequently, we will represent subsets of k as A, B, C. The standard notation in database theory for the set of attributes is AB rather than A∪B.

  1. Axiom of Reflexivity:
    If a set of attributes is P and its subset is Q, then P holds Q. If Q ⊆ P, then P → Q. This property is called as Trivial functional dependency. Where P holds Q (P → Q) denote P functionally decides Q.
  2. Axiom of Augmentation:
    If P holds Q (P → Q) and R is a set of attributes, then PR holds QR (PR → QR). It means that a change in attributes in dependencies does not create a change in basic dependencies. If P → Q, then PR → QR for any R.
  3. Axiom of Transitivity:
    If P holds Q (P → Q) and Q holds R (Q → R), then P hold R (P → R). Where P holds R (P → R) denote P functionally decides R, same with P holds Q and Q holds R.

2) Additional rules or secondary rules

These rules can be derived from the above axioms.

  1. Union:
    If P holds Q (P → Q) and P holds R (P → R), then P → QR. If X → Y and X → Z, then X → YZ.
  2. Composition:
    If P holds Q (P → Q) and A holds B (A → B), then PA → QB.
    1. P → Q (Given)
    2. A → B (Given)
    3. PA → QA (Augmentation of 1 and A)
    4. PA → Q (Decomposition of 3)
    5. PA → PB (Augmentation of 2 and P)
    6. PA → B (Decomposition of 5)
    7. PA → QB (Union 4 and 6)
  3. Decomposition:
    This rule is contrary of union rule. If P → QR, then P holds Q (P → Q) and P holds R (P → R). If X → YZ, then X → Y and X → Z.
    1. P → QR (Given)
    2. QR → Q (Reflexivity)
    3. P → Q (Transitivity of 1 and 2)
  4. Pseudo Transitivity:
    If P → RQ and Q → S, then P → RS.
    1. P → RQ (Given)
    2. Q → S (Given)
    3. RQ → RS (Augmentation of 2 and R)
    4. P → RS (Transitivity of 1 and 3)

Trivial Functional Dependency

Trivial If P holds Q (P → Q), where P is a subset of Q, then it is called a Trivial Functional Dependency. Trivial always holds Functional Dependency.
Non-Trivial If P holds Q (P → Q), where Q is not a subset of P, then it is called as a Non-Trivial Functional Dependency.
Completely Non-Trivial If P holds Q (P → Q), where P intersect Y = Φ, it is called as a Completely Non-Trivial Functional Dependency.


Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© some rights reserved.