APPENDIX D: NORMAL FORMS [58]

RULE: candidate key $\rightarrow$ everything

RULE: 1NF can't have arrays

RULE: 2NF can't have (proper) sub-key of composite key $\rightarrow$ non-key (non-prime)

RULE: 3NF can't have non-key $\rightarrow$ non-key (non-prime)

BCNF [59]

RULE: BCNF can't have non-key $\rightarrow$ prime

NOTE: non-key is prime itself and is a replacement

BCNF: if X $\rightarrow$ A then X is a (super) key

3NF: BCNF or A is prime

ARMSTRONG'S AXIOMS:

Transitivity: A $\rightarrow$ B and B $\rightarrow$ C implies A $\rightarrow$ C

Augmentation: A $\rightarrow$ B implies AC $\rightarrow$ BC

Reflexivity (trivial): AB $\rightarrow$ A

EXAMPLE: 2NF BUT NOT 3NF [60]

Main Problem with this 3NF:

If employee does not have a project, we don't know the department.

How to make 3NF schema:

1) Trial and Error until schema satisfies 3NF definition

2) Algorithm

a) find MINIMAL COVER of FD's (remove redundant FD's)

b) make each FD a relation (but combine based on key)

Above Example: remove Emp# $\rightarrow$ Dept#, Emp# $\rightarrow$ Off#

Minimal Cover: Emp# $\rightarrow$ Proj#, Emp# $\rightarrow$ Phone#

3NF Schema: Emps1(Emp#,Proj#) and Emps2(Emp#,Phone#)

Better 3NF Schema: Emps(Emp#,Proj#,Phone#)

EXAMPLE: 3NF BUT NOT BCNF [61]

CITY STREET $\rightarrow$ ZIP

ZIP $\rightarrow$ CITY

Hayward	Mission	94542
Hayward	Foothills	94542
Hayward	Tennyson	94543
...

All of Mission is 94542

All of Foothills is 94542

All of Tennyson is 94543

Overlapping Composite Candidate Keys: CITY STREET and ZIP STREET

3NF: YES

BAD: redundant data (94542 $\rightarrow$ Hayward)

BAD: if street entries missing, we don't know 94542 $\rightarrow$ Hayward

BCNF: NO because NON-KEY $\rightarrow$ PRIME (ZIP $\rightarrow$ CITY)

BCNF: ZIP STREET and ZIP CITY

94542	Mission
94542	Foothills
94543	Tennyson
...

94542	Hayward
94543	Hayward
...

GOOD: no redundant data

GOOD: if street entries missing, we know 94542 $\rightarrow$ Hayward

BAD: FD is not ``preserved'' : CITY STREET $\rightarrow$ ZIP

BCNF: may not preserve all FD's

3NF: always preserves FD's

EXAMPLE: OVERLAP AND BCNF [62]

AC $\rightarrow$ BD

4-digit,Course $\rightarrow$ Name,Grade

4 digit number is unique within the course.

BC $\rightarrow$ AD

Name,Course $\rightarrow$ 4-digit,Grade

Name is unique within the course.

Name does not determine 4-digits because there can be many students with the same name across the planet and they won't have the same 4 digits.

4-digits does not determine the name because there are duplicates once you leave the boundary of the course.

BCNF: keys are AC and BC so its OK because l.h.s. are keys.

Overlapping composite keys does NOT always lead to a BCNF problem.

CSZ example: Z $\rightarrow$ C where Z is not a key but C is prime.

3NF but not BCNF because we had to use the escape clause.

The problem is when a non-key is on the l.h.s.

But 3NF allows a non-key on the l.h.s. if the r.h.s. is prime.

CONCLUSIONS:

1. AC $\rightarrow$ BD and BC $\rightarrow$ AD do NOT imply A $\rightarrow$ B, B $\rightarrow$ A

[This means there are overlapping composite keys but no BCNF problem because both AC and BC are keys.]

2. AC $\rightarrow$ BD and B $\rightarrow$ A do imply BC $\rightarrow$ AD

[This means there are overlapping composite keys. This is 3NF but not BCNF because B is not a key and A is prime.]