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?"

Practice

1. What does the functional dependency X -> Y mean in a database?

easy

A. Knowing X allows you to find Y uniquely

B. X and Y are unrelated data sets

C. Y determines X uniquely

D. X and Y are always equal

Solution

1. Step 1: Understand the notation X -> Y

   This notation means that the value of X determines the value of Y uniquely in the database.

2. Step 2: Interpret the meaning in simple terms

   If you know X, you can find Y without ambiguity. This is the core idea of functional dependency.

3. Final Answer:

   Knowing X allows you to find Y uniquely -> Option A

4. Quick Check:

   Functional dependency means X determines Y [OK]

Hint: Remember: X determines Y means knowing X gives Y [OK]

Common Mistakes:

• Confusing which attribute determines which
• Thinking X and Y are unrelated
• Assuming dependency means equality

2. Which of the following is the correct way to write a functional dependency?

easy

A. X -> Y

B. X = Y

C. X <-> Y

D. X + Y

Solution

1. Step 1: Recall the standard notation for functional dependency

   The correct notation uses an arrow pointing from X to Y, written as X -> Y.

2. Step 2: Eliminate incorrect options

   X = Y means equality, X <-> Y suggests bidirectional dependency, and X + Y is not a valid notation here.

3. Final Answer:

   X -> Y -> Option A

4. Quick Check:

   Functional dependency uses arrow notation [OK]

Hint: Look for arrow notation X -> Y for functional dependency [OK]

Common Mistakes:

• Using equals sign instead of arrow
• Confusing bidirectional with functional dependency
• Using plus sign mistakenly

3. Given a table with columns StudentID and StudentName, which functional dependency is correct?

medium

A. StudentName -> StudentID

B. StudentID -> StudentName

C. StudentID -> StudentID

D. StudentName -> StudentName

Solution

1. Step 1: Identify the unique identifier

   Usually, StudentID uniquely identifies a student, so it determines StudentName.

2. Step 2: Check the direction of dependency

   Knowing StudentID gives StudentName, but not necessarily the other way around.

3. Final Answer:

   StudentID -> StudentName -> Option B

4. Quick Check:

   Unique ID determines name [OK]

Hint: Unique keys determine other attributes [OK]

Common Mistakes:

• Assuming name uniquely identifies ID
• Confusing attribute roles
• Ignoring uniqueness of StudentID

4. Identify the error in this functional dependency statement: EmployeeName -> EmployeeID where EmployeeID is unique.

medium

A. EmployeeName must be numeric

B. EmployeeID cannot be unique

C. Functional dependency must be bidirectional

D. EmployeeName may not uniquely determine EmployeeID

Solution

1. Step 1: Understand uniqueness of EmployeeID

   EmployeeID is unique, so it can determine EmployeeName, but not vice versa.

2. Step 2: Analyze the given dependency

   EmployeeName may repeat for different employees, so it cannot uniquely determine EmployeeID.

3. Final Answer:

   EmployeeName may not uniquely determine EmployeeID -> Option D

4. Quick Check:

   Non-unique attribute cannot determine unique ID [OK]

Hint: Only unique attributes determine others [OK]

Common Mistakes:

• Assuming all attributes are unique
• Thinking dependency is always two-way
• Confusing attribute types

5. In a database, if A -> B and B -> C, what can we conclude about the functional dependency between A and C?

hard

A. B -> A

B. C -> A

C. A -> C

D. C -> B

Solution

1. Step 1: Understand transitive dependency

   If A determines B, and B determines C, then A determines C by transitivity.

2. Step 2: Apply the rule to given dependencies

   Since A -> B and B -> C, it follows that A -> C.

3. Final Answer:

   A -> C -> Option C

4. Quick Check:

   Functional dependencies are transitive [OK]

Hint: Chain dependencies to find indirect ones [OK]

Common Mistakes:

• Reversing dependency direction
• Ignoring transitive property
• Confusing attributes order