Functional Dependencies

Before we can eliminate data redundancy by normalizing our database, we must understand the mathematical relationships between the columns in our tables. This is defined by Functional Dependencies (FDs).

1. What is a Functional Dependency?

A Functional Dependency is a constraint that specifies the relationship between two sets of attributes in a relation from a database.

If $R$ is a relation schema and $\alpha$ and $\beta$ are sets of attributes, then the functional dependency $\alpha \rightarrow \beta$ (read as "$\alpha$ functionally determines $\beta$") holds on $R$ if, for any two tuples (rows) in the table:

• If they have the exact same value for $\alpha$, they MUST have the exact same value for $\beta$.

Real-World Example

Consider a Student table with columns: StudentID, Name, DateOfBirth.

• StudentID -> Name: This is a valid functional dependency. If two rows have the exact same StudentID, they must belong to the exact same person, so the Name must be identical.
• Name -> DateOfBirth: This is NOT a valid functional dependency. Two different students can have the exact same name ("John Smith"), but they might be born on completely different dates.

2. Trivial vs. Non-Trivial FDs

• Trivial FD: An FD $\alpha \rightarrow \beta$ is trivial if $\beta$ is a subset of $\alpha$.
  • Example: {StudentID, Name} -> Name. This is mathematically obvious and doesn't give us any useful constraints.
• Non-Trivial FD: An FD $\alpha \rightarrow \beta$ is non-trivial if $\beta$ is not a subset of $\alpha$.
  • Example: StudentID -> Name.

3. Armstrong's Axioms

To systematically discover all functional dependencies in a database, we use Armstrong's Axioms. These are a set of sound and complete inference rules.

Let $X$, $Y$, and $Z$ be sets of attributes.

1. Reflexivity Rule: If $Y \subseteq X$, then $X \rightarrow Y$.
2. Augmentation Rule: If $X \rightarrow Y$, then $XZ \rightarrow YZ$.
3. Transitivity Rule: If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.

Derived Rules

From the three axioms above, we can prove several other extremely useful rules:

• Union Rule: If $X \rightarrow Y$ and $X \rightarrow Z$, then $X \rightarrow YZ$.
• Decomposition Rule: If $X \rightarrow YZ$, then $X \rightarrow Y$ and $X \rightarrow Z$.
• Pseudotransitivity Rule: If $X \rightarrow Y$ and $WY \rightarrow Z$, then $WX \rightarrow Z$.

4. Attribute Closure

The Closure of a set of attributes $X$ with respect to a set of functional dependencies $F$, denoted as $X^+$, is the set of all attributes that are functionally determined by $X$.

Why is this important? If the closure of $X$ ($X^+$) contains absolutely every attribute in the entire table, then $X$ is a Super Key for that table! If $X$ is minimal, it is a Candidate Key.

Finding attribute closures is the mathematical foundation for proving what the Primary Key of a table should be.