Normalization: 3rd NF and BCNF

3NF - Third normal form

2NF and every non-key attribute is non-transitively dependent on every candidate key.

The third normal form eliminates transitives dependencies.

Example: relation with

• attributes A, B, C
• candidate key A
• dependencies A → { B, C } and B → C

This relation is in second normal form but not in third, since there is a transitive dependency A → B → C.

Procedure: take (nonloss) projections to eliminate transitive FDs

E.g. R { A, B, C } PRIMARY KEY { A } and B → C

• project R1 { B, C } PRIMARY KEY { B }
• project R2 { A, B } PRIMARY KEY { A } FOREIGN KEY { B } REFERENCES R1

For relation SECOND (decomposition A): replace with SC { SID, CITY } and CS { CITY, STATUS }

• Again, process is reversible by joining, no information lost (check with Heath!)
• however, 3NF can contain more information about the real world, i.e. status of city without supplier
• SC and CS are independent: updates can be made to either one without regard for the other
• SID → CITY and CITY → STATUS are automatically enforced, and therefore also SID → STATUS

SQL:

create table SC as select distinct SID, CITY from second;
select * from sc;
  sid  |      city       
-------+-----------------
 S1    | London         
 S2    | Paris          
 S3    | Paris          
 S4    | London         

create table cs as select distinct CITY, STATUS from second;
select * from cs;
      city       | status 
-----------------+--------
 London          |     20
 Paris           |     10

Check reversibility:

select distinct sid, city, status from sc natural join cs;
  sid  |      city       | status 
-------+-----------------+--------
 S1    | London          |     20
 S2    | Paris           |     10
 S3    | Paris           |     10
 S4    | London          |     20

Dependency preservation

E.g. (decomposition B) project SECOND into SC { SID, CITY } and SS { SID, STATUS }

• lossless
• 3NF
• however:
  • FD CITY → STATUS is not preserved
  • SC and SS are not independent
  • need database constraint to ensure CITY → STATUS

SQL:

create table ss as select distinct sid, status from second;
select * from ss;
  sid  | status 
-------+--------
 S1    |     20
 S2    |     10
 S3    |     10
 S4    |     20

Check reversibility:

select distinct * from sc natural join ss;
  sid  |      city       | status 
-------+-----------------+--------
 S1    | London          |     20
 S2    | Paris           |     10
 S3    | Paris           |     10
 S4    | London          |     20

Theorem of Rissanen

Projections R1 and R2 of relation R are independent iff (if and only if):

• every FD in R is a logical consequence of those in R1 and R2
• common attributes of R1 and R2 form a candidate key for at least one of the pair

Check decomposition A:

• FDs in SECOND follow from SC and CS

  (SID → CITY, CITY → STATUS, and therefore SID → STATUS)

• Common attribute CITY is key in CS

Check decomposition B:

• CITY → STATUS does not follow from SC and SS

  (SID → CITY, SID → STATUS)

Note that decomposing SECOND into {SID, STATUS} and {CITY, STATUS} is not reversible!

Atomic relation: cannot be decomposed into independent projections

E.g. SP is atomic, S and P are not

BCNF - Boyce/Codd normal form

A relation is in BCNF iff every non-trivial, left-irreducible FD has a candidate key as its determinant (left-hand side).

In a diagram: only FD arrows out of candidate keys.

Codd's original definition of 3NF did not adequately deal with a relation that

1. has two or more candidate keys such that
2. candidate keys are composite, and
3. they overlap

BCNF is a stronger definition, and therefore not equal to 3NF:

3NF and BCNF are equivalent when the three conditions above are not met.

Example: Student-Subject-Teacher

• Students take several subjects
• For each subject, each student is taught by only one teacher
• Each teacher teaches only one subject, but each subject is taught by several teachers

Relation SJT with FDs { S, J } → T and T → J

S     J       T
-------------------
Smith Math    White
Smith Physics Green
Jones Math    White
Jones Physics Brown

• two overlapping candidate keys { S, J } and { S, T }
• SJT is in 3NF (see Zaniolo's definition below)
• T is determinant but not candidate key, therefore
• SJT is not in BCNF
• update anomalies, e.g. deleting 'Jones studies Physics' loses info that Brown teaches Physics

We can go to BCNF by projecting to ST { S, T } and TJ { T, J }

• avoids anomaly above, but
• ST and TJ are not independent, since
• only T → J is represented, and
• { S, J } → T cannot be deduced from T → J
  • insert Smith-Brown into ST
  • should be rejected since
    • Brown-Physics (Brown teaches Physics)
    • and we already have Smith-Physics-Green (Smith studies Physics with Green)
  • but need to check TJ to find out!

Note that the only candidate key for ST is { S, T }.

☞ Find a similar example with patients and specialist doctors!

Decomposition in SQL:

create table SJT (S char(8), J char(8), T char(8), primary key (S, J), unique (S, T));
insert into sjt values ('Smith', 'Math', 'White');
insert into sjt values ('Smith', 'Physics', 'Green');
insert into sjt values ('Jones', 'Math', 'White');
insert into sjt values ('Jones', 'Physics', 'Brown');

select s, j, t from SJT;
    s     |    j     |    t     
----------+----------+----------
 Smith    | Math     | White   
 Smith    | Physics  | Green   
 Jones    | Math     | White   
 Jones    | Physics  | Brown   

Project to ST and TJ:

create table ST as select distinct s, t from sjt;
select * from st;
    s     |    t     
----------+----------
 Jones    | Brown   
 Jones    | White   
 Smith    | Green   
 Smith    | White   

create table TJ as select distinct t, j from sjt;
select * from TJ;
    t     |    j     
----------+----------
 Brown    | Physics 
 Green    | Physics 
 White    | Math    

Check reversibility:

select s, j, t from ST natural join TJ;
    s     |    j     |    t     
----------+----------+----------
 Jones    | Physics  | Brown   
 Smith    | Physics  | Green   
 Jones    | Math     | White   
 Smith    | Math     | White   

We cannot decompose every relation into components that are BCNF and independent.

We also observe that SJT is atomic.

Zaniolo's definition of 3NF

• X any subset of attributes
• A any single attribute
• 3NF iff for every FD X → A at least one of the following is true:
  1. X contains A (trivial FD)
  2. X is a superkey
  3. A is contained in a candidate key

For a definition of BCNF drop condition 3.

Apply Zaniolo's definition to SJT:

• Functional dependencies { S, J } → T and T → J
• Candidate keys { S, J } and { S, T }

1. Functional dependency { S, J } → T
   • X contains A i.e. { S, J } contains T: false
   • X is superkey i.e. { S, J } is superkey: true
   • A is contained in a candidate key i.e. T ∈ { S, T }: true

   OK for 3NF, OK for BCNF

2. Functional dependency T → J
   • X contains A i.e. { T } contains { J }: false
   • X is superkey i.e. { T } is superkey: false
   • A is contained in a candidate key i.e. J ∈ { S, J }: true

   OK for 3NF, not OK for BCNF

Therefore, SJT is in 3NF but not in BCNF.

Algorithms for Normalization

Synthesis to 3NF

Go from relation R to set S of relations in 3NF:

S = empty
Find a minimal cover C of FDs in relation R
For every FD X → Y in C:
   Add relation XY to S
If no attribute set of any relation in S contains a key K for R:
   Add relation K to S

The resulting decomposition is always lossless and dependency-preserving.

The minimal cover of a set of functional dependencies is the smallest set of FDs implying all FDs in the original set; not necessarily unique.

Two relations with common keys can be combined, e.g., { A, B } and { A, C } can be combined to { A, B, C }.

In the result of this algorithm a relation can be dropped if all its attributes are contained in those of another relation.

Decomposition to BCNF

Go from relation R to set S of relations in BCNF:

S = { R } 
While S has a relation R' that is not in BCNF do:   
   Choose FD X → Y in R' that violates BCNF
   Add relation XY to S
   R' = R' - Y

Note that dependency preservation is not guaranteed.