Functional Dependencies

Describes a relationship between attributes in a relation. Defines if one set of attributes can determine another.

If attribute set $X$ determines attribute set $Y$, it’s denoted as $X → Y$. Which means, for any two tuples in a relation, if their $X$ values are the same, their $Y$ values must also be the same.

Here:

• X is called the determinant
• Y is called the dependent

A functional dependency represents a constraint on valid data. All candidate keys of a relation are determinants (they functionally determine every attribute).

Usage

Functional dependencies are basis of normalization. Helps find redundancy, anomalies.

Functional dependencies help identify candidate keys and are essential for designing robust relational schemas.

Trivial

A functional dependency is trivial if it is satisfied by all instances of a relation. Of the form $A \rightarrow B$ where $B \subseteq A$.

Legal Instance

For a relation: An instance of a relation that satisfies all real-world constraints.

If a relation $r$ is legal under set of functional dependencies $F$, it’s mentioned as $r$ satisfies $F$.

For a database: an instance of a database in which all the relations are legel.

If a set of functional dependencies $F$ is legal under a relation schema $R$, it’s mentioned as $F$ holds on $R$.

Armstrong’s Axioms

• Reflexivity
  If $\beta \subseteq \alpha$ then $\alpha \rightarrow \beta$
• Augmentation
  If $\alpha \rightarrow \beta$ then $\gamma\alpha \rightarrow \gamma\beta$
• Transitivity
  If $\alpha \rightarrow \beta$ and $\beta \rightarrow \gamma$ and $\alpha \rightarrow \gamma$

The above rules are:

• Sound
  Generate functional dependencies that hold.
• Complete
  Generate all functional dependencies that hold.

Other inferred rules:

• Union
  If $\alpha \rightarrow \beta$ and $\alpha \rightarrow \gamma$ then $\alpha \rightarrow \beta\gamma$
• Decomposition
  If $\alpha \rightarrow \beta\gamma$ then $\alpha \rightarrow \gamma$ and $\alpha \rightarrow \beta$
• Pseudotransitivity
  If $\alpha \rightarrow \beta$ and $\gamma\beta \rightarrow \delta$ then $\alpha\gamma \rightarrow \delta$

Closure

Suppose $F$ is a set of functional dependencies.

Closure of $F$, denoted as $F^+$, is the complete set of all functional dependencies that can be logically inferred from $F$. Armstrong’s axioms are repeatedly applied to compute $F^+$.

$F^+$ can be computed by:

Step-by-Step Procedure

1. Initialize $F^+$ = F
2. For each functional dependency of $F^+$, apply Armstrong’s axioms:

• Reflexivity
• Augmentation
• Transitivity

3. Add each new functional dependency to $F^+$.
4. Continue applying rules until no new dependencies appear

Takes exponential time to compute.

Canonical Cover

For a set of functional dependencies $F$, its canonical cover is the minimal set of functional dependencies equivalent to $F$, having no redundant dependencies or redundant parts of dependencies.

Multivalued Dependencies

A multivalued dependency (MVD) $\alpha \twoheadrightarrow \beta$ holds on a relation $R$ iff for any 2 tuples $t_1$ and $t_2$ with $t_1[\alpha] = t_2[\alpha]$, the relation also has tuples $t_3$ and $t_4$ such that:

• $t_3[\alpha] = t_4[\alpha] = t_1[\alpha]$
• $t_3[\beta] = t_1[\beta]$ and $t_3[R - \alpha - \beta] = t_2[R - \alpha - \beta]$
• $t_4[\beta] = t_2[\beta]$ and $t_4[R - \alpha - \beta] = t_1[R - \alpha - \beta]$

The $\beta$ values of an $\alpha$ value are independent of the remaining attributes. Every combination of them appears in the relation.

An MVD is trivial if $\beta \subseteq \alpha$ or $\alpha \cup \beta = R$.

Every functional dependency is also a multivalued dependency.

Example:
In $R(\text{Employee}, \text{Skill}, \text{Language})$, $\text{Employee} \twoheadrightarrow \text{Skill}$ and $\text{Employee} \twoheadrightarrow \text{Language}$ hold. If Ann has the skills SQL and Java and the languages EN and FR, all 4 combinations of skill and language appear in $R$.