What are Armstrong’s Axioms in DBMS?

Last Updated on June 23, 2023 by Prepbytes

This article will explore the different Armstrong Axioms employed to deduce all the functional dependencies in a relational database. Subsequently, we will examine additional rules derived from these Axioms, along with their corresponding proofs.

What are Armstrong’s Axioms in DBMS?

Armstrong’s axioms, introduced by William W. Armstrong in 1974, are a set of inference rules utilized to deduce all the functional dependencies within a relational database. These rules, when applied to a set of functional dependencies denoted as F+, are both sound, ensuring that only dependencies within the closure set F are generated, and complete, meaning that applying these rules iteratively will derive all functional dependencies within the closure F+.

Types of Axioms

There are 3 types of Axioms:

1. Reflexivity Axiom:
   For a set of attributes A and a subset B of A, if B is a subset of A (B⊆A), then A→B. This axiom represents a trivial property where a set of attributes implies itself.

2. Augmentation Axiom:
   If A→B is true and Y is a set of attributes, then AY→BY is also true. This axiom demonstrates that adding attributes to dependencies does not alter the fundamental dependencies. If A→B holds, AC→BC holds for any set of attributes C.

3. Transitivity Axiom:
   If A→B holds and B→C holds, then A→C also holds, similar to the transitive rule in algebra. Functionally, it means that if A determines B and B determines C, then A determines C. If X→Y and Y→Z are true, then X→Z is also true.

Rules of Axioms

Below are the rules of Axioms in DBMS:

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)

What is Armstrong Relation in DBMS?

An Armstrong relation refers to a relation that satisfies all the functional dependencies present in the closure F+ and no other dependencies, based on a given set of functional dependencies F. However, it is worth noting that for a given set of dependencies, the smallest possible Armstrong relation can have a size that grows exponentially with the number of attributes in the dependencies being considered.

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

When we say that the Armstrong axioms are sound, it implies that any dependency that can be stated on a relation schema R, based on a set of functional dependencies F specified on the same relation schema R, will hold true in every relation state r of R that satisfies the dependencies in F. In other words, any dependency inferred from F using the primary rules of the Armstrong axioms will be valid in all applicable relation states.

On the other hand, when we say that the Armstrong axioms are complete, it means that repeatedly inferring dependencies using the primary Armstrong axioms until no further dependencies can be deduced will yield the complete set of all possible dependencies implied from F. This ensures that we have derived all the relevant dependencies that can be inferred from the given set of functional dependencies.

Conclusion
Armstrong’s axioms are a set of inference rules used in database management systems (DBMS) to deduce all the functional dependencies within a relational database. These axioms provide a systematic approach to deriving additional dependencies based on a given set of functional dependencies. The axioms are both sound, ensuring that the derived dependencies hold true in all valid relation states, and complete, guaranteeing that applying the axioms repeatedly will result in the complete set of all implied dependencies.

FAQs related to Armstrong Axioms in DBMS

Q1. What is the significance of Armstrong’s axioms in DBMS?
Armstrong’s axioms play a crucial role in the design, normalization, and analysis of relational databases. They provide a formal framework to identify and derive functional dependencies, which are essential for maintaining data integrity and designing efficient database schemas.

Q2. How are Armstrong’s axioms applied in DBMS?
In DBMS, Armstrong’s axioms are used to infer additional functional dependencies from a given set of functional dependencies. By repeatedly applying the axioms, one can systematically derive all the dependencies that hold in the database schema.

Q3. Can Armstrong’s axioms generate incorrect dependencies?
Armstrong’s axioms are sound, meaning that the dependencies they generate hold true in all valid relation states. However, if the initial set of functional dependencies is incorrect or incomplete, the derived dependencies may also be incorrect or incomplete.

Q4. Are Armstrong’s axioms limited to specific types of databases?
No, Armstrong’s axioms are applicable to any relational database. They are independent of the specific database management system and can be used in the normalization and analysis of databases across different domains and industries.

Q5. Are there any limitations to the use of Armstrong’s axioms?
One limitation of Armstrong’s axioms is that the size of the minimum Armstrong relation can grow exponentially with the number of attributes in the dependencies being considered. This can pose challenges in terms of storage requirements and computational complexity for large databases.

Q6. Are there any alternative methods to derive functional dependencies?
Apart from Armstrong’s axioms, there are other methods to derive functional dependencies, such as the closure algorithm and the attribute closure method. These methods use different approaches but aim to achieve the same goal of identifying all the functional dependencies in a database schema.