CHAPTER - 3

DATABASE DESIGN

3.1 Entity Relationship Model

The Entity-Relationship (E-R) data model, which is popular for high level database
design, provides a means for representing relationships between entities. This approach was
profounded by P.P. Chen in 1976. The salient features of the E-R model are represented in
the following section:
 This is used to give structure to the data.
 Model can be evolved independent of any DBMS.
 It is an aid for database design.
 It is easy to visualize and understand.
The database structure, employing the E-R model is usually depicted pictorially using
entity-relationship (E-R) diagram as shown in Fig. 2.1.

ITEM ITEM CUST CUST

NO. NO.
DESC NAME

ITEM SHIPMENT CUSTOMER

COLOUR PRICE CUST CUST

QTY
CATEGORY COUNTR
Y
Notations used
Entity

Attributes

Relationship

Fig.3.1 Entity - Relationship diagram

 Database Design 3.2

3.1.1 Basic Concepts

There are three basic conventions that the E-R model employs:
 Entity Set
 Attributes
 Relational sets
(a) Entity Set: An entity is a “thing” or “object” in the real world that is distinguishable
from all other objects.

Example: a particular person, car, house, etc.

An entity has set of properties, and the values for some set of properties may
uniquely identify an entity.

For example person may a have a person-id property whose value uniquely
identities that person.

An entity set is a collection of entities having the same properties.

The individual entities in an entity set are called the extension of the entity set.

All the individual bank customers are the extension of the entity set customer.

(b) Attributes

The properties that describe an entity are called attributes.

In the customer entity customer id, name, street are the attributes.

An attribute can be classified into various types.

(i) Simple attribute: An attribute that cannot be divided into further subparts.

Example: Customer-id of customer entity.

(ii) Composite attribute: An attribute that can be divided into a set of subparts.

Example: In a customer entity, the attribute name can further be divided into
first-name, middle-name, last-name.

(iii) Single value attribute: An attribute having only one value in a particular
entity.

Example: In a customer entity, name, id, street are single valued attributes.
3.3 Database Management Systems

(iv) Multi-valued attribute: An attribute having more than one value for a
particular entity.

Example: Consider the customer entity set with the attribute phone no. A
customer may have zero, one or several phone nos and different customers
may have different numbers of phone.

(v) Derived attribute: An attribute that is derived from other related attributes or
entities.

For example, the age of a customer entity set is derived from the attribute
date-of-birth of a customer.

(c) Relationship set

Relationship is an association among several entities.
Relationship set is a set of relationships of the same type.
For example, relationship set borrower denotes the association between customer
and bank loan entity sets.

Customer Borrower Loan

Same entity set participates in a relationship set more than once, in different roles is
called recursive relationship set.
For example, employee entity set participates in relationship set works for as manager
or worker. A relationship set may also have descriptive attributes. For example, consider the
relationship set depositor with entity sets customer and account. Here we would associate the
attribute access date to the relationship to specify the most recent date on which a customer
accessed an account.
The number of entity sets that participate in a relationship set is called the degree of
relationship set.
Relationship between 2 entity sets are called binary relationship set.

Customer Borrower Loan

Relationships between 3 entity sets are called ternary relationship set.

 Database Design 3.4

Medical

Doctor Prescription Patient

3.1.2 Constraints
An E-R enterprise schema may define certain constraints to which the constraints to
which the contents of a database must conform.
Two types of constraints are
(i) Mapping cardinalities
(ii) Participation constraint
(i) Mapping Cardinalities

Mapping cardinalities or Cardinality ratio is defined as the number entities to

which another entity can be associated via a relationship set.

For a binary relationship set R between entity sets A and B, the mapping co-ordinality
must be one of the following

(i) One-to-one (1 : 1)

An entity in A is associated with at most one entity in B, and an entity in B is

associated with at most one entity in A.

(a) (b)

Fig. 3.2 One-to-One & One-to-Many

3.5 Database Management Systems

(ii)One-to-many (1 : M)

An entity in A is associated with any number of entities in B. An entity in B can be

associated with at most one entity in A.

(iii)Many-to-Many (M : N)

An entity in A is associated with any number of entities in B, and an entity in B is

associated with any number of entities in A.

(iv) Many to one (M : 1)

An entity in A is associated with at most one entity in B. An entity in B can be

associated with any number of entities in A.

(c) (d)
Fig. 3.3 Many-to-Many & Many-to-One
(ii) Participation Constraint
It specifies whether the existence of an entity depends on its being related to another
entity via the relationship type.

Total Participation Constraint

Types

Partial Participation Constraint

Eg. If a company policy states that every employee must work for a department, then
an employee entity can exist only if it participates in a WORKS – FOR relationship instance.
 Database Design 3.6

The participation of EMPLOYEE in WORKS – FOR is called total participation,

meaning that every entity in “total set” of employee entities must be related to a department
entity via, WORKS For.

In above eg. Not every employee manages a department, so the participation of

employee in the manages relationship type is partial. “Part of the set of” employee entities are
related to the department entity via manages relationship.

3.1.3 Weak Entity Set

Entity types that do not have key attributes of their own are called weak entity types.

A weak entity type always has a total participation constraint (existence dependency)
with respect to its identifying relationship, because a weak entity cannot be identified without
an owner entity type.

A weak entity set is indicated in E-R diagrams by a doubly outlined rectangular box
and the corresponding identifying relationship by a doubly outlined diamond.

For example in Fig.2.8 DEPENDENTS_OF, a 1:N relationship type between

EMPLOYEE and DEPENDENT, which is also the identifying relationship for the weak entity
type DEPENDENT. The participation of EMPLOYEE is partial, whereas that of
DEPENDENT is total.

3.1.4 Strong Entity Set

Entity types that have key attributes of their own are called strong entity types. A
strong entity set is indicated in E-R diagrams by rectangular box and its relationship by a
diamond.

For example in Fig.2.8 WORKS_FOR, a 1:N relationship type between

DEPARTMENT and EMPLOYEE. Both participations are total.

3.2 ER DIAGRAMS
The logical representation of the overall logical structure of a database is called as E-R
diagram.

Symbols used in the diagram

Rectangle   to represent an entity set

Ellipses   to represent an attribute
3.7 Database Management Systems

Diamonds  to represent relationship sets

Lines  to link attributes to entity sets and entity sets to relationship sets
Double ellipses   to represent multivalued attributes
Dashed ellipses   to represent derived attributes
Double rectangle  to represent weak entity sets
Double line  to represent total participation of an entity in a relationship set.
Symbol Meaning

Entity

Weak entity

Relationship

Identifying relationship

Attribute

Key attribute

Multivalued

Composite attribute

Derived attribute

E1 R E2
Total participation of E2 in R
1 N
E1 R E2
Cardinality ratio 1:N for E1:E2 in R
 Database Design 3.8

(min,
max)
R E
Structural constraint (min,max) on participation of E in R

Fig. 3.4 Summary of ER diagram notation

Fname Minit Lname

Name Address Salary

Locations
Bdate (1, 1) WORKS_FOR (4, N)
Sex Employee Department Name
Ssn

EMPLOYEE Start_date Number_of_employees DEPARTMENT

(1, 1) (0,N) Controlling

(0, 1) Department
Department
Manager MANAGES Managed
(0, N) (0, 1) CONTROLS
Supervision Supervisee

(1, N) Hours (1, 1) Controlled

Worker
Project
Project
SUPERVISION WORKS_ON PROJECT
(0, N) (1,N)
Employee

Name
Locations

Number
DEPENDENTS_OF

(1, 1) Dependent

DEPENDENT

Name Sex Birth_date Relationship

Fig. 3.5 ER diagram for the company schema

In above example, as shown in Fig. 3.5 we specify the following relationship types:
1. MANAGES, a 1:1 relationship type between EMPLOYEE and
[Link] participation is partial. DEPARTMENT participation is
not clear from the requirements. We question the users, who say that a department
must have a manager at all times, which implies total participation. The attribute
StartDate is assigned to this relationship type.
3.9 Database Management Systems

2. WORKS_For, a 1:N relationship type between DEPARTMENT and EMPLOYEE.

Both participations are total.
3. CONTROLS, a 1:N relationship type between DEPARTMENT and PROJECT. The
participation of PROJECT is total, whereas that of DEPARTMENT is determined to
be partial, after consultation with the users.
4. SUPERVISION, a 1:N relationship type between EMPLOYEE (in the supervisor role)
and EMPLOYEE (in the supervisee role). Both participations are determined to be
partial, after the users indicate that not every employee is a supervisor and not every
employee has a supervisor.
5. WORKS_ON, determined to be an M:N relationship type with attribute Hours, after
the users indicate that a project can have several employees working on it. Both
participations are determined to be total.
6. DEPENDENTS_OF, a 1:N relationship type between EMPLOYEE and
DEPENDENT, which is also the identifying relationship for the weak entity type
DEPENDEMT. The participation of EMPLOYEE is partial, whereas that of
DEPENDENT is total.
ER diagram examples
1. ER diagram for an Airline schema

Fig. 3.6 ER diagram for an Airline schem

 Database Design 3.10

2. ER diagram for a Bank schema

Fig. 3.7 ER diagram for a Bank schema

3.3 ER-TO-RELATIONAL MAPPING

ER Model, when conceptualized into diagrams, gives a good overview of entity-relationship,
which is easier to understand. ER diagrams can be mapped to relational schema, that is, it is
possible to create relational schema using ER diagram. We cannot import all the ER
constraints into relational model, but an approximate schema can be generated.
There are several processes and algorithms available to convert ER Diagrams into Relational
Schema. Some of them are automated and some of them are manual. We may focus here on
the mapping diagram contents to relational basics.
ER diagrams mainly comprise of −

 Entity and its attributes

 Relationship, which is association among entities.
3.11 Database Management Systems

EXAMPLE:
College Management System
1. A college contains many departments
2. Each department can offer any number of courses
3. Many instructors can work in a department
4. An instructor can work only in one department
5. For each department there is a Head
6. An instructor can be head of only one department
7. Each instructor can take any number of courses
8. A course can be taken by only one instructor
9. A student can enroll for any number of courses
10. Each course can have any number of students
Step 1 : Identify the Entities

What are the entities here?

From the statements given, the entities are

1. Department
2. Course
3. Instructor
4. Student
Stem 2 : Identify the relationships

1. One department offers many courses. But one particular course can be offered by only one
department. hence the cardinality between department and course is One to Many (1:N)
2. One department has multiple instructors . But instructor belongs to only one department.
Hence the cardinality between department and instructor is One to Many (1:N)
3. One department has only one head and one head can be the head of only one department.
Hence the cardinality is one to one. (1:1)
4. One course can be enrolled by many students and one student can enroll for many courses.
Hence the cardinality between course and student is Many to Many (M:N)
5. One course is taught by only one instructor. But one instructor teaches many courses.
Hence the cardinality between course and instructor is Many to One (N :1)

Step 3: Identify the key attributes

1. "Departmen_Name" can identify a department uniquely. Hence Department_Name is the

key attribute for the Entity "Department".
2. Course_ID is the key attribute for "Course" Entity.
 Database Design 3.12

3. Student_ID is the key attribute for "Student" Entity.

4. Instructor_ID is the key attribute for "Instructor" Entity.

Step 4: Identify other relevant attributes

1. For the department entity, other attributes are location

2. For course entity, other attributes are course_name,duration

3. For instructor entity, other attributes are first_name, last_name, phone

4. For student entity, first_name, last_name, phone

Step 5: Draw complete ER diagram

3.4 ENHANCED (EXTENDED) ER DIAGRAMS

The E-R diagrams discussed so far represents the basic concepts of a database schema.
However, some aspects of a database such as inheritance among various entity types cannot be
expressed using the basic E-R model. These aspects can be expressed by enhancing the E-R
3.13 Database Management Systems

model. The resulting diagrams are known as enhanced E-R or EER diagrams and the model
is called EER model.

The basic E-R model can represent the traditional database applications such as typical
data processing application of an organization effectively. On the other hand, the EER model
is used to represent the new and complex database applications such as telecommunications,
Geographical Information Systems (GIS), etc. This section discusses the extended E-R
features including specialization, generalization, and aggregation and their representation
using EER diagrams.

Enhanced (Extended) ER Diagrams

 Contain all the basic modeling concepts of an ER Diagram

 Adds additional concepts:

 Specialization/generalization

 Subclass/super class

 Categories

 Attribute inheritance

 Extended ER diagrams use some object-oriented concepts such as inheritance.

 EER is used to model concepts more accurately than the ER diagram.

Sub classes and Super classes

 In some cases, and entity type has numerous sub-groupings of its entities that are
meaningful, and need to be explicitly represented, because of their importance.

 For example, members of entity Employee can be grouped further into Secretary,
Engineer, Manager, Technician, Salaried_Employee.

 The set listed is a subset of the entities that belong to the Employee entity, which
means that every entity that belongs to one of the sub sets is also an Employee.

 Each of these sub-groupings is called a subclass, and the Employee entity is called
the super-class.
 Database Design 3.14

SSN Employee Name

Engineer
Secretary

Typing Eng Type

Speed
 An entity cannot only be a member of a subclass; it must also be a member of the
super-class.

 An entity can be included as a member of a number of sub classes, for example, a

Secretary may also be a salaried employee, however not every member of the
super class must be a member of a sub class.

Type Inheritance

 The type of an entity is defined by the attributes it possesses, and the

relationship types it participates in.

 Because an entity in a subclass represents the same entity from the super class,
it should possess all the values for its attributes, as well as the attributes as a
member of the super class.

This means that an entity that is a member of a subclass inherits all the attributes of the
entity as a member of the super class; as well, an entity inherits all the relationships in which
the super class participates.

Employee Wor Department

kFor

Secretary Engineer Technician

3.15 Database Management Systems

Specialization

 The process of defining a set of subclasses of a super class.

 Specialization is the top-down refinement into (super) classes and subclasses
 The set of sub classes is based on some distinguishing characteristic of the super
class.
 For example, the set of sub classes for Employee, Secretary, Engineer, Technician,
differentiates among employee based on job type.
 There may be several specializations of an entity type based on different
distinguishing characteristics.
 Another example is the specialization, Salaried_Employee and Hourly_Employee,
which distinguish employees based on their method of pay.
Notation for Specialization
 To represent a specialization, the subclasses that define a specialization are
attached by lines to a circle that represents the specialization, and is connected to
the super class.
 The subset symbol (half-circle) is shown on each line connecting a subclass to a
super class, indicates the direction of the super class/subclass relationship.
 Attributes that only apply to the sub class are attached to the rectangle representing
the subclass. They are called specific attributes.
A sub class can also participate in specific relationship types. See Example

Wor Department
Employee
kFor

Secretary Engineer Technician

Belon Professional
gs To
Organization
Reasons for Specialization
 Certain attributes may apply to some but not all entities of a super class. A
subclass is defined in order to group the entities to which the attributes apply.
 The second reason for using subclasses is that some relationship types may be
participated in only by entities that are members of the subclass.
 Database Design 3.16

Summary of Specialization
Allows for:
 Defining set of subclasses of entity type
 Create additional specific attributes for each sub class
 Create additional specific relationship types between each sub class and other
entity types or other subclasses.
Generalization
 The reverse of specialization is generalization.
 Several classes with common features are generalized into a super class.
 For example, the entity types Car and Truck share common attributes
License_PlateNo, VehicleID and Price, therefore they can be generalized into the
super class Vehicle.
Constraints on Specialization and Generalization
 Several specializations can be defined on an entity type.
 Entities may belong to subclasses in each of the specializations.
 The specialization may also consist of a single subclass, such as the manager
specialization, in this case we don’t use the circle notation.
Types of Specializations

Predicate-defined or Condition-defined specialization

 Occurs in cases where we can determine exactly the entities of each sub class by
placing a condition of the value of an attribute in the super class.

 An example is where the Employee entity has an attribute, Job Type. We can
specify the condition of membership in the Secretary subclass by the condition,
JobType=”Secretary”

Another Example:

University Incom
e

Income > 0
Instructor
Student

 The condition is called the defining predicate of the sub class.

3.17 Database Management Systems

 The condition is a constraint specifying exactly those entities of the Employee

entity type whose attribute value for Job Type is Secretary belong to the subclass.

 Predicate defined subclasses are displayed by writing the predicate condition next
to the line that connects the subclass to the specialization circle.

Attribute-defined specialization

 If all subclasses in a specialization have their membership condition on the

same attribute of the super class, the specialization is called an attribute-
defined specialization, and the attribute is called the defining attribute.

 Attribute-defined specializations are displayed by placing the defining attribute

name next to the arc from the circle to the super class.

User-defined specialization

 When we do not have a condition for determining membership in a subclass the

subclass is called user-defined.

 Membership to a subclass is determined by the database users when they add

an entity to the subclass.

Disjointness/Overlap Constraint

 Specifies that the subclass of the specialization must be disjoint, which means
that an entity can be a member of, at most, one subclass of the specialization.

 The d in the specialization circle stands for disjoint.

 If the subclasses are not constrained to be disjoint, they overlap.

 Overlap means that an entity can be a member of more than one subclass of the
specialization.

 Overlap constraint is shown by placing an o in the specialization circle.

Completeness Constraint

 The completeness constraint may be either total or partial.

 A total specialization constraint specifies that every entity in the superclass

must be a member of at least one subclass of the specialization.
 Database Design 3.18

 Total specialization is shown by using a double line to connect the super class
to the circle.

 A single line is used to display a partial specialization, meaning that an entity

does not have to belong to any of the subclasses.

Disjointness vs. Completeness

 Disjoint constraints and completeness constraints are independent. The

following possible constraints on specializations are possible:

a) Disjoint, total

Department

Academic Administrative

b) Disjoint, partial

Employee

Secretary Analyst Engineer

3.19 Database Management Systems

c) Overlapping, total

Part

Manufactured Puchased

d) Overlapping, partial

Movie

Children Comedy Drama

3.5 FUNCTIONAL DEPENDENCY

3.5.1 Introduction
Relational database design requires that we find a “good” collection of relation
schemas.
Pit-falls in Relational Database Design
A bad design may lead to
(a) Repetition of information - that leads to insertion, deletion, updation problems.
(b) Inability to represent certain information.
 Database Design 3.20

Design goals
(a) Avoid redundant data.
(b) Ensure that relationships among attributes are represented.
(c) Facilitate the checking of updates for violation of database integrity constraints.
Example
Consider the relation schema:
Lending-schema (branch_name, branch_city, assets,
customer_name, loan_no, amount)
branch_ name branch_ assets Customer_ Laon_no amount
city name

Avadi Chennai 90,00,000 Prajan L-17 1000

Gandhi Nagar Bangalore 21,00,000 Dharshan L-23 2000
Sivaji Nagar Bangalore 17,00,000 Pradeep L-15 1500
Avadi Chennai 90,00,000 Praveen L-14 3500

Here branch Downtown details are represented 2 times. This leads to a redundancy
problem.
Redundancy
Data for branch_name, branch_city, assets are repeated for each loan that a branch makes:
(a)wastes space
(b) complicates updating, introducing inconsistency of assets value.
Null Values
(a) Cannot store information about a branch if no loan exist.
(b) Can use null values, but they are difficult to handle.
Decomposition
 Decompose the relation-schema, lending schema into
Branch-schema (branch_name, branch_city, assets)
Loan-schema (customer_name, loan_no, branch_name, amount)
 All attributes of original schema (R) must appear in decomposition (R1, R2).

R = R1  R2
3.21 Database Management Systems

 Lossless join decomposition.

All possible relations r on schema R.

r = πR1 (r) πR2 (r)

Goal: To decide whether a particular relation R is in ‘good’ form, decompose it into a set of
relations (R1, R2, ..., Rn) such that

 each relation is in “good” form.

 the decomposition should be lossless decomposition.

3.5.2 Functional Dependencies

 It requires that the value for a certain set of attributes determines uniquely the
value for another set of attributes.

 In a given relation R, X and Y are attributes. Attributes Y is functionally

dependent on attribute X if each value of X determines exactly one value of Y,
which is represented as

XY

i.e., “X determines Y” or “Y is functionally dependent on X”

X  Y does not imply Y  X

For example, in a student relation the value of an attribute “Marks” is known then the
value of an attribute “Grade” is determined since

Marks  Grade.

Types

(a) Full functional dependency

(b) Partial functional dependency

(c) Transitive functional dependency

(a) Full dependencies

In a relation R, X and Y are attributes. X functionally determines Y. Subset of X

should not functionally determine Y.
 Database Design 3.22

Student_no

Marks

Course_no

In the above example marks is fully functionally dependent on student_no and

course_no together and not on subset of {student_no, course_no}.

This means marks cannot be determined either by student_no or course_no alone. It

can be determined only using student_no and course_no together.

Hence marks is fully functionally dependent on {student_no, course_no}.

(b) Partial Dependencies

Attribute Y is partially dependent on the attribute X only if it is dependent on a subset

of attribute X.

For example course_name, Instructor_name are partially dependent on composite

attributes {student_no, course_no} because course_no alone defines course_name,
Instructor_name.

(c) Transitive Dependencies

X, Y and Z are 3 attributes in the relation R.

X Y
 Y Z
X Z

For example, grade depends on marks and in turn make depends on {student_no
course_no}, hence Grade depends fully transitively on {student_no & course_no}.

Use of Functional Dependencies

We use functional dependencies to

 Test relations to see if they are legal under a given set of functional dependencies.

If a relation r is legal under a set F of functional dependencies, we say that r

satisfies F.
3.23 Database Management Systems

 Specify constraints on the set of legal relations.

 A specific instance of a relation schema must satisfy a functional dependency

even if the functional dependency does not hold on all legal instances.

For example, a specific instance of loan-schema may by chance satisfy

Loan_no  customer_name

 A functional dependency is trivial if it is satisfied by all instance of a relation.

For example, A  A is satisfied by all relations involving attribute A. Reading the

definition of functional dependency literally we see that for all tuples t 1 and t2 such
that t1[A] = t2[A], it is the case that t1[A] = t2[A]. similarly, AB  A is satisfied by
all relations involving attribute A.

In general a functional dependency of the form  is trivial if   

3.6 NORMALIZATION
Normalizing a logical database design involves organizing the data into more than one
table. Normalization improves performance by avoiding the redundancy. Redundancy can
lead to:

• Inconsistencies - Errors are more likely to occur when facts are repeated.

• Update anomalies - Inserting, modifying and deleting data may cause

inconsistencies.

There is a high likelihood of data in one table being updated or deleted, while
corresponding changes in other relations are omitted.

Normalization has numerous benefits. These include faster sorting and index creation,
few indexes per table, few NULLs and an increase in the compactness of the database.
However the number and complexity of joins increase with the increase in normalization. If
the number of joins between table increases, the performance of the database may deteriorate.
Normalization helps to simplify the structure of tables. The performance of an application is
directly linked to the data base design. A poor design hinders the performance of the system.
The logical design of the database lays the foundation for an optimal database.

Some rules that should be followed to achieve a good database design are:

• Each table should have an identifier.

• Each table should store data for a single type of entity.

 Database Design 3.24

• Nullable columns in tables should be avoided.

• The repetition of values of columns in table should be avoided.

Normal Forms:

Normalization results in the formation of tables that satisfy certain specified

constraints, and represent certain normal forms. The normal forms are used to ensure that
various types of anomalies and inconsistencies are not introduced in the database. Normal
forms are table structures with minimum redundancy. Several normal forms have been
identified. The most important and widely used of these are:
• First Normal Form (1 NF)
• Second Normal Form (2 NF)
• Third Normal Form (3 NF)
• Boyce-Codd Normal Form (BCNF)
3.6.1 First Normal Form
A table is said to be in the 1 NF when each cell of the table constants precisely one
value.
Consider the following table Project.
Project:
Ecode Dept Proj Code Hours
E101 Systems P27 90
P51 101
P20 60
P27 100
E305
Sales P22 98
P51 Null
E508
Admin P27 72

The data in the table is not normalized because a cell in ProjCode and Hours has more
then one value.
By applying the INF definition to the project table, you arrive at the following table.

Project:
Ecode Dept Proj Code Hours
3.25 Database Management Systems

E101 Systems P27 90

E101 Systems P51 101
E101 Systems P20 60
E305 Sales P27 109
E305 Sales P22 98
Admin P51 Null
E508
E508 Admin P27 72

3.6.2 Second Normal Form

A table is said to be in 2 NF when it is in 1 NF and every attribute in the row is
functionally dependent upon the whole key and not just part of the key.
Consider the Project Table:
Project
Ecode
ProjCode
Dept
Hours

The table has the following rows:

Ecode Proj Code Dept Hours

E101 P27 Systems 90
E305 P27 Finance 10
E508 P51 Admin Null
E101 P51 Systems 101
E101 P20 Systems 60
E508 P27 Admin 72

This situation could lead to the following problems:

• Insertion
 Database Design 3.26

The department of a particular employee cannot be recorded until the employee

is assigned a project.

• Updating

For giving employee, the employee code and department are repeated several
times. Hence if an employee is transferred to another department, this change
will have to be recorded in every row of the employee table. Any omission will
lead to inconsistencies.

• Deletion

If an employee works on a project, the employee’s record will be deleted. The

information regarding the department to which the employee belongs will also
be lost.

The primary key here is composite ( ECode + ProjCode).

The table satisfies the definition of 1 NF. You need to now check if it satisfies 2NF.

In the table for each value of ECode, there is more than one value of Hours. For
example, for ECode, E101, there are three values of Hours: 90, 101 and 60. Hence, Hours is
not functionally dependent on ECode. Similarly, for each value of ProjCode, there is more
than one value of Hours. For example for ProjCode, P27 there is three values of Hours, 90, 10
and 72. However, for a combination of the ECode and ProjCode values, there is exactly one
value of Hours. Hence Hours is functionally dependent on the whole key, ECode + ProjCode.
i.e. Ecode Hours and Projcode  Hours.

Now you are must check it Dept is functionally dependent on the whole key,
ECode+ProjCode. For each value of ECode, there is exactly one value of Dept. For example,
for ECode 101, there is exactly one value the systems department. Hence, Dept is functionally
department on ECode i.e. Ecode Dept. However, for each value of ProjCode, there is more
than one value of Dept. For example, for ProjCode P27, there are two values of Dept, System
and Finance. Hence, Dept is not functionally dependent on ProjCode. Dept is not functionally
dependent on ProjCode. Dept is, therefore, functionally dependent on part of the key (which is
ECode) and not functionally dependent on the whole key (ECode+ProjCode). Therefore the
table Project is not in 2NF. For the table to be in 2NF, the non-key attributes must be fully
functionally dependent on the whole key and not part of the key.

Guidelines for Converting a Table to 2 NF

3.27 Database Management Systems

• Find and remove attributes that are functionally dependent on only a part of the
key and not on the whole key. Place them in a different table.

• Group the remaining attributes.

To convert the table Project into 2NF, you must remove the attributes that are not fully
functionally dependent on the whole key and place them in a different table along with the
attribute that it is functionally dependent on. In the above example, since Dept is not fully
functionally dependent on the whole key ECode+ProjCode, you place Dept along with ECode
in a separate table called EmployeeDept.

Now the table Project will contain ECode, ProjCode and Hours.

EmployeeDept:

Ecode Dept
E101 Systems
E305 Sales
E508 Admin

Project
Ecode Proj Code Hours
E101 P27 90
E101 P51 101
E101 P20 60
E305 P27 10
E508 P51 Null
E508 P27 72

3.6.3 Third Normal Form

A relation is said to be in 3 NF when it is in 2 NF and every non-key attribute is
functionally dependent only on the primary key.
Consider the table Employee
 Database Design 3.28

Ecode Dept DeptHead

E101 Systems E901
E305 Finance E909
E402 Sales E906
E508 Admin E908
E607 Finance E909
E608 Finance E909

The problems with dependencies of this kind are:

• Insertion
The department head of the new department that does not have any employees
at present cannot be entered in the DeptHead column. This is because the primary
key is unknown.
• Updating
For a given department, the code for a particular department head (DeptHead) is
repeated several times. Hence if a department head moves to another department,
the change will have to be made consistently across the table.
• Deletion
If the record of an employee is deleted, the information regarding the head of
the department will also be deleted. Hence there will be a loss of information.

You must check if the table is in 3NF. Since each cell in the table has the single
value, the table is in 1NF.
The primary key in Employee table is ECode. For Each value of Ecode, there is
exactly one value of Dept. Hence the attribute Dept is functionally dependent on the primary
key ECode i.e. Ecode Dept. Similarly for each value of ECode, there is exactly one value
of DeptHead. Hence DeptHead is functionally dependent on the primary key ECode. Hence
all the attributes are functionally dependent on the whole key, ECode. Hence the table is in
2NF.
However, the attribute DeptHead is dependent on the attribute Dept also.
i.e. Dept Depthead As per 3NF, all non-key attributes have to be functionally dependent
3.29 Database Management Systems

only on the primary key. This table is not in 3NF since DeptHead is functionally dependent on
Dept, which is not a primary key.
Guidelines for Converting a Table to 3NF
• Find and remove non-key attributes that are functionally dependent on the
attributes that are not the primary key. Place them in a different table.
• Group the remaining attributes.
To convert the table employee into 3NF, you must remove the column DeptHead since
it is not functionally dependent on only the primary key ECode and place it in another table
called Department along with the attribute dependent on.

Employee
Ecode Dept
E101 Systems
E305 Finance
E402 Sales
E508 Admin
E607 Finance
E608 Finance
Department
Ecode DeptHead
E101 E901
E305 E909
E402 E906
E508 E908
E607 E909
E608 E909
 Database Design 3.30

3.6.4 Boyce-Codd Normal Form

The original definition of 3NF was inadequate in some situation. It was not
satisfactory for the tables:
 That had multiple candidate keys
 Where the multiple candidate key were composite.
 Where the multiple candidate key overlapped (Had at least one attribute in
common)
Hence, a new normal form - the Boyce-Codd normal form was introduced. You must
understand that in table were the above three condition do not apply, you can stop at the third
normal form. In such cases, the third NF is the same as the Boyce-Codd normal form.
A relation is in the Boyce-Codd normal form (BCNF) if and only if every determinant
is a candidate key.
Consider the table Project given below.
Project
Ecode Name Proj Code Hours
E1 Veronica P2 48
E2 Anthony P5 100
E3 Mac P6 15
E4 Susan P3 250
E4 Susan P5 75
E1 Veronica P5 40

This table has redundancies. If the name of an employee is changed, the change will
have to be made in every row of the table, otherwise there will be inconsistencies.
ECode+ProjCode is the primary key. You will notice that Name+ProjCode could be
chosen as the primary key and hence, is a candidate key.
* Hours is functionally dependent on ECode+ProjCode.
* Hours is also functionally dependent on Name+ProjCode.
* Name is functionally dependent on Ecode.
* ECode Is functionally dependent on Name.
You will notice that this table has:
• Multiple candidate keys, that is ECode+ProjCode and Name+ProjCode.
3.31 Database Management Systems

• The candidate keys are composite.

• The candidate keys overlap since the attribute - ProjCode is common.
This is the case of the Boyce-Codd Normal form. This is in third NF. The only non
key item is Hours, which is dependent on the whole key that is ECode + ProjCode or Name+
ProjCode.
ECode and Name are determinants since they are functionally dependent on the each
other. However, they are not candidate keys by themselves. As per BCNF, the determinants
have to be candidate keys.

Guidelines for Converting a Table to BCNF

• Find the remove the overlapping candidate keys. Place the part of the candidate
key and the attribute it is functionally dependent on, in a different table.
• Group the remaining items into a table.
Hence, remove Name and ECode and place them in a different table. You will arrive at
the following tables.
Employee
Ecode Name
E1 Veronica
E2 Anthony
E3 Mac
E4 Susan
E4 Susan
E1 Veronica
Project

Ecode Proj Code Hours

E1 P2 48
E2 P5 100
E3 P6 15
E4 P3 250
E4 P5 75
E1 P5 40
 Database Design 3.32

3.6.5 Relational Decomposition

A single decomposition schema R={A1,A2,…..An} that includes all the attributes of the
database. Every attributes name is unique using the FDs, the algorithms decomposes the
universal relation schema R into a set of relation schema D={R 1, R2,….Rm} that will become
the relational database schema D is called decomposition of R.
We must make sure that each attribute in R will appear in atleast one relation schema
Ri in the decomposition so that no attributes are lost formally.
m
R i  R
i 1

This is called attribute preservation condition of decomposition.

Properties of Decomposition
(1) Dependency preservation.
(2) Lossless (or non additive) join property.
[Link] Dependency Preservation
If each functional dependency X  Y specified in F either appeared directly in one of
the relation schemas Ri in the decomposition D or could be from the dependencies that appear
in some Ri. Informally this Dependency preservation condition.

Definition
Given a set of dependencies F on R, the projection of F on R i, denoted by Ri(F)
where Ri-subset of R, is the set of dependencies X  Y in F+ such that the attributes in XUY
are all condition in Ri.

Hence the projection of F on each relation schema R i in the decomposition D is the set of
FDs in F+, such that all their left and RHS attributes are in Ri.
A decomposition D={R1, R2…Rm} of R is dependency preserving with respect to F if
the union of the properties of F on each Ri on D is equivalent to F.
(ie)
 R i , (R)  .....   R m (F) )  F
[Link] Lossless (non additive) Joins
This property ensures that no spurious tuples are generated when a natural join
operation is applied to the relations in the decomposition.
3.33 Database Management Systems

A decomposition D={R1, R2…Rm}of R has the lossless (non additive) join property
with respect to the set of dependencies F on r if, for every relation state r of R that satisfies F,
the following holds, where
 is the natural join of all the relations in D.
 (Ri (r), ……Rm (r)) = r

3.7.6 Comparison of BCNF and 3NF

It is always possible to decomposes a relation into relations in 3NF and

 the decomposition is lossless
 dependencies are preserved
It is always possible to decomposes a relation into relations in BCNF and
 the decomposition is lossless
 it may not be possible to preserve dependencies
R = (J, K, L)
F = {JK  L, L  K}
J L K
J1 L1 K1
J2 L1 K1
J3 L1 K1
null L2 K2
Consider the relation described in table

A schema that is in 3NF but not in BCNF has the problems of:

 repetition of information (e.g., the relationship i1, k1)

 need to use null values (e.g., to respect the relationship i 2, k2 where there is
no corresponding value for J).
3.7.7 Multivalued Dependencies and Fourth Normal Form

[Link] Formal Definition of Multivalued Dependency

A multivalued dependency (MVD) x y specified on relation schema R, where x

and y are both subsets of R, specifies the following constraint on any relation state r of R.

If two tuples t1 and t2 exist in r such that t1 [x] = t2 [x], then two tuples t3 and t4 should
also exist in r with the following properties.
 Database Design 3.34

 t3 [X] = t4[X] = t1[X] = t2 [X]

 t3 [Y] = t1[Y] and t4[Y] = t2 [Y]

 t3 [Z] = t2[Z] and t4[Z] = t1 [Z]

Here, X Y denotes that x multi-determines Y.

An MVD X Y in r is called a trivial MVD if
a) Y is a subset of X or
b) XUY = R
Eg.. Fig. 2.7 (b)
An MVD that satisfies neither (a) nor (b) is called a nontrivial MVD.

3.7.8 Fourth Normal Form

A relation schema R is in 4 NF with respect to a set of dependencies F (that includes

functional dependencies and multivalued dependencies) if, for every nontrivial multivalued
dependency x y in F+, x is a superkey for R.

The EMP relation of Fig. 10.1 (a) is not in 4NF because in the nontrivial MVDs
ENAME PNAME and ENAME DNAME, ENAME is not a superkey of EMP. We
decompose EMP into EMP – PROJECTS and EMP - DEPENDENTS, shown in Fig. (b). Both
EMP - PROJECTS and EMP - DEPENDENTS are in 4NF, because the MVDs ENAME
PNAME in EMP - PROJECTS and ENAME DNAME in EMP - DEPENDENTS are
trivial MVDs. No other nontrivial MVDs hold in either EMP - PROJECTS or EMP -
DEPENDENTS.
EMP
(a)
ENAME PNAME DNAME

Dharshan X Prajan
Dharshan Y Pradeep
Dharshan X Pradeep
Dharshan Y Prajan
3.35 Database Management Systems

EMP-PROJECTS EMP-DEPENDENTS
(b)
ENAME PNAME ENAME DNAME

Dharshan X Dharshan Prajan

Dharshan Y Dharshan Pradeep

Fig. 3.8 Fourth normal form

a) The EMP relation with two MVDs:

ENAME PNAME and ENAME DNAME
b) Decomposing EMP into two relations into two 4NF relations
EMP - PROJECTS and EMP-DEPENDENTS

[Link] Loss less Join Decomposition into 4NF Relations

Whenever we decompose a relation schema R into R 1 = (XY) and R2 = (R – Y)
based on an MVD X Y that holds in R, the decomposition has the lossless join property.
This is a necessary and sufficient condition for decomposing a schema into two schemas that
has the loss less join property, as given by the property LJ.

Property LJ

The relation schemas R1 and R2 form a lossless join decomposition of R if and only if
(R1  R2) (R1 – R2 ).

Algorithm

Relational decomposition into 4NF relations with lossless join property.

Input
A universal relation R and a set of FDs and multivalued dependencies F.
1. SetD:={R};
2. While there is a relation schema Q in D that is not in 4NF do
{
choose a relation schema Q in D that is not in 4NF;
Find a nontrivial MVD X Y in Q that violates 4NF.
replace Q in D by two relations schemas (Q – Y) and (X  Y);
};
 Database Design 3.36

3.7.9 Join Dependencies and Fifth Normal Form

The normal forms discussed so far required that the given relation R if not in the given
normal form be decomposed in two relations to meet the requirements of the normal form. In
some rare cases, a relation can have problems like redundant information and update
anomalies because of it but cannot be decomposed in two relations to remove the problems. In
such cases it may be possible to decompose the relation in three or more relations using the
5NF.

The fifth normal form deals with join-dependencies which is a generalisation of the
MVD. The aim of fifth normal form is to have relations that cannot be decomposed further. A
relation in 5NF cannot be constructed from several smaller relations.

A relation R satisfies join dependency (R1, R2, ..., Rn) if and only if R is equal to the
join of R1, R2, ..., Rn where Ri are subsets of the set of attributes of R.

A relation R is in 5NF (or project-join normal form, PJNF) if for all join
dependencies at least one of the following holds.

(a) (R1, R2, ..., Rn) is a trivial join-dependency (that is, one of Ri is R)

(b) Every Ri is a candidate key for R.

An example of 5NF can be provided by the example below that deals with departments,
subjects and students.

Dept Subject Student

Comp. Sc. CP1000 John Smith
Mathematics MA1000 John Smith
Comp. Sc. CP2000 Arun Kumar
Comp. Sc. CP3000 Reena Rani
Physics PH1000 Raymond Chew
Chemistry CH2000 Albert Garcia

The above relation says that Comp. Sc. offers subjects CP1000, CP2000 and CP3000
which are taken by a variety of students. No student takes all the subjects and no subject has
all students enrolled in it and therefore all three fields are needed to represent the information.
3.37 Database Management Systems

The above relation does not show MVDs since the attributes subject and student are
not independent; they are related to each other and the pairings have significant information in
them. The relation can therefore not be decomposed in two relations

(dept, subject), and

(dept, student)
without losing some important information. The relation can however be decomposed
in the following three relations

(dept, subject), and

(dept, student)
(subject, student)

and now it can be shown that this decomposition is lossless.

3.7.10 Domain key normal form (DKNF)

The idea behind DKNF is to specify the “ultimate normal form” that takes into account
all possible types of dependencies and constraints.

A relation is said to be in DKNF if all constraints and dependencies that should hold
on the relation can be enforced simply by enforcing the domain constraint and key constraint
on the relation.

For a relation in DKNF, it becomes very straight forward to enforce all data base
constraints by simply checking that each attribute value in a tuple is of the appropriate domain
and that every key constraint is enforced.

3.7.11 De-normalization

De-normalization is the process of attempting to optimize the read performance of a

database by adding redundant data or by grouping data. In some cases, denormalization helps
cover up the inefficiencies inherent in relational database software. A relational normalized
database imposes a heavy access load over physical storage of data even if it is well tuned for
high performance.

A normalized design will often store different but related pieces of information in
separate logical tables (called relations). If these relations are stored physically as separate
disk files, completing a database query that draws information from several relations (a join
operation) can be slow. If many relations are joined, it may be prohibitively slow. There are
two strategies for dealing with this. The preferred method is to keep the logical design
 Database Design 3.38

normalized, but allow the database management system (DBMS) to store additional redundant
information on disk to optimize query response. In this case it is the DBMS software's
responsibility to ensure that any redundant copies are kept consistent. This method is often
implemented in SQL as indexed views (Microsoft SQL Server) or materialized views
(Oracle). A view represents information in a format convenient for querying, and the index
ensures that queries against the view are optimized.

The more usual approach is to denormalize the logical data design. With care this can
achieve a similar improvement in query response, but at a cost—it is now the database
designer's responsibility to ensure that the denormalized database does not become
inconsistent. This is done by creating rules in the database called constraints, that specify how
the redundant copies of information must be kept synchronized. It is the increase in logical
complexity of the database design and the added complexity of the additional constraints that
make this approach hazardous. Moreover, constraints introduce a trade-off, speeding up reads
(SELECT in SQL) while slowing down writes (INSERT, UPDATE, and DELETE). This
means a denormalized database under heavy write load may actually offer worse performance
than its functionally equivalent normalized counterpart.

A denormalized data model is not the same as a data model that has not been
normalized, and denormalization should only take place after a satisfactory level of
normalization has taken place and that any required constraints and/or rules have been created
to deal with the inherent anomalies in the design. For example, all the relations are in third
normal form and any relations with join and multi-valued dependencies are handled
appropriately.

Examples of denormalization techniques include:

 Materialized views, which may implement the following:

 Storing the count of the "many" objects in a one-to-many relationship as an

attribute of the "one" relation

 Adding attributes to a relation from another relation with which it will be

joined

 Star schemas, which are also known as fact-dimension models and have been extended
to snowflake schemas

 Prebuilt summarization or OLAP cubes

De-normalization techniques are often used to improve the scalability of Web

applications.
3.39 Database Management Systems

IMPORTANT QUESTIONS AND ANSWERS

PART - A

1. What is an entity relationship model?

The entity relationship model is a collection of basic objects called
entities and relationship among those objects. An entity is a thing or object in
the real world that is distinguishable from other objects.

2. What are attributes? Give examples.

An entity is represented by a set of attributes. Attributes are descriptive
properties possessed by each member of an entity set.
Example: possible attributes of customer entity are customer name, customer
id, Customer Street, customer city.
3. What is an entity?
An entity is an object that exists and is distinguishable from other objects.
Example: specific person, company, event, plant

4. Define the terms: i) Entity set ii) Relationship set

Entity set: The set of all entities of the same type is termed as an entity set.
Relationship set : The set of all relationships of the same type is termed as a
relationship set.

5. Define single valued and multivalued attributes.

Single valued attributes: attributes with a single value for a particular entity
are called single valued attributes.
Multivalued attributes : Attributes with a set of value for a particular
entity are called multivalued attributes.

6. What are stored and derived attributes?

Stored attributes: The attributes stored in a data base are called stored attributes.
Derived attributes: The attributes that are derived from the stored attributes
are called derived attributes.

7. Define null values.

In some cases a particular entity may not have an applicable value for an
attribute or if we do not know the value of an attribute for a particular entity.
In these cases null value is used.

8. What does the cardinality ratio specify?

 Database Design 3.40

Mapping cardinalities or cardinality ratios express the number of entities to

which another entity can be associated. Mapping cardinalities must be one of the
following:
• One to one
• One to many
• Many to one
• Many to many
9. Define the terms: i) Key attribute ii) Value set
Key attribute : An entity type usually has an attribute whose values are
distinct from each individual entity in the collection. Such an attribute is called a key
attribute.
Value set: Each simple attribute of an entity type is associated with a
value set that specifies the set of values that may be assigned to that attribute
for each individual entity.

10. Define weak and strong entity sets?

Weak entity set: entity set that do not have key attribute of their own are
called weak entity sets.
Strong entity set: Entity set that has a primary key is termed a strong entity set.

11. Explain the two types of participation constraint.

Total: The participation of an entity set E in a relationship set R is said
to be total if every entity in E participates in at least one relationship in R.
Partial: if only some entities in E participate in relationships in R, the
participation of entity set E in relationship R is said to be partial.

12. Define the terms Generalization and Aggregation?

Generalization is a containment relationship that exists between a high-level Entity
set and one or more low-level entity set.
Aggregation is an abstraction through which relationships are treated as higher-level
entities.

13. What is ER diagram?

An entity-relationship diagram is a data modeling technique that creates a
graphical representation of the entities, and the relationships between entities, within
an information system.

14. What are the steps involved in creating in ERD?

3.41 Database Management Systems

a) Identify the entities.

b) Find the relationships
c) Identify key attributes for every entity
d) Draw the ERD.

15. Define tuple and attribute

Attributes: Name of Columns or fields
Tuple : Name of Rows or records

16. Define the term Domain.

For each attribute there is a set of permitted values called the domain of that
attribute.

17. What are referential integrity constraints?

A value that appears in one relation for a given set of attributes also appears for a
certain set of attributes in another relation.

18. What is the use of integrity constraints?

Integrity constraints ensure that changes made to the database by authorized users do
not result in a loss of data consistency. Thus integrity constraints guard against
accidental damage to the database.

19. What is normalization?

Database normalization is the process of organizing the fields and tables of
a relational database to minimize redundancy and eliminate dependency.
Normalization usually involves dividing large tables into smaller (and less
redundant) tables and defining relationships between them.

20. What are the needs of normalization?

 To reduce redundancy
 To eliminate dependency
 To solve insert, delete, update anomalies.

21. Define 1NF
A relation said to be first normal form if and if only all attributes are atomic in
nature.

22. Define 2NF

A relation said to be second normal form if and if only relation should be in first
 Database Design 3.42

normal form and to eliminate partial dependency.

23. Define 3NF

A relation said to be third normal form if and if only relation should be in second
normal form and to eliminate transitive dependency.

24. Define BCNF

A relational schema R is in Boyce–Codd normal form if and only if for every one of
its dependencies X → Y, at least one of the following conditions hold

 X → Y is a trivial functional dependency (Y ⊆ X)

 X is a superkey for schema R

25. Define 4NF
A Table is in 4NF if and only if, for every one of its non-trivial multivalued
dependencies X Y, X is a superkey that is, X is either a candidate key or a superset

26. Define 5NF

A table is said to be in the 5NF if and only if every non-trivial join dependency in it
is implied by the candidate keys.

PART – B

1. Explain about Entity Relationship Model with ER diagrams and example.

2. Explain Extended ER Model
3. Draw an E-R diagram for
 Banking system
 Airline Reservation system
 Payroll system
4. Construct an ER diagram for a car-insurance company whose customers own one
or more cars each. Each car has associated with its zero to any number of record
accidents. State any assumptions you make.

5. What is normalization? Explain normalization techniques using functional

dependencies with relevant examples.
6. Compare and contrast 3NF and BCNF
7. Explain the multi-valued dependency and fourth normal form with example.
3.43 Database Management Systems

8. Explain the Join dependency and fifth normal form with example.
9. Draw an ER diagram for Hospital management system.
10. What is Functional Dependency? Explain types and properties of FD’s.
11. Construct an ER diagram for university registrar’s office. The office maintains
data about each class, including the instructor, the enrollment and the time and
place of the class meetings. For each student class pair a grade is recorded.
Determine the entities and relationships.
12. Define generalization and aggregation. Demonstrate generalization and
aggregation using E-R diagram.