Megan Taylor

front-end dev, volunteacher, news & data junkie, bibliophile, Flyers fan, sci-fi geek and kitteh servant

Intro to Databases: Relational Design Theory, Multivalued Dependencies, 4th Normal Form

Fourth Normal Form is stricter than BCNF
All FNF is in BCNF

Example:
Apply(SSN, cName, hobby)
FDs? No.
Keys? All attributes.
BCNF? Yes.
Good design? No.

If someone applies to 5 colleges and has 6 hobbies, they will have 30 tuples in the database

Multivalued Dependency
based on knowledge of real world
all instances of relations must adhere
R A ->> B
also called tuple-generating dependencies

Example:
Apply(SSN, cName, hobby)
SSN ->> cName
SSN ->> hobbby

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

November 12, 2011 | Comments Off on Intro to Databases: Relational Design Theory, Multivalued Dependencies, 4th Normal Form | Categories: Posts | Permalink

Comments are closed.

%d bloggers like this: