Closure of attributes in DBMS Theory - Time & Space Complexity

Time Complexity: Closure of attributes

O(n^3)

Understanding Time Complexity

When working with database attributes, finding the closure helps us know all attributes we can get from a starting set.

We want to understand how the time needed grows as the number of attributes and rules increases.

Scenario Under Consideration

Analyze the time complexity of the following closure calculation.

-- Given a set of attributes and functional dependencies
-- Find closure of attribute set X
closure = X
repeat
  for each functional dependency (A -> B):
    if A is subset of closure and B not in closure:
      add B to closure
until no new attributes added
    

This code finds all attributes reachable from X using the given rules.

Identify Repeating Operations

Look for loops and repeated checks.

• Primary operation: Checking each functional dependency repeatedly.
• How many times: Until no new attributes are added, potentially multiple passes over all dependencies.

How Execution Grows With Input

As the number of attributes and dependencies grows, the checks increase.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the number of attributes and dependencies.

Common Mistake

[X] Wrong: "The closure calculation finishes in linear time because we just check each dependency once."

[OK] Correct: We often need to check dependencies multiple times as new attributes get added, so the process repeats until no changes occur.

Interview Connect

Understanding how closure calculation scales helps you explain database normalization and dependency analysis clearly in interviews.

Self-Check

"What if we stored dependencies in a way that lets us quickly find which ones apply? How would that affect the time complexity?"