Why functional dependencies guide schema design in DBMS Theory - Performance Analysis

Time Complexity: Why functional dependencies guide schema design

O(n)

Understanding Time Complexity

We want to understand how the time to check or use functional dependencies changes as the data grows.

How does the work needed to keep data consistent grow when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of checking a functional dependency in a table.

-- Check if attribute B functionally depends on A in table T
SELECT A, COUNT(DISTINCT B) AS distinct_B
FROM T
GROUP BY A
HAVING COUNT(DISTINCT B) > 1;
    

This query finds if any value of A maps to more than one value of B, violating the dependency A -> B.

Identify Repeating Operations

Look at what repeats as the table size grows.

• Primary operation: Scanning all rows in the table to group by A.
• How many times: Once over all rows, but grouping requires comparing and counting values per group.

How Execution Grows With Input

As the number of rows grows, the database must process more data to group and count.

Input Size (n)	Approx. Operations
10	About 10 rows scanned and grouped
100	About 100 rows scanned and grouped
1000	About 1000 rows scanned and grouped

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the functional dependency grows linearly with the number of rows.

Common Mistake

[X] Wrong: "Checking functional dependencies is instant no matter the data size."

[OK] Correct: The database must look at all rows to be sure, so more data means more work.

Interview Connect

Understanding how data size affects dependency checks helps you design efficient databases and explain your reasoning clearly.

Self-Check

"What if the table had an index on attribute A? How would that change the time complexity of checking the functional dependency?"