Functional dependency definition in DBMS Theory - Time & Space Complexity

Time Complexity: Functional dependency definition

O(n)

Understanding Time Complexity

We want to understand how the time to check a functional dependency grows as the data size increases.

Specifically, how does the number of operations change when verifying if one attribute determines another?

Scenario Under Consideration

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

-- Assume a table with columns A and B
-- Check if A functionally determines B
SELECT A, COUNT(DISTINCT B) AS distinct_B_count
FROM table_name
GROUP BY A
HAVING COUNT(DISTINCT B) > 1;
    

This query groups rows by attribute A and counts distinct B values for each group to find violations of the dependency.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Scanning all rows and grouping by attribute A.
• How many times: Each row is processed once, but grouping requires comparing and counting distinct B values per group.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 row scans and grouping steps
100	About 100 row scans and grouping steps
1000	About 1000 row scans and grouping steps

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 in the table.

Common Mistake

[X] Wrong: "Checking a functional dependency only looks at a few rows, so it's very fast regardless of data size."

[OK] Correct: The check must examine all rows to be sure no violations exist, so time grows with data size.

Interview Connect

Understanding how data size affects dependency checks helps you reason about database design and query efficiency in real projects.

Self-Check

"What if the table is already indexed on attribute A? How would the time complexity change?"