NORMALIZATION
Normalization
• Normalization is the process of
minimizing redundancy (several copy of same
data) from a relation or set of relations.
• Redundancy in relation may cause insertion,
deletion, and update anomalies.
• So, it helps to minimize the redundancy in
relations. Normal forms are used to eliminate
or reduce redundancy in database tables.
First Normal From
• A table is in the first normal form iff
– The domain of each attribute contains only
atomic values, and
– The value of each attribute contains only a single
value from that domain.
First Normal From
• Each table cell should contain only a single
value.
• Each column should have a unique name.
• The first normal form helps to eliminate
duplicate data and simplify queries.
Example
• For a library
Student Borrowed books
ID
CSE32 B33, B44, B55
CSE33 B56
1-NF Solution
Student ID Borrowed book
CSE35 B33
CSE35 B44
CSE35 B33
CSE32 B56
Implication for the ER model
• Watch for entities that can have multiple
values for the same attribute
– Phone numbers, …
• What about course schedules?
– MW 5:30-7:00pm
• Can treat them as atomic time slots
Functional dependency
Let X and Y be sets of attributes in a table T
• Y is functionally dependent on X in T iff for
each set x R.X there is precisely one
corresponding set y R.Y
• Y is fully functional dependent on X in T if Y is
functional dependent on X and Y is not
functional dependent on any proper subset of
X
Example
• Book table
BookNo Title Author Year
B1 Moby Dick H. Melville 1851
B2 Lincoln G. Vidal 1984
Author attribute is:
functionally dependent on the pair
{ BookNo, Title}
fully functionally dependent on BookNo
Why it matters
• table BorrowedBooks
BookNo Patron Address Due
B1 J. Fisher 101 Main Street 3/2/15
B2 L. Perez 202 Market Street 2/28/15
Address attribute is
functionally dependent on the pair
{ BookNo, Patron}
fully functionally dependent on Patron
Problems
• Cannot insert new patrons in the system until
they have borrowed books
– Insertion anomaly
• Must update all rows involving a given patron if
he or she moves.
– Update anomaly
• Will lose information about patrons that have
returned all the books they have borrowed
– Deletion anomaly
Armstrong inference rules (1974)
• Axioms:
– Reflexivity: if YX, then X→Y
– Augmentation: if X→Y, then WX→WY
– Transitivity: if X→Y and Y→Z, then X→Z
• Derived Rules:
– Union: if X→Y and X→Z, the X→YZ
– Decomposition: if X→YZ, then X→Y and X→Z
– Pseudotransitivity: if X→Y and WY→Z, then XW→Z
Armstrong inference rules (1974)
• Axioms are both
– Sound:
when applied to a set of functional dependencies
they only produce dependency tables that belong
to the transitive closure of that set
– Complete:
can produce all dependency tables that belong to
the transitive closure of the set
Armstrong inference rules (1974)
• Three last rules can be derived from the first
three (the axioms)
• Let us look at the union rule:
if X→Y and X→Z, the X→YZ
• Using the first three axioms, we have:
– if X→Y, then XX→XY same as X→XY (2nd)
– if X→Z, then YX→YZ same as XY→YZ (2nd)
– if X→XY and XY→YZ, then X→YZ (3rd)
Second Normal Form
• A table is in 2NF iff
– It is in 1NF and
– no non-prime attribute is dependent on any
proper subset of any candidate key of the table
• A non-prime attribute of a table is an
attribute that is not a part of any candidate
key of the table
• A candidate key is a minimal superkey
Second Normal Form
• 2NF eliminates redundant data by requiring
that each non-key attribute be dependent on
the primary key.
• It implies that each column should be directly
related to the primary key, and not to other
columns.
Example
• Library allows patrons to request books that
are currently out
BookNo Patron PhoneNo
B3 J. Fisher 555-1234
B2 J. Fisher 555-1234
B2 M. Amer 555-4321
Example
• Candidate key is {BookNo, Patron}
• We have
– Patron → PhoneNo
• Table is not 2NF
– Potential for
• Insertion anomalies
• Update anomalies
• Deletion anomalies
2NF Solution
• Put telephone number in separate Patron
table
BookNo Patron Patron PhoneNo
B3 J. Fisher J. Fisher 555-1234
B2 J. Fisher M. Amer 555-4321
B2 M. Amer
Third Normal Form
• A table is in 3NF iff
– it is in 2NF and
– all its attributes are determined only by its
candidate keys and not by any non-prime
attributes
Example
• Table BorrowedBooks
BookNo Patron Address Due
B1 J. Fisher 101 Main Street 3/2/15
B2 L. Perez 202 Market Street 2/28/15
Candidate key is BookNo
Patron → Address
3NF Solution
• Put address in separate Patron table
BookNo Patron Due
B1 J. Fisher 3/2/15
B2 L. Perez 2/28/15
Patron Address
J. Fisher 101 Main Street
L. Perez 202 Market Street
Another example
• Tournament winners
Tournament Year Winner DOB
Indiana Invitational 1998 Al 21 July 1975
Fredrickson
Cleveland Open 1999 Bob Albertson 28 Sept. 1968
Des Moines Masters 1999 Al 21 July 1975
Fredrickson
• Candidate key is {Tournament, Year}
• Winner →DOB
Boyce-Codd Normal Form
• Stricter form of 3NF
• A table T is in BCNF iff
– for every one of its non-trivial dependencies
X → Y, X is a super key for T
• Most tables that are in 3NF also are in BCNF
Example
Manager Project Branch
Alice Alpha Austin
Alice Delta Austin
Carol Alpha Houston
Dean Delta Houston
• We can assume
– Manager → Branch
– {Project, Branch} → Manager
Example
Manager Project Branch
Alice Alpha Austin
Bob Delta Houston
Carol Alpha Houston
Alice Delta Austin
• Not in BCNF because Manager → Branch and
Manager is not a superkey
• Will decomposition work?
A decomposition (I)
Manager Project Manager Branch
Alice Alpha Alice Austin
Bob Delta Bob Houston
Carol Alpha Carol Houston
Alice Delta
• Two-table solution does not preserve the
dependency {Project, Branch} → Manager
A decomposition (II)
Manager Project Manager Branch
Alice Alpha Alice Austin
Bob Delta Bob Houston
Carol Alpha Carol Houston
Alice Delta Dean Houston
Dean Delta
• Cannot have two or more managers managing
the same project at the same branch
Multivalued dependencies
• Assume the column headings in a table are
divided into three disjoint groupings X, Y, and
Z
• For a particular row, we can refer to the data
beneath each group of headings as x, y, and z
respectively
Multivalued dependencies
• A multivalued dependency X =>Y occurs if
– For any xc actually occurring in the table and the list of
all the xcyz combinations that occur
in the table, we will find that xc is associated with the
same y entries regardless of z.
• A trivial multivalued dependency X =>Y is one
where either
• Y is a subset of X, or
• Z is empty (X Y has all column headings)
Fourth Normal Form
• A table is in 4NF iff
– For every one of its non-trivial multivalued
dependencies X => Y, X is either:
• A candidate key or
• A superset of a candidate key
Example from Wikipedia
Restaurant Pizza DeliveryArea
Pizza Milano Thin crust SW Houston
Pizza Milano Thick SW Houston
crust
Pizza Firenze Thin crust NW Houston
Pizza Firenze Thick NW Houston
crust
Pizza Milano Thin crust NW Houston
Pizza Milano Thick NW Houston
crust
Discussion
• The table has no non-key attributes
– Key is { Restaurant, Pizza, DeliveryArea}
• Two non-trivial multivalued dependencies
– Restaurant => Pizza
– Restaurant => DeliveryArea
since each restaurant delivers the same pizzas
to all its delivery areas
4NF Solution Restaurant DeliveryArea
Pizza Milano SW Houston
Pizza NW Houston
Firenze
Pizza Milano NW Houston
• Two separate tables
Restaurant Pizza
Pizza Milano Thin crust
Pizza Milano Thick crust
Pizza Firenze Thin crust
Pizza Firenze Thick crust
Join dependency
• A table T is subject to a join dependency if it can
always be recreated by joining multiple tables
each having a subset of the attributes of T
• The join dependency is said to be trivial if one of
the tables in the join has all the attributes of the
table T
• Notation: *{ A, B, …} on T
Fifth normal form
• A table T is said to be 5NF iff
– Every non-trivial join dependency in it is implied
by its candidate keys
• A join dependency *{A, B, … Z} on T is implied
by the candidate key(s) of T if and only if each
of A, B, …, Z is a superkey for T
An example
Store Brand Product
Circuit City Apple Tablets
Circuit City Apple Phones
Circuit City Toshiba Laptops
CompUSA Apple Laptops
• Note that Circuit City sells Apple tablets and
phones but only Toshiba laptops
A very bad decomposition
Store Product Brand Product
Circuit City Tablets Apple Tablets
Circuit City Phones Apple Phones
Circuit City Laptops Apple Laptops
CompUSA Laptops Toshiba Laptops
• Let see what happens when we do a natural join
The result of the join
Store Brand Product
Circuit City Apple Tablets
Circuit City Apple Phones
Circuit City Apple Laptops
Circuit City Toshiba Laptops
CompUSA Apple Laptops
CompUSA Toshiba Laptops
• Introduces two spurious tuples
A different table
Store Brand Product
Circuit City Apple Tablets
Circuit City Apple Phones
Circuit City Apple Laptops
Circuit City Toshiba Laptops
CompUSA Apple Laptops
• Assume now that any store carrying a given
brand and selling a product that is made by that
brand will always carry that product
The same decomposition
Store Product Brand Product
Circuit City Tablets Apple Tablets
Circuit City Phones Apple Phones
Circuit City Laptops Apple Laptops
CompUSA Laptops Toshiba Laptops
• Let see what happens when we do a natural join
The result of the join
Store Brand Product
Circuit City Apple Tablets
Circuit City Apple Phones
Circuit City Apple Laptops
Circuit City Toshiba Laptops
CompUSA Apple Laptops
CompUSA Toshiba Laptops
• Still one spurious tuple
The right decomposition
Store Product Brand Product
Circuit City Tablets Apple Tablets
Circuit City Phones Apple Phones
Circuit City Laptops Apple Laptops
CompUSA Laptops Toshiba Laptops
Store Brand
Circuit City Apple
Circuit City Toshiba
CompUSA Apple
Conclusion
• The first "big" table was 5NF
• The second table was decomposable
Lossless
Decomposition
General Concept
• If R(A, B, C) satisfies AB
– We can project it on A,B and A,C
without losing information
– Lossless decomposition
• R = AB(R) ⋈ AC(R)
– AB(R) is the projection of R on AB
– ⋈ is the natural join operator
Example
Course Instructor Text
4330 Paris none
4330 Cheng none
3330 Hillford Patterson & Hennessy
• Observe that Course Text
A lossless decomposition
Course Text
Course, Text (R) 4330 none
3330 Patterson & Hennessy
Course Instructor
4330 Paris
Course, Instructor (R)
4330 Cheng
3330 Hillford
A different case
Course Instructor Text
4330 Paris Silberschatz and Peterson
4330 Cheng none
3330 Hillford Patterson & Hennessy
• Now Course Text
• R cannot be decomposed
A lossy decomposition
Course Text
4330 none
Course, Text (R)
4330 Silberschatz & Peterson
3330 Patterson & Hennessy
Course Instructor
4330 Paris
Course, Instructor (R) 4330 Cheng
3330 Hillford
An Example
Normalisation Example
• We have a table • Columns
representing orders in – Order
an online store – Product
• Each row represents an – Quantity
item on a particular
– UnitPrice
order
• Primary key is – Customer
{Order, Product} – Address
Functional Dependencies
• Each order is for a single customer:
– Order Customer
• Each customer has a single address
– Customer Address
• Each product has a single price
– Product UnitPrice
• As Order Customer and Customer Address
– Order Address
2NF Solution (I)
• First decomposition
– First table
Order Product Quantity UnitPrice
– Second table
Order Customer Address
2NF Solution (II)
• Second decomposition
– First table
Order Product Quantity
– Second table
Order Customer Address
– Third table
Product UnitPrice
3NF
• In second table
Order Customer Address
– Customer Address
• Split second table into
Order Customer
Customer Address
Normalisation to 2NF
• Second normal form means • To remove the first FD we
no partial dependencies on project over
candidate keys {Order, Customer,
– {Order} {Customer, Address} (R1)
Address} and
– {Product} {UnitPrice} {Order, Product, Quantity, UnitPrice}
(R2)
Normalisation to 2NF
• R1 is now in 2NF, but there • To remove this we project over
is still a partial FD in R2 {Product, UnitPrice} (R3)
{Product} {UnitPrice} and
{Order, Product, Quantity} (R4)
Normalisation to 3NF
• R has now been split into 3 • To remove
relations - R1, R3, and R4 {Order} {Customer}
– R3 and R4 are in 3NF {Address}
– R1 has a transitive FD on • we project R1 over
its key – {Order, Customer}
– {Customer, Address}
Normalisation
• 1NF:
– {Order, Product, Customer, Address, Quantity, UnitPrice}
• 2NF:
– {Order, Customer, Address}, {Product, UnitPrice}, and
{Order, Product, Quantity}
• 3NF:
– {Product, UnitPrice}, {Order, Product, Quantity},
{Order, Customer}, and {Customer, Address}