Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What are Armstrong’s Axioms in DBMS?
3.
Types of Axioms
3.1.
1. Axiom of reflexivity
3.2.
2. Axiom of augmentation
3.3.
3. Axiom of transitivity
4.
Secondary Rules
4.1.
1. Decomposition
4.2.
2. Composition
4.3.
3. Union (Notation)
4.4.
4. Pseudo transitivity
4.5.
5. Self-determination
4.6.
6. Extensivity
5.
Armstrong Relation
6.
Why do the Sound and Complete axioms appear in the Armstrong axioms?
7.
Functional Dependencies
8.
Advantages of Using Armstrong’s Axioms in Functional Dependency
9.
Disadvantages of Using Armstrong’s Axioms in Functional Dependency
10.
Frequently Asked Questions
10.1.
What are the primary rules of Armstrong Axioms?
10.2.
What are Armstrong's axioms in DBMS?
10.3.
What is the Armstrong theorem in DBMS?
10.4.
How do you prove Union Armstrong's axioms?
11.
Conclusion
Last Updated: Mar 27, 2024
Easy

Armstrong’s Axioms in DBMS

Author Ankit Kumar
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Welcome to our blog, where we delve into Armstrong’s Axioms in Functional Dependency in DBMS! Armstrong’s Axioms are essential rules used in database management systems to derive new functional dependencies from existing ones. Understanding these axioms is crucial for designing efficient databases and ensuring data integrity. 

Armstrong’s Axioms in DBMS

What are Armstrong’s Axioms in DBMS?

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+.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Types of 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.

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.

Advantages of Using Armstrong’s Axioms in Functional Dependency

The advantages of using Armstrong’s Axioms in Functional Dependency are:

  • Logical Deduction: Armstrong’s Axioms provide a systematic and logical approach to deducing new functional dependencies from given sets of functional dependencies. This helps in understanding the relationships between attributes in a database.
  • Normalization: By applying Armstrong’s Axioms, databases can be normalized efficiently, reducing redundancy and improving data integrity. This leads to better organization and management of data, enhancing overall database performance.
  • Query Optimization: Understanding functional dependencies using Armstrong’s Axioms can aid in query optimization by allowing for the creation of efficient indexes and data structures, leading to faster query execution times.
  • Data Integrity: By identifying and enforcing functional dependencies, Armstrong’s Axioms help maintain data integrity by ensuring that updates, inserts, and deletes adhere to the defined constraints, thereby minimizing inconsistencies in the database.

Disadvantages of Using Armstrong’s Axioms in Functional Dependency

The disadvantages of using Armstrong’s Axioms in Functional Dependency are:

  • Complexity: Understanding and applying Armstrong’s Axioms can be challenging, especially for complex databases with numerous attributes and dependencies. This complexity may lead to errors in identifying and implementing functional dependencies.
  • Computational Overhead: The process of deriving all possible functional dependencies using Armstrong’s Axioms can be computationally intensive, especially for large databases. This may result in increased processing time and resource utilization.
  • Limited Scope: Armstrong’s Axioms are primarily focused on determining functional dependencies based on given sets of attributes. However, they may not address all aspects of database design and optimization, such as performance tuning and data security.
  • Dependency Maintenance: As databases evolve over time, maintaining and updating functional dependencies using Armstrong’s Axioms can become cumbersome, especially when dealing with frequent schema changes or complex relationships between attributes.

Must Recommended Topic, Schema in DBMS

Frequently Asked Questions

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.

What are Armstrong's axioms in DBMS?

Armstrong's axioms are a set of rules used to derive functional dependencies in database management systems, helping to ensure data integrity and normalization.

What is the Armstrong theorem in DBMS?

The Armstrong theorem states that if a functional dependency X→Y holds in a relation, then it also implies other functional dependencies derivable from Armstrong's axioms.

How do you prove Union Armstrong's axioms?

To prove Union Armstrong's axioms, you typically apply the axioms systematically to the given set of functional dependencies, deriving new dependencies until no additional ones can be deduced.

Conclusion

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.

Recommended Reading - Canonical Cover In DBMS, Lock based protocol in DBMS

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 Coding Ninjas Studio to practice programming problems for your complete interview preparation.

Live masterclass