Neural Sync Active

14 - Functional Dependencies

Registry Synced

14 - Functional Dependencies

3402 words

17 min read

Reading compass

Now · 🎯 Learning Objectives

14 - Functional Dependencies

🎯 Learning Objectives

After reading this topic, you will be able to:

Define functional dependencies and explain why they matter
Apply Armstrong's axioms to derive implied FDs
Compute closure of a set of FDs (F⁺)
Compute attribute closure (α⁺) to find keys
Check equivalence of two FD sets
Find superkeys and candidate keys using attribute closure

📋 Prerequisites

03 - Relational Model — Relations, attributes, keys
Set theory basics (subsets, supersets)

📖 Core Content

14.1 Intuition: What Data Relationships Tell Us

A functional dependency (FD) describes a relationship between attributes in a relation. It says: If I know the value of attribute(s) X, I can determine the value of attribute(s) Y. Real-world examples:

{Aadhaar_number} → {name, DOB} — If I know your Aadhaar number, I know your name and date of birth
{student_id} → {student_name} — If I know your student ID, I know your name
{zip_code} → {city} — If I know the zip code, I know the city Formally: $X \rightarrow Y$ (read as "X determines Y" or "Y is functionally dependent on X")

Why This Matters: FDs are the foundation of normalization — the process of designing schemas that avoid data redundancy and anomalies. Understanding FDs is critical for good database design.

14.2 Formal Definition

Given relation

R

, a functional dependency

X \rightarrow Y

holds iff: For any two tuples

t_1

and

t_2

R

\text{if } t_1[X] = t_2[X] \text{ then } t_1[Y] = t_2[Y]

In plain English: "Whenever two rows have the same X value, they must also have the same Y value." Example: In instructor(ID, name, dept_name, salary), the FD

ID \rightarrow name

means: if two rows have the same ID, they MUST have the same name.

14.3 Trivial vs. Non-Trivial FDs

Type	Definition	Example	Always True?
Trivial	$X \rightarrow Y$ where $Y \subseteq X$	$A \rightarrow A$ , $AB \rightarrow A$	Yes
Non-trivial	$Y \nsubseteq X$	$ID \rightarrow name$	No (depends on data)
Completely non-trivial	$X \cap Y = \emptyset$	$ID \rightarrow name$	No

Trivial FDs are always true — they convey no useful information.

14.4 Armstrong's Axioms

Armstrong's axioms are a set of inference rules for deriving new FDs from existing ones. They're sound (every derived FD is true) and complete (every implied FD can be derived).

Rule	Name	Formal Definition	Example
1	Reflexivity	If $Y \subseteq X$ , then $X \rightarrow Y$	$AB \rightarrow A$
2	Augmentation	If $X \rightarrow Y$ , then $XZ \rightarrow YZ$	If $A \rightarrow B$ , then $AC \rightarrow BC$
3	Transitivity	If $X \rightarrow Y$ and $Y \rightarrow Z$ , then $X \rightarrow Z$	If $A \rightarrow B$ and $B \rightarrow C$ , then $A \rightarrow C$

Derived Rules

Rule	Derivation	Example
Union	If $X \rightarrow Y$ and $X \rightarrow Z$ , then $X \rightarrow YZ$	$A \rightarrow B$ and $A \rightarrow C$ → $A \rightarrow BC$
Decomposition	If $X \rightarrow YZ$ , then $X \rightarrow Y$ and $X \rightarrow Z$	$A \rightarrow BC$ → $A \rightarrow B$ and $A \rightarrow C$
Pseudotransitivity	If $X \rightarrow Y$ and $WY \rightarrow Z$ , then $WX \rightarrow Z$	$A \rightarrow B$ and $CB \rightarrow D$ → $CA \rightarrow D$

14.5 Closure of FD Sets (F⁺)

The closure of a set of FDs

F

, denoted

F^+

, is the set of ALL FDs that can be derived from

F

using Armstrong's axioms. Example: Given

F = \{A \rightarrow B, B \rightarrow C\}

, find

F^+

Start with F: $A \rightarrow B$ , $B \rightarrow C$
By transitivity: $A \rightarrow C$
By reflexivity: $A \rightarrow A$ , $B \rightarrow B$ , $C \rightarrow C$ , $AB \rightarrow A$ , etc.
By augmentation: $AB \rightarrow B$ , $AB \rightarrow BC$ , $AC \rightarrow BC$ , etc.
By union/decomposition: $A \rightarrow BC$ (from $A \rightarrow B$ and $A \rightarrow C$ )
Continue until no new FDs can be derived $F^+$ can be very large — up to $2^n$ FDs for n attributes. That's why we use attribute closure instead.

14.6 Attribute Closure (α⁺)

Instead of computing

F^+

(all FDs), we compute the attribute closure of a set of attributes

\alpha

: the set of ALL attributes that can be determined by

\alpha

. Algorithm:


pseudo
attribute_closure(α, F):
    result = α
    while result changes:
        for each FD X → Y in F:
            if X ⊆ result:
                result = result ∪ Y
    return result

Worked Example: Attribute Closure

Given

R(A, B, C, D, E)

and

F = \{A \rightarrow BC, CD \rightarrow E, B \rightarrow D\}

Compute $A^+$ :

result = {A}
$A \rightarrow BC$ : A ⊆ result? Yes → result = {A, B, C}
$B \rightarrow D$ : B ⊆ result? Yes → result = {A, B, C, D}
$CD \rightarrow E$ : CD ⊆ result? Yes → result = {A, B, C, D, E}
No more changes. $A^+ = {A, B, C, D, E}$ (all attributes!) Since $A^+$ contains all attributes, $A$ is a superkey.

14.7 Using Attribute Closure

Finding Candidate Keys

Method:

Find attributes that never appear on the RHS of any FD — they MUST be in every candidate key
Compute closure of these mandatory attributes
If closure covers all attributes, they form a candidate key
If not, add one attribute at a time and recompute Example: $R(A, B, C, D, E)$ with $F = \{A \rightarrow B, BC \rightarrow D, D \rightarrow E\}$ Step 1: Find mandatory attributes:

Attributes not on RHS: $A, C$ (A appears only on LHS; C appears on LHS but never on RHS) Step 2: Compute $\{A, C\}^+$ :
result = {A, C}
$A \rightarrow B$ : A ⊆ result → result = {A, B, C}
$BC \rightarrow D$ : BC ⊆ result → result = {A, B, C, D}
$D \rightarrow E$ : D ⊆ result → result = {A, B, C, D, E}
$\{A, C\}^+$ = ALL attributes! Step 3: $\{A, C\}$ is a candidate key (can we remove A? No, $C^+ = {C}$ . Can we remove C? No, $A^+ = {A, B} \neq R$ .) Result: Candidate key = $\{A, C\}$

Checking if an FD Holds

To check if

X \rightarrow Y

holds in

F

Compute $X^+$ using F
If $Y \subseteq X^+$ , then $X \rightarrow Y$ holds Example: Does $AB \rightarrow E$ hold in $F = \{A \rightarrow B, BC \rightarrow D, D \rightarrow E\}$ ?
Compute $\{A, B\}^+$ ${A, B}^{+}$ :
- result = {A, B}
- No FD applies (A→B applies but B is already there)
- Wait: $BC \rightarrow D$ needs C, which isn't in result
- $\{A, B\}^+ = {A, B}$
E ∉ {A, B}, so $AB \rightarrow E$ does NOT hold.

14.8 Equivalence of FD Sets

Two FD sets

F_1

and

F_2

are equivalent if

F_1^+ = F_2^+

(they have the same closure). Algorithm to check equivalence:

For each FD $X \rightarrow Y$ in $F_1$ , check if it holds in $F_2$ (using attribute closure with $F_2$ )
For each FD $X \rightarrow Y$ in $F_2$ , check if it holds in $F_1$
If all hold, $F_1$ and $F_2$ are equivalent Example: $F_1 = \{A \rightarrow B, B \rightarrow C\}$ $F_2 = \{A \rightarrow B, A \rightarrow C\}$ Check $A \rightarrow C$ in $F_1$ : $A^+$ using $F_1$ = {A, B, C}. C ⊆ $A^+$ ✓ Check $B \rightarrow C$ in $F_2$ : $B^+$ using $F_2$ = {B}. C ∉ $B^+$ ✗ $F_1$ and $F_2$ are NOT equivalent.

14.9 Worked Examples

Example 1: Finding Superkeys from Attribute Closure

Given

R(A, B, C, D, G)

and

F = \{A \rightarrow BCD, BC \rightarrow D, B \rightarrow D, D \rightarrow A\}

Prove

AG

is a superkey:

Compute $\{A, G\}^+$ ${A, G}^{+}$ :
- result = {A, G}
- $A \rightarrow BCD$ : A ⊆ result → result = {A, B, C, D, G}
- All attributes covered! $\{A, G\}^+$ = R
Therefore, $AG$ is a superkey.

Example 2: First way to find candidate keys

R(A, B, C, D)

with

F = \{A \rightarrow BCD, D \rightarrow A\}

Step 1: Attributes not on RHS: C appears on RHS of none → C is mandatory. Actually C doesn't appear on LHS of any FD, and isn't on RHS... Let me check:

A→BCD means A determines B,C,D
D→A means D determines A
C is never on RHS and never on LHS So C must be in every candidate key. Step 2: Compute $\{C\}^+$ : just {C}. Not all attributes. Step 3: Try $\{C, A\}^+$ :
result = {C, A}
$A \rightarrow BCD$ → result = {A, B, C, D} = R
$\{C, A\}$ is a superkey. Is it minimal? If we remove C, $A^+ = {A, B, C, D} = R$ , so A alone is sufficient. If we remove A, $C^+ = {C}$ . Wait, let me re-examine. A is on LHS, not on RHS... Actually A is never on RHS. So both A and C are mandatory? Let me check again: $F = \{A \rightarrow BCD, D \rightarrow A\}$ Attributes on RHS: B, C, D, A (from D→A) Attributes NOT on RHS: (none — A appears on RHS via D→A) Let me compute all candidate keys:
Compute $D^+$ $D^{+}$ :
- result = {D}
- $D \rightarrow A$ → {D, A}
- $A \rightarrow BCD$ → {A, B, C, D} = R
- So D is a candidate key.
Compute $A^+$ $A^{+}$ :
- result = {A}
- $A \rightarrow BCD$ → {A, B, C, D} = R
- So A is a candidate key. Candidate keys: {A} and {D}.

14.10 Tracing Table: Systematic Attribute Closure

The attribute closure algorithm is best understood with a tracing table. Let's work through a complex example. Given:

R(A, B, C, D, E, G)

and

F = \{A \rightarrow BCD, BC \rightarrow DE, B \rightarrow D, D \rightarrow A\}

Compute $AG^+$ :

Step	Result	FD Checked	FD Applies?	New Attributes
1	{A, G}	—	—	—
2	{A, G}	$A \rightarrow BCD$	Yes (A⊆{A,G})	B, C, D
3	{A, B, C, D, G}	$BC \rightarrow DE$	Yes (BC⊆result)	E
4	{A, B, C, D, E, G}	$B \rightarrow D$	Yes, but D already present	—
5	{A, B, C, D, E, G}	$D \rightarrow A$	Yes, but A already present	—
6	$\{A, B, C, D, E, G\} = R$	Done	—	All attributes!

Result:

AG^+ = R

, therefore

AG

is a superkey.

14.11 Complete Example: Finding All Candidate Keys

Given:

R(A, B, C, D, E, G)

and

F = \{AB \rightarrow CD, C \rightarrow E, E \rightarrow B, D \rightarrow G\}

Step 1: Identify mandatory attributes — those that never appear on RHS.

Attribute	Appears on RHS?	Mandatory in CK?
A	No (only in AB→CD LHS)	Yes
B	Yes (E→B)	No
C	Yes (AB→CD)	No
D	Yes (AB→CD)	No
E	Yes (C→E)	No
G	Yes (D→G)	No

A MUST be in every candidate key. Step 2: Compute

\{A\}^+

result = {A}
$AB \rightarrow CD$ : needs B (not in result) ✗
$C \rightarrow E$ : needs C ✗
$E \rightarrow B$ : needs E ✗
$D \rightarrow G$ : needs D ✗
$\{A\}^+ = \{A\}$ — not a superkey. Step 3: Add one attribute at a time. Try $\{A, B\}$ :

Step	Result	FD	New
1	{A, B}	—	—
2	{A, B}	$AB \rightarrow CD$	C, D
3	{A, B, C, D}	$C \rightarrow E$	E
4	{A, B, C, D, E}	$E \rightarrow B$	B (already)
5	{A, B, C, D, E}	$D \rightarrow G$	G
6	{A, B, C, D, E, G} = R	Done	✓

\{A, B\}^+ = R

. CK found:

\{A, B\}

. Try $\{A, C\}$ :

Step	Result	FD	New
1	{A, C}	—	—
2	{A, C}	$C \rightarrow E$	E
3	{A, C, E}	$E \rightarrow B$	B
4	{A, B, C, E}	$AB \rightarrow CD$	D
5	{A, B, C, D, E}	$D \rightarrow G$	G
6	{A, B, C, D, E, G} = R	Done	✓

\{A, C\}^+ = R

. CK found:

\{A, C\}

. Try $\{A, D\}$ :

Step	Result	FD	New
1	{A, D}	—	—
2	{A, D}	$D \rightarrow G$	G
3	{A, D, G}	No other FD applies	—

\{A, D\}^+ = \{A, D, G\} \neq R

. Not a superkey. Try $\{A, E\}$ :

Step	Result	FD	New
1	{A, E}	—	—
2	{A, E}	$E \rightarrow B$	B
3	{A, B, E}	$AB \rightarrow CD$	C, D
4	{A, B, C, D, E}	$D \rightarrow G$	G
5	{A, B, C, D, E, G} = R	Done	✓

\{A, E\}^+ = R

. CK found:

\{A, E\}

. Try $\{A, G\}$ :

Step	Result	FD	New
1	{A, G}	—	—
2	{A, G}	No FD has A or G alone on LHS	—

\{A, G\}^+ = \{A, G\} \neq R

. Not a superkey. Candidate keys:

\{A, B\}

\{A, C\}

\{A, E\}

Superkey count: With 6 attributes, three CKs of size 2, all sharing A:

= 2^{6-2} + 2^{6-2} + 2^{6-2} - 2^{6-3} - 2^{6-3} - 2^{6-3} + 2^{6-4}

= 16 + 16 + 16 - 8 - 8 - 8 + 4 = 28

superkeys

14.12 Practice: Attribute Closure Walkthrough

Problem: Given

F = \{A \rightarrow B, AC \rightarrow D, B \rightarrow C, D \rightarrow E\}

, compute

\{A\}^+

\{B\}^+

\{C\}^+

, and

\{A, C\}^+

. $\{A\}^+$ :

result = {A}
$A \rightarrow B$ → {A, B}
$B \rightarrow C$ → {A, B, C}
$AC \rightarrow D$ → {A, B, C, D}
$D \rightarrow E$ → {A, B, C, D, E}
Done. $\{A\}^+ = \{A, B, C, D, E\}$ $\{B\}^+$ :
result = {B}
$B \rightarrow C$ → {B, C}
No other FD applies (A not in result)
$\{B\}^+ = \{B, C\}$ $\{C\}^+$ :
result = {C}
No FD has C alone on LHS (AC→D needs A)
$\{C\}^+ = \{C\}$ $\{A, C\}^+$ :
result = {A, C}
$A \rightarrow B$ → {A, B, C}
$B \rightarrow C$ → {A, B, C} (C already there)
$AC \rightarrow D$ → {A, B, C, D}
$D \rightarrow E$ → {A, B, C, D, E}
Done. $\{A, C\}^+ = \{A, B, C, D, E\}$ Check: Is $\{A, C\}$ a candidate key? $\{A, C\}^+ = R$ . Is it minimal?

Remove A: $\{C\}^+ = \{C\} \neq R$ ✓ A needed
Remove C: $\{A\}^+ = \{A, B, C, D, E\} = R$ ! So A alone is a candidate key.
Final CK: $\{A\}$ only.

Concept	Description	Formula
Functional Dependency	X determines Y	$X \rightarrow Y$
Trivial FD	Y is subset of X	$Y \subseteq X$
Attribute Closure	All attributes determined by α	$\alpha^+$
Closure of F	All FDs derivable from F	$F^+$
Candidate Key	Minimal superkey	Any α where $\alpha^+ = R$ and no proper subset has closure = R

⚠️ Common Pitfalls

Pitfall 1: Thinking FDs are "One-to-One Mappings"

The Mistake: "X → Y means X maps to a unique Y like a function." Why It's Wrong: That's actually correct for our purposes, but students confuse it with "every X maps to exactly one Y" (which is always true in relations — each attribute has one value per tuple). The FD says: same X → same Y across different tuples. Correct: Think of it as: "If two tuples have the same X, they MUST have the same Y."

Pitfall 2: Confusing Attribute Closure with FD Closure

The Mistake: Using F⁺ and α⁺ interchangeably. Why It's Wrong:

$F^+$ = all FDs derivable from F (a set of FDs)
$\alpha^+$ = all attributes derivable from α (a set of attributes) Memory Aid: $F^+$ has a superscript + on the FD set; $\alpha^+$ has it on the attribute set.

Pitfall 3: Assuming Transitivity Works Backwards

The Mistake: "A → B and A → C implies B → C." Why It's Wrong: Transitivity requires a chain: X → Y and Y → Z gives X → Z. A → B and A → C mean both B and C are determined by A, but there's no relationship between B and C. Correct: From A → B and A → C, we can use UNION to get A → BC, then DECOMPOSITION to get back to A → B and A → C. But we cannot derive B → C.

📝 Practice Questions

Q1. What is a functional dependency? Give a real-world example.

Answer

A functional dependency $X \rightarrow Y$ means: if two tuples have the same value for attribute(s) X, they must have the same value for attribute(s) Y.

Real-world example: In a student table, $student_id \rightarrow student_name$ — any two rows with the same student_id must have the same student_name.

Q2. List Armstrong's three basic axioms.

Answer

Reflexivity: If $Y \subseteq X$ , then $X \rightarrow Y$

Augmentation: If $X \rightarrow Y$ , then $XZ \rightarrow YZ$

Transitivity: If $X \rightarrow Y$ and $Y \rightarrow Z$ , then $X \rightarrow Z$

These are sound and complete — every implied FD can be derived using these rules.

Q3. Given $F = \{A \rightarrow B, B \rightarrow C\}$ , compute $\{A\}^+$ .

Answer

result = {A}

$A \rightarrow B$ : A ⊆ result → result = {A, B}

$B \rightarrow C$ : B ⊆ result → result = {A, B, C}

No more changes. $\{A\}^+ = \{A, B, C\}$

Q4. Given $R(A, B, C, D)$ and $F = \{A \rightarrow B, A \rightarrow C, B \rightarrow D\}$ , find all candidate keys.

Answer

Step 1: Attributes not on RHS of any FD: A (appears only on LHS of FDs). So A is mandatory.

Step 2: Compute $\{A\}^+$ :

result = {A}

$A \rightarrow B$ → {A, B}

$A \rightarrow C$ → {A, B, C}

$B \rightarrow D$ → {A, B, C, D} = R

Step 3: $\{A\}^+$ covers all attributes. Since A is a single attribute, it's minimal.

Candidate key: {A}

Q5. Check if $F_1 = \{A \rightarrow B, A \rightarrow C\}$ and $F_2 = \{A \rightarrow BC\}$ are equivalent.

Answer

Check each FD from $F_1$ against $F_2$ :

$A \rightarrow B$ : Using $F_2$ , compute $A^+$ = {A, B, C}. B ⊆ $A^+$ ✓

$A \rightarrow C$ : Using $F_2$ , compute $A^+$ = {A, B, C}. C ⊆ $A^+$ ✓

Check each FD from $F_2$ against $F_1$ :

$A \rightarrow BC$ : Using $F_1$ , compute $A^+$ = {A, B, C}. BC ⊆ $A^+$ ✓

All FDs hold in the other set. Therefore, $F_1$ and $F_2$ are equivalent.

Q6. Does $AB \rightarrow C$ hold in $F = \{A \rightarrow B, B \rightarrow C\}$ ?

Answer

Compute $\{A, B\}^+$ :

result = {A, B}

$A \rightarrow B$ : A ⊆ result (B already there)

$B \rightarrow C$ : B ⊆ result → result = {A, B, C}

$\{A, B\}^+ = \{A, B, C\}$

C ⊆ $\{A, B\}^+$ ? Yes! So $AB \rightarrow C$ holds in F.

(Note: This is expected because $A \rightarrow B$ and $B \rightarrow C$ gives $A \rightarrow C$ by transitivity, so with A alone we can determine C.)

Q7. What is a trivial FD? Give three examples.

Answer

A trivial FD $X \rightarrow Y$ is one where $Y \subseteq X$ — the RHS is a subset of the LHS. Trivial FDs are always true.

Examples:

$A \rightarrow A$

$AB \rightarrow A$

$ABC \rightarrow AB$

Non-trivial example: $ID \rightarrow name$ (name is not a subset of ID)

Q8. Given $R(A, B, C, D, E)$ with $F = \{A \rightarrow B, BC \rightarrow D, D \rightarrow E\}$ , find all candidate keys.

Answer

Step 1: Attributes not on RHS: A, C. (A appears on LHS only; C appears on LHS only; B appears on RHS of A→B; D appears on RHS of BC→D; E appears on RHS of D→E)

So A and C must be in every candidate key.

Step 2: Compute $\{A, C\}^+$ :

result = {A, C}

$A \rightarrow B$ → {A, B, C}

$BC \rightarrow D$ → {A, B, C, D}

$D \rightarrow E$ → {A, B, C, D, E} = R

Step 3: $\{A, C\}^+$ = R. Is it minimal?

Remove A: $\{C\}^+ = \{C\} \neq R$

Remove C: $\{A\}^+ = \{A, B\} \neq R$ (no BC → D without C)

Candidate key: {A, C}

🔗 Cross-References

Next Topic: 15 - Canonical Cover
Previous Topic: 13 - ER-to-Relational Mapping
Related: BSMA1001 (Maths 1) — Set theory, relations
Related: 16 - Normalization (using FDs to design good schemas)
Textbook: Silberschatz, Korth, Sudarshan — Chapter 8 (Relational Database Design) Join Discord Previous13 - ER-to-Relational MappingNext15 - Canonical Cover