Normalization - To study the process of normalization. - Computer Programming

# Computer Programming

C C++ Java Python Perl Programs Examples with Output -useful for Schools & College Students

## Wednesday, October 27, 2010

DESCRIPTION OF NORMALIZATION

DEFINITION

Normalization is the process of decomposing a relation schema into fragments / sub-relations. It is a technique for producing a set of relations with desirable properties, given the data requirements of an enterprise. It is a formal method that can be used to identify relations based on their keys and the functional dependencies among their attributes. It is a refinement process and has two properties namely,
·         Lossless Decomposition
·         Dependency Preservation decomposition

DIFFERENT NORMAL FORMS

UNNORMALIZED FORM
A relation that contains one or more repearting groups.

FIRST NORMAL FORM (1NF)
A relation in which the intersection of each row and column contains one and only one value. (no repeating groups and atomic values)

SECOND NORMAL FORM (2NF)
A relation that is in first normal form and every non primary key attribute is fully functionally dependent on any candidate key. (eliminate partial dependency)

THIRD NORMAL FORM (3NF)
A relation that is in first and second normal form and in which no non primary key attribute is transitively dependent on any candidate key. (eliminate transitive dependency)

BOYCE-CODD NORMAL FORM (BCNF)
A relation is in BCNF if and only if every determinant is a candidate key.(all determinants – candidate keys)

FOURTH NORMAL FORM (4NF)
A relation that is in Boyce–codd normal form and contains no nontrivial multi-valued dependencies. ( eliminate multi valued dependency)

FIFTH NORMAL FORM (5NF)
A relation that has no join dependency.(eliminate join dependency)
DESCRIPTION OF FUNCTIONAL DEPENDENCY (FD)

DEFINITION
A functional dependency from X to Y exists if and only if for every instance of |R| of R, if two tuples in |R| agree on the values of the attributes in X, then they agree on the values of the attributes in Y.
Eg: XàY ie. X determines Y (or) Y is functionally dependent on X.
The determinant of a FD refers to the attribute, or group of attributes on the left hand side of the arrow.

FORMS OF DEPENDENCIES

FULL DEPENDENCY
A functional dependency XàY is a full FD if the dependency does not hold on removal of any attribute ‘a’ from the set of attributes A in X ie. if A and B are attributes of a relation, B is fully functionally dependent on A, if B is functionally dependent on A but not on any proper subset of A..

PARTIAL DEPENDENCY
A functional dependency XàY is a partial FD if some attribute A that belongs to X, can be removed from X and the dependency still holds.

For example consider the table EMPLOYEE ,

 Employee name Serial no Project no hours Project name Project location Aaa 1000 501 10 hospital 1st floor Bbb 1005 505 20 inventory 8th floor Ccc 1009 509 30 analysis 9th floor

The functional dependencies for this relation are as follows,
{serial no , project no} à {hours}
If any of the attributes are removed the relationship cannot be determined . So this is full FD.
{ serial no , project no } à {project name}
{ serial no , project no } à {employee name}
{project no } à {project name , project location}
In these FD’s on removal of one attribute also the relationship exists. So this is partial FD.

TRANSITIVE DEPENDENCY
A condition where A, B and C are attributes of a relation such that if AàB and BàC , then C is transitively dependent on A via B (provided that A is not functionally dependent on B or C).

MULTI – VALUED DEPENDENCY
Represents a dependency between attributes for example A, B and C in a relation, such that each value of A there is a set of values for B and a set of values for C.. However, the set of values for B and C are independent of each other.

LOSSLESS JOIN DEPENDENCY
A property of decomposition, which ensures that no spurious tuples are generated when relations are reunited through a natural join operation.

JOIN DEPENDENCY
Describes a type of dependency. For example, for a relation R with subsets of the attributes of R denoted as A,B,…..,Z, a relation R satisfies a join dependency if, and only if, every legal value of R is equal to the join of its projections on A,B,…..,Z.

APPLICATION

This is an example of an unnormalized table

CLIENT RENTAL

 Client No Cname Property No Paddress Rentstart Rentfinish Rent Owner no Oname CR76 John Kay PG4 PG16 6,Lawrence St,Glasgow5,Novar Dr,Glasgow 1-Jul-00 1-Sep-02 31-Aug-01 1-Sep-02 350 450 CO40 CO93 Tina Murphy Tony Shaw CR56 Aline Stewart PG4 PG36 PG16 6,Lawrence St,Glasgow2,Manor Rd,Glasgow5,Novar Dr,Glasgow 1-Sep-99 10-Oct-00 1-Nov-02 10-Jun-00 1-Dec-01 10-Aug-03 350 375 450 CO40 CO93 CO93 Tina Murphy Tony Shaw Tony shaw

Client  (Client No,Cname)

FIRST NORMAL FORM

CLIENT

 Client No Cname CR76 John Kay CR56 Aline Stewart

PROPERTY RENTAL OWNER

 Client No Property No Paddress Rentstart Rentfinish Rent Owner No Oname CR76 PG4 6, Lawrence St,Glasgow 1-Jul-00 31-Aug-01 350 CO40 Tina Murphy CR76 PG16 5 Novar Dr, Glasgow 1-Sep-01 1-Sep-02 450 CO93 Tony Shaw CR56 PG4 6 Lawrence St,Glasgow 1-Sep-99 10-Jun-00 350 CO40 Tina Murphy CR56 PG36 2 Manor Rd,Glasgow 10-Oct-00 1-Dec-01 375 CO93 Tony Shaw CR56 PG16 5 Novar dr,Glasgow 1-Nov-02 10-Aug-03 450 CO93 Tony Shaw

SECOND NORMAL FORM

CLIENT
 Client No Cname CR76 John Kay CR56 Aline Stewart

RENTAL

 Client No Property No Rentstart Rentfinish CR76 PG4 1-Jul-00 31-Aug-01 CR76 PG16 1-Sep-01 1-Sep-02 CR56 PG4 1-Sep-99 10-Jun-00 CR56 PG36 10-Oct-00 1-Dec-01 CR56 PG16 1-Nov-02 10-Aug-03

 Property no Paddress Rent Owner no Oname PG4 6, Lawrence St, Glasgow 350 CO40 Tina Murphy PG16 5 Novar Dr,  Glasgow 450 CO93 Tony Shaw PG36 2 Manor Rd, Glasgow 375 CO93 Tony Shaw

PROPERTY OWNER

THIRD NORMAL FORM

PROPERTY FOR RENT

 Property No Paddress Rent Owner No PG4 6, Lawrence St,Glasgow 350 CO40 PG16 5 Novar Dr, Glasgow 450 CO93 PG36 2 Manor Rd,Glasgow 375 CO93

OWNER
 Owner No Oname CO40 Tina Murphy CO93 Tony Shaw

CLIENT
 Client no Cname Cr76 John kay Cr56 Aline stewart

RENTAL

 Client No Property No Rentstart Rentfinish CR76 PG4 1-Jul-00 31-Aug-01 CR76 PG16 1-Sep-01 1-Sep-02 CR56 PG4 1-Sep-99 10-Jun-00 CR56 PG36 10-Oct-00 1-Dec-01 CR56 PG16 1-Nov-02 10-Aug-03

PROPERTYFORRENT
 Property No Paddress Rent Owner No PG4 6, Lawrence St,Glasgow 350 CO40 PG16 5 Novar Dr, Glasgow 450 CO93 PG36 2 Manor Rd,Glasgow 375 CO93

OWNER
 Owner No Oname CO40 Tina Murphy CO93 Tony Shaw

BOYCE CODD NORMAL FORM

CLIENT INTERVIEW

 Client No Interview Date Interview Time Staff No Room No CR76 13-May-02 10.30 SG5 G101 CR56 13-May-02 12.00 SG5 G101 CR74 13-May-02 12.00 SG37 G102 CR56 1-Jul-02 10.30 SG5 G102

INTERVIEW

 Client No Interview Date Interview Time Staff No CR76 13-May-02 10.30 SG5 CR56 13-May-02 12.00 SG5 CR74 13-May-02 12.00 SG37 CR56 1-Jul-02 10.30 SG5

STAFFROOM

 Interview Date Staff No Room No 13-May-02 SG5 G101 13-May-02 SG5 G101 13-May-02 SG37 G102 1-Jul-02 SG5 G102