Principles of Database Management

Prof. Dr. Manon Reusens

 Normalization Forms
2NF BCNF
A relation R is in the second A relation R is in the Boyce-
normal form (2 NF) if it Codd normal form (BCNF)
satisfies 1 NF and every non- provided each of its non-
prime attribute type A in R is trivial functional
fully functional dependent dependencies X → Y, X is a
on any key of R superkey—that is, X is either
a candidate key or a
superset thereof

2
 Normalization Forms
2NF BCNF
• R1(SSN, PNUMBER, • R1(SUPNR, SUPNAME,
PNAME, HOURS) PRODNR, QUANTITY)
– assume an employee can – Assume a supplier can
work on multiple projects; supply multiple products; a
multiple employees can product can be supplied by
work on the same project multiple suppliers and a
and a project has a unique supplier has a unique name
name • R11(SUPNR, PRODNR,
• R11(SSN, PNUMBER, QUANTITY)
HOURS) • R12(SUPNR, SUPNAME)
• R12(PNUMBER, PNAME) 3
 Normalization Forms: 2NF
• R1(SSN, PNUMBER, PNAME, HOURS)
– assume an employee can work on multiple projects;
multiple employees can work on the same project and
a project has a unique name
• R11(SSN, PNUMBER, HOURS)
• R12(PNUMBER, PNAME)

Because PNUMBER  PNAME (non-prime attribute

type) fully functionally dependent
4
 Normalization Forms: BCNF
• R1(SSN, PNUMBER, PNAME, HOURS)
– assume an employee can work on multiple projects;
multiple employees can work on the same project and
a project has a unique name
• R11(SSN, PNUMBER, HOURS)
• R12(PNUMBER, PNAME)

1) Find the non-trivial functional dependencies

2) Check that for every X Y: X is a superkey of the
relation 5
 Example: difference 2NF and BCNF
• R1(SSN, ENAME, DNUMBER, DNAME, DMGRSSN)
– Assumptions: an employee works in one department, a
department can have multiple employees and a department has
one manager
• It is in 2NF: SSN  ENAME, DNUMBER, DNAME,
DMGRSSN
• BUT not in 3NF (transitive dependency)
• Also not in BCNF:
– Functional dependencies:
• SSN  ENAME, DNUMBER, DNAME, DMGRSSN & DNUMBER  DNAME,
DMGRSSN
– DNUMBER is not a superkey of the relation 6
 Example difference 2NF and BCNF
• R1(SSN, DNumber, DMGRSSN)
– Assumptions: An employee can work in multiple departments.
Every manager manages exactly one department
• 2NF: Yes: SSN,Dnumber  DMGRSSN
• 3NF: Yes: dependencies: SSN,DNumber  DMGRSSN and
DMGRSSN  Dnumber
– No transitive dependency:
• A relation is in the third normal form (3 NF) if it satisfies 2 NF and no
non-prime attribute type of R is transitively dependent on the primary
key
• BCNF: No as DMGRSSN is not a superkey
7
 4NF
A relation is in the fourth normal form (4 NF) if it is in
Boyce-Codd normal form and for every one of its non-trivial
mul valued dependencies X →→ Y, X is a superkey—that is,
X is either a candidate key or a superset thereof
• R1(course, instructor, textbook)
– Assume a course can be taught by different instructors,
and a course uses the same set of textbooks for each
instructor
• R11(course, textbook)
• R12(course, instructor)
8
6. Relational Databases (2)

[Link]
 Introduction
• Relational Model
• Normalization
• Mapping a conceptual ER model to a relational
model
• Mapping a conceptual EER model to a relational
model

10
 Mapping a Conceptual ER Model to a Relational Model

• Mapping Entity Types

• Mapping Relationship Types
• Mapping Multivalued Attribute Types
• Mapping Weak Entity Types
• Putting it All Together

11
 Mapping Entity Types

SSN PNR

address
EMPLOYEE PROJECT

ename pname

first Last
pduration
name name

EMPLOYEE(SSN, address, first name, last name)

PROJECT(PNR, pname, pduration)
12
 Mapping Relationship Types
• Mapping a binary 1:1 relationship type
• Mapping a binary 1:N relationship type
• Mapping a binary M:N relationship type
• Mapping unary relationship types
• Mapping n-ary relationship types

13
Mapping a Binary 1:1 Relationship Type
• Create two relations: one for each entity type
participating in the relationship type
• The connection can be made by including a foreign key in
one of the relations to the primary key of the other
• In case of existence dependency, put the foreign key in
the existent dependent relation and declare it as NOT
NULL
• The attribute types of the 1:1 relationship type can then
be added to the relation with the foreign key

14
Mapping a Binary 1:1 Relationship Type
SSN

ename
EMPLOYEE

address
1..1

dep-mgr
mgr-dep MANAGES

0..1

DEPARTMENT

DNR dname dlocation

15
Mapping a Binary 1:1 Relationship Type
EMPLOYEE(SSN, ename, address, DNR)
DEPARTMENT(DNR, dname, dlocation)
EMPLOYEE( SSN, ename, address, DNR) SSN

511 John Smith 14 Avenue of the Americas, New York 001

ename
EMPLOYEE
289 Paul Barker 208 Market Street, San Francisco 003
address
356 Emma Lucas 432 Wacker Drive, Chicago NULL 1..1

412 Michael Johnson 1134 Pennsylvania Avenue, Washington NULL

dep-mgr

564 Sarah Adams 812 Collins Avenue, Miami 001 mgr-dep MANAGES

DEPARTMENT(DNR, dname, dlocation) 0..1

001 Marketing 3th floor DEPARTMENT

002 Call center 2nd floor

DNR dname dlocation
003 Finance basement
004 ICT 1st floor 16
Mapping a Binary 1:1 Relationship Type
EMPLOYEE(SSN, ename, address)
DEPARTMENT(DNR, dname, dlocation, SSN)
EMPLOYEE( SSN, ename, address)
SSN

511 John Smith 14 Avenue of the Americas, New York ename

EMPLOYEE
289 Paul Barker 208 Market Street, San Francisco
address
1..1
356 Emma Lucas 432 Wacker Drive, Chicago
dep-mgr
mgr-dep MANAGES
DEPARTMENT(DNR, dname, dlocation, SSN)
0..1
001 Marketing 3th floor 511
DEPARTMENT
002 Call center 2nd floor 511
003 Finance basement 289 DNR dname dlocation

004 ICT 1st floor 511 17

 Mapping a Binary 1:N Relationship Type
• Binary 1:N relationship types can be mapped by including a foreign
key in the relation corresponding to the participating entity type at
the N-side of the relationship type
• The foreign key refers to the primary key of the relation
corresponding to the entity type at the 1-side of the relationship
type
• Depending upon the minimum cardinality, the foreign key can be
declared as NOT NULL or NULL ALLOWED
• The attribute types of the 1:N relationship type can be added to the
relation corresponding to the participating entity type

18
 Mapping a Binary 1:N Relationship Type
SSN EMPLOYEE(SSN, ename,
address, starting
ename
EMPLOYEE date, DNR)
address
1..N
DEPARTMENT(DNR, dname,
WORKS IN
dep-emp
emp-dep
dlocation)
starting
date
1..1

DEPARTMENT

DNR dname dlocation

19
Mapping a Binary 1:N Relationship Type

20
 Mapping a Binary N:M Relationship Type
• M:N relationship types are mapped by introducing
a new relation R
• The primary key of R is a combination of foreign
keys referring to the primary keys of the relations
corresponding to the participating entity types
• The attribute types of the M:N relationship type
can also be added to R

21
Mapping a Binary M:N Relationship Type
hours PNR
SSN

0..M 0..N
ename pro- emp-
PROJECT
EMPLOYEE emp pro

address WORKS ON

pname

pduration

EMPLOYEE(SSN, ename, address)

PROJECT(PNR, pname, pduration)
WORKS_ON(SSN, PNR, hours) 22
Mapping a Binary M:N Relationship Type
PROJECT( PNR, pname, pduration)
EMPLOYEE( SSN, ename, address, DNR)
1001 B2B 100
511 John Smith 14 Avenue of the Americas, New York 001
1002 Analytics 660
289 Paul Barker 208 Market Street, San Francisco 001
1003 Web site 52
356 Emma Lucas 432 Wacker Drive, Chicago 002
1004 Hadoop 826

WORKS_ON( SSN, PNR, hours)

511 1001 10
289 1001 80
289 1003 50

23
 Exercise (1)
• Map the ER to a relational model, indicate the primary
and foreign keys and add NULL declarations. Also
explicitly mention which (if any) cardinalities are not
supported

24
 Mapping Unary Relationship Types
• A recursive 1:1 or 1:N relationship type can be
implemented by adding a foreign key referring to
the primary key of the same relation
• For a N:M recursive relationship type, a new
relation R needs to be created with two NOT NULL
foreign keys referring to the original relation

25
 Mapping Unary Relationship Types
Super Super-
vises vised
by
SSN
0..1 0..1
ename
EMPLOYEE

address

EMPLOYEE(SSN, ename, address,

supervisor)
26
Mapping Unary Relationship Types

EMPLOYEE( SSN, ename, address, supervisor)

511 John Smith 14 Avenue of the Americas, New York 289

289 Paul Barker 208 Market Street, San Francisco 412
356 Emma Lucas 432 Wacker Drive, Chicago 289
412 Dan Kelly 668 Strip, Las Vegas NULL

27
 Mapping Unary Relationship Types

EMPLOYEE(SSN, ename, address)

SUPERVISION(Supervisor, Supervisee)
28
 Mapping Unary Relationship Types

EMPLOYEE( SSN, ename, address) SUPERVISION(Supervisor, Supervisee)

511 John Smith 14 Avenue of the Americas, New York 289 511
289 Paul Barker 208 Market Street, San Francisco 289 356
356 Emma Lucas 432 Wacker Drive, Chicago 412 289
412 Dan Kelly 668 Strip, Las Vegas 412 511

29
 Mapping n-ary Relationship Types
• To map an n-ary relationship type, we first create
relations for each participating entity type
• We then also define one additional relation R to represent
the n-ary relationship type and add foreign keys referring
to the primary keys of each of the relations corresponding
to the participating entity types
• The primary key of R is the combination of all foreign keys
which are all NOT NULL
• Any attribute type of the n-ary relationship can also be
added to R
30
 Mapping n-ary Relationship Types
BOOKING
0..N 0..N
Tourist Hotel
price

TNR 0..N HNR

Travel
Agency
ANR

TOURIST(TNR, …)
TRAV_AGENCY(ANR, …)
HOTEL(HNR, …)
BOOKING(TNR, ANR, HNR, price)
31
 Mapping n-ary Relationship Types
OFFERS
1..N 0..N
Instructor Semester

INR 0..N SEM-YEAR

Course

CNR

INSTRUCTOR(INR, …)
COURSE(CNR, …)
SEMESTER(SEM-YEAR, …)
OFFERS(INR,CNR,SEM-YEAR) 32
 Mapping n-ary Relationship Types

INSTRUCTOR( INR, iname, ….) COURSE( CNR, cname, ….) SEMESTER( SEM-YEAR, ….)

10 Bart 100 Database Management 1-2015

12 Wilfried 110 Analytics 2-2015
14 Seppe 120 Java Programming 1-2016

OFFERS( INR, CNR, SEM-YEAR)

10 100 1-2015
12 100 1-2016
10 120 1-2015
14 120 1-2015

33
 Exercise (2)
• Map the ER to a relational model, indicate the primary
and foreigns keys and add NULL declarations. Also
explicitly mention which (if any) cardinalities are not
supported.

34
Mapping Multivalued Attribute Types
• For each multivalued attribute type, we create a
new relation R
• We put the multivalued attribute type in R
together with a foreign key referring to the
primary key of the original relation
• Multivalued composite attribute types are again
decomposed into their components
• The primary key can then be set based upon the
assumptions
35
Mapping Multivalued Attribute Types
SSN
EMPLOYEE
ename

address
phonenr

EMPLOYEE(SSN, ename, address)

EMP-PHONE(PhoneNr, SSN)
36
Mapping Multivalued Attribute Types
EMPLOYEE( SSN, ename, address, DNR)

511 John Smith 14 Avenue of the Americas, New York 001

289 Paul Barker 208 Market Street, San Francisco 001
356 Emma Lucas 432 Wacker Drive, Chicago 002

EMP-PHONE( PhoneNR, SSN)

900-244-8000 511
900-244-8000 289
900-244-8002 289
900-246-6006 356

37
 Mapping Weak Entity Types
• A weak entity type should be mapped into a
relation R with all its corresponding attribute types
• A foreign key must be added referring to the
primary key of the relation corresponding to the
owner entity type
• Because of the existence dependency, the foreign
key is declared as NOT NULL
• The primary key of R is then the combination of the
partial key and the foreign key
38
 Mapping Weak Entity Types
HNR
RNR

0..N 1..1 Hotel

HNR Room

Beds Belongs to
Hname

Hotel (HNR, Hname)

Room (RNR, HNR, beds)
39
Mapping Weak Entity Types

40
 Putting it All Together
ER Model Relational model

Entity type Relation

Weak entity type Foreign key

1:1 or 1:N relationship type Foreign key

M:N relationship type New relation with two foreign keys

N-ary relationship type New relation with N foreign keys

Simple attribute type Attribute type

Composite attribute type Component attribute type

Multivalued attribute type Relation and foreign key

Key attribute type Primary or alternative key

41
 Putting it All Together
• EMPLOYEE(SSN, ename, streetaddress, city, sex,
dateofbirth, MNR, DNR)
– MNR foreign key refers to SSN in EMPLOYEE, NULL ALLOWED
– DNR foreign key refers to DNR in DEPARTMENT, NOT NULL
• DEPARTMENT (DNR, dname, dlocation, MGNR)
– MGNR: foreign key refers to SSN in EMPLOYEE, NOT NULL
• PROJECT (PNR, pname, pduration, DNR)
– DNR: foreign key refers to DNR in DEPARTMENT, NOT NULL
• WORKS-ON (SSN, PNR, HOURS)
– SSN foreign key refers to SSN in EMPLOYEE, NOT NULL
– PNR foreign key refers to PNR in PROJECT, NOT NULL

42
 Mapping a Conceptual EER Model to a Relational Model

• Mapping an EER specialization

• Mapping an EER categorization
• Mapping an EER aggregation

43
 Mapping an EER Specialization
• 3 options:
– Create a relation for the superclass and each subclass
and link them with foreign keys
– Create a relation for each subclass and none for the
superclass
– Create one relation with all attribute types of the
superclass and subclasses and add a special attribute
type

44
 Mapping an EER Specialization

ARTIST(ANR, aname, …)
SINGER(ANR, music style, …)
ACTOR(ANR, …) 45
Mapping an EER Specialization

46
 Mapping an EER Specialization
SINGER(ANR, aname, music style, …)
ACTOR(ANR, aname, …)

47
 Mapping an EER Specialization
ARTIST(ANR, aname, music style, …,
discipline)

48
 Mapping an EER Specialization

EMPLOYEE(SSN, …)
STUDENT(SNR, …)
PHD-STUDENT(SSN, SNR, …) 49
 Mapping an EER Categorization

PERSON(PNR, …, CustNo)
COMPANY(CNR, …, CustNo)
ACCOUNT-HOLDER(CustNo, …)
50
Mapping an EER Categorization

51
 Mapping an EER Aggregation

CONSULTANT(CNR, …)
PROJECT(PNR, …)
PARTICIPATION(CNR, PNR, CONTNR, date)
CONTRACT(CONTNR, …)
52
 Exercise (3)
• Map the EER to a relational model, indicate the primary and foreigns keys and
add NULL declarations. Also explicitly mention which (if any) cardinalities are not
supported.

53
 Conclusions
• Relational Model
• Normalization
• Mapping a conceptual ER model to a relational
model
• Mapping a conceptual EER model to a relational
model

54
More information?

[Link] 55