CSE 544
Principles of Database
Management Systems
Fall 2016
Lecture 3 –Schema Normalization
CSE 544 - Fall 2016 1
Projects
• We have 27 teams
• Impossible to discuss projects at office hours tomorrow
• Instead, sign up on doodle for a 10’ slot on Monday.
CSE 544 - Fall 2016 2
Database Design
• The relational model is great, but how do I design my
database schema?
CSE 544 - Fall 2016 3
Outline
• Conceptual db design: entity-relationship model
• Problematic database designs
• Functional dependencies
• Normal forms and schema normalization
CSE 544 - Fall 2016 4
Database Design Process
Conceptual SQL
Refinement Files
Modeling Tables
Conceptual Schema
ER diagrams Physical Schema
Relations
CSE 544 - Fall 2016 5
Conceptual Schema Design
name
Conceptual Model: Patient patien_of Doctor
zip name dno
Relational Model:
plus FD’s
(FD = functional dependency)
Normalization:
Eliminates anomalies
CSE 544 - Fall 2016 6
Entity-Relationship Diagram
name
since
dno
pno
Patient patient_of Doctor
zip specialty name
Attributes Entity sets Relationship sets
name Patient patient_of 7
Entity-Relationship Model
• Typically, each entity has a key
Many One
• ER relationships can include multiplicity
– One-to-one, one-to-many, etc.
– Indicated with arrows
• Can model multi-way relationships
• Can model subclasses
• And more...
CSE 544 - Fall 2016 8
Subclasses to Product
Relations Name Price Category
name category Gizmo 99 gadget
Camera 49 photo
price
Toy 39 gadget
Product
[Link] Name platforms
isa isa
Gizmo unix
Software Product Educational Product [Link]
Age
platforms Age Group Name
Group
Gizmo toddler
Other ways to convert are possible Toy retired
CSE 544 - Fall 2016 9
General approach to Translating
Diagram into Relations
Normally translate as follows:
• Each entity set becomes a relation
• Each relationship set becomes a relation
– Except many-one relationships. Can combine them with entity set.
One bad way to translate our diagram into relations
• PatientOf (pno, name, zip, dno, since)
• Doctor (dno, dname, specialty)
CSE 544 - Fall 2016 10
Outline
• Conceptual db design: entity-relationship model
• Problematic database designs
• Functional dependencies
• Normal forms and schema normalization
CSE 544 - Fall 2016 11
Problematic Designs
• Some db designs lead to redundancy
– Same information stored multiple times
• Problems
– Redundant storage
– Update anomalies
– Insertion anomalies
– Deletion anomalies
CSE 544 - Fall 2016 12
Problem Examples
PatientOf
pno name zip dno since Redundant
1 p1 98125 2 2000 If we update
1 p1 98125 3 2003 to 98119, we
get inconsistency
2 p2 98112 1 2002
3 p1 98143 1 1985
What if we want to insert a patient without a doctor?
What if we want to delete the last doctor for a patient?
Illegal as (pno,dno) is the primary key, cannot have nulls
CSE 544 - Fall 2016 13
Solution: Decomposition
Patient PatientOf
pno name zip pno dno since
1 p1 98125 1 2 2000
2 p2 98112 1 3 2003
3 p1 98143 2 1 2002
3 1 1985
Decomposition solves the problem,
but need to be careful…
CSE 544 - Fall 2016 14
Lossy Decomposition
Patient PatientOf
pno name zip name dno since
1 p1 98125 p1 2 2000
2 p2 98112 p1 3 2003
3 p1 98143 p2 1 2002
p1 1 1985
Decomposition can cause us to lose information!
CSE 544 - Fall 2016 15
Schema Refinement Challenges
• How do we know that we should decompose a relation?
– Functional dependencies
– Normal forms
• How do we make sure decomposition does not lose info?
– Lossless-join decompositions
– Dependency-preserving decompositions
CSE 544 - Fall 2016 16
Outline
• Conceptual db design: entity-relationship model
• Problematic database designs
• Functional dependencies
• Normal forms and schema normalization
CSE 544 - Fall 2016 17
Functional Dependency
• A functional dependency (FD) is an integrity constraint
that generalizes the concept of a key
• An instance of relation R satisfies the FD: X ® Y
– if for every pair of tuples t1 and t2
– if t1.X = t2.X then t1.Y = t2.Y
– where X, Y are two nonempty sets of attributes in R
• We say that X determines Y
• FDs come from domain knowledge
CSE 544 - Fall 2016 18
FD Example
An FD holds, or does not hold on an instance:
EmpID Name Phone Position
E0045 Smith 1234 Clerk
E3542 Mike 9876 Salesrep
E1111 Smith 9876 Salesrep
E9999 Mary 1234 Lawyer
EmpID à Name, Phone, Position
Position à Phone
but not Phone à Position
CSE 544 - Fall 2016 19
FD Terminology
• FD’s are constraints
– On some instances they hold
– On others they do not
• If every instance of R will be one in which a given FD will
hold, then we say that R satisfies the FD
– If we say that R satisfies an FD F, we are stating a constraint on R
• FDs come from domain knowledge
CSE 544 - Fall 2016 20
Decomposition Problems
• FDs will help us identify possible redundancy
– Identify redundancy and split relations to avoid it.
• Can we get the data back correctly ?
– Lossless-join decomposition
• Can we recover the FD’s on the ‘big’ table from the FD’s
on the small tables?
– Dependency-preserving decomposition
– So that we can enforce all FDs without performing joins
CSE 544 - Fall 2016 21
Outline
• Conceptual db design: entity-relationship model
• Problematic database designs
• Functional dependencies
• Normal forms and schema normalization
CSE 544 - Fall 2016 22
Normal Forms
• Based on Functional Dependencies
– 2nd Normal Form (obsolete)
– 3rd Normal Form We only discuss
– Boyce Codd Normal Form (BCNF) these two
• Based on Multivalued Dependencies
– 4th Normal Form
• Based on Join Dependencies
– 5th Normal Form
CSE 544 - Fall 2016 23
BCNF
A simple condition for removing anomalies from relations:
A relation R is in BCNF if:
If A1, ..., An ® B is a non-trivial dependency in R ,
then {A1, ..., An} is a superkey for R
BCNF ensures that no redundancy can be detected
using FD information alone
CSE 544 - Fall 2016 24
Our Example
PatientOf
pno name zip dno since
1 p1 98125 2 2000
1 p1 98125 3 2003
2 p2 98112 1 2002
3 p1 98143 1 1985
pno,dno is a key, but pno ® name, zip
BCNF violation so we decompose
CSE 544 - Fall 2016 25
Decomposition in General
R(A1, ..., An, B1, ..., Bm, C1, ..., Cp)
R1(A1, ..., An, B1, ..., Bm) R2(A1, ..., An, C1, ..., Cp)
R1 = projection of R on A1, ..., An, B1, ..., Bm
R2 = projection of R on A1, ..., An, C1, ..., Cp
Theorem If A1, ..., An à B1, ..., Bm
Then the decomposition is lossless
Note: don’t necessarily need A1, ..., An à C1, ..., Cp
CSE 544 - Fall 2016 26
BCNF Decomposition Algorithm
Repeat
choose A1, …, Am ® B1, …, Bn that violates BCNF condition
split R into
R1(A1, …, Am, B1, …, Bn) and R2(A1, …, Am, [rest])
continue with both R1 and R2
Until no more violations
Lossless-join decomposition: Attributes common to R1 and
R2 must contain a key for either R1 or R2
CSE 544 - Fall 2016 27
BCNF and Dependencies
Unit Company Product
FD’s: Unit ® Company; Company, Product ® Unit
So, there is a BCNF violation, and we decompose.
CSE 544 - Fall 2016 28
BCNF and Dependencies
Unit Company Product
FD’s: Unit ® Company; Company, Product ® Unit
So, there is a BCNF violation, and we decompose.
Unit Company
Unit ® Company
Unit Product
No FDs
In BCNF we lose the FD: Company, Product ® Unit
CSE 544 - Fall 2016 29
3NF
A simple condition for removing anomalies from relations:
A relation R is in 3rd normal form if :
Whenever there is a nontrivial dep. A1, A2, ..., An ® B for R,
then {A1, A2, ..., An } is a super-key for R,
or B is part of a key.
CSE 544 - Fall 2016 30
3NF Discussion
• 3NF decomposition v.s. BCNF decomposition:
– Complex: see book
• Tradeoffs
– BCNF = no anomalies, but may lose some FDs
– 3NF = keeps all FDs, but may have some anomalies
CSE 544 - Fall 2016 31
Summary
• Database design is not trivial
– Use ER models
– Translate ER models into relations
– Normalize to eliminate anomalies
• Normalization tradeoffs
– BCNF: no anomalies, but may lose some FDs
– 3NF: keeps all FDs, but may have anomalies
– Too many small tables affect performance
CSE 544 - Fall 2016 32