RELATIONAL MODEL AND
NORMALIZATION
(LOGICAL DATABASE DESIGN)
Database Management Systems
M. Ehtasham Ul Haq
1
RELATION
A relation is a named, two-dimensional table of data.
A table consists of rows (records) and columns (attributes or
fields).
Requirements for a table to qualify as a relation:
It must have a unique name.
Every attribute value must be atomic (not multivalued, not composite).
Every row must be unique (two rows can’t have exactly same values).
Attributes (columns) in tables must have unique names.
The order of the columns must be irrelevant.
The order of the rows must be irrelevant.
2
CORRESPONDENCE WITH E-R MODEL
Relations (tables) correspond with entity types and
with many-to-many relationship types.
Columns correspond with attributes.
Rows correspond with entity instances and with
many-to-many relationship instances.
NOTE: The word relation (in relational database) is
NOT the same as the word relationship (in E-R
model).
3
KEY FIELDS
Keys are special fields that serve two main
purposes:
Primary keys. Unique identifiers of the relation.
Examples include employee numbers, social security
numbers, etc. This guarantees that all rows are
unique.
Foreign keys .Identifiers that enable a dependent
relation (on the many side of a relationship) to refer to
its parent relation (on the one side of the
relationship).
Serves as a primary key of another relation
Keys can be simple (a single field) or composite
(more than one field).
4
Schema for four relations
Primary Key
Foreign Key
(implements 1:N relationship
between customer and order)
Combined, these are a composite
primary key (uniquely identifies the
order line)…individually they are
foreign keys (implement M:N
relationship between order and product)
5
INTEGRITY CONSTRAINTS
Domain Constraints
All value must be from the same domain (allowable values)
Domain is a collection of all possible values of one or more attributes
Entity Integrity
No primary key attribute can be null. All primary key fields
MUST have data
6
INTEGRITY CONSTRAINTS
Referential Integrity–rule states that any foreign key
value (on the relation of the many side) MUST match a
primary key value in the relation of the one side. (Or the
foreign key can be null)
For example: Delete Rules
Restrict–don’t allow delete of “parent” side if related rows
exist in “dependent” side
Cascade–automatically delete “dependent” side rows that
correspond with the “parent” side row to be deleted
Set-to-Null–set the foreign key in the dependent side to null
if deleting from the parent side
7
Referential integrity constraints
Referential
integrity
constraints are
drawn via arrows
from dependent to
parent table
8
TERMINOLOGIES
Null is a value that may be assigned to an attribute
when no other value applies or when the applicable
value is unknown
Well-Structure Relation contains minimal redundancy
and allows users to insert, modify and delete rows in
a table without errors
Anomaly: An error or inconsistency that may result
when a user attempts to update a table that contains
redundant data
Surrogate Primary key: A serial number or other
system-assigned primary key for a relation
9
TRANSFORMING EER DIAGRAMS INTO
RELATIONS
Mapping Regular Entities to Relations
Simple attributes: E-R attributes map
directly onto the relation
Composite attributes: Use only their
simple, component attributes
Multivalued Attribute: Becomes a
separate relation with a foreign key
taken from the superior entity
10
Mapping a regular entity
(a) CUSTOMER
entity type with
simple
attributes
(b) CUSTOMER relation
11
Mapping a composite attribute
(a) CUSTOMER
entity type with
composite
attribute
(b) CUSTOMER relation with address detail
12
Mapping an entity with a multivalued attribute
(a)
Multivalued attribute becomes a separate relation with foreign key
(b)
One-to-many relationship between original entity and new relation
13
TRANSFORMING EER DIAGRAMS INTO
RELATIONS (CONT.)
Mapping Weak Entities
Becomes a separate relation with a foreign
key taken from the superior entity
Primary key composed of:
Partial
identifier of weak entity
Primary key of identifying relation (strong entity)
14
Example of mapping a weak entity
a) Weak entity DEPENDENT
b) Relations resulting from weak entity
NOTE: the domain constraint
for the foreign key should NOT
allow null value if
DEPENDENT is a weak entity
Foreign key
Composite primary key
15
TRANSFORMING EER DIAGRAMS INTO
RELATIONS (CONT.)
Mapping Binary Relationships
One-to-Many–Primary key on the one side
becomes a foreign key on the many side
Many-to-Many–Create a new relation with the
primary keys of the two entities as its primary
key
One-to-One–Primary key on mandatory side
becomes a foreign key on optional side
16
Example of mapping a 1:M relationship
a) Relationship between customers and orders
Note the mandatory one
b) Mapping the relationship
Again, no null value in the
foreign key…this is because
of the mandatory minimum
cardinality
Foreign key
17
Example of mapping an M:N relationship
a) Completes relationship (M:N)
The Completes relationship will need to become a separate relation
b) Three resulting relations
Composite primary key
Foreign key Foreign key
new intersection
relation
18
Example of mapping a binary 1:1 relationship
a) In charge relationship (1:1)
Often in 1:1 relationships, one direction is optional
b) Resulting relations
Foreign key goes in the relation on the optional side,
matching the primary key on the mandatory side
19
TRANSFORMING EER DIAGRAMS INTO
RELATIONS (CONT.)
Mapping Associative Entities
Identifier Not Assigned
Default primary key for the associative
relation is composed of the primary keys of
the two entities (as in M:N relationship)
Identifier Assigned
It
is natural and familiar to end-users
Default identifier may not be unique
20
Example of mapping an associative entity
a) An associative entity
b) Three resulting relations
Composite primary key formed from the two foreign keys
21
Example of mapping associative entity with identifier
a) SHIPMENT associative entity
b) Three resulting relations
Primary key differs from foreign keys
22
TRANSFORMING EER DIAGRAMS INTO
RELATIONS (CONT.)
Mapping Unary Relationships
One-to-Many–Recursive foreign key in the
same relation
Many-to-Many–Two relations:
One for the entity type
One for an associative relation in which
the primary key has two attributes, both
taken from the primary key of the entity
23
Mapping a unary 1:N relationship
(a) EMPLOYEE
entity with unary
relationship
(b) EMPLOYEE relation with recursive foreign key
24
Mapping a unary M:N relationship
(a) Item contains items
relationship (M:N)
(b) ITEM and
COMPONENT
relations
25
TRANSFORMING EER DIAGRAMS INTO
RELATIONS (CONT.)
Mapping Ternary Relationships
One relation for each entity and one for
the associative entity
Associative entity has foreign keys to
each entity in the relationship
26
Mapping a ternary relationship
a) PATIENT TREATMENT Ternary relationship with associative entity
b) Mapping the ternary relationship PATIENT TREATMENT
Treatment date and time are included to make unique composite key
But this makes a very cumbersome key…
It would be better to create a Surrogate key like Treatment#
27
TRANSFORMING EER DIAGRAMS
INTO RELATIONS (CONT.)
Mapping Supertype/Subtype Relationships
One relation for supertype and for each subtype
Supertype attributes (including identifier and subtype
discriminator) go into supertype relation, Subtype
attributes go into each subtype relation
primary key of supertype relation also becomes
primary key of subtype relation
1:1 relationship established between supertype and
each subtype, with supertype as primary table
28
Supertype/subtype relationships
29
Mapping supertype/subtype relationships to relations
These are implemented as one-to-one relationships
30
TRANSLATE ER-DIAGRAM INTO RELATIONAL SCHEMA
Suppose 1 book is written by only 1 author
31
WELL-STRUCTURED RELATIONS
A relation that contains minimal data
redundancy and allows users to insert, delete,
and update rows without causing data
inconsistencies
Goal is to avoid anomalies
Insertion Anomaly–adding new rows forces user to
create duplicate data
Deletion Anomaly–deleting rows may cause a loss
of data that would be needed for other future rows
Modification Anomaly–changing data in a row
forces changes to other rows because of
duplication
32
DATA NORMALIZATION
Primarily a tool to validate and improve a logical
design so that it satisfies certain constraints
that avoid unnecessary duplication of data
Normalization is a process of decomposing
relations with anomalies to produce smaller,
well-structured relations
Normal Form: A state of relation that requires
that certain rules regarding relationships
between attributes are satisfied
33
Steps in normalization
3rd normal form is
generally considered to be
sufficient, although higher
degrees of normalization
are possible.
34
Table with multivalued attributes, not in 1st normal form
Note: this is NOT a relation
35
FIRST NORMAL FORM
No multivalued attributes (atomic value)
All rows should be unique
No multivalued attributes and unique rows, its in 1st normal form
Question–Is this a relation? Yes: Unique rows and no multivalued attributes.
But still not well-structure
36
ANOMALIES IN THIS TABLE
Insertion–if new product is ordered for order 1007 of
existing customer, customer data must be re-entered,
causing duplication
Deletion–if we delete the Dining Table from Order
1006, we lose information concerning this product like
price
Update–changing the price of product ID 4 requires
update in multiple records
Why do these anomalies exist?
Because there are multiple entity types in one
relation. This results in duplication and an
unnecessary dependency between the entities.
37
FUNCTIONAL DEPENDENCIES AND KEYS
Functional Dependency: A constraint in which
the value of one attribute is determined by the
value of another attribute
Notation: AB read as “A determines B”
Value of A (uniquely) determines the value of B
The attribute on the left side of the arrow in a
functional dependency is called Determinant.
e.g. SSN Name, Address, Birthday
ISBN Title, AuthorName, Publisher
38
CANDIDATE KEYS
Candidate Key: An attribute that uniquely
identifies a row in a relation
A unique identifier.
One of the candidate keys will become the
primary key
e.g. if both credit card number and SS# are present
in a table then both are candidate keys
Each non-key field is functionally dependent on
every candidate key
39
Functional dependency diagram for INVOICE
OrderID OrderDate, CustomerID, CustomerName, CustomerAddress
CustomerID CustomerName, CustomerAddress
ProductID ProductDescription, ProductFinish, ProductStandardPrice
OrderID, ProductID OrderQuantity
Therefore, NOT in 2nd Normal Form
40
SECOND NORMAL FORM
1NF PLUS every non-key attribute is fully
functionally dependent on the ENTIRE primary
key
Every non-key attribute must be defined by the
entire key, not by only part of the key
No partial functional dependencies
Partial Functional Dependency exists when one
or more nonkey attributes are functionally
dependent on part of primary key
41
Removing partial dependencies
Getting it into
Second Normal Form
Partial dependencies are removed,
but there are still transitive dependencies
42
EXAMPLE EXERCISE
Accountant Skill Proficiency Skill Account Accountant Group Group Group
Number Number Category Name Age Number City Supervisor
21 113 3 Systems Waseem 30 52 GJR Ali
35 113 5 Systems Ehtasham 31 44 LHR Naeem
50 179 1 Tax Saeed 40 44 LHR Naeem
77 204 6 Audit Asad 35 52 GJR Ali
Which Functional Dependency should be eliminated?
Convert it into 2NF
Accountant Account Accountant Group Group City Group Skill Skill
Number Name Age Number Supervisor Number Category
21 Waseem 30 52 GJR Ali 113 Systems
35 Ehtasham 31 44 LHR Naeem 179 Tax
50 Saeed 40 44 LHR Naeem 204 Audit
77 Asad 35 52 GJR Ali
Accountant Skill Proficiency
Number Number
21 113 3
35 113 5
50 179 1
77 204 6 43
THIRD NORMAL FORM
2NF PLUS no transitive dependencies
Transitive dependency is a functional
dependencies on non-primary-key attributes
Note: This is called transitive, because the
primary key is a determinant for another
attribute, which in turn is a determinant for a
third attribute
Solution: Non-key determinant with transitive
dependencies go into a new table; non-key
determinant becomes primary key in the new
table and stays as foreign key in the old table
44
Removing transitive dependencies
Getting it into
Third Normal
Form
Transitive dependencies are removed
45
RELATIONAL MODEL
Presented by E.F. Codd in 1970
In Relational model, data is stored in relations.
Relation is another name used for table
Degree of relation is the number of columns
Degree of relationship is entities participating in
relationship
46
EXERCISE
CustomerInvoice (InvoiceID, CustomerID, CustomerName, CustomerAddress)
The functional dependencies in this relation are?
InvoiceID CustomerID CustomerName
InvoiceID CustomerID CustomerAddress
Which dependency is present in the relation?
Answer: Transitive Dependency
Convert it into 3NF…
47
EXAMPLE EXERCISE
Accountant Account Accountant Group Group City Group
Number Name Age Number Supervisor
21 Waseem 30 52 GJR Ali
35 Ehtasham 31 44 LHR Naeem
50 Saeed 40 44 LHR Naeem
77 Asad 35 52 GJR Ali
Which Functional Dependency should be eliminated?
Convert it into 3NF
Accountant Account Accountant Group
Number Name Age Number
Group Group Group
21 Waseem 30 52
Number City Supervisor
35 Ehtasham 31 44 52 GJR Ali
50 Saeed 40 44 44 LHR Naeem
77 Asad 35 52
Relations in 3NF
48
