Normalization: Convert a schema to normal form that guarantees good design.

Principle: Avoid Redundancy

Redundant Data: If some fields in the database can be inferred from others when removed, they are redundant.

• e.g. Don’t store this: (part → manufacturer, manufacturer → manAddress, seller → sellerAddress)

  

Update Anomaly: When a change must update many entries to stay consistant (e.g. when updating seller addresses, all tuples with that seller must change)

Deletion Anomaly: When a deletion removes more data than intended (e.g. when deleting the 1983 Walmart entry, Walmart’s address is lost)

Functional Dependency Theory

Functional Dependency: $X \rightarrow Y$ (x functionally determines y)

• X and Y are subsets of attributes of R, Y depends on X
• If two tuples agree on all attributes in X, they must also agree on all attrs in Y $\forall t_1, t_2, (t_1[X]=t_2[X]) \implies (t_1[Y]=t_2[Y])$
• Multiple Attributes: $X_1X_2\dots X_m \rightarrow Y_1\dots Y_m$ $\forall t_1, t_2, (t_1[X_1] = t_2[X_1] \land \dots t_1[X_m] = t_2[X_m]) \implies (t_1[Y_1] = t_2[Y_1] \land \dots)$

Superkey: A superkey is a FD that determines every other attribute

• A superkey’s closure FD+ is all attrs in a relation

Functional Dependency Algorithms

Online Checkers: raymondcho.net

Equivalent Sets of FDs: $S_1$ is equivalent to $S_2$ when $S_1$ holds $\Leftrightarrow S_2$ holds (e.g. $S_1=\{A \rightarrow BC\}, S_2=\{A\rightarrow B, A\rightarrow C\}$)

Closure Test: To determine if an FD follows from a set of FDs: (e.g. S = {A → B, B → C}, want to know if FD = A → BC follows)

1. Start with the X+ = LHS of FD, expand to add all RHS of F ∈ S that has LHS ⊂ X+ (e.g. A = AB = ABC)
2. If the RHS of FD ⊂ X+, conclude that FD follows. (e.g. BC ⊂ ABC, so A → BC follows)