DATABASE MANAGEMENT SYSTEMS Unit IV Normalization

K Vydehi

Assistant Professor

Department of CSE

Aditya University

DBMS K Vydehi, Asst Professor, CSE Dept.

2

Normalization is a process of making relations by decomposing them into smaller relations to

1. Reduce redundancy:- some information is stored repeatedly.
2. Eliminate update anomaly:- if one copy of repeated data is updated, an inconsistency is created unless all copies are similarly updated.
3. Eliminate delete anomaly:- it may not be possible to delete some information without losing other information.
4. Eliminate insert anomaly:- it may not be possible to store some information unless some other information is stored as well.

Definitions

​

DBMS K Vydehi, Asst Professor, CSE Dept.

3

Hourly Emps(ssn, name, lot, rating, hourly wages, hours _worked)

Hourly_Emps

Hourly_Emps2

Wages

DBMS K Vydehi, Asst Professor, CSE Dept.

4

An attribute is functionally dependent on another. If we can use the value of one attribute to determine the value of another.

y is functionally dependent on x

or

x determines y

Ex:-ssn Employee_name

ssn can be used to uniquely identify by an employee_name

Functional Dependency

FID FNAME

CID CNAME

DBMS K Vydehi, Asst Professor, CSE Dept.

5

Closure of a set of Functional Dependencies

A Closure is a set of FDs is a set of all possible FDs that can be derived from a given set of FDs. This closure set is denoted by F+.

Armstrong Rules

x,y,z denote set of attributes over a relation R

​

DBMS K Vydehi, Asst Professor, CSE Dept.

6

Closure of a set of Functional Dependencies

Step 1:

​

​

​

Step2:

​

​

​

Step 3:

​

Step 4:

DBMS K Vydehi, Asst Professor, CSE Dept.

7

Attribute Closure

Input:-Set of Functional dependencies(F) and set of attributes(α)

Output:-stored in a variable result. Finding the super key

DBMS K Vydehi, Asst Professor, CSE Dept.

8

Attribute Closure

(AG)+ is a super key as result variable contains all the attributes in R

DBMS K Vydehi, Asst Professor, CSE Dept.

9

Normal Forms

First Normal Form :-A relation is in 1NF if every attribute in every row can contain only one single value.

DBMS K Vydehi, Asst Professor, CSE Dept.

10

First Normal Form

FIRST(SUPPLIER_NO,STATUS,CITY,PART_NO,QUANTITY)

PRIMARY KEY(SUPPLIER_NO,PART_NO)

FD:- SUPPLIER_NO🡪CITY

CITY🡪STATUS

PART_NO🡪QUANTITY

DBMS K Vydehi, Asst Professor, CSE Dept.

11

First Normal Form

Insert Anomaly:-we cannot insert supplier information until that supplier supplies atleast one part.

Delete Anomaly:- If we delete a tuple in FIRST with supplier_no s3 and part_no p3, we lose the information that s3 is located in chennai.

Update Anomaly:- If supplier s1 moves from bombay to ahmedabad, to find every tuple s1 and bombay and to replace it.

Table FIRST contains too much information packed together. Unpack-to place shipment information in one table and supplier information in another.

DBMS K Vydehi, Asst Professor, CSE Dept.

12

Second Normal Form

A relation is in 2NF if and only if it is in 1NF and every nonkey attribute is dependent on the primary key.(no partial dependency)

​

​

​

​

​

​

​

​

​

​

SECOND(SUPPLIER_NO,STATUS,CITY)

PRIMARY KEY(SUPPLIER_NO)

SHIPMENTS(SUPPLIER_NO,PART_NO,QUANTITY)

PRIMARY KEY(SUPPLIER_NO,PART_NO)

FOREIGN KEY(SUPPLIER_NO) REFERENCES SECOND(SUPPLIER_NO)

DBMS K Vydehi, Asst Professor, CSE Dept.

13

Second Normal Form

Insert Anomaly:-we can insert information that s5 is located in Delhi,even s5 doesn’t currently supply any parts.

Delete Anomaly:-we can delete s3p3 in shipments table, we don't lose information that s3 is located in chennai.

Update Anomaly:-we can change the city for s1 from bombay to ahmedabad by changing it once in SECOND table.

Primary key attributes-Supplier_no,Part_no

Nonkey attributes-status,city,quantity

DBMS K Vydehi, Asst Professor, CSE Dept.

14

Third Normal Form

A relation is in 3NF if & only if it is in 2NF and every non key attribute is non transitively dependent on the primary key.(No transitive dependency).

Supplier_no🡪City

City🡪Status

Then Supplier_no🡪status

Insert Anomaly:-we cannot insert a supplier in bangalore have status of 50 until some supplier actually located in that city.

Delete Anomaly:-we can delete supplier s5 without losing status for delhi is 30. unpack- supplier information in one table & city information in another.

Update Anomaly:-we need to change the status for bombay from 20 to 40 we need to find every tuple for bombay for changing it.

DBMS K Vydehi, Asst Professor, CSE Dept.

15

Third Normal Form

CS(CITY,STATUS)

PRIMARY KEY(CITY)

SC(SUPPLIER_NO,CITY)

PRIMARY KEY(SUPPLIER_NO)

FOREIGN KEY(CITY) REFERENCES CS(CITY)

DBMS K Vydehi, Asst Professor, CSE Dept.

16

Boyce-codd normal form

A relation is in 3NF and every determinant is a candidate key. If we join BCNF two relations then 3NF relation is obtained.

​

​

​

​

​

​

​

Supp(supplier_no,city,part_no,quantity)

FD:- Supplier_no🡪city

part_no🡪quantity

Supplier_no,part_no are determinants & candidate key

DBMS K Vydehi, Asst Professor, CSE Dept.

17

Boyce-codd normal form

SUPPL(SUPPLIER_NO,CITY)

PRIMARY KEY(SUPPLIER_NO)

SHIPMENT(SUPPLIER_NO,PART_NO,QUANTITY)

PRIMARY KEY(SUPPLIER_NO,PART_NO)

FOREIGN KEY(SUPPLIER_NO) REFERENCES SUPPL(SUPPLIER_NO)

DBMS K Vydehi, Asst Professor, CSE Dept.

18

Properties of Decomposition

1. Loss-less join decomposition

Let R be a relation schema and let F be a set of FDs over R. A decomposition of R into two schemas is said to be loss less join, if we recover original relation from decomposed relation. Otherwise it is lossy join.

We take projections of a relation and recombine them using natural join, to obtain original relation.

R

​

R1 R2

DBMS K Vydehi, Asst Professor, CSE Dept.

19

Dependency Preservation

It allows us to enforce all FDs by examining a single relation on each insertion or modification of a tuple.

Ex:-R(SUPPLIER_NO,STATUS,CITY,PART_NO,QUANTITY)

FD:- SUPPLIER_NO🡪CITY

CITY🡪STATUS

PART_NO🡪QUANTITY

R1(SUPPLIER_NO,STATUS,CITY)

FD1,FD2

R2(SUPPLIER_NO,PART_NO,QUANTITY)

FD3

R1,R2 Satisfies dependency preservation.

DBMS K Vydehi, Asst Professor, CSE Dept.

20

Fourth Normal Form

A relation is in 4NF if and only if it is in BCNF and all Multivalued dependencies in R are FDs out of keys.

Ex:-

Two or more multivalued facts about the same attribute occur in the same table.

R(A,B,C)

A,B,C-Attributes

B,C-Multivalued facts about A

MVD:-A🡪🡪B and A🡪🡪C

B is multi-dependent on A

Every FD is an MVD. But there exist MVDs that are not FDs.

DBMS K Vydehi, Asst Professor, CSE Dept.

21

Fourth Normal Form

​

FDS: EMPNO🡪SKILL

EMPNO🡪PROJECT_NO

MVDS: EMPNO🡪🡪SKILL

EMPNO🡪🡪PROJECT_NO

DBMS K Vydehi, Asst Professor, CSE Dept.

22

Fourth Normal Form

EMP_PROJECT(EMP_NO,PROJECT_NO)

EMP_SKILL(EMP_NO,SKILL)

DBMS K Vydehi, Asst Professor, CSE Dept.

23

Fifth Normal Form

A relation is in 4NF and that has no join dependency

if we combine 2 decompositions or projections using natural join we need to obtain loss less join decomposition--join dependency

​

​

​

​

​

​

​

​

Dept->->Subject Dept->->Student

DBMS K Vydehi, Asst Professor, CSE Dept.

24

Fifth Normal Form

Dept->->Subject Dept->->Student

DBMS K Vydehi, Asst Professor, CSE Dept.

25

Fifth Normal Form

If we combine the two decompositions we obtained this table

It is lossy join decomposition and join dependency

DBMS K Vydehi, Asst Professor, CSE Dept.

26

Fifth Normal Form

We need to decompose in the relation into two relations

Dept->->Subject Subject->->Student

DBMS K Vydehi, Asst Professor, CSE Dept.

Fifth Normal Form

​

We combine two relations using natural join. We obtain this relation. It is loss less join decomposition and no join dependency.

​

​

​

​

​

​

​

​

​

Surrogate Key: It is unique,notnull and updatable.

Ex:- Mobile_number

DBMS K Vydehi, Asst Professor, CSE Dept.

28

DBMS K Vydehi, Asst Professor, CSE Dept.

29

Thank You