Functional Dependency

A functional dependency (FD) is a constraint between two sets of attributes in a relation. We say X functionally determines Y (written X → Y) if for every...

Definition

A functional dependency (FD) is a constraint between two sets of attributes in a relation. We say X functionally determines Y (written X → Y) if for every pair of tuples in the relation that have the same value for X, they must also have the same value for Y.

Example

X -> Y means: If two rows agree on X, they MUST agree on Y. Equivalently: given a value of X, there is exactly one associated Y value. Example: StudentID -> StudentName Knowing the StudentID uniquely determines the student's name. Two rows with the same StudentID cannot have different names.

Functional dependencies are the foundation of normalization theory. They express the constraints inherent in your data, and understanding them is essential for designing redundancy-free database schemas.

Partial vs. Full Functional Dependency

Full Functional Dependency

Y is fully functionally dependent on X if Y depends on the entire X and NOT on any proper subset of X.

Relation	Enrollment(StudentID, CourseID, Grade)
Primary Key	(StudentID, CourseID)
(StudentID, CourseID) -> Grade	FULL dependency

Partial Functional Dependency

Y is partially dependent on X if Y depends on only a proper subset of X (when X is composite).

Relation	Enrollment(StudentID, CourseID, Grade, StudentName)
Primary Key	(StudentID, CourseID)
StudentID -> StudentName	PARTIAL dependency

Partial dependencies cause Second Normal Form (2NF) violations.

Transitive Functional Dependency

A transitive dependency exists when a non-key attribute determines another non-key attribute through an intermediate attribute.

Relation	Employee(EmpID, DeptID, DeptName, DeptLocation)
Primary Key	EmpID
EmpID -> DeptName (TRANSITIVE	via DeptID)
EmpID -> DeptLocation (TRANSITIVE	via DeptID)
Chain	EmpID -> DeptID -> DeptName

Transitive dependencies cause Third Normal Form (3NF) violations.

Finding Functional Dependencies

FDs come from understanding the business rules of the domain, not from looking at current data. Consider:

EmpID	Name	Salary
E001	Alice	70000
E002	Bob	70000

Current data

Just because two employees happen to have the same salary today

Properties of Functional Dependencies

Reflexivity (Trivial FDs)

If Y ⊆ X, then X → Y always holds.

Augmentation

If X → Y, then XZ → YZ for any attribute set Z.

Transitivity

If X → Y and Y → Z, then X → Z.

These three are Armstrong's Axioms — they form a sound and complete inference system for deriving all FDs implied by a given set.

Derived Rules

Rule	Statement	Derivation
Union	If X→Y and X→Z, then X→YZ	From augmentation + transitivity
Decomposition	If X→YZ, then X→Y and X→Z	From reflexivity + transitivity
Pseudo-transitivity	If X→Y and WY→Z, then WX→Z	From augmentation + transitivity

Functional Dependencies and Keys

FDs define what constitutes a key:

Example

R(A, B, C, D, E) F = {A -> BC, C -> DE} A+ = {A} -> A->BC -> {A,B,C} -> C->DE -> {A,B,C,D,E} = all attributes A is a superkey (and candidate key since it's a single attribute). C+ = {C} -> C->DE -> {C,D,E} -- not all attributes C is NOT a superkey.

Practical Example — University Database

FD1	SID -> SName, Major, AdvisorID (student ID determines student info)
FD2	AdvisorID -> AdvisorName, AdvisorOffice (advisor ID determines advisor info)
Transitive	SID -> AdvisorID -> AdvisorName (transitive!)
This violates 3NF. Solution	decompose.

Anomalies Caused by FD Violations

Anomaly	Description	Example
Insertion	Cannot insert one fact without another	Cannot add a new advisor without assigning a student
Deletion	Deleting one fact loses another	Deleting last student of an advisor loses advisor info
Update	Must update multiple rows for one fact	Changing advisor's office requires updating all their students

These anomalies are the motivation for normalization — systematically eliminating problematic FDs by decomposing relations into smaller, well-structured tables.

Definition

Example

Partial vs. Full Functional Dependency

Full Functional Dependency

Y is fully functionally dependent on X if Y depends on the entire X and NOT on any proper subset of X.

Relation	Enrollment(StudentID, CourseID, Grade)
Primary Key	(StudentID, CourseID)
(StudentID, CourseID) -> Grade	FULL dependency

Partial Functional Dependency

Y is partially dependent on X if Y depends on only a proper subset of X (when X is composite).

Relation	Enrollment(StudentID, CourseID, Grade, StudentName)
Primary Key	(StudentID, CourseID)
StudentID -> StudentName	PARTIAL dependency

Partial dependencies cause Second Normal Form (2NF) violations.

Transitive Functional Dependency

A transitive dependency exists when a non-key attribute determines another non-key attribute through an intermediate attribute.

Relation	Employee(EmpID, DeptID, DeptName, DeptLocation)
Primary Key	EmpID
EmpID -> DeptName (TRANSITIVE	via DeptID)
EmpID -> DeptLocation (TRANSITIVE	via DeptID)
Chain	EmpID -> DeptID -> DeptName

Transitive dependencies cause Third Normal Form (3NF) violations.

Finding Functional Dependencies

FDs come from understanding the business rules of the domain, not from looking at current data. Consider:

EmpID	Name	Salary
E001	Alice	70000
E002	Bob	70000

Current data

Just because two employees happen to have the same salary today

Properties of Functional Dependencies

Reflexivity (Trivial FDs)

If Y ⊆ X, then X → Y always holds.

Augmentation

If X → Y, then XZ → YZ for any attribute set Z.

Transitivity

If X → Y and Y → Z, then X → Z.

These three are Armstrong's Axioms — they form a sound and complete inference system for deriving all FDs implied by a given set.

Derived Rules

Rule	Statement	Derivation
Union	If X→Y and X→Z, then X→YZ	From augmentation + transitivity
Decomposition	If X→YZ, then X→Y and X→Z	From reflexivity + transitivity
Pseudo-transitivity	If X→Y and WY→Z, then WX→Z	From augmentation + transitivity

Functional Dependencies and Keys

FDs define what constitutes a key:

Example

Practical Example — University Database

FD1	SID -> SName, Major, AdvisorID (student ID determines student info)
FD2	AdvisorID -> AdvisorName, AdvisorOffice (advisor ID determines advisor info)
Transitive	SID -> AdvisorID -> AdvisorName (transitive!)
This violates 3NF. Solution	decompose.

Anomalies Caused by FD Violations

Anomaly	Description	Example
Insertion	Cannot insert one fact without another	Cannot add a new advisor without assigning a student
Deletion	Deleting one fact loses another	Deleting last student of an advisor loses advisor info
Update	Must update multiple rows for one fact	Changing advisor's office requires updating all their students

These anomalies are the motivation for normalization — systematically eliminating problematic FDs by decomposing relations into smaller, well-structured tables.

Functional Dependency

Definition

Partial vs. Full Functional Dependency

Full Functional Dependency

Partial Functional Dependency

Transitive Functional Dependency

Finding Functional Dependencies

Properties of Functional Dependencies

Reflexivity (Trivial FDs)

Augmentation

Transitivity

Derived Rules

Functional Dependencies and Keys

Practical Example — University Database

Anomalies Caused by FD Violations

Continue learning this concept

Functional Dependency

Definition

Partial vs. Full Functional Dependency

Full Functional Dependency

Partial Functional Dependency

Transitive Functional Dependency

Finding Functional Dependencies

Properties of Functional Dependencies

Reflexivity (Trivial FDs)

Augmentation

Transitivity

Derived Rules

Functional Dependencies and Keys

Practical Example — University Database

Anomalies Caused by FD Violations

Continue learning this concept