## 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.

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