IST366: Exampel 3.

Second Normal Form

Consider the following "bad" relation:
```
   Employee1(SSN, FName, LName, PNumber, PName, Hours)
```
Represents employees and the projects that he works on.

Sample content of the Employee1 relation:

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

Relation Employee1 has anomalies...
- Key of relation: (SSN, PNumber)
- Insert: cannot insert a new project (say pj3) that does not have any employees (NULL values in keys are NOT allowed in the relational model)
- Delete: deleting "John Smith" from project "pj2" will unintentionally delete information of project "pj2"
Once again: A relation is in 2NF if:
- Relation is in 1NF, and
- every non-key attribute is fully functionally determined by the primary key (In other words: you cannot find any non-key attribute that is functionally determined by only a (proper) subset of the primary key)
Relation Employee1 is not in 2NF because:
- Primary key is (SSN, PNumber)
- SSN -> FName
- (There are many more violations)
The $6,000,000,000 (inflation) question:
So what are you gonna do about it ???
A relation R that is NOT in 2NF can always be decomposed to an equivalent collection of 2NF relations.
A decomposition of a relation R is a collection of relations R1, R2, ..., Rn, such that each attribute in R1, R2, ..., Rn is in R and every attribute of R appears in R1, R2, ..., Rn at least once

The transformation process consists of replacing the None-2NF relation by a set of projections of the original relation.
The original relation can be obtained by taking the natural join of the projections
NOTE: the natural join operation on two relations joins the relations using the equality condition for every attribute that they have in common. If the relations do not have any attribute in common, the natural join is equal to a cartesian product

Example:

Employee1

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

Employee = Projection(SSN,FName,LName) Project = Projection(PNumber,PName,Hours)

SSN	FName	LName
111-11-1111	John	Smith
111-22-3333	Jane	Doe

PNumber	PName	Hours
pj1	DBApplet	20
pj2	WebServer	10
pj1	DBApplet	5

Collection of projection is: {(SSN,FName,LName), (PNumber,PName,Hours)}

This is a BAD decomposion because the natural join of the resulting tables does NOT equal to the original content:

SSN	FName	LName
111-11-1111	John	Smith
111-22-3333	Jane	Doe

PNumber	PName	Hours
pj1	DBApplet	20
pj2	WebServer	10
pj1	DBApplet	5

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-11-1111	John	Smith	pj1	DBApplet	5
111-22-3333	Jane	Doe	pj1	DBApplet	20
111-22-3333	Jane	Doe	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

is different from the original content:

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

Notice: all original tuples are present in natural join
BUT: there are some "extraneous" tuples.
What does this mean: a tuple represents a fact (something true) in the real world. Extraneous tuples introduced will corrupt the "truth" of the database.
The decomposition must NOT introduce untrue fiction; i.e., it must not introduce new tuples.

Another Example:

Take the same relation again: Employee1

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

Employee = Projection(SSN,FN,LN) Project = Projection(SSN,PNum,PName,Hours)

SSN	FName	LName
111-11-1111	John	Smith
111-22-3333	Jane	Doe

SSN	PNumber	PName	Hours
111-11-1111	pj1	DBApplet	20
111-11-1111	pj2	WebServer	10
111-22-3333	pj1	DBApplet	5

Collection of projection is: {(SSN,FName,LName), (SSN,PNumber,PName,Hours)}

This is a GOOD decomposion because the natural join of the resulting tables is equal to the original content:

SSN	FName	LName
111-11-1111	John	Smith
111-22-3333	Jane	Doe

SSN	PNumber	PName	Hours
111-11-1111	pj1	DBApplet	20
111-11-1111	pj2	WebServer	10
111-22-3333	pj1	DBApplet	5

SSN	FName	LName	PNumber	PName	Hours
111-11-1111	John	Smith	pj1	DBApplet	20
111-11-1111	John	Smith	pj2	WebServer	10
111-22-3333	Jane	Doe	pj1	DBApplet	5

is the SAME as the original content !!!

A decomposition of a relation R into 2 relations R1 and R2 is called lossless iff
```
		 R1 * R2 = R
```
So can we guarantee that a decomposition to be lossless ???
- Yes: click here
Decomposition is "relatively" easy if you use "semantics" to guide you in the decomposition. But semantics is very difficult to be use objectively.
So to prove that the decomposition technique is useful, let us try to decompose the following relation:
```
	R = (A, B, C, D, E, F, G)

	A   -> B, C
	D   -> E, F
	A,D -> G
```
- Step 0: Is (A, B, C, D, E, F, G) in 2NF ?
  In other words:
  - Does every non-key attribute fully dependent on the primary key ?
  We CANNOT answer this question without first finding the key(s) !!!
- Step 1: Find the key(s) (This is the HARDEST step)
```
	(A, D)
	
```
- Step 2: find non-key attributes (easy after you found the key...)
```
	B, C, E, F, G
	
```
- Step 3: is (A, B, C, D, E, F, G) in 2 NF ?
```
	No:   A -> B, C
	
```
- Step 4: Decompose: remove the violating FD (remove A) !
  Compute: A⁺ to fond all the attributes that "belongs" to A
```
	A⁺ = A B C
	
```
  Decompose (A, B, C, D, E, F, G) into:
```
	R₁ = (A, B, C)		   (A⁺)
	R₂ = (A, D, E, F, G)	 (We need to satisfy Lemma 2 !)
	
```
- Step 5: Check !
```
	R₁ = (A, B, C)		  Key = A		is in 2NF
	R₂ = (A, D, E, F, G)	Key = (A,D)	is NOT in 2NF !!
	
```
- Repeat procedure for R₂ = (A, D, E, F, G)
```
	Key = (A,D)
	Non-key attributes: E, F, G
	Violation: D -> E, F
	D⁺ = D E F
	
```
  Decompose R₂ = (A, D, E, F, G) into
```
	   R₃ = (D, E, F)
	   R₄ = (A, D, G)
	
```
- Result:
```
  (A, B, C)
  (D, E, F)
  (A, D, G)
  
```
- Now, plug in a real world example:
```
  A = SSN		D = PNumber			  G = Hours
  B = FName	  E = PName
  C = LName	  F = ControllingDept

  A   -> B, C
  D   -> E, F
  A,D -> G

  Result:

  (SSN, FName, LName)
  (PNumber, PName, ControllingDept)
  (SSN, PNumber, Hours)
  
```
Pretty amazing...