Functional Dependencies

What are Functional Dependencies?

A functional dependency is a relationship between two sets of attributes in a relation (table). It states that the value of one attribute (or set of attributes) uniquely determines the value of another attribute (or set of attributes).

Formally, a functional dependency is written as X → Y, which means “Y is functionally dependent on X” or “X determines Y”.

Basic Concepts

Attribute Sets

In functional dependency notation:

X and Y represent sets of attributes from a relation
X is called the determinant (the attribute that determines)
Y is the dependent attribute (the attribute being determined)

Definition

X → Y means that for any two tuples t1 and t2 in relation R, if t1[X] = t2[X], then t1[Y] = t2[Y].

In simpler terms: if two rows have the same values for attributes in X, they must also have the same values for attributes in Y.

Examples of Functional Dependencies

Consider a Students table with attributes: StudentID, Name, DateOfBirth, DepartmentID, DepartmentName.

Some functional dependencies might be:

StudentID → Name, DateOfBirth
DepartmentID → DepartmentName
StudentID, CourseID → Grade (from an Enrollments table)

These dependencies mean:

A specific StudentID uniquely determines a student’s Name and DateOfBirth
A specific DepartmentID uniquely determines a DepartmentName
A specific combination of StudentID and CourseID uniquely determines a Grade

Types of Functional Dependencies

1. Trivial Functional Dependencies

A functional dependency X → Y is trivial if Y is a subset of X.

Examples:

{StudentID, Name} → StudentID
StudentID → StudentID

Trivial dependencies always hold and don’t provide any useful information for database design.

2. Non-Trivial Functional Dependencies

A functional dependency X → Y is non-trivial if Y is not a subset of X.

Examples:

StudentID → Name
{CourseID, Semester} → Instructor

Non-trivial dependencies are important for database design as they reveal real relationships between attributes.

3. Completely Non-Trivial Functional Dependencies

A functional dependency X → Y is completely non-trivial if X and Y have no attributes in common.

Example:

StudentID → Major (where StudentID and Major have no overlapping attributes)

4. Partial Functional Dependencies

A functional dependency X → Y is a partial dependency if some proper subset of X also functionally determines Y.

Example:

If {StudentID, CourseID} → InstructorName, but CourseID → InstructorName also holds, then the first dependency is a partial dependency.

Partial dependencies indicate that a table is not in Second Normal Form (2NF).

5. Transitive Functional Dependencies

A functional dependency X → Y is transitive if there exists a set of attributes Z such that X → Z and Z → Y, and Z is not a subset of X or Y.

Example:

If StudentID → DepartmentID and DepartmentID → DepartmentLocation, then StudentID → DepartmentLocation is a transitive dependency.

Transitive dependencies indicate that a table is not in Third Normal Form (3NF).

Properties of Functional Dependencies

Functional dependencies follow certain logical rules known as Armstrong’s Axioms:

1. Reflexivity

If Y is a subset of X, then X → Y (trivial dependency).

Example: {StudentID, Name} → StudentID

2. Augmentation

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

Example: If StudentID → Name, then {StudentID, CourseID} → {Name, CourseID}

3. Transitivity

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

Example: If StudentID → DepartmentID and DepartmentID → DepartmentName, then StudentID → DepartmentName

Additional Rules Derived from Armstrong’s Axioms

4. Union

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

Example: If StudentID → Name and StudentID → Address, then StudentID → {Name, Address}

5. Decomposition

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

Example: If StudentID → {Name, Address}, then StudentID → Name and StudentID → Address

6. Pseudotransitivity

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

Example: If CourseID → InstructorID and {StudentID, InstructorID} → Grade, then {StudentID, CourseID} → Grade

Finding All Functional Dependencies

To find all possible functional dependencies in a relation:

Identify the primary key - it determines all other attributes
Check for partial dependencies - parts of the key determining non-key attributes
Look for transitive dependencies - non-key attributes determining other non-key attributes
Consider business rules - some dependencies may come from domain knowledge

Functional Dependency Closure

The closure of a set of functional dependencies F (denoted F⁺) is the set of all functional dependencies that can be derived from F using Armstrong’s axioms.

Computing the closure helps determine all the dependencies that exist in a relation.

Attribute Closure

The attribute closure of a set of attributes X under a set of functional dependencies F (denoted X⁺) is the set of all attributes that are functionally determined by X.

Algorithm to compute X⁺:

Start with X⁺ = X
For each functional dependency Y → Z in F, if Y is a subset of the current X⁺, add Z to X⁺
Repeat step 2 until no more attributes can be added to X⁺

Example: Given:

F = {A → B, B → C, CD → E, AE → F}
X = {A, D}

Compute X⁺:

Start with X⁺ = {A, D}
A → B applies, so X⁺ = {A, D, B}
B → C applies, so X⁺ = {A, D, B, C}
CD → E applies, so X⁺ = {A, D, B, C, E}
AE → F applies, so X⁺ = {A, D, B, C, E, F}
No more dependencies apply, so X⁺ = {A, D, B, C, E, F}

Minimal Cover

A minimal cover is a simplified set of functional dependencies that is equivalent to the original set but has:

No redundant dependencies
No redundant attributes in dependency determinants
All dependencies with single attributes on the right-hand side

Finding a minimal cover helps simplify the set of functional dependencies.