Question

I'm not clear with decompose to 3NF for database. Can someone explain to me with example please?

Answer 1

Decomposition of a Relation Schema -

If a relation is not in a desired normal form, it can be decomposed into multiple relations that each are in that normal form.

Suppose that relation R contains attributes A1 ... An. A decomposition of R consists of replacing R by two or more relations such that: Each new relation scheme contains a subset of the attributes of R, and Every attribute of R appears as an attribute of at least one of the new relations.

Normalization Using Functional Dependencies-

When we decompose a relation schema R with a set of functional dependencies F into R1, R 2,.., R n we want -

1.Lossless-join Decomposition (complete reproduction)

2. No Redundancy (BCNF or 3NF)  

3. Dependency Preservation.

Lossless-join Decomposition--

All attributes of an original schema (R) must appear in the decomposition ( R1, R 2): R = R1 ∪ R 2

For all possible relations Ri on schema R

R = ∏ R1 ( R) natural join ∏R2 ( R)

We Want to be able to reconstruct big (e.g. universal) relation by joining smaller ones (using natural joins) (i.e. R1 natural join R2 = R)

Testing for Lossless-Join Decomposition -

Rule: A decomposition of R into (R1, R2) is lossless, iff: R1 ∩ R2 =key( R1 )or R1 ∩ R2 =key( R2) in F+.

Lossless- Example: Lossless-join Decomposition

R = {A,B,C,D,E}. F = {A →BC, CD →E, B → D, E →A }. Is the following decomposition a lossless join?

1. R1 = {A,B,C}, R2 ={A,D,E} Since R1 ∩ R2 = A , and A is a key for R 1 , the decomposition is lossless join.

2. R1 = {A,B,C}, R2 ={C,D,E} Since R1 ∩ R2 = C, and C is not a key for R1 or R2, the decomposition is not lossless join.

Dependency Preserving Decomposition -

The decomposition of a relation scheme R with FDs F is a set of tables (fragments) Ri with FDs Fi

Fi is the subset of dependencies in F+ (the closure of F) that include only attributes in Ri.

The decomposition is dependency preserving iff (∪ i F i)+ = F+ .

In other words: we want to minimize the cost of global integrity constraints based on FD’s ( i.e. avoid big joins in assertions) ( F 1 ∪ F2 ∪ … ∪ Fn ) + = F + (F+ = closure of F).

Third Normal Form Decomposition-

Third Normal Form 3NF: A schema R is in third normal form (3NF) if for all FD α → β in F +, at least one of the following holds:

(1) α → β is trivial (i.e., β ⊆ α).

( 2 ) α is a superkey superkey for R.

(3)Each attribute A in β – α is contained in a candidate key for R (prime).

The decomposition is both lossless-join and dependency-preserving.

Third Normal Form -

A relational schema R is in 3NF if for every FD X → A associated with R either: A ⊆ X (i.e., the FD is trivial) or X is a superkey of R or A is part of some key (not just superkey!) 3NF weaker than BCNF (every schema that is in BCNF is also in 3NF).

Third Normal Form

Compromise - Not all redundancy removed, but dependency-preserving decompositions are always possible

3NF decomposition is based on the concept of minimal cover of a set of FDs.

Decomposition---

(1) Eliminate redundant FDs, resulting in a canonical cover Fc of F

(2) Create a relation Ri = XY for each FD X → Y in Fc

(3) If the key K of R does not occur in any relation Ri, create one more relation Ri=K

Example

R =(A, B, C, D). F = {C→D, C→A, B→C}.

Decompose R into a set of 3NF relations.

The canonical cover is Fc = {C→DA, B→C}. For each functional dependency in Fc we create a table: R1 = {C, D, A}, R2 = {B, C}. The table R2 contains the candidate key for R – we done.