Data Stores
• Outline
– Design principles
– Normalization
– Normal forms (1NF, 2NF and 3NF)
Design Principles
• Data flow in must flow out
– Set of data generated by processes ?= Set of data
consumed by processes
• Redundancy consideration
– Same data should have only one copy
– Similar data should be represented as one same data
• Data access consideration
– Easy access and maintenance
– Space consideration
Operational vs. Informational
Access to Data
• Operational access: for normal operation of
the business
• Examples
– Retrieving a customer address for editing an
order
– Retrieving a customer’s payment history for
credit checking
Operational vs. Informational
Access to Data
• Informational access: for better decision
making or faster response to customer
queries
• Examples
– What were the most sold commodities in last
September?
– What was the vacancy rate during last
Christmas? (for a hotel)
Define the Contents of Data Stores
17 19
New hires Salary Raise
Maintain terminations, changes autjorizations
Process
employee address raises
data changes
D5 EMPLOYEE DETAILS
Employee Salary Employee
addresses details history
18 20 21
Generate Produce Produce
mailing lists for salary individual
house journal listing profile
PERSONNEL MANAGEMENT
Data Flows
Flow into D5
New-hires (17-D5) Terminations (17-D5) Address-changes (17-D5) Salary-changes (19-D5)
Date-hired Name Name Name
Name SSN SSN SSN
SSN Old-address Old-salary
Address New-address New-salary
Job-title Date-effective
Salary
Flow out of D5
Employee-address (D5-18) Salary-details (D5-20) Employee-history (D5-21)
Date-hired Name Name
Name SSN SSN
SSN Old-address
Address New-address
Job-title
Salary
Data Structure of D5 and
Normalization
Name Name SSN
SSN SSN Job-title
Address Address Date-effective
Current-salary Current-salary
Date-hired Date-hired
Job-history*
Job-title
Date-effective SSN
Salary-history* Salary
Salary Date-effective
Date-effective [review-summary]
[review-summary]
The Relational (Scheme) Model
ID# Name Address Item QTY
111 Sowa New York Cheese 100
222 Sowa New York Bacon 150
333 Tully York Egg 300
Components:
Attributes (key/non-key)
Tuples (rows)
Relations (data between them)
The Relational (Scheme) Model
ID# Name Address Item QTY
111 Sowa New York Cheese 100
222 Sowa New York Bacon 150
333 Tully York Egg 300
Attributes: ID#, Name, Address, Item, QTY
Domains:
Dom(ID#)={3-digits Integers}, …
Dom(QTY)={Integers}
Relation: SDom(ID#)…Dom(QTY)
Key(S)=ID#
Features of the Relational Model
• Information represented by tables
• All attribute values are atomic
• All tuples are distinct
• The tuples are unordered
• Key attribute(s) uniquely identifies the
tuples
• Key attribute(s) is put in the first column(s)
Bad Choice of Schemes
ID# (missed) Name Address Item QTY
111 Sowa New York Cheese 100
222 Sowa New York Bacon 150
333 Tully York Egg 300
1. Redundancy: e.g., address for Sowa
2. Update anomalies: e.g., update Sowa’s address in the first tuple but
overlook the other tuple
3. Insert anomalies: e.g., can’t insert Chang and his address unless he order
some item
• Use Null? The value for Item can not be null
• Allow Null for Item? What happen if customer really orders some item
4. Delete anomalies: e.g., after finishing business with Sowa, and delete these
tuples, the record for Sowa is also lost
Functional Dependency (FD)
ID# Name Address Item QTY
111 Sowa New York Cheese 100
222 Sowa New York Bacon 150
333 Tully York Egg 300
• ID# uniquely determines address
f1: Dom(ID#)Dom(Address)
• ID# and Item uniquely determine QTY
f2: Dom(ID#)Dom(Item) Dom(Qty)
• Address is functionally dependent on ID#
• QTY is functionally dependent on ID# and Item
Relational Database Design
• Determine a preliminary set of relational
schemes
• Determine the functional dependencies
• Refine the preliminary relational schemes
– Relational schemes are in some normal forms,
which can be used to tell the good schemes
from the bad ones.
1NF
• A scheme is in 1NF iff all components in the scheme has
only one atomic value.
Problems?
Part Warehouse QTY WH-add
• Redundancy-WH-add
Bolt Station 600 105, 40 Av • Trouble in data update-
Cam Downtown 500 9, 2 St. WH-add
Cog Downtown 100 9, 2 St. • Potential inconsistency-
Nut Station 800 106, 40 Av
4th tuple
• Trouble in data deletion-
Screw Station 900 105, 40 Av
remove all items from
Screw Center 200 29, 2 Dr. Center
2NF
• A scheme is in 2NF iff all its non-key attributes are fully dependent on
key attributes. (see previous page for WH-add)
• Fully dependency: ALL key attributes are used to determine different
tuples. (partial dependency?)
Part Warehouse QTY
Bolt Station 600
Warehouse WH-add
Cam Downtown 500
Station 105, 40 Av
Cog Downtown 100
Downtown 9, 2 St.
Nut Station 800
Center 29, 2 Dr.
Screw Station 900
Screw Center 200
Problems with 2NF
Employee Dept Location
Tom CS NH 301
Mary CS NH 301
John ECE WH 404
• Redundancy-location’s values
• If CS is merged with ECE and moved to WH, then many
tuples must be updated.
• Potential inconsistency: Tom’s location may be different
from Mary’s.
• If a dept has no employee (new dept), there may be no way
to record its location (why?)
3NF
• A scheme is in 3NF iff it is in 2NF and all its non-key
attributes are not interrelated.
Employee Dept
Employee Dept Location Tome CS
Tome CS NH 301 Mary CS
Mary CS NH 301 John ECE
John ECE WH 404
• Dept Location
EmployeeDept
• Employee Location CS NH 301
• Dept Location ECE NH404
• Location ??Dept
Is 3NF enough?
Student Subject Teacher (Prof)
Smith Math White
Smith Physics Green
Jones Math White
Jones Physics Brown
1. Student, Subject Teacher
2. Teacher Subject
3. Subject Teacher
Problems:
• If the last tuple is deleted, the information that “Brown can teach Physics”
will be lost.
• “Chang teaches DBMS” can not be added, unless some student is enrolled
in that course.
Data Store Design Procedure
1. Study the flows of data store, and generate an
unnormalized scheme
2. Decompose the scheme into normalized schemes
(How?)
3. Refine the schemes to 1NF schemes (How?)
4. Refine the 1NF schemes to 2NF schemes (How?)
5. Refine the 2NF schemes to 3NF schemes (How?)