Definition
If we have
$$
\forall t,u \in R,, t[A_1,\ldots,A_n] = u[A_1,\ldots,A_n] \implies t[B_1,\ldots,B_n] = u[B_1,\ldots,B_n]
$$
that is “for every pair of tuples in the relation, if the two tuples have the same values for attributes $A_1$ through $A_n$, then the two tuples also have the same values for attributes $B_1$ through $B_n$”.
We write
$$
A_1,A_2,\ldots,A_n \to B_1,B_2,\ldots,B_n
$$
and say that a set of attributes $A_1,\ldots,A_n$ functionally determines the set of attributes $B_1,\ldots,B_n$.
All instances of the relation must adhere to the functional dependencies.
Functional Dependencies and Keys
In a relation without duplicate tuples, a set of attributes $\overline{A}$ forms a key if and only if
$$
\overline{A} \to \text{all attributes}
$$
(i.e. $\overline{A}$ functinally determines all other attributes)
Trivial Functional Dependencies
Definition: We say a functional dependency $\overline{A} \to \overline{B}$ is trivial if $\overline{B} \subseteq \overline{A}$.
This should be quite intuitive. If some tuples tuples have unique values across attributes in $\overline{A}$, then any they should also be the same for attributes in any subset of $\overline{A}$.
Definition: We say a functional dependency is non-trivial if it is not a trivial functional dependency.
#completely_nontrivial_fd
Definition: We say a functional dependency $\overline{A} \to \overline{B}$ is completely nontrivial if $\overline{A} \cap \overline{B} = \emptyset$.
Rules for FDs
Splitting Rule
$$
\overline{A} \to B_1,B_2,\ldots,B_n \implies \overline{A} \to B_1,,\overline{A} \to B_2,,\ldots,, \overline{A} \to B_n
$$
Note that we can only split the right-hand side (NOT the left-hand side).
In the college application example, high school code uniquely defines the high school name and the high school city; but conversely, high school name or high school city alone does not uniquely define the high school code.
Given a set of FDs, we can often infer further FDs.
Big task: given a set of FDs, infer every othe FDs that must also hold.
Simpler task: given a set of FDs, check whether a given FD must also hold.
Combining Rule
$$
(\overline{A} \to B_1,,\overline{A} \to B_2,,\ldots,, \overline{A} \to B_n) \implies \overline{A} \to B_1,B_2,\ldots,B_n
$$
Trivial Dependency Rule
$$
\overline{A} \to \overline{B} \implies \overline{A} \to \overline{A} \cup \overline{B}
$$
and
$$
\overline{A} \to \overline{B} \implies \overline{A} \to \overline{A} \cap \overline{B}
$$
Note that the second rule is also implied by the splitting rule.
Transitive Rule
$$
(\overline{A} \to \overline{B},,\overline{B} \to \overline{C}) \implies \overline{A} \to \overline{C}
$$
Attributes Closure
Given a relation, functional dependencies, and a set of attributes $\overline{A}$, we can compute the closure of attributes in $\overline{A}$, denoted $\overline{A}^+$, that is all $B$ such that $\overline{A} \to B$.
To compute the closure of a set of attribtues:
AttributeClosure($\overline{A}$, $\overline{A}^+$)
- start with $\overline{A}^+={A_1,\ldots,A_n}$
- repeat until no change
- if $\overline{A} \to \overline{B}$ and $\overline{A}$ is in the set
- add $\overline{B}$ to the set
After running the closure algorithm, if we discover that $\overline{A}^+ = \text{all attributes}$, then $\overline{A}$ is a key. Conversely, we can find all keys by consider every subset of the attributes.
If a given attribute $A$ is not originally in $\overline{A}$ and it never shows up on the right-hand side, then it cannot be in the closure of $\overline{A}$.
Closure Test
$S$ is a set of FDs; return true if and only if LHS -> RHS follows from $S$. The algorithm for checking if a FD follows from $S$ is:
FDFollows($S$, $LHS \to RHS$)
- $Y^+$ = AttributeClosure(LHS, $S$)
- return (RHS is in $Y^+$)
Projecting FDs
Relation $R(A_1,\ldots,A_n)$ with set of attributes $A$. Let $R_1 = \pi_{B}(R)$ and $R_2 = \pi_C(R)$.
Minimal Basis
Given a set of FDs $S$, the minimal basis is a set of FDs that is equivalent to $S$ but has
- no redundant FDs, and
- no FDs with unnecessary attributes on the LHS
- all RHS will be single attributes