Armstrong's axioms in DBMS Theory - Time & Space Complexity

Time Complexity: Armstrong's axioms

O(n^3)

Understanding Time Complexity

We want to understand how the time to find all functional dependencies grows when using Armstrong's axioms.

How does the number of steps change as the number of attributes and dependencies increases?

Scenario Under Consideration

Analyze the time complexity of applying Armstrong's axioms to find all implied functional dependencies.

-- Given a set of functional dependencies (FDs)
-- Apply Armstrong's axioms: reflexivity, augmentation, transitivity
-- Repeat until no new FDs are found
WHILE new FDs are added DO
  FOR each FD X -> Y DO
    FOR each FD W -> Z DO
      IF Y includes W THEN
        Add FD X -> Z
      END IF
    END FOR
  END FOR
END WHILE

This process finds all functional dependencies implied by the initial set using Armstrong's axioms.

Identify Repeating Operations

Look for loops and repeated checks in the process.

• Primary operation: Nested loops comparing pairs of functional dependencies.
• How many times: Repeated until no new dependencies are added, potentially many times.

How Execution Grows With Input

As the number of attributes and dependencies grows, the number of pairs to check grows quickly.

Input Size (number of FDs)	Approx. Operations
10	About 100 checks per iteration
100	About 10,000 checks per iteration
1000	About 1,000,000 checks per iteration

Pattern observation: The number of operations grows roughly with the square of the number of dependencies.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to find all implied dependencies grows roughly with the cube of the number of initial dependencies.

Common Mistake

[X] Wrong: "Applying Armstrong's axioms takes linear time because we just check each dependency once."

[OK] Correct: The process repeats many times and compares pairs of dependencies, causing the time to grow much faster than linear.

Interview Connect

Understanding how Armstrong's axioms scale helps you reason about database design and normalization efficiently in real projects.

Self-Check

"What if we had a way to avoid rechecking all pairs every time? How would that affect the time complexity?"

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