Normalization

Functional Dependency (FD)

restriction is derived from the meaning of attributes and relationships between attributes
There is a functional dependency from X to Y indicates that the value of attribute X determine the unique value of attribute Y
- Written as X --> Y
- Can be read as: determine the X or Y, Y is determined by the X or, there are functional dependency from X to Y
- FD is obtained from the fact that there is (obtained at the analysis system)

Example :

• Relation instance Teach potentially have on the functional dependency TEXT --> COURSE

• There is no FD TEACHER -->COURSE
• FD should apply to all lines in the relationship. To determine the FD must understand the semantics of data, consider the instance that there is now and will have in the future.

On the relations EMP_PROJ there are 3 FD:
• (SSN, PNUMBER) --> HOURS
• SSN --> ENAME
• PNUMBER --> PNAME, PLOCATION


Normalization
Normalization should be performed for:
- Optimization table structures
- Increase the speed
- Eliminate income data the same
- More efficient use of storage media
- Reduce redundancy
- Avoiding anomalies (insertion anomalies, deletion anomalies, update anomalies).
- Improved data integrity

• There are several normal forms based on a number of criteria:
- Primary keys (1NF, 2NF, 3NF)
- All Candidate Keys (2NF, 3NF, BCNF)
- Multivalued dependencies (4NF)
- Join dependencies (5NF)

Normalization should be done in order to design the database that produced good quality and meet the desired nature. Normalization in practice difficult to do if the restrictions of a basic normalization difficult to understand or difficult to detect. The database does not need to do a form of normalization to the highest, usually done to achieve 3NF or BCNF

Denormalisasi: reverse process of normalization, ie, combine several relations, brought to normal form of a lower

First Normal form (1NF)
First normal form (1NF) is part of the definition of relations.
• The form does not allow the normal first:
- Composite attributes,
- Multivalue attributes,
- Nested relations.

Second Normal form (2NF)
• Using the concept of FD and the primary key
• Definition:
- Full functional dependency: a FD X --> Y if such until one of the attribute of X removed, then the FD is not there anymore.
• Example:
- (SSN, PNUMBER) --> HOURS is a full FD, as there is no SSN --> HOURS, and PNUMBER --> HOURS
- (SSN, ENAME --> PNUMBER) is a partial dependency, not because there is a full FD dependency SSN ENAME
• A relation R is in second normal form (2NF) if R is in 1NF and every nonprime attribute A in relation R is functional dependent on the full primary key.
• A relation R can didekomposisi to-customer relationships that meet 2NF through the process of 2NF normalization

Third Normal form (3NF)
• A relation R is in third normal form (3NF) if R is in 2NF and no nonprime attribute A in R which has a transitive dependency on the primary key.
• A relation R can-decomposition relationships to meet the 3NF relations via the process of 3NF normalization
• Note:
- In the FD X -> Y and Y -> Z, with X as the primary key, we consider this as a problem only if Y is not a candidate key.
- If Y is a candidate key, there is no problem with this transitive dependency
- Example: Relations EMP (SSN, Emp #, Salary) does not violate 3NF because even though there are FD SSN à Emp # à Salary, Emp # is a candidate key

Normal is defined in the form of informal
• 1st normal form
- All attributes depend on the key
• 2nd normal form
- All attributes depend on the whole key
• 3rd normal form
- All attributes depend on nothing but the key

Boyce Codd Normal Form (BCNF)
• A relation scheme R is in BCNF with the requirement if there are X à FD on R, then X is superkey of R.
• Every BCNF definitely meet 3NF
• There are relationships that are in 3NF but not BCNF
• Goal to achieve normalization generally 3NF or BCNF

example
• There are 2 FD on the relation Teach:
- Fd1: (student, course) -> instructor
- Fd2: instructor -> course
• (student, course) is a candidate key to reach
- Relations are located in 3NF but not in BCNF
• BCNF relations that have not been able to achieve BCNF decomposition, but sometimes the FD can eliminate the existing

• There are 3 decomposition is possible to teach the relation:
- (Student, instructor) and (student, course)
- (Course, instructor) and (course, student)
- (Instructor, course) and (instructor, student)
• All is lost decomposition FD1
- All of the FD relations are kept as much as possible, but can also disappear in the normalization BCF
- However, the nature of lossless and non-additivity property after decomposition must remain guarded

Normal form of the fourth and fifth
• Relations in fourth normal form (NF 4) if the relation in BCNF and does not contain a lot of dependence values. To remove the dependency of many values from a relation, we divide the relationship into two new relations. Each relation contains two attributes that have a lot of relationship value.

• Relations in fifth normal form (5NF) deal with the property called the join without any loss of information (lossless join). Fifth normal form (also called the 5 NF PJNF (projection join normal form). The case is very rare and appear difficult to detect in practice.