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 pair of tuples in t

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 also have the same value for Y.

X → Y means: if two tuples agree on X, they MUST agree on Y. Example: StudentID → StudentName If two rows have the same StudentID, they MUST have the same StudentName.

Types of Functional Dependencies

1. Trivial Functional Dependency

Y is a subset of X — the dependency is always true and carries no information.

{A, B}	A (trivial: A is part of {A,B})
{A, B}	{A, B} (trivial: same set)
StudentID	StudentID (trivial)

2. Non-Trivial Functional Dependency

Y is not a subset of X — contains useful information.

StudentID → StudentName (non-trivial) {StudentID, CourseID} → Grade (non-trivial)

3. Partial Functional Dependency

A non-key attribute depends on only a part of the composite primary key (not the whole key).

Relation	Enrollment(StudentID, CourseID, Grade, StudentName)
Primary Key	(StudentID, CourseID)
StudentID	StudentName ← PARTIAL dependency
(StudentID, CourseID)	Grade ← Full dependency ✓

Partial dependencies cause 2NF violations.

4. Transitive Functional Dependency

A non-key attribute depends on another non-key attribute.

Relation	Employee(EmpID, DeptID, DeptName)
Primary Key	EmpID
EmpID	DeptID (direct)
DeptID	DeptName (direct)
EmpID	DeptName (transitive via DeptID)

Transitive dependencies cause 3NF violations.

Notation and Examples

EmpID	Name (EmpID determines Name)
EmpID	DeptID (EmpID determines department)
EmpID	Salary (EmpID determines salary)
DeptID	DeptName (department determines dept name)
EmpID	DeptName (transitive: through DeptID)
Primary Key	(SID, CID)
SID	SName (partial)
CID	CName (partial)
CID	Credits (partial)
(SID, CID)	Grade (full — needs both)

Finding Functional Dependencies

To identify FDs from a table instance, look for:

Which columns always have the same value when another column has the same value?
Which combinations of columns uniquely identify rows?

Example Table

EmpID	Name	Dept	Manager	Salary
101	Alice	CS	Dr. Roy	75000
102	Bob	Math	Dr. Sen	62000
103	Carol	CS	Dr. Roy	88000

Observations

Closure of a Functional Dependency Set

The closure F+ of a set F of FDs is the set of ALL FDs that can be derived from F using Armstrong's Axioms.

The closure of a set of attributes X (written X+) is the set of all attributes that are functionally determined by X under F.

Example

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

F = { A → B, B → C, A → D }

Compute A+

Start: A+ = {A}

Apply A → B: A+ = {A, B}

Apply B → C: A+ = {A, B, C}

Apply A → D: A+ = {A, B, C, D}

No more FDs apply.

A+ = {A, B, C, D}

A is a superkey if A+ includes all attributes.

Here A+ = {A,B,C,D} — missing E, so A alone is not a superkey.

Canonical Cover (Fc)

A canonical cover Fc is a minimal, simplified set of FDs equivalent to F (same closure). It removes:

Redundant FDs
Redundant attributes on the left-hand side

Properties:

No FD in Fc is redundant
Left-hand side of each FD has no redundant attributes
Fc+ = F+ (same closure as original)

Definition

X → Y means: if two tuples agree on X, they MUST agree on Y. Example: StudentID → StudentName If two rows have the same StudentID, they MUST have the same StudentName.

Types of Functional Dependencies

1. Trivial Functional Dependency

Y is a subset of X — the dependency is always true and carries no information.

{A, B}	A (trivial: A is part of {A,B})
{A, B}	{A, B} (trivial: same set)
StudentID	StudentID (trivial)

2. Non-Trivial Functional Dependency

Y is not a subset of X — contains useful information.

StudentID → StudentName (non-trivial) {StudentID, CourseID} → Grade (non-trivial)

3. Partial Functional Dependency

A non-key attribute depends on only a part of the composite primary key (not the whole key).

Relation	Enrollment(StudentID, CourseID, Grade, StudentName)
Primary Key	(StudentID, CourseID)
StudentID	StudentName ← PARTIAL dependency
(StudentID, CourseID)	Grade ← Full dependency ✓

Partial dependencies cause 2NF violations.

4. Transitive Functional Dependency

A non-key attribute depends on another non-key attribute.

Relation	Employee(EmpID, DeptID, DeptName)
Primary Key	EmpID
EmpID	DeptID (direct)
DeptID	DeptName (direct)
EmpID	DeptName (transitive via DeptID)

Transitive dependencies cause 3NF violations.

Notation and Examples

EmpID	Name (EmpID determines Name)
EmpID	DeptID (EmpID determines department)
EmpID	Salary (EmpID determines salary)
DeptID	DeptName (department determines dept name)
EmpID	DeptName (transitive: through DeptID)
Primary Key	(SID, CID)
SID	SName (partial)
CID	CName (partial)
CID	Credits (partial)
(SID, CID)	Grade (full — needs both)

Finding Functional Dependencies

To identify FDs from a table instance, look for:

Which columns always have the same value when another column has the same value?
Which combinations of columns uniquely identify rows?

Example Table

EmpID	Name	Dept	Manager	Salary
101	Alice	CS	Dr. Roy	75000
102	Bob	Math	Dr. Sen	62000
103	Carol	CS	Dr. Roy	88000

Observations

Closure of a Functional Dependency Set

The closure F+ of a set F of FDs is the set of ALL FDs that can be derived from F using Armstrong's Axioms.

The closure of a set of attributes X (written X+) is the set of all attributes that are functionally determined by X under F.

Example

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

F = { A → B, B → C, A → D }

Compute A+

Start: A+ = {A}

Apply A → B: A+ = {A, B}

Apply B → C: A+ = {A, B, C}

Apply A → D: A+ = {A, B, C, D}

No more FDs apply.

A+ = {A, B, C, D}

A is a superkey if A+ includes all attributes.

Here A+ = {A,B,C,D} — missing E, so A alone is not a superkey.

Canonical Cover (Fc)

A canonical cover Fc is a minimal, simplified set of FDs equivalent to F (same closure). It removes:

Redundant FDs
Redundant attributes on the left-hand side

Properties:

No FD in Fc is redundant
Left-hand side of each FD has no redundant attributes
Fc+ = F+ (same closure as original)

Functional Dependency

Definition

Types of Functional Dependencies

1. Trivial Functional Dependency

2. Non-Trivial Functional Dependency

3. Partial Functional Dependency

4. Transitive Functional Dependency

Notation and Examples

Finding Functional Dependencies

Example Table

Closure of a Functional Dependency Set

Example

Compute A+

Canonical Cover (Fc)

Continue learning this concept

Functional Dependency

Definition

Types of Functional Dependencies

1. Trivial Functional Dependency

2. Non-Trivial Functional Dependency

3. Partial Functional Dependency

4. Transitive Functional Dependency

Notation and Examples

Finding Functional Dependencies

Example Table

Closure of a Functional Dependency Set

Example

Compute A+

Canonical Cover (Fc)

Continue learning this concept