Armstrong Axioms

Ankit Kumar
Last Updated: May 13, 2022

Introduction

In the article, we will learn about the various Armstrong Axioms used to infer all the functional dependencies on a relational database. Then we will be checking out some secondary rules based on the Axioms and their proofs. 

Functional Dependencies

A functional dependency is a constraint between two sets of attributes in a database relation in relational database theory. A functional dependency, in other terms, is a constraint between two qualities in a relation.

If attribute A functionally determines attribute B, it is written as AB.

  1. Trivial Functional Dependency: A functional dependency AB is trivial only when B is a subset of A.
    Example: 
    ABC→A
    AB→B
    ABC→ABC
  2. Non Trivial Functional Dependency: AB is a functional dependency when B is not a subset of A.
    It is called completely non-trivial when AB is NULL.
  3. Semi Non-Trivial Functional Dependency: AB is non-trivial when AB is not NULL.

Armstrong axioms

Armstrong's axioms are a set of references (or, more precisely, inference rules) for inferring all of a relational database's functional dependencies. In a paper published in 1974, William W. Armstrong developed them.  When applied to a set of functional dependencies (denoted as F+), the axioms are sound in generating only functional dependencies in the closure of that set (denoted as F). They're also complete in the sense that applying these rules repeatedly will cause all functional dependencies in the closure F+.

Axioms

  1. Axiom of reflexivity:
    Let A be a set of attributes, and B is a subset of A. If B⊆A then A→B. This property is Trivial property.
  2. Axiom of augmentation:
    If A→B is true and Y is an attribute set, then AY→BY is also true. Adding attributes to dependencies does not affect the fundamental dependencies. If A→B is true, AC→BC is true for any C.
  3. Axiom of transitivity:If A→B holds and B→C holds, then A→C also holds, similar to the transitive rule in Algebra. Functionally, A→B is referred to as A, which determines B. If X→Y and Y→Z are true, X→Y is true.

Secondary Rules

  1. Decomposition

If A→BC, then A→B and A→C

Proof:

A→BC (given)_______________ (i)

BC→B (reflexivity)____________ (ii)

A→B (transitivity from i and ii)

2. Composition

If A→B and C→D then AC→BD

Proof

A→B_________(i)

C→D_________(ii)

AC→BC________(iii) (Augmentation of i and C)

AC→B________(iv) Decomposition of iii)

AC→AD_______(v) (Augmentation of ii and A)

AC→D___________(vi) (Decomposition of v)

AC→BD________ (Union iv and vi)

3. Union (Notation)

If A→B and A→C then A→BC

Proof

A→B________(i) (given)

A→C________(ii) (given)

A→AC_______(iii) (Augmentation of ii and A)

AC→BC______(iv) (Augmentation of i and C)

A→BC________(transitivity of iii and ii)

4. Pseudo transitivity

If A→B and BC→D then AC→D

Proof

A→B__________(i) (Given)

BC→D________(ii) (Given)

AC→BC_______(iii) (Augmentation of i and C)

AC →D_________(Transitivity of iii and ii)

5. Self-determination

A→A for any given A.

This rule directly follows the Axiom of Reflexivity.

6. Extensivity

Extensivity is a particular case of augmentation where C=A

If A→B, then A→AB

In the sense that augmentation can be proven from extensivity and other axioms, extensivity can replace augmentation as an axiom.

Proof

AC→A____(i)

A→B________(ii)

AC→B________(iii) (Transitivity of i and ii)

AC→ABC_______(iv) (Extensivity of iii)

ABC→BC______(v) (Reflexivity)

AC→BC (Transitivity of iv and v)

Armstrong Relation

An Armstrong relation is a relation that satisfies all of the functional dependencies in the closure F+ and only those dependencies, given a set of functional dependencies F. Unfortunately, for a given set of dependencies, the minimum-size Armstrong relation can have a size that is an exponential function of the number of attributes in the dependencies under consideration.

Why do the Sound and Complete axioms appear in the Armstrong axioms?

By sound, we mean that any dependency may be stated on a relation schema R given a set of functional dependencies F specified on a relation schema R, any dependency inferred from F using the Armstrong axioms primary rules holds in every relation state r of R that satisfies the dependencies in F.

By complete, we mean that repeatedly inferring dependencies using primary Armstrong axioms until no more dependencies can be inferred results in the complete set of all possible dependencies implied from F.

Frequently Asked questions

  1. For what purpose are the Armstrong Axioms used?
    The axioms of Armstrong are used to determine the functional dependencies of a relational database. A type of assertion is the inference rule. It can e used to derive other FDs from a set of FDs (functional dependencies). The inference rule can derive additional functional dependency from the initial stage.
     
  2. What are the primary rules of Armstrong Axioms?
    Following are the primary rules of Armstrong Axioms:
    1. Reflexivity
    2. Augmentation
    3. Transitivity
    We have already covered the Axioms in detail in the above article.
     
  3. What is the purpose of inference rules?
    The templates or instructions for creating valid arguments from the statements we currently know are provided by Rules of Inference.

Key takeaways

In the article, we discussed functional dependencies briefly and what Armstrong Axioms are. We saw various axioms included in Armstrong Axioms. And then, we looked into different secondary rules based on the axioms and their proofs.

Ninja, don't stop here; check out the Top 100 SQL Problems to get hands-on experience with frequently asked interview questions and land your dream job. Also, try CodeStudio to practice programming problems for your complete interview preparation.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think