Closure of Functional Dependencies

Example: 1
Compute the closure(F+) of the following set functional dependencies for the relation schema
R=(A,B,C,D,E) and F={A->B,C->E,B->D,E->A}. List the candidate keys for R.

Given

Relation schema:
R = (A, B, C, D, E)

Functional Dependencies:
F = {A → B,B → D,C → E,E → A}

Step 1: Compute Closure (F⁺) – Important Derived Dependencies

We derive new dependencies using Armstrong’s axioms.

Given (already in F ⊆ F⁺)

 A→B
 B→D
 C→E
 E→A

Derived using Transitivity

1. From E → A and A → B
⇒E→B
2. From E → B and B → D
⇒E→D
3. From A → B and B → D
⇒A→D
4. From C → E and E → A
⇒C→A
5. From C → A and A → B
⇒C→B
6. From C → B and B → D
⇒C→D
Step 2: List All Important Dependencies in F⁺

�Given

 A→B
 B→D
 C→E
 E→A

�Derived

 A→D
 E→B
 E→D
 C→A
 C→B
 C→D

Final Closure (F⁺)

A → B, A → D
B→D
C → E, C → A, C → B, C → D
E → A, E → B, E → D

�Plus reflexive dependencies like A→A, B→B, etc.

(Usually not written in exams unless asked.)

PART 2: Deep Explanation of Candidate Key

What is a Candidate Key?

A candidate key is:

1. Minimal (no extra attributes)

2. Can determine all attributes in R

Step 1: Compute Attribute Closure

Let’s find C⁺

Start with:
C⁺ = {C}
Now apply FDs:

1. C→E
2. E→A
3. A→B
4. B→D

So:

C⁺ = {C, E, A, B, D} = R

�C determines every attribute in R

2. E⁺

 E→A
 A→B
 B→D

E⁺ = {E, A, B, D}
� Missing C → Not a key

3. A⁺

 A→B
 B→D

A⁺ = {A, B, D}
� Missing C, E → Not a key

4. CE⁺

Since C alone is already a key, CE is not minimal

� Not a candidate key

�Final Answers

Closure (F⁺) includes:

A → B, A → D,
B → D,
C → E, C → A, C → B, C → D,
E → A, E → B, E → D
(along with reflexive dependencies)

Candidate Key(s) for R

Example 2:

Compute the closure of the following set of functional dependencies AB->C, C->D, D->A for
the relation R=(A,B,C,D).Also list the candidate key for R.

Given

Relation:
R = (A, B, C, D)

Functional Dependencies:
F={

1. AB → C
2. C → D
3. D → A
}

Step 1: Compute F⁺ (Closure of F)

1. Start with given FDs

 AB → C
 C→D
 D→A

2. Derive new dependencies using transitivity

Step 1: AB → C → D
  AB → C
 C→D
➡ AB → D

Step 2: AB → D → A

 AB → D
 D→A
➡ AB → A

Step 3: AB → A, AB → B

 Reflexivity: AB → A, AB → B
 Already AB → A derived above

3. Check for other closures

 C → D → A → B?
 C→D→A
 C⁺ = {C, D, A}
 Missing B → C alone is NOT key
 D → A → ??? D⁺ = {D, A} → A → ??? → nothing more

� Important F⁺ dependencies

 AB → C (given)
 AB → D (derived)
 AB → A (derived)
 C → D (given)
 D → A (given)
 Reflexive dependencies like A→A, B→B, etc.

Step 2: Find Candidate Key(s)

A candidate key is a minimal set of attributes that determines all attributes of R.

Step A: Check AB

Compute AB⁺:

1. Start: AB⁺ = {A, B}

2. AB → C → add C → AB⁺ = {A, B, C}
3. C → D → add D → AB⁺ = {A, B, C, D}
� AB⁺ = R →AB is a key

Step B: Check minimality

 Can we remove A? Try B⁺:

o B⁺ = {B} → B alone cannot give C, D, A → � Not a key
 Can we remove B? Try A⁺:
o A⁺ = {A} → A alone cannot give B, C, D → � Not a key

� AB is minimal → AB is a candidate key

Step C: Any other candidate key?

 Check other combinations:

o AC → C → D, D → A → AC⁺ = {A, C, D} → Missing B → �
o AD → D → A → AD⁺ = {A, D} → Missing B, C → �
o BC → C → D → D → A → BC⁺ = {B, C, D, A} = R → BC is also a candidate
key
 Check minimality of BC:
o B⁺ = {B} → �
o C⁺ = {C, D, A} → �
� BC is minimal → BC is another candidate key
 Check CD:
o C⁺ = {C, D, A} → missing B → �
 Check AD:
o Already checked → �

� SoCandidate keys = {AB, BC}

Closure of an Attribute Set

Example 1 (Simple)

Given:

Relation:
R(A, B, C, D)

Functional Dependencies:

 A→B
 B→C
 C→D

Find: A⁺
Step-by-Step Solution:

Step 1:
Start with A

A⁺ = {A}

Step 2:
A → B ⇒ add B

A⁺ = {A, B}

Step 3:
B → C ⇒ add C

A⁺ = {A, B, C}

Step 4:
C → D ⇒ add D

A⁺ = {A, B, C, D}

Final Answer:

A⁺ = {A, B, C, D}

�Since A⁺ contains all attributes, A is a candidate key.

�Example 2 (Multiple Attributes)

Given:

Relation:
R(A, B, C, D)

Functional Dependencies:

 AB → C
 C→D

Find: (AB)⁺

Solution:

Step 1:
(AB)⁺ = {A, B}

Step 2:
AB → C ⇒ add C

(AB)⁺ = {A, B, C}

Step 3:
C → D ⇒ add D

(AB)⁺ = {A, B, C, D}

Final Answer:

(AB)⁺ = {A, B, C, D}

�AB is a candidate key

Canonical Cover

Example 1:

Consider the following functional dependencies over the attribute set R(ABCDE). Find minimal
cover for FD= {AC,ACD,BADE}

Given

Relation:
R(A, B, C, D, E)

Functional Dependencies:

F={A→C, AC→D, B→ADE}

Step 1: Make RHS single attribute

Split B→ADE

B→A, B→D, B→E

Now the FD set becomes:

F1={A→C,AC→D,B→A,B→D,B→E}
�Step 2: Remove extraneous attributes from LHS

Check AC → D and AC

 Check if C is extraneous:

 From A→C, get C

 Now AC→D, get D

So,

A+={A,C,D}

Therefore, C is extraneous

So replace:

AC→D ⇒ A→D

Now FD set:

F2={A→C, A→D, B→A, B→D, B→E}

�Step 3: Remove redundant functional dependencies

Check B → D

 From B→A and A→D:

B→A→D

So B → D is redundant �
Remove it.

Example 2:
Write the algorithm to find the canonical cover. Compute the canonical cover for the following
functional dependencies. R=(A,B,C)F={A->BC,B->C,A->B,AB->C}

Algorithm

1. Split RHS
o Convert each FD so that it has only one attribute on RHS.
2. Remove Extraneous Attributes
o For each FD X→A
 Check if any attribute in X is extraneous by computing closure.
3. Remove Redundant Functional Dependencies
o For each FD X→A
 Remove it temporarily.
4. Combine FDs with Same LHS (optional)
o Merge FDs having same LHS.

The resulting FD set is the Canonical Cover.

Compute Canonical Cover

Given

Relation:

R(A,B,C)

Functional Dependencies:

F={A→BC, B→C, A→B, AB→C}

�Step 1: Convert RHS to Single Attribute

Split A→BC

A→B, A→C

Now FD set becomes:

F1={A→B, A→C, B→C, AB→C}

�Step 2: Remove Extraneous Attributes

�Check AB → C

Check if A is extraneous:
Compute B⁺:

 From B→C

Since C ∈ B⁺,
�A is extraneous

So:

AB→C ⇒ B→C

Now FD set:

F2={A→B, A→C, B→C}

�Step 3: Remove Redundant Functional Dependencies

�Check A → C

Remove A → C temporarily.

Remaining FDs:

{A→B, B→C}

Compute A⁺:

 A→B
 B→C

A+={A,B,C}

Since C ∈ A⁺,
�A → C is redundant �
Remove it.

�Step 4: Final Canonical Cover

NORMALIZATION

 1NF
 2NF
 3NF
 BCNF
 4NF
 5NF

1NF – First Normal Form

Rule:

A relation (table) is in First Normal Form (1NF) if:

✔ Each field contains atomic (indivisible) values

✔ There are no repeating groups or multi-valued attributes
✔ Each record can be uniquely identified (primary key)

�Atomic = cannot be further divided

Why 1NF is Needed

Without 1NF:

 Data becomes difficult to search

 Updating data causes errors
 Repeating values increase redundancy

Table Not in 1NF

STUDENT(StudentID, Name, Phone)

StudentID Name PhoneNumbers

S1 Ravi 9876543210, 9123456789

S2 Anu 9988776655

Problem:
PhoneNumbers contains multiple values → not atomic

Converting to 1NF

Step 1: Split multi-valued attribute

StudentID Name PhoneNumber

S1 Ravi 9876543210

S1 Ravi 9123456789

S2 Anu 9988776655

✔ Each field has single value

✔ No repeating groups
✔ Table is now in 1NF

2NF – Second Normal Form

Rule:

 It is already in First Normal Form (1NF).

 No non-prime attribute is partially dependent on a candidate key

What is Partial Dependency?

Partial dependency occurs when a non-key attribute depends on only ONE PART of a
composite primary key, not the entire key.

This happens only when the primary key has more than one attribute.

Relation:

ENROLLMENT(StudentID, CourseID, StudentName, CourseName, Marks)

Primary Key:

(StudentID, CourseID)

Sample Data:

StudentID CourseID StudentName CourseName Marks

S1 C1 Ravi DBMS 85

S1 C2 Ravi AI 78

S2 C1 Anu DBMS 90
Identify Partial Dependencies

 StudentName depends only on StudentID

 CourseName depends only on CourseID
 Marks depends on (StudentID, CourseID)

So:

StudentID → StudentName
CourseID → CourseName
(StudentID, CourseID) → Marks

Note:
StudentName and CourseName depend on part of the key → Partial dependency exists

Convert to 2NF

Step 1: Remove attributes with partial dependency

Table 1:

STUDENT(StudentID, StudentName)
StudentID StudentName

S1 Ravi

S2 Anu

Table 2:

COURSE(CourseID, CourseName)
CourseID CourseName

C1 DBMS

C2 AI

Table 3:

ENROLLMENT(StudentID, CourseID, Marks)

StudentID CourseID Marks

S1 C1 85

S1 C2 78

S2 C1 90
Now the Tables are in 2NF

✔ No partial dependency
✔ All non-key attributes depend on the entire primary key

3NF – Third Normal Form

Rule:

 Table must be in 2NF

 No transitive dependency
 Non-key attribute should not depend on another non-key attribute

What is Transitive Dependency?

When:

 Primary Key → Non-key attribute

 Non-key attribute → Another non-key attribute

Then the second non-key attribute is transitively dependent on the primary key.

Table NOT in 3NF

EMPLOYEE Table

Primary Key: EmpID

EmpID EmpName DeptID DeptName

E1 Ravi D1 Sales

E2 Anita D2 HR

Functional Dependencies

 EmpID → EmpName, DeptID

 DeptID → DeptName

This is a transitive dependency, so the table is NOT in 3NF.

Converting to 3NF

1. EMPLOYEE Table
EmpID EmpName DeptID

E1 Ravi D1

E2 Anita D2

2. DEPARTMENT Table

DeptID DeptName

D1 Sales

D2 HR

✔ Final Result

 No transitive dependency
 All non-key attributes depend only on the primary key
 Tables are now in 3NF

BCNF – Boyce-Codd Normal Form

Rule:

 Stronger than 3NF

 For every functional dependency A → B, A must be a super key

In simple words:
The left side of every dependency must uniquely identify a row.

Simple Example (NOT in BCNF)

Table:

CLASS(StudentID, Course, Instructor)

Assumptions:

 A student can take many courses

 Each course is taught by one instructor

Functional Dependencies:

(StudentID, Course) → Instructor

Course → Instructor
Candidate Keys:

(StudentID, Course)

Why This Table Is NOT in BCNF

Sample Data:

StudentID Course Instructor

S1 DBMS Prof.A
S1 AI Prof.B
S2 DBMS Prof.A

Look at:

Step 1: Check uniqueness of attributes

 StudentID �
o S1 appears more than once → not unique
 Course �
o DBMS appears more than once → not unique
 Instructor �
o Prof.A appears more than once → not unique

So, no single attribute can uniquely identify a row.

Step 2: Check combinations of attributes

 {StudentID, Course} �
o Each combination is unique
o Example: (S1, DBMS), (S1, AI), (S2, DBMS)
 {StudentID, Instructor} �
o (S1, Prof.A) could repeat in future
 {Course, Instructor} �
o DBMS–Prof.A appears for multiple students

✅Super Keys

A super key is any attribute set that uniquely identifies a row.

✔ Super Keys here are:

 {StudentID, Course}
 {StudentID, Course, Instructor} (has extra attribute but still unique)
Convert to BCNF

Step 1: Split the table

Table 1:

COURSE_INSTRUCTOR(Course, Instructor)

Course Instructor

DBMS Prof. A

AI Prof. B

Table 2:

STUDENT_COURSE(StudentID, Course)
StudentID Course

S1 DBMS

S1 AI

S2 DBMS

Now Both Tables Are in BCNF

✔ Every determinant is a super key

✔ No redundancy
✔ No anomalies

4NF – Fourth Normal Form

Rule:

 It is already in Boyce–Codd Normal Form (BCNF).

 It has no non-trivial multivalued dependencies
 A table should not store two or more independent multivalued facts about the same
entity in one table.

Example:

Table is NOT in 4NF

Relation:
STUDENT(StudentID, Course, Hobby)

Sample Data:

StudentID Course Hobby

S1 DBMS Cricket

S1 DBMS Music

S1 AI Cricket

S1 AI Music

 One student can take multiple courses

 One student can have multiple hobbies
 Courses and hobbies are independent

So we have:

StudentID →→ Course
StudentID →→ Hobby

This is a multivalued dependency �

So the table is NOT in 4NF

Problems in this Table

� Data redundancy
� Insertion anomalies
� Deletion anomalies

Because:

 If student drops a hobby, course data may be affected

Converting to 4NF (Decomposition)

Split the table into two relations:

Table 1:

STUDENT_COURSE(StudentID, Course)
StudentID Course

S1 DBMS
StudentID Course

S1 AI

Table 2:

STUDENT_HOBBY(StudentID, Hobby)
StudentID Hobby

S1 Cricket

S1 Music

Now the Tables are in 4NF

✔ No multivalued dependency
✔ No redundancy
✔ Clean and efficient design

5NF – Fifth Normal Form

Rule:

 Table must be in 4NF

 It is already in 4NF
 Every join dependency is implied by candidate keys
 The table should be broken down as much as possible, but still allow correct
reconstruction using joins without adding false data.

Why Do We Need 5NF?

5NF is required when:

 Information can be reconstructed only by joining 3 or more tables

 There is no single functional or multivalued dependency
 Still, redundancy exists due to join dependency

Key Concept: Join Dependency (JD)

A join dependency exists when a table can be reconstructed only by joining multiple smaller
tables.

Notation: JD(R1, R2, R3)

Key Concept: Join Dependency (JD)

A join dependency exists when a table can be reconstructed only by joining multiple smaller
tables.

Notation:

JD(R1, R2, R3)

Example (NOT in 5NF)

Relation:

SUPPLY(Supplier, Part, Project)

Meaning:

 A supplier supplies certain parts

 A part is used in certain projects
 A supplier works on certain projects

Assume:

 Supplier supplies part

 Supplier works on project
 Part is used in project

But no direct functional dependency exists.

Sample Data:

Supplier Part Project

S1 P1 J1

S1 P2 J1

S2 P1 J1

Note:

This table looks normalized, but it has hidden redundancy.

The relationship depends on three attributes together, not two.

Convert/Decomposition into 5NF

Split into three tables:

Table 1:
SUPPLIER_PART(Supplier, Part)
Supplier Part

S1 P1

S1 P2

S2 P1

Table 2:

SUPPLIER_PROJECT(Supplier, Project)
Supplier Project

S1 J1

S2 J1

Table 3:

PART_PROJECT(Part, Project)
Part Project

P1 J1

P2 J1

Why This is 5NF?

✔ No functional dependency
✔ No multivalued dependency
✔ No further lossless decomposition possible
✔ Join dependency is based on candidate keys only

When we join all three tables, we get the original data without extra (spurious) tuples.

Quick Summary Table

Normal Form Removes

1NF Multivalued attributes
2NF Partial dependency
3NF Transitive dependency
BCNF Weak determinants
4NF Multivalued dependency
5NF Join dependency