Database Management Systems - 24CS403

Module - 4 Notes
Chapter 14 - Basics of Functional Dependencies and Normalization for Relational Databases
Informal Design Guidelines for Relation Schemas; Functional Dependencies; Normal Forms Based on Primary
Keys-1NF, 2NF, 3NF, Boyce-Codd Normal Form. Multi-valued Dependencies and Fourth Normal Form.

In this chapter, we study the concepts and principles developed to judge whether a relational database schema
is well designed or not.”

 Relational schema → structure of database tables and attributes

 Design quality → how good the database design is (less redundancy, fewer anomalies, better
organization)
Informal Design Guidelines for Relation Schemas
a) Imparting Clear Semantics to Attributes in Relations
b) Reducing the redundant information in tuples
c) Reducing the NULL values in tuples
d) Disallowing the possibility of generating spurious tuples

a) Imparting Clear Semantics to Attributes in Relations

 A relation (table) should have a clear and simple meaning.
 The semantics of a relation means:
 what the relation represents
 what each tuple (row) means in the real world

Guideline 1 – A relation should represent one entity or one relation, i.e. do not mix unrelated entities into
one relation

I. Example of Good Design - EMPLOYEE relation

Ename Ssn Bdate Address Dnumber

Meaning is very clear - each row represents one employee

II. Bad Design Example - EMP_DEPT

Ename Ssn Dnumber Dname Dmgr_ssn

This table mixes employee & department information. So semantics become confusing.

b) Reducing the redundant information in tuples & Update anomalies

Design relations so that they do not suffer from anomalies:
 i. insertion anomalies
ii. deletion anomalies
iii. modification anomalies

These problems happen mainly because of redundancy (same data repeated many times)

Consider the table - EMP_DEPT Table

Ename Ssn Dnumber Dname Dmgr_ssn
John 101 5 Research 9001
Alice 102 5 Research 9001
Ravi 103 1 Administration 9002
Meena 104 1 Administration 9002
David 105 4 Headquarters 9003
Sara 106 5 Research 9001
Kiran 107 4 Headquarters 9003

Why redundancy is bad ??

 “Research” department details appear again and again for all employees in that department.

 This wastes: storage space &

 update effort
Insertion Anomaly - Suppose company creates a new department:

Dnumber Dname Dmgr_ssn

7 Testing 9004

 But no employee is assigned yet.

 We cannot insert department alone, because Ename & Ssn become NULL
 Ssn is primary key & can not be NULL

Issue - A department without employees cannot be inserted properly.

Deletion Anomaly - Suppose employee David (105) and Kiran (107) leave the company.

After deleting both rows:

Ename Ssn Dnumber Dname Dmgr_ssn

John 101 5 Research 9001
Alice 102 5 Research 9001
Ravi 103 1 Administration 9002
 Meena 104 1 Administration 9002
Sara 106 5 Research 9001

Now information about department 4 (Headquarters) is completely lost.

So Deleting employee rows accidentally delete department information too.

Modification Anomaly
 Suppose manager of Research department changes from 9001 to 9010.

 We must update ALL these rows:

Ename Ssn Dnumber Dname Dmgr_ssn

John 101 5 Research 9010
Alice 102 5 Research 9010
Sara 106 5 Research 9001

Imagine we update only two rows:

Ename Ssn Dnumber Dname Dmgr_ssn

John 101 5 Research 9010
Alice 102 5 Research 9010
Sara 106 5 Research 9001

Now database says: same department has two managers.

This creates inconsistency.

So Repeated data causes difficult and error-prone updates.

Guideline 2 - Design the base relation schemas so that no insertion, deletion, or modification anomalies
are present in the relations.

c) NULL Values in Tuples

Guideline 3
i. Avoid attributes that contain too many NULL values.
ii. If an attribute applies only to a few tuples, it is better to place it in a separate relation.

A fat relation is a table containing too many attributes (columns).

Example:
EmpId Name Salary PassportNo VisaStatus OfficeNo
Problem: many employees may not have:
o passport
o visa
 o office

So table becomes full of NULLs.

Example with NULLs

EmpId Name VisaStatus OfficeNo
101 John H1B 201
102 Ravi NULL NULL
103 Meena NULL NULL
104 Sara NULL 305
105 David NULL NULL

Problems Caused by NULLs

i. Wastage of Storage Space - Even NULL values occupy storage

ii. Difficult to Understand Data - What does NULL mean?
VisaStatus = NULL
Possible meanings:
 employee does not need visa
 visa status unknown
 value not entered yet

iii. Problems in Queries and JOINs – Functions like COUNT, SUM, AVG handle NULL in special ways

d. Generation of Spurious Tuples

 Spurious tuples are: incorrect or meaningless rows produced after a JOIN operation.
 They are not real data; they appear because tables were joined improperly.

Example
STUDENT COLLEGE

Sid Name City Cid College City

1 Ravi Mysore 10 NIE Mysore
2 Meena Mysore 20 VVCE Mysore

Suppose we JOIN using City: [Link] = [Link]

Result:
Name College
Ravi NIE
Ravi VVCE
Meena NIE
Meena VVCE

Problem:
 Ravi may study only in NIE

 Meena may study only in VVCE

But JOIN created extra false rows.

These false rows are called Spurious Tuples

Main cause for this:

 Poor schema design
 Improper JOIN condition is usually a result of bad design.

Better design:
STUDENT(Sid, Name, Cid)
COLLEGE(Cid, College, city)

Now join on common attribute – Cid generates correct tuples

14.2 Functional Dependencies (FD)

A functional dependency describes how one attribute determines another attribute.

Notation: X→Y

Meaning:
If two rows have same X value, they must also have same Y value.
OR
X uniquely determines Y.

FD is based on the meaning (semantics) of data not merely current table contents.

Example from EMP_PROJ

Ssn Ename Pnumber Pname Hours

101 John 1 ProductX 20

101 John 2 ProductY 10

From semantics:
1. Ssn → Ename - one SSN identifies one employee.
2. Pnumber → Pname - one project number identifies one project.
3. {Ssn,Pnumber}→Hours - hours depend on both employee and project together.

Problem-1

Find all FDs for the below instance –

A B C D
a1 b1 c1 d1
a1 b2 c2 d2
a2 b2 c2 d3
a3 b3 c4 d3
Solution –
B→C
C→B
AB→C
AB→D
CD→B

Problem – 2

Consider the following relation R(A,B,C)

A B C TUPLE#
10 b1 c1 1
10 b2 c2 2
11 b4 c1 3
12 b3 c4 4
13 b1 c1 5
14 b3 c4 6

Determine whether each of the following functional dependencies holds in the given relation instance. If a
dependency does not hold, identify the tuples that violate it.

1. A→B
2. B→C
3. C→B
4. B→A
5. C→A

1. A → B Does NOT hold Tuple 1: A = 10 → B = b1

Tuple 2: A = 10 → B = b2
2. B → C May hold.

3. C → B Does NOT hold. c1 → b1 (tuple 1)

c1 → b4 (tuple 3)
4. B → A Does NOT hold. b1 → 10 (tuple 1)
b1 → 13 (tuple 5)
5. C → A Does NOT hold. c1 → 10 (tuple 1)
c1 → 11 (tuple 3)
c1 → 13 (tuple 5)

14.3 Normal Forms Based on Primary Keys

Normalization is a process of improving database design by organizing relations properly.

Goal:
 reduce redundancy
 remove anomalies
 improve consistency
Main Idea - If a table has problems like repeated data, insertion/deletion/update anomaly then split table it
into smaller better tables. This process is called normalization

Normalization is done step-by-step using rules called Normal Forms

They are:
1. 1NF
2. 2NF
3. 3NF
4. BCNF
5. 4NF
6. 5NF

Higher normal form generally means:

 better design
 less redundancy

Basis of Normalization: Normalization mainly uses Functional Dependencies (FDs)

First Normal Form – 1NF

A relation is in First Normal Form (1NF) if every attribute contains only single atomic values. Does not
allow composite values.

Example NOT in 1NF ::

DEPARTMENT
Dnumber Dname Dlocations
5 Research {Bellaire, Houston, Sugarland}
1 Admin {Stafford}

Problem: Dlocations contains multiple values in one cell.

So table is NOT in 1NF

There are three main techniques to achieve first normal form for such a relation:

a) Method 1 - Remove the multivalued attribute (Dlocations) and create a new relation. The resulting
tables are given below. This decomposes the non-1NF relation into two 1NF relations.

DEPARTMENT DEPT_LOCATIONS

Dnumber Dname Dnumber Dlocation

5 Research 5 Bellaire
1 Administration 5 Houston
5 Sugarland
1 Stafford
 b) Method 2 - Expand the Key - Instead of creating a separate table, create one tuple for each
multivalued value.

Converted Relation - DEPARTMENT

Dnumber Dname Dmgr_ssn Dlocation
5 Research 333445555 Bellaire
5 Research 333445555 Houston
5 Research 333445555 Sugarland
1 Administration 987654321 Stafford

Note - This solution has the disadvantage of introducing redundancy in the relation and hence is rarely
adopted.

c) Method 3 - Create Multiple Atomic Columns

Resulting Table
Dnumber Dname Dlocation1 Dlocation2 Dlocation3
5 Research Bellaire Houston Sugarland
1 Admin Stafford NULL NULL

Note – This is bad because it introduces NULL values, Introduces Spurious tuples, Querying
Becomes Difficult.

Second Normal Form – 2 NF

2NF is based on full functional dependency

Full Functional Dependency –

A dependency: X→Y is called full functional dependency if:
 Y depends on the whole key
 not on part of the key.

Example :

Suppose primary key is: {Ssn, Pnumber}

{Ssn, Pnumber} → Hours is a full dependency

Partial Dependency - Consider {Ssn, Pnumber} → Ename

Ename depends only on part of the key. This is partial dependency

Definition of 2NF
A relation is in 2NF if:
 it is already in 1NF
 every non-prime attribute is fully dependent on the entire primary key.
Non-prime Attribute - an attribute that is not part of any candidate key.
Prime attribute - part of any candidate key

Consider the below schema with THREE FDs –

Primary key: {Ssn, Pnumber}

Functional dependencies –
 FD1 - {Ssn, Pnumber} → Hours – Fully dependent
 FD2 – Ssn → Ename - Partial dependence as Ename depends only on Ssn (part of primary key)
 FD3 – Pnumber → { Pname, Plocation } - Partial dependence as { Pname, Plocation } depends only
on Pnumber.

Hence this relation is not in 2NF.

Convert into 2NF - Decompose relation.

EP1 EP2 EP3

Ssn Pnumber Hours Ssn Ename Pnumber Pname Plocation

This is in 2NF

Simple Intuition - If an attribute depends on only part of a composite key, move it into another table where
that part becomes the full key.

Note - If primary key has only one attribute then partial dependency cannot exist and relation automatically
satisfies 2NF.

Problems on 2NF – check if it is in 2NF, else normalize to 2NF

Consider the following relation: STUDENT_COURSE

StudentId CourseId StudentName CourseName Marks
S1 C1 Ravi DBMS 85
S1 C2 Ravi OS 78
S2 C1 Meena DBMS 92
S3 C2 Arjun OS 88
Assume:
 A student can enroll in many courses.
 A course can have many students.
Functional Dependencies:
o StudentId → StudentName
o CourseId → CourseName
o {StudentId, CourseId} → Marks

Primary Key: {StudentId, CourseId}

Prime attributes:
 StudentId
 CourseId

Non-prime attributes:
 StudentName
 CourseName
 Marks

Check dependency :
StudentId → StudentName Partial dependency
CourseId → CourseName Partial dependency
{StudentId, CourseId} → Marks Full dependency

Now split into 3 tables

STUDENT COURSE ENROLLMENT

StudentId StudentName CourseId CourseName StudentId CourseId Marks

S1 Ravi C1 DBMS S1 C1 85
S2 Meena C2 OS S1 C2 78
S3 Arjun S2 C1 92
S3 C2 88

All resulting relations are in 2NF because all non-prime attributes are fully functionally dependent on their
respective primary keys.

Third Normal Form

A relation is in Third Normal Form (3NF) if:

1. It is already in Second Normal Form (2NF), and
2. No non-prime attribute depends on another non-prime attribute.

That is, there should be no transitive dependency.

A transitive dependency occurs when a non-key attribute depends on another non-key attribute instead of
depending directly on the primary key.
If: A → B and B → C,
then: A → C

This indirect dependency is called a transitive dependency.

Example-1
Consider: Student(s_id, dept_id, dept_name)

Functional dependencies:
o s_id → dept_id
o dept_id → dept_name

So: s_id → dept_name indirectly through dept_id.

Why is this a problem?

Department information gets repeated for every employee in the same department.
This causes redundancy, update anomalies, insertion/deletion problems.
Solution : Convert to 3NF – by Splitting the table into two tables:
o Employee (Ssn, Ename, Dnumber)
o Department (Dnumber, Dname, Dmgr_ssn)

A table is in 3NF if:

i. it is already in 2NF
ii. non-key attributes depend only on the primary key
iii. non-key attributes should not depend on other non-key attributes

Example-2:

BCNF - Boyce-Codd Normal Form

 named after the persons – Raymond Boyce & Edagar Codd
 BCNF is a stronger version of 3NF.
o Every relation in BCNF is also in 3NF
o But every relation in 3NF may not be in BCNF

 Why BCNF Was Needed ?

o 3NF still allows some redundancy in special cases.
 o Specifically, 3NF allows a dependency: X→A even when X is not a super key OR A is a
prime attribute

 BCNF removes this relaxation.

A relation is in BCNF if for every non-trivial functional dependency X→A ; X must be a super key.

Example :
Consider relation: TEACH(Student, Course, Instructor)
Candidate Key - (Student,Course)
Functional dependencies:
o (Student, Course) → Instructor
o Instructor → Course

For the FD : Instructor → Course

FD : Instructor → Course FD : Instructor → Course

It is in 3NF NOT in BCNF

Instructor is not a superkey
BCNF says: Left side must always be a super key
but Course is part of candidate key
Instructor is not a superkey.
So 3NF allows it.
Hence relation is in 3NF. Hence BCNF is violated.

Solution ::
Since BCNF is violated, split the table.
Instructor_Course - (Instructor, Course)
Student_Instructor - (Student, Instructor)

A Multivalued Dependency (MVD) occurs when one attribute determines multiple independent values of
another attribute.

It is represented as: A↠B and is read as: “A multi determines B.”

Example - Consider relation: EMP(Ename, Project, Dependent)

An employee may:
o work on many projects
o have many dependents

Projects and dependents are independent of each other.

Here: Ename ↠ Project

Ename ↠ Dependent
Problem with MVD - The same project and dependent information gets repeated many times, causing
redundancy.

Solution : Decompose into separate relations:

o EMP_PROJECT (Ename, Project)
o EMP_DEPENDENT (Ename, Dependent)

This removes redundancy.

Chapter 21 - Concurrency Control Techniques

21.1 - Two-Phase Locking Techniques for Concurrency Control
21.2 - Concurrency Control Based on Timestamp Ordering

21.1 Two-Phase Locking Techniques for Concurrency Control

Concurrency control is the process of managing simultaneous execution of multiple transactions in a
database so that data consistency and correctness are maintained.

It ensures that concurrent transactions do not interfere with each other and produce incorrect results.
Example
Suppose two transactions access the same bank account having balance ₹10,000.

o Transaction T1- Withdraw ₹2,000

o Transaction T2 - Deposit ₹5,000

Without concurrency control:

T1 reads ₹10,000
T2 reads ₹10,000
T1 writes ₹8,000
T2 writes ₹15,000

Final balance becomes ₹15,000, which is incorrect.

Correct balance should be: 10000−2000+5000=13000

Concurrency control ensures proper coordination so that the final result remains correct.

Serializability – is a property of a schedule that ensures concurrent transactions produce the same result as
some serial execution of those transactions.

A serial schedule means one transaction completes fully before another starts.

Why Serializability is Needed ??

When transactions run concurrently, their operations may interleave.

Serializability ensures that even though execution is concurrent, the final result remains correct.
 Example- Suppose account balance: X=100
Transaction T1 Transaction T2
Adds 50 to X. Multiplies X by 2.

read(X)
read(X)
X = X + 50
write(X) X=X*2
write(X)

Serial executions :
Case 1: T1 followed by T2 Case 2: T2 followed by T1
100+50=150 100×2=200
150×2=300 200+50=250

Final value: X=300 Final value:X=250

Both are valid serial schedules.

Concurrent Schedule - Suppose operations interleave:

T1: read(X=100)
T2: read(X=100)
T1: X = 150
T1: write(150)
T2: X = 200
T2: write(200)

Final value: X=200

This result matches neither: 300 nor 250

Hence this schedule is not serializable.

A concurrent schedule is serializable if its final result is equivalent to some serial execution.

Two-Phase Locking (2PL) – is a concurrency control technique used in DBMS to ensure

serializability when multiple transactions execute simultaneously.

It works using locks on data items.

What is a Lock? - A lock controls access to a database item.

Before accessing data:

o transaction must lock the item
o after use, it unlocks the item

Locks help prevent conflicting operations.

Types of Locks :
1. Shared Lock (Read Lock)
o Used when transaction only reads data.
o Multiple transactions can hold shared locks on same item simultaneously.
Example: read_lock(X)

2. Exclusive Lock (Write Lock)

o Used when transaction updates data.
o Only one transaction can hold it.
o No other transaction can read or write the item.
Example: write_lock(X)

Two-Phase Locking (2PL)

A transaction has two phases:
1. Growing Phase - Transaction can acquire locks but cannot release locks
2. Shrinking Phase - Transaction can release locks but cannot acquire new locks

Main Rule of 2PL - after a transaction releases its first lock, it cannot obtain any new lock.

Example::
Correct 2PL sequence: Incorrect:

lock(X) lock(X)
lock(Y) unlock(X)
read/write lock(Y) ← violates 2PL
unlock(X)
unlock(Y) because new lock is acquired after unlocking.

Types of 2PL :
a) Basic 2PL
b) Conservative 2PL
c) Strict 2PL
d) Rigorous 2PL

a) Basic 2PL - Follows growing and shrinking phases.

b) Conservative 2PL - Locks all required items before transaction starts.

Advantage: deadlock free
Disadvantage: difficult to know all items beforehand

c) Strict 2PL - Keeps all write locks until commit/abort.

Advantage: avoids cascading rollback & most commonly used

d) Rigorous 2PL - Keeps all read and write locks until commit/abort. Stricter than strict 2PL.
Problems with Locking :
 Deadlock - Two transactions wait forever for each other’s locks.
 Starvation - A transaction waits indefinitely because others keep getting priority.

Example :
Basic 2PL Conservative (Static) 2PL Strict 2PL Rigorous 2PL

read_lock(A) read_lock(A) read_lock(A) read_lock(A)

read(A) write_lock(B) read(A) write_lock(B)

write_lock(B) read(A) write_lock(B) read(A)

write(B) write(B) write(B) write(B)

unlock(A) unlock(A) unlock(A) COMMIT

unlock(B) unlock(B)
COMMIT unlock(A)
COMMIT COMMIT unlock(B)
unlock(B)
Note - After first Note - All locks are
unlock: no new lock obtained before execution Note - Write locks held Note -All locks held
can be acquired.
starts. until commit. until commit
Commit may happen Locks can be released
later. before commit.

Comparison :
Type Lock Release Rule
Basic 2PL No new lock after first unlock
Conservative 2PL All locks acquired before start
Strict 2PL Write locks released after commit
Rigorous 2PL All locks released after commit

Timestamp Ordering (TO) - is a concurrency control technique that uses timestamps instead of locks to
maintain serializability.

Core Idea - If older transaction should logically happen before younger transaction, then database
operations must preserve that order.

If any operation violates timestamp order: the violating transaction is aborted and restarted.

Each transaction gets a unique timestamp when it starts.

Example: TS(T1)=1, TS(T2)=2

This means: T1 is older, T2 is younger
The system ensures operations execute in timestamp order.

Main Idea- If TS(T1) < TS(T2) then the schedule should behave as if T1 executed before T2.

Important Features of Timestamp ordering:

o does not use locks
o avoids deadlocks
But transactions may be aborted and restarted.

Timestamps Maintained for Each Data Item X

For every item X, system stores:
o read_TS(X) - Largest timestamp of any transaction that successfully read X.
o write_TS(X) - Largest timestamp of any transaction that successfully wrote X.

Basic Timestamp Ordering Rules :

Read Rule - When transaction T wants to read X: Write Rule - When transaction T wants to write X:

If: write_TS(X) < TS(T) If: read_TS(X) < TS(T) OR write_TS(X) < TS(T)

then: then:
o allow read o allow write
o update read_TS(X) o update write_TS(X)
else else
o a younger transaction already updated X o younger transaction already read/wrote X
o abort T o abort T
endif endif

Advantages : Disadvantages:
o deadlock free o transactions may restart repeatedly
o ensures serializability o starvation may occur
o no locking overhead o cascading rollback possible in basic TO

Thomas’s Write Rule :

If an older transaction tries to write an outdated value, then system may ignore the write instead of aborting
transaction. This reduces unnecessary aborts.

Summary - Timestamp Ordering controls concurrency by executing transactions according to timestamp

order rather than using locks.