Functional Dependancies

These describe a relationship between attributes (columns) in a table. So we can think of these as relationships inside same table. This is the main component we need to do database normalizations and avoid huge messy tables and make consistent smaller simpler tables.

Notation

$$X \rightarrow Y$$

This means $X$ determines $Y$.

• $X$ - Determinant
• $Y$ - Dependent

Rule 1

Right Side depends on Left Side.

If $X$ is given, $Y$ must be only one possible value nothing else.

Rule 2

Multiple Determinants ($X$) can share same $Y$ value, but one $X$ can have only ONE $Y$ value.

Armstrong's Axioms

These are a set of axioms like in Boolean Algebra, we use to combine different functional dependancies to find hidden relationships. These are useful to further normalize a database.

Reflexivity

If $Y$ is inside $X$, then $X \rightarrow Y$

• eg: $\{\text{Name}, \text{Age}\} \rightarrow \text{Name}$

Augmentation

If $X \rightarrow Y$, you can add $Z$ to both sides: $XZ \rightarrow YZ$.

• eg: $\text{Emp\_ID} \rightarrow \text{Salary}$, then $\{\text{Emp\_ID}, \text{Dept}\} \rightarrow \{\text{Salary}, \text{Dept}\}$.

Transitivity

If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.

• eg: $\text{Zip\_Code} \rightarrow \text{City}$, and $\text{City} \rightarrow \text{State}$, so $\text{Zip\_Code} \rightarrow \text{State}$.

Derived Axioms (Shortcuts)

Union

If $X \rightarrow Y$ and $X \rightarrow Z$, then $X \rightarrow YZ$.

Decomposition

If $X \rightarrow YZ$, then $X \rightarrow Y$ and $X \rightarrow Z$.

Pseudo Transitivity

If $X \rightarrow Y$  and $YZ\rightarrow W$ , then $XZ\rightarrow W$

Attribute Closure ($X^+$)

These are useful to determine if a attribute set is a candidate key or a given functional dependency holds.

Algorithm

1. Initialize $X = X^+$
2. Search for any dependency $U \rightarrow V$ in $F$ where $U$ is in $X^+$ but $V$ is not
3. Add $V$ to $X^+$
4. Repeat until no new attributes can be added

If $X^+$ includes all attributes of a relation $R$, then $X$ is a super key of $R$

Functional Dependency Closure ($F^+$)

This is the set of all possible functional dependencies that can be logically derived from the functional dependency set $F$

Used to evaluate equivalence between sets of dependencies and determine schema normalization (e.g., 3NF, BCNF)