Relational Database Design
Module - 4
Introduction
• Pitfalls in relational database design
• Normalization
• First Normal Form
• Functional Dependencies
• Decomposition
• Boyce Codd Normal Form
• Third Normal Form
Pitfalls in Relational Database
Design
• Repetition of Information
• Inability to represent certain Information
Normalization
• Definition:
– Normalization is the process of efficiently
organizing data in a database.
– This is the process of structuring relational
database schema such that most ambiguity is
removed.
• Goals :
– Eliminate redundant data
– Ensure data dependencies make sense
Normalization
• The database community has developed a
series of guidelines for ensuring that
databases are normalized.
• These are referred to as normal forms and
are numbered from one (the lowest form of
normalization, referred to as first normal
form or 1NF) through five (fifth normal
form or 5NF).
1NF
First normal form (1NF) sets the very basic
rules for an organized database:
• Eliminate duplicative columns from the same table. (atomic)
• Create separate tables for each group of related data and identify
each row with a unique column or set of columns (the primary key).
• Eg: Consider a faculty and student relationship.
– Scenario 1 :
• Faculty
• Student1
• Student2
• Student3
– Scenario 2 :
• Faculty
• Student ( multi valued)
– Scenario 3 :
• Faculty ID
• Student ID
2NF
Second normal form (2NF) further addresses the
concept of removing duplicative data:
• Meet all the requirements of the first normal form.
• Remove subsets of data that apply to multiple rows of a
table and place them in separate tables.
• Create relationships between these new tables and their
predecessors through the use of foreign keys.
• Eg : Consider a schema with the following attributes :
– Scenario 1 :
• CustNum , FirstName , LastName , Address , City , State , ZIP
– Scenario 2 :
• Schema 1 : CustNum, FirstName , LastName , Address , ZIP
• Schema 2 : ZIP, City, State
Decomposition
• A decomposition could be :
– Lossy – join
– Lossless join
• Desirable properties :
– Lossless-join Decomposition
– Dependency Preservation
– Repetition of Information
Example for lossy
decompostion
Join Operator
JOIN is used to combine related tuples from two relations:
• In its simplest form the JOIN operator is just the cross
product of the two relations.
• As the join becomes more complex, tuples are removed
within the cross product to make the result of the join
more meaningful.
• JOIN allows you to evaluate a join condition between the
attributes of the relations on which the join is undertaken.
Join Operations
R R CROSS S
A 1 A 1 A 1 F 4 A 1
B 2 A 1 C 2 F 4 C 2
D 3 A 1 D 3 F 4 D 3
F 4 A 1 E 4 F 4 E 4
E 5 B 2 A 1 E 5 A 1
S B 2 C 2 E 5 C 2
B 2 D 3 E 5 D 3
A 1 B 2 E 4 E 5 E 4
C 2 D 3 A 1
D 3 D 3 C 2
E 4 D 3 D 3
D 3 E 4
Join Operations
• Take two relations and return resultant
relation.
• Join Type : defines how tuples in each
relation that do not match any tuple in the
other relation are treated.
• Join Condition : defines the tuples in the
two relations match and attributes present
in the result of the join
Join Operations
• Join Type :
– Inner Join
– Left Outer Join
– Right Outer Join
– Full Outer Join
• Join Condition :
– Natrual
– On < predicate>
– Using (A1,A2,A3……An)
Inner Join
• Invariably the JOIN involves an equality test, and is often described
as an equi-join.
• It selects only those records from the two tables which have
matching values.
• These joins result in two attributes in the resulting relation having
exactly the same value. A ‘natural join’ will remove the duplicate
attribute(s).
• In most systems a natural join will require that the attributes have
the same name to identify the attribute(s) to be used in the join.
• SQL
select *
from customer
INNER JOIN depositor
on [Link]=[Link]
Join Example
R ColA ColB R JOIN [Link] = [Link] S
A 1 A 1 A 1
B 2 D 3 D 3
D 3 E 5 E 4
F 4
E 5
S R JOIN [Link] = [Link] S
SColA SColB
A 1 A 1 A 1
C 2 B 2 C 2
D 3 D 3 D 3
E 4 F 4 E 4
Outer Join
• Outer Joins unlike Inner Joins select all the records from one
database table and only those records from the second table which
have a matching value in the joined field.
• There are three forms of the outer join, depending on which data is
to be kept.
– LEFT OUTER JOIN - keep data from the left-hand table
– RIGHT OUTER JOIN - keep data from the right-hand table
– FULL OUTER JOIN - keep data from both tables
Left And Right Outer Join
R LEFT OUTER JOIN [Link] = [Link] S
R ColA ColB
A 1 A 1 A 1
B 2 D 3 D 3
D 3 E 5 E 4
F 4 B 2 - -
E 5 F 4 - -
S R RIGHT OUTER JOIN [Link] = [Link] S
SColA SColB
A 1 A 1 A 1
C 2 D 3 D 3
D 3 E 5 E 4
E 4 - - C 2
select * select *
from customer from customer
LEFT OUTER JOIN depositor RIGHT OUTER JOIN depositor
on [Link]=[Link] on [Link]=[Link]
Full Outer Join
R FULL OUTER JOIN [Link] = [Link] S
R ColA ColB
A 1 A 1 A 1
B 2 D 3 D 3
D 3 E 5 E 4
F 4 B 2 - -
E 5 F 4 - -
- - C 2
S SColA SColB
A 1
C 2
D 3
E 4 select *
from customer
FULL OUTER JOIN depositor
on [Link]=[Link]
Functional Dependency
• Definition: A functional dependency occurs when one
attribute in a relation uniquely determines another
attribute. This can be written A -> B which would be the
same as stating "B is functionally dependent upon A.“
• Examples: In a table listing employee characteristics
including Social Security Number (SSN) and name, it
can be said that name is functionally dependent upon
SSN (or SSN -> name) because an employee's name
can be uniquely determined from their SSN. However,
the reverse statement (name -> SSN) is not true
because more than one employee can have the same
name but different SSNs.
BCNF
• Definition: A relation is in Boyce-Codd Normal
Form (BCNF) if every determinant is a candidate
key.
• Eg :
– Conisder a database table that stores employee
information and has the attributes employee_id,
first_name, last_name, title.
– In this table, the field employee_id determines
first_name and last_name.
– Similarly, the tuple (first_name, last_name)
determines employee_id.
3NF
Third normal form (3NF) goes one large step
further:
• Meet all the requirements of the second
normal form.
• Remove columns that are not dependent
upon the primary key
3NF
• Eg : Imagine that we have a table of widget
orders that contains the following attributes:
– Scenario 1 :
• Order_no , Cust_no , Unit_Price, Qty ,Total
– Scenario 2 :
• Order_no , Cust_no , Unit_Price, Qty
• We can now use the following query:
SELECT OrderNumber, UnitPrice * Quantity AS Total
FROM WidgetOrders
To achieve the same results without violating normalization
rules.
4NF
• Finally, fourth normal form (4NF) has one
additional requirement:
• Meet all the requirements of the third
normal form.
• A relation is in 4NF if it has no multi-valued
dependencies.
Properties of normal form and their
decomposition
Property 3NF BCNF 4NF
Eliminates redundancy Most Yes Yes
due to Functional
Dependencies
Eliminates redundancy No No Yes
due to multivalued
Dependencies
Preserves Functional Yes Maybe Maybe
Dependencies
Preserves multivalued Maybe Maybe yes
Dependencies