Functional Dependency

Functional dependency is the ‘mapping’ of sets of attributes, which identifies which sets can be uniquely map to another sets.

Definitions §

Let $W,X,Y,Z$ be sets of attributes. Let the primary key be $(X,Y)$

• Key attribute: In functional dependency, refers to any attribute that belongs to the primary key
• Determinants: Attributes that determine another set of attributes, see below.
• Partial Functional Dependency: A functional dependency where one or more non-key attributes depend upon a proper subset of the primary key. For example: $X\to Z$ and $Y\to Z$ are partial dependency, but $(X,Y)\to Z$ is not.
• Transitive Dependency: A functional dependency consisting of only non-key attributes. $W\to Z$ is a transitive dependency.

Determinants §

In functional dependency, a set of attributes $X$ determine another set of attributes $Y$ if there each value of $X$ is associated with only one value of $Y$.

This is not the same as injective functions, as there can be multiple values in $X$ that map to the same $Y$, something that is not allowed in injective functions.

$$X\to Y⟺\text{Each value in X is associated with only one value in Y}⟺X\text{ determines }Y$$

This does not mean each value in $Y$ is mapped to only one value in $X$

Another example is $(X,Y)\to Z$, meaning $X$ and $Y$ together determine $Z$.

Armstrong’s Axioms §

Let $A,B,C$ be sets.

Reflexivity §

$$B\subseteq A⟹A\to B$$

If $B$ is a subset of $A$, then $A$ determines $B$. This is obvious, since we can just take that value of $B$ that is in $A$ and use it on the left side.

This type of functional dependency is known as trivial

Augmentation §

$$A\to B⟹(A,C)\to (B,C)$$

We can augment extra sets to a functional dependency, and it will still hold

Transitivity §

This is different from transitive functional dependencies!

$$A\to B\wedge B\to C⟹A\to C$$

Functional dependencies are transitive.