Example:
Apply(SSN, cName, hobby)
Reveal hobbies to colleges selectively
MVDs? None
Good design? Yes.

Example:
Apply(SSN, cName, date, major, hobby)
Reveal hobbies to colleges selectively
Apply once to each college (one date)
May apply to multiple majors
FDs: SSN, cName -> date
MVDs: SSN, cName, date ->> major

Trivial Multivalued Dependency
A ->> B
B is a subset of A or A union B = all attributes

Nontrivial MVD
otherwise

Rules for MVDs

FD-is-an-MVD-rule
If A -> B then A ->> B

Intersection Rule
If A ->> B and A ->> C then A ->> B intersect C

Transitive Rule
If A ->> B and B ->> C then A ->> C – B

Fourth Normal Form
Relation R with MVDs is in 4NF if:
For every nontrivial A ->> B, A is a key

NF decomposition algorithm
Input: relation R + FDs for R + MVDs for R
Output: decomposition of R into 4NF relations with lossless join

Compute keys for R
Repeat until all relations are in 4NF:
Pick any R with nontrivial A ->> B that violates 4NF
Decompose R into R1(A, B) and R2(A, rest)
Compute FDs and MVDs for R1 and R2
Compute keys for R1 and R2

4NF Decomposition Example #1
Apply(SSN, cName, hobby)
SSN ->> cName
NO KEYS
A1(SSN, cName)
A2(SSN, hobby)
No FDs and No MVDs
4NF!

4NF Decomposition Example #2
Apply(SSN, cName, date, major, hobby)
SSN, cName -> date
SSN, cName, date ->> major x
NO KEYS A1(SSN, cName, date, major) A2(SSN, cName, date, hobby)
A3(SSN, cName, date)
A4(SSN, cName, major)
A5(SSN, cName, hobby)

Relational Design
Functional dependencies and BCNF
R(A, B, C) A -> B
Multivalued dependencies and Fourth Normal Form
R(A, B, C, D) A ->> B