Armstrong's axioms in DBMS Theory - Step-by-Step Execution

Concept Flow - Armstrong's axioms

Start with given FDs

↓

Apply Reflexivity

↓

Apply Augmentation

↓

Apply Transitivity

↓

Add new FDs

↓

Repeat until no new FDs

↓

Closure of FDs

Armstrong's axioms are a set of rules applied repeatedly to find all functional dependencies implied by a given set.

Execution Sample

DBMS Theory

Given FDs: A -> B, B -> C
Apply Transitivity: A -> C

Shows how to derive new functional dependencies using Armstrong's axioms.

Analysis Table

Step	Rule Applied	Input FDs	New FD Derived	Explanation
1	Given	A -> B, B -> C	None	Start with initial functional dependencies
2	Transitivity	A -> B, B -> C	A -> C	Since A determines B and B determines C, A determines C
3	Reflexivity	A -> B, B -> C, A -> C	A -> A	Every attribute determines itself
4	Augmentation	A -> B	AC -> BC	Adding attribute C to both sides of A -> B
5	Augmentation	B -> C	AB -> AC	Adding attribute A to both sides of B -> C
6	No new FDs	All above	None	No further dependencies can be derived
Exit	Termination			No new functional dependencies found, closure complete

💡 No new functional dependencies can be derived, so the process stops.

State Tracker

Functional Dependencies	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
FD Set	A->B, B->C	A->B, B->C, A->C	A->B, B->C, A->C, A->A	A->B, B->C, A->C, A->A, AC->BC	A->B, B->C, A->C, A->A, AC->BC, AB->AC	A->B, B->C, A->C, A->A, AC->BC, AB->AC

Key Insights - 3 Insights

Why do we add A->A using Reflexivity when it seems obvious?

Reflexivity states every attribute determines itself; including A->A ensures completeness and helps in further derivations as shown in step 3.

How does Augmentation work when adding attributes to both sides?

Augmentation adds the same attribute(s) to both sides of a FD, preserving the dependency; see steps 4 and 5 where C or A is added to both sides.

When do we stop applying Armstrong's axioms?

We stop when no new functional dependencies can be derived, as shown in step 6 and the exit note.

Visual Quiz - 3 Questions

Look at the execution table at step 2, what new functional dependency is derived?

A A -> C

B B -> A

C C -> A

D C -> B

💡 Hint

Check the 'New FD Derived' column in step 2 of the execution table.

At which step is the Augmentation rule first applied?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look for the first occurrence of 'Augmentation' in the 'Rule Applied' column.

According to the variable tracker, what is the FD set after step 5?

A A->B, B->C, A->C

B A->B, B->C, A->C, A->A

C A->B, B->C, A->C, A->A, AC->BC, AB->AC

D A->B, B->C

💡 Hint

Check the 'After Step 5' column in the variable tracker for the FD set.

Concept Snapshot

Armstrong's axioms are rules to find all functional dependencies:
1. Reflexivity: If B ⊆ A, then A -> B
2. Augmentation: If A -> B, then AC -> BC
3. Transitivity: If A -> B and B -> C, then A -> C
Apply repeatedly until no new dependencies appear.

Full Transcript

Armstrong's axioms are a set of three rules used in database management to find all functional dependencies implied by a given set. The rules are Reflexivity, Augmentation, and Transitivity. Starting with initial functional dependencies, we apply these rules step-by-step to derive new dependencies. For example, from A->B and B->C, we derive A->C by Transitivity. We also add trivial dependencies like A->A by Reflexivity. Augmentation allows adding attributes to both sides of a dependency. This process repeats until no new dependencies can be found, resulting in the closure of the functional dependencies.

Practice

1. Which of the following is NOT one of Armstrong's axioms used in database theory?

easy

A. Reflexivity

B. Augmentation

C. Transitivity

D. Normalization

Solution

1. Step 1: Recall Armstrong's axioms

   Armstrong's axioms include Reflexivity, Augmentation, and Transitivity.

2. Step 2: Identify the option not in the axioms

   Normalization is a database design process, not an axiom.

3. Final Answer:

   Normalization -> Option D

4. Quick Check:

   Armstrong's axioms exclude Normalization [OK]

Hint: Remember the three axioms: Reflexivity, Augmentation, Transitivity [OK]

Common Mistakes:

• Confusing normalization with axioms
• Thinking all database terms are axioms
• Mixing up augmentation with normalization

2. Which Armstrong's axiom states that if Y is a subset of X, then X functionally determines Y?

easy

A. Reflexivity

B. Transitivity

C. Augmentation

D. Decomposition

Solution

1. Step 1: Understand the axiom definitions

   Reflexivity states if Y is subset of X, then X determines Y.

2. Step 2: Match the statement to the axiom

   The given statement matches Reflexivity exactly.

3. Final Answer:

   Reflexivity -> Option A

4. Quick Check:

   Subset implies functional dependency by Reflexivity [OK]

Hint: Subset implies dependency = Reflexivity [OK]

Common Mistakes:

• Confusing reflexivity with transitivity
• Choosing decomposition which is not an axiom
• Mixing augmentation with reflexivity

3. Given the functional dependencies: A -> B and B -> C, what can we infer using Armstrong's axioms?

medium

A. A -> C

B. B -> A

C. C -> A

D. C -> B

Solution

1. Step 1: Identify the given dependencies

   We have A determines B, and B determines C.

2. Step 2: Apply Transitivity axiom

   Transitivity says if A -> B and B -> C, then A -> C.

3. Final Answer:

   A -> C -> Option A

4. Quick Check:

   Transitivity gives A -> C [OK]

Hint: Chain dependencies to find indirect ones using Transitivity [OK]

Common Mistakes:

• Reversing dependencies incorrectly
• Ignoring transitivity rule
• Assuming dependencies go backward

4. Identify the error in this application of Armstrong's axioms: Given A -> B, the conclusion is B -> A.

medium

A. Correct use of augmentation

B. Proper use of reflexivity

C. Mistakenly reversed dependency

D. Valid transitivity application

Solution

1. Step 1: Analyze the given dependency

   A -> B means A determines B, not the other way around.

2. Step 2: Check the conclusion

   Concluding B -> A reverses the dependency, which Armstrong's axioms do not allow.

3. Final Answer:

   Mistakenly reversed dependency -> Option C

4. Quick Check:

   Dependencies do not reverse automatically [OK]

Hint: Dependencies don't reverse unless explicitly stated [OK]

Common Mistakes:

• Assuming dependencies are symmetric
• Confusing augmentation with reversal
• Ignoring direction of functional dependency

5. If you have A -> B and A -> C, which Armstrong's axiom allows you to combine these into A -> BC?

hard

A. Transitivity

B. Union

C. Decomposition

D. Augmentation

Solution

1. Step 1: Understand the given dependencies

   A determines B and A determines C separately.

2. Step 2: Apply the Union axiom

   Union allows combining A -> B and A -> C into A -> BC.

3. Final Answer:

   Union -> Option B

4. Quick Check:

   Union combines dependencies into one [OK]

Hint: Combine dependencies with same left side using Union [OK]

Common Mistakes:

• Confusing union with augmentation
• Using decomposition instead of union
• Applying transitivity incorrectly here