Database Design: Logical
Models: Normalization and
The Relational Model
Application 1 Application 2 Application 3 Application 4
External External External External
Model Model Model Model
Application 1
Conceptual
requirements
Application 2
Conceptual
requirements
Internal
Conceptual Logical Model
Application 3 Model Model
Conceptual
requirements
Application 4
Conceptual
requirements
Each entity in the ER Diagram becomes a relation.
A properly normalized (next time) ER diagram will
indicate where intersection relations for many-to-
many mappings are needed.
Relationships are indicated by common columns (or
domains) in tables that are related.
We will examine the tables for the Diveshop derived
from the ER diagram
Normalization theory is based on the
observation that relations with certain
properties are more effective in inserting,
updating and deleting data than other sets of
relations containing the same data
Normalization is a multi-step process beginning
with an “unnormalized” relation
Hospital example from Atre, S. Data Base:
Structured Techniques for Design, Performance,
and Management.
First Normal Form (1NF)
Second Normal Form (2NF)
Third Normal Form (3NF)
Boyce-Codd Normal Form (BCNF)
Fourth Normal Form (4NF)
Fifth Normal Form (5NF)
Functional
dependency
No transitive
of nonkey
dependency
attributes on
between
the primary
nonkey Boyce- key - Atomic
attributes
Codd and values only
All
Higher Full
determinants Functional
are candidate dependency
keys - Single of nonkey
multivalued attributes on
dependency the primary
key
IS 257 – Fall 2006
First step in normalization is to convert the data
into a two-dimensional table
In unnormalized relations data can repeat
within a column
IS 257 – Fall 2006
Patient # Surgeon # Surg. date Patient Name Patient Addr Surgeon Surgery Postop drug
Drug side effects
Gallstone
s removal;
Jan 1, 15 New St. Beth Little Kidney
145 1995; June New York, Michael stones Penicillin, rash
1111 311 12, 1995 John White NY Diamond removal none- none
Eye
Charles Cataract
Apr 5, Field removal
243 1994 May 10 Main St. Patricia Thrombos Tetracyclin Fever
1234 467 10, 1995 Mary Jones Rye, NY Gold is removal e none none
Dogwood
Lane Open
Jan 8, Harrison, David Heart Cephalosp
2345 189 1996 Charles Brown NY Rosen Surgery orin none
55 Boston
Post Road,
Nov 5, Chester, Cholecyst
4876 145 1995 Hal Kane CN Beth Little ectomy Demicillin none
Blind Brook Gallstone
May 10, Mamaronec s
5123 145 1995 Paul Kosher k, NY Beth Little Removal none none
Eye
Cornea
Replacem
Apr 5, Hilton Road ent Eye
1994 Dec Larchmont, Charles cataract Tetracyclin
6845 243 15, 1984 Ann Hood NY Field removal e Fever
IS 257 – Fall 2006
To move to First Normal Form a relation must
contain only atomic values at each row and
column.
No repeating groups
A column or set of columns is called a Candidate
Key when its values can uniquely identify the row in
the relation.
IS 257 – Fall 2006
Patient # Surgeon # Surgery DatePatient Name Patient Addr Surgeon Name Surgery Drug adminSide Effects
15 New St.
New York, Gallstone
1111 145 01-Jan-95 John White NY Beth Little s removal Penicillin rash
15 New St. Kidney
New York, Michael stones
1111 311 12-Jun-95 John White NY Diamond removal none none
Eye
10 Main St. Cataract Tetracyclin
1234 243 05-Apr-94 Mary Jones Rye, NY Charles Field removal e Fever
10 Main St. Thrombos
1234 467 10-May-95 Mary Jones Rye, NY Patricia Gold is removal none none
Dogwood
Lane Open
Charles Harrison, Heart Cephalosp
2345 189 08-Jan-96 Brown NY David Rosen Surgery orin none
55 Boston
Post Road,
Chester, Cholecyst
4876 145 05-Nov-95 Hal Kane CN Beth Little ectomy Demicillin none
Blind Brook Gallstone
Mamaronec s
5123 145 10-May-95 Paul Kosher k, NY Beth Little Removal none none
Eye
Hilton Road Cornea
Larchmont, Replacem Tetracyclin
6845 243 05-Apr-94 Ann Hood NY Charles Field ent e Fever
Hilton Road Eye
Larchmont, cataract
6845 243 15-Dec-84 Ann Hood NY Charles Field removal none none
IS 257 – Fall 2006
Insertion: A new patient has not yet undergone surgery
-- hence no surgeon # -- Since surgeon # is part of the
key we can’t insert.
Insertion: If a surgeon is newly hired and hasn’t
operated yet -- there will be no way to include that
person in the database.
Update: If a patient comes in for a new procedure, and
has moved, we need to change multiple address
entries.
Deletion (type 1): Deleting a patient record may also
delete all info about a surgeon.
Deletion (type 2): When there are functional
dependencies (like side effects and drug) changing one
item eliminates other information.
IS 257 – Fall 2006
A relation is said to be in Second Normal Form
when every nonkey attribute is fully
functionally dependent on the primary key.
That is, every nonkey attribute needs the full
primary key for unique identification
IS 257 – Fall 2006
Patient # Patient Name Patient Address
15 New St. New
1111 John White York, NY
10 Main St. Rye,
1234 Mary Jones NY
Charles Dogwood Lane
2345 Brown Harrison, NY
55 Boston Post
4876 Hal Kane Road, Chester,
Blind Brook
5123 Paul Kosher Mamaroneck, NY
Hilton Road
6845 Ann Hood Larchmont, NY
IS 257 – Fall 2006
Surgeon # Surgeon Name
145 Beth Little
189 David Rosen
243 Charles Field
311 Michael Diamond
467 Patricia Gold
IS 257 – Fall 2006
Patient # Surgeon # Surgery Date Surgery Drug Admin Side Effects
Gallstones
1111 145 01-Jan-95 removal
Kidney Penicillin rash
stones
1111 311 12-Jun-95 removal none none
Eye Cataract
1234 243 05-Apr-94 removal Tetracycline Fever
Thrombosis
1234 467 10-May-95 removal none none
Open Heart Cephalospori
2345 189 08-Jan-96 Surgery n none
Cholecystect
4876 145 05-Nov-95 omy Demicillin none
Gallstones
5123 145 10-May-95 Removal none none
Eye cataract
6845 243 15-Dec-84 removal none none
Eye Cornea
6845 243 05-Apr-94 Replacement Tetracycline Fever
IS 257 – Fall 2006
Insertion: Can now enter new patients without
surgery.
Insertion: Can now enter Surgeons who haven’t
operated.
Deletion (type 1): If Charles Brown dies the
corresponding tuples from Patient and Surgery tables
can be deleted without losing information on David
Rosen.
Update: If John White comes in for third time, and has
moved, we only need to change the Patient table
IS 257 – Fall 2006
Insertion: Cannot enter the fact that a particular drug
has a particular side effect unless it is given to a
patient.
Deletion: If John White receives some other drug
because of the penicillin rash, and a new drug and side
effect are entered, we lose the information that
penicillin can cause a rash
Update: If drug side effects change (a new formula) we
have to update multiple occurrences of side effects.
IS 257 – Fall 2006
A relation is said to be in Third Normal Form if there is
no transitive functional dependency between nonkey
attributes
When one nonkey attribute can be determined with one or
more nonkey attributes there is said to be a transitive
functional dependency.
The side effect column in the Surgery table is
determined by the drug administered
Side effect is transitively functionally dependent on drug so
Surgery is not 3NF
IS 257 – Fall 2006
Patient # Surgeon # Surgery Date Surgery Drug Admin
1111 145 01-Jan-95 Gallstones removal Penicillin
Kidney stones
1111 311 12-Jun-95 removal none
1234 243 05-Apr-94 Eye Cataract removal Tetracycline
1234 467 10-May-95 Thrombosis removal none
2345 189 08-Jan-96 Open Heart Surgery Cephalosporin
4876 145 05-Nov-95 Cholecystectomy Demicillin
5123 145 10-May-95 Gallstones Removal none
6845 243 15-Dec-84 Eye cataract removal none
Eye Cornea
6845 243 05-Apr-94 Replacement Tetracycline
IS 257 – Fall 2006
Drug Admin Side Effects
Cephalosporin none
Demicillin none
none none
Penicillin rash
Tetracycline Fever
IS 257 – Fall 2006
Insertion: We can now enter the fact that a
particular drug has a particular side effect in the
Drug relation.
Deletion: If John White recieves some other
drug as a result of the rash from penicillin, but
the information on penicillin and rash is
maintained.
Update: The side effects for each drug appear
only once.
IS 257 – Fall 2006
Most 3NF relations are also BCNF relations.
A 3NF relation is NOT in BCNF if:
Candidate keys in the relation are composite keys
(they are not single attributes)
There is more than one candidate key in the
relation, and
The keys are not disjoint, that is, some attributes in
the keys are common
IS 257 – Fall 2006
Patient # Patient Name Patient Address
15 New St. New
1111 John W hite York, NY
10 Main St. Rye,
1234 Mary Jones NY
Charles Dogwood Lane
2345 Brown Harrison, NY
55 Boston Post
4876 Hal Kane Road, Chester,
Blind Brook
5123 Paul Kosher Mamaroneck, NY
Hilton Road
6845 Ann Hood Larchmont, NY
IS 257 – Fall 2006
Patient # Patient Name Patient # Patient Address
15 New St. New
1111 John W hite 1111 York, NY
10 Main St. Rye,
1234 Mary Jones 1234 NY
Charles Dogwood Lane
2345 Brown 2345 Harrison, NY
55 Boston Post
4876 Hal Kane 4876 Road, Chester,
Blind Brook
5123 Paul Kosher 5123 Mamaroneck, NY
Hilton Road
6845 Ann Hood 6845 Larchmont, NY
IS 257 – Fall 2006
Any relation is in Fourth Normal Form if it is
BCNF and any multivalued dependencies are
trivial
Eliminate non-trivial multivalued dependencies
by projecting into simpler tables
IS 257 – Fall 2006
A relation is in 5NF if every join dependency in
the relation is implied by the keys of the
relation
Implies that relations that have been
decomposed in previous NF can be recombined
via natural joins to recreate the original
relation.
IS 257 – Fall 2006
Focus on the relational model
Any column in a relational database can be
searched for values.
To improve efficiency indexes using storage
structures such as BTrees and Hashing are used
But many useful functions are not indexable
and require complete scans of the the database
IS 257 – Fall 2006
In conventional RDBMS, when a text field is
indexed, only exact matching of the text field
contents (or Greater-than and Less-than).
Can search for individual words using pattern
matching, but a full scan is required.
Text searching is still done best (and fastest) by
specialized text search programs (Search
Engines) that we will look at more later.
IS 257 – Fall 2006
Normalization is performed to reduce or
eliminate Insertion, Deletion or Update
anomalies.
However, a completely normalized database
may not be the most efficient or effective
implementation.
“Denormalization” is sometimes used to
improve efficiency.
IS 257 – Fall 2006
Normalization splits database information
across multiple tables.
To retrieve complete information from a
normalized database, the JOIN operation must
be used.
JOIN tends to be expensive in terms of
processing time, and very large joins are very
expensive.
IS 257 – Fall 2006
Customer Customer
Before: After:
ID ID
Address Address
Name Name
Telephone Telephone
Order Order
Order No Order No
Date Taken Date Taken
Date Dispatched Date Dispatched
Date Invoiced Date Invoiced
Cust ID Cust ID
Cust Name
IS 257 – Fall 2006
Order Order
Order No Order No
Date Taken Date Taken
Date Dispatched Date Dispatched
Date Invoiced Date Invoiced
Cust ID Cust ID
Cust Name Cust Name
Order Price
Order Item
Order No Order Item
Item No Order No
Item Price Item No
Num Ordered Item Price
Num Ordered
IS 257 – Fall 2006
Usually driven by the need to improve query
speed
Query speed is improved at the expense of
more complex or problematic DML (Data
manipulation language) for updates, deletions
and insertions.
Relational Database Management Systems
(RDBMS)
Possible to design complex data storage and
retrieval systems with ease (and without
conventional programming).
Support for ACID transactions
Atomic
Consistent
Independent
Durable
Support for very large databases
Automatic optimization of searching (when
possible)
RDBMS have a simple view of the database that
conforms to much of the data used in business
Standard query language (SQL)
Until recently, no real support for complex objects
such as documents, video, images, spatial or time-
series data. (ORDBMS add -- or make available support
for these)
Often poor support for storage of complex objects
from OOP languages (Disassembling the car to park it
in the garage)
Usually no efficient and effective integrated support
for things like text searching within fields (MySQL does
have simple keyword searching now with index
support)