DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CST 204 - Database Management Systems

Prof. Smitha Jacob, Prof. Sarju S

17 March 2025
CST 204 - Database Management Systems

[Link]

Page 2
 MODULE 4

Page 3
 Module 4

► Different anomalies in designing a database, The idea of normalization, Functional

dependency, Armstrong’s Axioms (proofs not required), Closures and their computation,
Equivalence of Functional Dependencies (FD), Minimal Cover (proofs not required).
► First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), Boyce Codd
Normal Form (BCNF), Lossless join and dependency preserving decomposition, Algorithms
for checking Lossless Join (LJ) and Dependency Preserving (DP) properties.

Page 4 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Different anomalies in designing a database

Page 5
 Redundancy

► Redundancy
► Data redundancy is a condition created within a database or data storage
technology in which the same piece of data is held in two separate places.
► Row-level redundancy
► We can solve it by making SID a primary Key

SID Sname Age

1 Ram 24
2 Varun 25
1 Ram 24

Page 6 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Redundancy

SID Sname CID Cname FID Fname Salary

1 Ram C1 DBMS F1 John 30000
2 Ravi C2 JAVA F2 Bob 40000
3 Nithin C1 DBMS F1 John 30000
4 Amrit C1 DBMS F1 John 30000

► Column level redundancy

► insertion, deletion and updation anomalies

Page 7 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Redundancy

► Column level redundancy

► insertion, deletion and updation anomalies

Page 8 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Database Anomalies

Page 9 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Insertion anomaly:

► An Insertion Anomaly occurs when attributes cannot be inserted into the database without the presence of other
attributes. Usually when a child is inserted without a parent.
► Jerry is a new Student with department id 6. There is no Department with this Dept_ID 6. Hence, the anomaly. The usual
behavior should be a new department id with 6 and only then Student could have it.
► An insertion anomaly is the inability to add data to the database due to the absence of other data

Page 10 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Updation anomaly:

► When duplicated data is updated at one instance and not across all instances where it was
duplicated. That’s an update anomaly.
► See below English department has now Dept_ID 8, but unfortunately it was not updated in the
Student table.

Page 11 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Deletion anomaly:

► A deletion anomaly is the unintended loss of data due to the deletion of other data.
► If someone decides to delete the Computer Science department, he may end up deleting all
student data who had the Department of Computer Science.
► So to say deletion of some attribute which causes deletion of other attributes is deletion
anomaly.

Page 12 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 NORMALISATION &FUNCTIONAL DEPENDENCIES

Page 13
 Functional Dependency

► A functional dependency is a constraint between two sets of attributes from the database.
► Suppose that our relational database schema has n attributes A1, A2, ...,An;
► let us think of the whole database as being described by a single universal relation schema R =
{A1, A2, ... , An}.
► Definition. A functional dependency, denoted by X → Y, between two sets of attributes X and Y
that are subsets of R specifies a constraint on the possible tuples that can form a relation state r
of R.

Page 14 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► Y component of a tuple in R depends on, or is determined by, the values of the X component;
► alternatively, the values of the X component of a tuple uniquely (or functionally) determine the
values of the Y component.
► We also say there is a functional dependency from X to Y(X determines Y), or Y is functionally
dependent on X.
► The abbreviation for functional dependency is FD or f.d.
► The set of attributes X is called the left-hand side of the FD, and Y is called the right-hand side.

Page 15 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► Consider the relation schema EMP_PROJ in Figure; from the semantics of the attributes and the
relation, we know that the following functional dependencies should hold:
► Ssn→Ename [FD2]
► Pnumber →{Pname, Plocation}[FD3]
► {Ssn, Pnumber}→Hours [FD1]

Page 17 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► Ssn→Ename
► Pnumber →{Pname, Plocation}
► {Ssn, Pnumber}→Hours
► The value of an employee’s Social Security number (Ssn) uniquely determines the employee
name (Ename)
► The value of a project’s number (Pnumber) uniquely determines the project name (Pname) and
location (Plocation)
► A combination of Ssn and Pnumber values uniquely determines the number of hours the
employee currently works on the project per week (Hours).

Page 18 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► From the table we can conclude some valid functional adm_no name
dept_na
me
dept_buil
ding
dependencies: 19CS042 abc CS A4

► adm_no → { name, dept_name, dept_building },→ Here, 20IT043 pqr IT A3

adm_no can determine values of fields name, dept_name and 19CS044 xyz CS A4
dept_building, hence a valid Functional dependency 21IT045 xyz IT A3
► adm_no → dept_name , Since, adm_no can determine whole 20EC046 mno EC B2
set of {name, dept_name, dept_building}, it can determine its 20ME117 jkl ME B2
subset dept_name also.

Page 19 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency
► From the table we can conclude some valid functional
dependencies:
► dept_name → dept_building , dept_name can identify the adm_no name
dept_na dept_buil
me ding
dept_building accurately, since departments with different
dept_name will also have a different dept_building
19CS042 abc CS A4

20IT043 pqr IT A3

19CS044 xyz CS A4

21IT045 xyz IT A3
► More valid functional dependencies: 20EC046 mno EC B2
adm_no→name,
20ME117 jkl ME B2
{adm_no,name}⇢{dept_name,dept_building}

Page 20 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► Here are some invalid functional dependencies:

► name → dept_name
► Students with the same name can have different dept_name, hence adm_no name dept_name dept_building
this is not a valid functional dependency. [xyz=xyz,but CS#AD]
► dept_building → dept_name 19CS042 abc CS DBIII

► There can be multiple departments in the same building, For example,20IT043 pqr AD DBII

in the above table departments ME and AD are in the same building B2,
19CS044 xyz CS DBIII
hence dept_building → dept_name is an invalid functional
21IT045 xyz AD DBII
dependency.
[B2=B2,But EC#AD] 20EC046 mno EC DBII

► More invalid functional dependencies: 20ME117 jkl ME DB1

name → adm_no,
{name, dept_name} → roll_no,
dept_building→ roll_no, etc.

Page 21 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Inference Rules or Axioms

Page 22
 Inference rules or axioms

1. Armstrong's axioms are basic inference rules used to

conclude functional dependencies on the relational database.

2. An inference rule asserts that a user can apply to a set of

functional dependencies to derive other FD (functional
dependencies).

3. William w. Armstrong developed these axioms in the database

management system in 1974.

Page 23 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Inference rules or axioms

Page 24 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Inference rules or axioms

Page 25 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency

► Armstrong’s axioms/properties of functional roll_no name

dept_na dept_buil
me ding
dependencies:
42 abc CO A4
1. Reflexivity: If Y is a subset of X, then X→Y holds
43 pqr IT A3
by reflexivity rule
44 xyz CO A4
► For example, {roll_no, name} → name is valid.
45 xyz IT A3
2. Augmentation: 46 mno EC B2
If X → Y is a valid dependency, then XZ → YZ
47 jkl ME B2
is also valid by the augmentation rule.
► For example, If {roll_no, name} → dept_building is valid, hence
{roll_no, name, dept_name} → {dept_building,dept_name} is also valid.

Page 26 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Functional Dependency
dept_na dept_buil
roll_no name
me ding
► Armstrong’s axioms/properties of functional dependencies:
42 abc CO A4
3. Transitivity: If X → Y and Y → Z are both valid dependencies, 43 pqr IT A3
then X→Z is also valid by the Transitivity rule.
44 xyz CO A4
► For example, roll_no → dept_name &
45 xyz IT A3
dept_name → dept_building, then 46 mno EC B2
roll_no → dept_building is also valid. 47 jkl ME B2

Page 27 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Types of Functional dependencies in DBMS:

► Trivial functional dependency

► Non-Trivial functional dependency
► Multivalued functional dependency
► Transitive functional dependency

Page 28 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Trivial Functional Dependency

► In Trivial Functional Dependency, a dependent is always a

subset of the determinant. roll_no name age

42 abc 17
► i.e. If X → Y and Y is the subset of X, then it is called trivial
functional dependency 43 pqr 18

44 xyz 18
► Here, {roll_no, name} → name is a trivial functional
dependency, since the dependent name is a subset
of determinant set {roll_no, name}
► Similarly, roll_no → roll_no is also an example of
trivial functional dependency.

Page 29 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Non-trivial Functional Dependency

► In Non-trivial functional dependency, the dependent is strictly not a

subset of the determinant. roll_no name age
► i.e. If X → Y and Y is not a subset of X, then it is called Non-trivial 42 abc 17

functional dependency. 43 pqr 18

► Here, roll_no → name is a non-trivial functional dependency since the 44 xyz 18
dependent name is not a subset of determinant roll_no
► Similarly, {roll_no, name} → age is also a non-trivial functional dependency
since age is not a subset of {roll_no, name}

Page 30 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Multivalued Functional Dependency

► In Multivalued functional dependency, entities of the dependent roll_no name age

set are not dependent on each other. 42 abc 17

► i.e. If a → {b, c} and there exists no functional dependency 43 pqr 18

between b and c, then it is called a multivalued functional 44 xyz 18

dependency. 45 abc 19
► Here, roll_no → {name, age} is a multivalued functional dependency,
since the dependents name & age are not dependent on each other(i.e.
name → age or age → name doesn’t exist !)

Page 31 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Transitive Functional Dependency

► In transitive functional dependency, dependent is indirectly

dependent on determinant.
enrol_no name dept building_no
► i.e. If a → b & b → c, then according to axiom of 42 Abc CO 4
transitivity, a → c. This is a transitive functional 43 Pqr EC 2
dependency
44 xyz IT 1
► Here, enrol_no → dept and dept → building_no,
45 abc EC 2
► Hence, according to the axiom of transitivity, enrol_no →
building_no is a valid functional dependency. This is an indirect
functional dependency, hence called Transitive functional
dependency.

Page 32 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 KEYS IN DBMS

Page 33
 Keys in DBMS

► Keys play an important role in the relational database.

► It is used to uniquely identify any record or row of data from the table.
► It is also used to establish and identify relationships between tables.

Page 34 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Keys in DBMS

Page 35 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Primary Key and Foreign key in DBMS

Page 36 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Primary Key in DBMS

► It is the first key used to identify one and only one instance of
an entity uniquely.
► An entity can contain multiple keys, as we saw in the PERSON
table. The key which is most suitable from those lists
becomes a primary key.
► In the EMPLOYEE table, ID can be the primary key since it is
unique for each employee. In the EMPLOYEE table, we can
even select License_Number and Passport_Number as
primary keys since they are also unique.
► For each entity, the primary key selection is based on
requirements and developers.

Page 37 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Foreign key in DBMS
► A FOREIGN KEY is a field (or collection of fields) in one table, that refers to the PRIMARY KEY in
another table
► We add the primary key of the DEPARTMENT table, Department_Id, as a new attribute in the
EMPLOYEE [Link] the EMPLOYEE table, Department_Id is the foreign key, and both the
tables are related.

Page 38 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Super Keys in DBMS

► Super key is an attribute set that can uniquely identify a tuple.

► A super key is a superset of a candidate key.
► For example: In the above EMPLOYEE table, for(EMPLOEE_ID, EMPLOYEE_NAME), the name of two
employees can be the same, but their EMPLYEE_ID can't be the same. Hence, this combination can also
be a key.

Page 39 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Super Key in DBMS

► Super key is an attribute set that can uniquely identify a tuple.

► A super key is a superset of a candidate key.

Page 40 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Candidate Keys in DBMS

► A candidate key is an attribute or set of attributes that can uniquely identify a tuple.
► Except for the primary key, the remaining attributes are considered a candidate key.
The candidate keys are as strong as the primary key.
► For example:
► In the EMPLOYEE table, id is best suited for the primary key. The rest of the attributes,
like SSN, Passport_Number, License_Number, etc., are considered a candidate key.

Page 41 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Candidate Keys in DBMS

Page 42 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Composite Keys in DBMS

► Whenever a primary key consists of more than one

attribute, it is known as a composite key. This key is also
known as Concatenated Key.
► For example, in employee relations, we assume that an
employee may be assigned multiple roles, and an
employee may work on multiple projects simultaneously.
► So the primary key will be composed of all three attributes,
namely Emp_ID, Emp_role, and Proj_ID in combination.
So these attributes act as a composite key since the
primary key comprises more than one attribute.

Page 43 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Surrogate Keys in DBMS

► The key created using arbitrarily assigned data are known as surrogate/ artificial keys.
► These keys are created when a primary key is large and complex and has no relationship with
many other relations.
► The data values of the artificial keys are usually numbered in a serial order.
► For example, the primary key, which is composed of Emp_ID, Emp_role, and Proj_ID, is large in
employee relations. So it would be better to add a new virtual attribute to identify each tuple in the
relation uniquely.

Page 44 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Surrogate Keys in DBMS

Page 45 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 NORMALISATION

Page 46
 NORMALISATION

Page 47 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 NORMALISATION

► Normalization is the process of minimizing redundancy from a relation or set of relations

► It helps to minimize the redundancy in relations, hence avoids anomalies.
► Normalization rules divides larger tables into smaller tables and links them using relationships.
► The inventor of the relational model Edgar Codd proposed the theory of normalization of data
with the introduction of the First Normal Form, and he continued to extend theory with Second
and Third Normal Form.
► Later he joined Raymond F. Boyce to develop the theory of Boyce-Codd Normal Form.

Page 48 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 NORMALISATION

Page 49 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 NORMALISATION

Page 50 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Database Normal Forms

► 1NF (First Normal Form)

► 2NF (Second Normal Form)
► 3NF (Third Normal Form)
► BCNF (Boyce-Codd Normal Form)

Page 51 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Database Normal Forms

Page 52 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 1NF (First Normal Form)

Page 53 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 1NF (First Normal Form)

Page 54 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 1NF (First Normal Form)

► 1 NF form

► Each table cell should contain a single value.

► Each record needs to be unique.
Page 55 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

Page 56 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

► In the 2NF, relational must be in 1NF.

► Every non-prime attribute should be fully functionally dependent on the prime key
attribute.

► Prime attribute − An attribute, which is a part of the primary key, is known as a

prime attribute.
► Non-prime attribute − An attribute, which is not a part of the primary key, is said
to be a non-prime attribute.

Page 57 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

► Student_Project relation that the prime key attributes are Stu_ID and Proj_ID.
► According to the rule, non-key attributes, i.e. Stu_Name and Proj_Name must be dependent upon both and not on
any of the prime key attribute individually.
► But we find that Stu_Name can be identified by Stu_ID and Proj_Name can be identified by Proj_ID independently.
► This is called partial dependency, which is not allowed in Second Normal Form.

Page 58 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

► The relation is divided in to two as shown in the picture. So there exists no partial dependency.

Page 59 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

In the 2NF, relational

must be in 1NF.
Every non-prime
attribute should be
fully functionally
dependent on the
prime key attribute.

Page 60 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

Page 61 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

Page 62 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

Page 63 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 2NF (Second Normal Form)

Page 64 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 65 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

► Definition 1:
A relation is in third normal form, if there is no transitive dependency for non-prime
attributes as well as it is in second normal form.
► The reason for the transitive dependency is the dependency between two non prime
attributes NPANPA
► Definition 2:

► A relation is in 3NF if at least one of the following condition holds in every non-trivial
function dependency X –> Y:
► X is a super key.
► Y is a prime attribute (each element of Y is part of some candidate key).

Page 66 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

X Y Z

► XY,YZ THEN XZ

► The reason for the transitive dependency is the dependency between two non prime attributes
NPANPA [Not allowed in 3NF] (ZipCity)
► Stu_ID is the key and only prime key attribute.
► We find that City can be identified by Stu_ID as well as Zip itself.
► Neither Zip is a superkey nor City is a prime attribute.

Page 67 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

► Break the relation into two relations as shown in the figure.

Page 68 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

► FD − {rollno -> game,

rollno -> feestructure, game -> fee}
► Rollno+= {rollno, game, feestructure}
► => rollno is primary key
► The above student table is in 1NF because there are
no multivalue attributes.
► Student table is also in 2NF because all non-key
attributes are fully functional and dependent on the
primary key (rollno).
► But the table is not in 3NF because there is transitive
dependency i.e. game-> feestructure.

Page 69 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

► If X->Y is transitive dependency then divide R into

R1(X+) and R2(R-Y+).
► Game->feestructure is a transitive dependency [since
neither game is a key nor fee is a key attribute,
NPANPA [Not allowed in 3NF] ]
► So divide the student table into
R1(game, feestructure) and
R2 (rollno, game).

Page 70 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

FD set:
{STUD_NO -> STUD_NAME, STUD_NO -> STUD_STATE, STUD_STATE -> STUD_COUNTRY,
STUD_NO -> STUD_AGE}
Primary Key:
{STUD_NO}
STUD_NO -> STUD_STATE and STUD_STATE -> STUD_COUNTRY are true. X
So STUD_COUNTRY is transitively dependent on STUD_NO NOT ALLOWED

To convert it in third normal form, we will decompose the relation

STUDENT (STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE, STUD_COUNTRY_STUD_AGE)
as:

Page 71 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 72 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 73 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 74 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 75 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Third Normal Form

Page 76 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

Page 77 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

► BCNF is the advanced version of 3NF.

► It is stricter than 3NF.
► A table is in BCNF if every functional dependency X → Y, X is the super key of the table.
► For BCNF, the table should be in 3NF, and for every FD, LHS is super key.
► A relation is in BCNF iff, X is a superkey for every functional dependency (FD)

Page 78 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

► Boyce-Codd Normal Form (BCNF) is an extension of Third Normal Form on strict terms. BCNF states
that
► For any non-trivial functional dependency, X → Y, X must be a super-key.

► Stu_ID is the super-key in the relation Student_Detail and Zip is

the super-key in the relation ZipCodes.
► Stu_ID → Stu_Name, Zip

and
► Zip → City

► Which confirms that both the relations are in BCNF.

Page 79 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

► One student can enroll for multiple subjects.

► For each subject, a professor is assigned to the [Link] can be multiple professors teaching one subject.
► Primary Key: student_id, subject together form the primary key
► one professor teaches only one subject, but one subject may have two different professors.

Page 80 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

► This table satisfies the 1st Normal form because all the values are atomic, column names are unique and Pk
exists to identify a tuple.
► This table also satisfies the 2nd Normal Form as there is no Partial Dependency.
► And, there is no Transitive Dependency, hence the table also satisfies the 3rd Normal Form. But this table is
not in Boyce-Codd Normal Form.
Page 81 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

BCNF, the
table
should be
in 3NF, and
for every
FD, LHS is
super key.

► Why this table is not in BCNF?

► In the table above, student_id, subject form primary key, which means subject column is a prime
[Link], there is one more dependency,
professor → subject.
► And while subject is a prime attribute, professor is a non-prime attribute, which is not allowed by
BCNF.
Page 82 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form
► How to satisfy BCNF?
► To make this relation(table) satisfy BCNF, we will decompose this table into two tables, the student
table and the professor table.
► Below we have the structure for both tables.
► Student Table

► And, Professor Table

Page 83 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

Page 84 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Boyce-Codd Normal Form

The table is not in BCNF because neither

EMP_DEPT_NO nor EMP_ID alone are keys. EMP_ID → EMP_COUNTRY
To convert the given table into BCNF, we EMP_DEPT_NO→ {EMP_DEPT,DEPT_TYPE}
decompose it into three tables:

Page 85 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization into 1NF

► Dnumber is primary key field..

Redundancy will not be allowed.
So make it into separate tables to
main 1NF

Page 87 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization into 1NF

Page 88 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization into 2NF

► Using Pnumber prime attribute we

can determine Pname and

plocation(FD3).same for FD2,FD1.

PD

► we don’t need ssn for [Link] their

PD
exists partial Dependency.

► Remove it by splitting the fields into

new tables,

Page 89 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization into 3NF

NPANPA

► SsnDnumber and DnumberDname then SsnDname makes a

transitive dependency and remove it by splitting it into separate tables

Page 90 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization - Summary

Page 91 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normalization - Summary

Page 92 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Module 4

► Different anomalies in designing a database, The idea of normalization, Functional

dependency, Armstrong’s Axioms (proofs not required), Closures and their computation,
Equivalence of Functional Dependencies (FD), Minimal Cover (proofs not required).
► First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), Boyce Codd
Normal Form (BCNF), Lossless join and dependency preserving decomposition, Algorithms
for checking Lossless Join (LJ) and Dependency Preserving (DP) properties.

Page 93 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 CLOSURES OF FUNCTIONAL DEPENDENCIES

Page 94
 Closure of Functional Dependency

Page 95 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure

Page 96
 Closure of Attributes

Page 97 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure

► Closure of an Attribute can be defined as a set of attributes that can be functionally determined
from it.
► Closure of a set F of FDs is the set F+ of all FDs that can be inferred from F
► Closure of an attribute X is the set of all attributes that are functional
dependent on X with respect to F.
► It is denoted by X+ which means what X can determine.
Algorithm
Let’s see the algorithm to compute X+
Step 1 − X+ =X
Step 2 − repeat until X+ does not change
For each FD Y->Z in F
If Y ⊆ X+ then X+ = X+ U Z
Page 98 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure - Example

► We are given the relation R(A, B, C, D, E). This means that the table R has five columns: A, B, C,
D, and E. We are also given the set of functional dependencies: {A->B, B->C, C->D, D->E}. What
is {A}+?
► First, we add A to {A}+.
► What columns can be determined given A? We have A -> B, so we can determine B. Therefore, {A}+ is now {A, B}.
► What columns can be determined given A and B? We have B -> C in the functional dependencies, so we can
determine C. Therefore, {A}+ is now {A, B, C}.
► Now, we have A, B, and C. What other columns can we determine? Well, we have C -> D, so we can add D to
{A}+.
► Now, we have A, B, C, and D. Can we add anything else to it? Yes, since D -> E, we can add E to {A}+.
► We have used all of the columns in R and we have all used all functional dependencies. {A}+ = {A, B, C, D, E}.

Page 99 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure - The Algorithm

► The procedure shown in the previous example can be generalized to an algorithm. Assume we
are given the set of functional dependencies FD and a set of attributes X. The algorithm is as
follows:
1. Add the attributes contained in the attribute set X to the result set X+.
2. Add the attributes to the result set X+ which can be functionally determined from the attributes already
contained in the result set.
3. Repeat step 2 until no more attributes can be added to the result set X+.

Page 100 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Closure of Attributes -Example

Page 101 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Closure of Attributes -Example

► {Q,R} Will be considered for finding closure T

► {Q,R,T} will be considered for finding closure S
,QR,RT,QT,QS,RS,TS etc may be considered
► {Q,R,T,S} may be considered to find U

Page 102 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Closure of Attributes -Example

Page 103 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 2

► Consider a relation R ( A , B , C , D , E , F , G ) with the functional dependencies- A → BC, BC →

DE, D → F, CF → G . Find A+,D+, BC+

Closure of attribute A-

A+ = { A }
= { A , B , C } ( Using A → BC )
= { A , B , C , D , E } ( Using BC → DE )
= { A , B , C , D , E , F } ( Using D → F )
= { A , B , C , D , E , F , G } ( Using CF → G )
Thus,
A+ = { A , B , C , D , E , F , G }

Page 104 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 2

► Consider a relation R ( A , B , C , D , E , F , G ) with the functional dependencies- A → BC, BC →

DE, D → F, CF → G

Closure of attribute D-

D+ = { D }
= { D , F } ( Using D → F )
We can not determine any other attribute using attributes D and F contained in the result set. Thus,
D+ = { D , F }

Page 105 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 2

► Consider a relation R ( A , B , C , D , E , F , G ) with the functional dependencies- A → BC, BC →

DE, D → F, CF → G

Closure of attribute set {B, C}-

{ B , C }+ = { B , C }
= { B , C , D , E } ( Using BC → DE )
= { B , C , D , E , F } ( Using D → F )
= { B , C , D , E , F , G } ( Using CF → G )
Thus,
{ B , C }+ = { B , C , D , E , F , G }

Page 106 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Closure of Attributes -Example

1. A+ = { A , B , C , D , E , F , G }
2. D+ = { D , F }
3. { B , C }+ = { B , C , D , E , F , G }

Here A+ Contain all other set of attributes ,A Can be considered for super key

Page 107 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure - Example

► Let’s look at another example. We are given R(A, B, C, D, E, F). The functional dependencies are
{AB->C, BC->AD, D->E, CF->B}. What is {A,B}+?
► We start with {A, B}.
► What columns can we determine, given A and B? We have AB -> C, so we can add C to {A, B}+.
► We now have A, B, and C. What other columns can we determine? We have BC -> AD. We already have A in {A,
B}+, so we can add D.
► So, we now have A, B, C, and D. What else can we add? We have D -> E, so we can add E to {A, B}+.
► Now {A, B}+ is {A, B, C, D, E}. Can we add anything else? No. We have one more functional dependency in our set
that we did not use: CF -> B. We can’t use this dependency because F is not in {A, B}+.
► Thus, {A, B}+ is {A, B, C, D, E}.

Page 108 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 4

► We are given R(A, B, C, D, E, F). The functional dependencies are

{AB->C, BC->AD, D->E, CF->B}. What is {A,B}+?

Closure of attribute set {A, B}-

{ A , B }+ = { A , B }
= { A, B , C } ( Using AB → C )
= { A, B , C , D } ( Using BC → AD)
= { A,B , C , D , E } ( Using D → E )
Thus,
{ A, B}+ = {A, B , C , D , E }

Page 109 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 5

► Problem: Consider a relation R ( A , B , C , D , E , F , G ) with the functional dependencies- A →

BC, BC → DE, D → F, CF → G . Find A+

A+ = { A }

= { A , B , C } ( Using A → BC )

= { A , B , C , D , E } ( Using BC → DE )

= { A , B , C , D , E , F } ( Using D → F )

= { A , B , C , D , E , F , G } ( Using CF → G )

Page 110 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Finding the Keys Using Closure-

► Super Key-
► If the closure result of an attribute set contains all the attributes of the relation, then that
attribute set is called as a super key of that relation.
► Consider a relation R ( A , B , C , D , E , F , G ) and
A+ = { A , B , C , D , E , F , G }.
► Thus, attribute A is a super key for that relation.

Page 111 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – to find candidate Keys

Page 112 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 5

Page 113 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure – Example 5

Page 114 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure - Example

► Here are the functional dependencies in this table:

► course, year -> teacher
► Given the course and year, you can determine the teacher who taught the course that year.
► teacher -> date_of_birth
► Given a teacher, you can determine the teacher’s date of birth
► year, date_of_birth -> age
► Given the year and date of birth, you can determine the age of the teacher at the time the course was taught.

Page 115 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Attribute Closure - Example

► course, year -> teacher

► teacher -> date_of_birth
► year, date_of_birth -> age
► Attribute Closures
► closure of a set {year}, denoted {year}+
► {year}+ contains only one column, year, that is {year}+ = {year}.
► {year, teacher}+
► teacher -> date_of_birth functional dependency. So, date_of_birth is also in {year, teacher}+, and I know three
columns: {year, teacher, date_of_birth}.
► Age can be determined by the year and date of birth Now, {year, teacher}+ has four columns
{year, teacher, date_of_birth, age}.
► can’t use the remaining dependency, course, year -> teacher because I don’t know the course.
► {year, teacher}+ = {year, teacher, date_of_birth, age}.

Page 116 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Practice Question -closure

Page 117 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 EQUIVALENCE OF FUNCTIONAL DEPENDENCIES

Page 118
 Equivalence of Functional Dependency

Page 119 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency

Page 120 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency

Page 121 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency

Page 122 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency

► To get  AD from S1 , AB,AA then AAB (1,5 Union)

Page 123 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency contd..

Page 124 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency

Page 125 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency –Example 2

Page 126 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency –Example 3

Page 127 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency –Example 3

► We need EAH, EA,EH THEN EAH ► AC,AD THEN ACD

But EAD,EA,ED AC given AA then AAC
4.EH, EA Implies EAH A AC ,ACD THEN A D
Page 128 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency –Example 3

► G covers F, so F and G are functionally Equivalent

Page 129 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Equivalence of Functional Dependency –Example 4

Page 130 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover

Page 131
 Minimal Cover

► A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin

that is equivalent to F.
► Simple properties/steps of minimal cover:
► 1. The Right-Hand Side (RHS) of all FDs should be a single attribute.
► 2. Remove extraneous attributes of L.H.S.
► 3. Eliminate redundant functional dependencies.

Page 132 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover

► BD, DA THEN BA, So remove

BA, as it is redundant

Page 133 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover-Question1

Page 134 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover

Page 135 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover-question2

Page 136 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover-univ question

Page 137 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover-univ question

Page 138 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover-question 4

Page 139 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Minimal Cover

Page 140 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Finding Attribute Closure and Candidate Keys using Functional
Dependencies

Page 142
 Find all the possible candidate keys

► We are given the relation R(A, B, C, D, E). This means that the table R has five columns: A, B, C,
D, and E. We are also given the set of functional dependencies: {A->B, BC->D, E->C, D->A}. Find
all the possible candidate keys?

Step-01:

 Determine all essential attributes of the given relation.(here it is E)

 Essential attributes are those attributes which are not present on RHS of any functional
dependency.
 Essential attributes are always a part of every candidate key.
 This is because they can not be determined by other attributes.
 Essential attributes of the relation is E.

Page 143 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Find all the possible candidate keys

► We are given the relation R(A, B, C, D, E). This means that the table R has five columns: A, B, C,
D, and E. We are also given the set of functional dependencies: {A->B, BC->D, E->C, D->A}. Find
all the possible candidate keys?

Step-02:

 Find E+
 E+ = { E }
= { E,C} ( Using E → C )
Thus, E alone can’t be a candidate key
 So, attribute E will definitely be a part of every candidate key.

Page 144 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Find all the possible candidate keys

► We are given the relation R(A, B, C, D, E). This means that the table R has five columns: A, B, C,
D, and E. We are also given the set of functional dependencies: {A->B, BC->D, E->C, D->A}. Find
all the possible candidate keys?

Step-02: Step-02:

 Find AE+  Find BE+

 AE+ = { A,E }  BE+ = { B,E }
= { A,E,B} ( Using A → B ) = { B,E,C } ( Using E → C )
= { A,E,B,C} ( Using E → C) = { B,E,C,D } ( Using BC → D )
= { A,E,B, C,D} ( Using BC → D) = { B,E,C,D,A } ( Using D → A )
Thus, AE can determine all other attributes so AE is Thus, BE can determine all other attributes
one of the candidate keys CK = {AE} so BE is one of the candidate keys CK = {AE,BE}

Page 145 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Find all the possible candidate keys

► We are given the relation R(A, B, C, D, E). This means that the table R has five columns: A, B, C,
D, and E. We are also given the set of functional dependencies: {A->B, BC->D, E->C, D->A}. Find
all the possible candidate keys?

Step-02: Step-02:

 Find DE+  Find CE+

 DE+ = { D,E }  CE+ = { C,E }
= { D,E,A } ( Using D → A ) Thus,CE can’t determine all other
= { D,E,A,B} ( Using A → B ) attributes so CE is not a candidate key
= { D,E,A,B,C} ( Using E → C) So the Candidate Keys are
= { D,E,A,B,C,D} ( Using BC → D) CK = {AE, DE, BE}
Thus, DE can determine all other attributes
so DE is one the candidate keys
CK = {AE,BE,DE}
Page 146 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Find all the possible candidate keys – University Question
► Given R(A,B,C,D,E) with the set of FDs, F = {AB→CD, ABC →E, C →A}.
► Find all candidate keys of R

► Find prime and nonprime attributes

Step-01:
The essential attribute of the relation is B.
Step -02:
 Find B+
 B+ = { B }
Thus, B alone can’t be a candidate key
 So, attribute B will definitely be a part of every candidate key.
 Find AB+, CB+, DB+, EB+
 Choose the proper candidate keys

Page 147 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Find all the possible candidate keys – University Question
► Given R(A,B,C,D,E) with the set of FDs, F = {AB→CD, ABC →E, C →A}.
► Find all candidate keys of R
► Find prime and nonprime attributes
Step-02: Step-02:

 Find AB+  Find CB+

 AB+ = { A,B}  CB+ = { C,B}
= { A,B,C,D} ( Using AB → CD) = { C,B,A} ( Using C → A)
= { A,B,C,D,E} ( Using ABC → E) = { C,B,A,D} ( Using AB → CD)
Thus, AB can determine all other attributes = { C,B,A,D,E} ( Using ABC → E)
so AB is one the candidate keys Thus, CB can determine all other attributes so AB is one
CK = {AB} of the candidate keys
CK = {AB,CB}

Prime attributes are: A, B, C Non-Prime attributes are: D, E

Page 148 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Exercise #1

► Given a relation R(A,B,C). Find the minimal cover of the set of functional dependencies given; F=
{A→BC, B→C, A→B, AB→C}

Page 149 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Exercise #2

► Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies-

► C → F, E → A, EC → D, A → B

► Which of the following is a key for R?

► CD
► EC
► AE
► AC

Page 150 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Exercise #3

► Let R = (A, B, C, D, E) be a relation scheme with the following dependencies-

► AB → C

► C→D

► B→E

► Determine the total number of candidate keys

Page 151 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Decomposition

Page 152
 What is decomposition?

► Decomposition is the process of breaking down in parts or elements.

► It replaces a relation with a collection of smaller relations.

► It breaks the table into multiple tables in a database.

► It should always be lossless because it confirms that the information in the original
relation can be accurately reconstructed based on the decomposed relations.
► If there is no proper decomposition of the relation, then it may lead to problems like
loss of information.

Page 153 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Properties of Decomposition

► Following are the properties of Decomposition,

► Lossless Decomposition
► Dependency Preservation
► Lack of Data Redundancy

Page 154 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 What is decomposition?

► Lossless Decomposition
► If the information is not lost from the relation that is
decomposed, then the decomposition will be lossless.
► The lossless decomposition guarantees that the join of
relations will result in the same relation as it was
decomposed.
► The relation is said to be lossless decomposition if
natural joins of all the decomposition give the original
relation.

Page 155 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossless Decomposition

► Decomposition must be lossless. It means that the information should not get lost
from the relation that is decomposed.
► Example:
► Let's take 'E' is the Relational Schema, With instance 'e'; is decomposed into: E1, E2, E3, . .
. . En; With instance: e1, e2, e3, . . . . en, If e1 ⋈ e2 ⋈ e3 . . . . ⋈ en, then it is called as
'Lossless Join Decomposition'.
► In the above example, it means that, if natural joins of all the decomposition give the original
relation, then it is said to be lossless join decomposition.

Page 156 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossless Decomposition

► Example: <Employee_Department> Table

► Decompose the above relation into two relations to check whether a decomposition is lossless or
lossy.
► Now, we have decomposed the relation that is Employee and Department.

Page 157 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossless Decomposition

► Relation 1 : <Employee> Table

► Employee Schema contains (Eid, Ename, Age, City, Salary).

Page 158 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossless Decomposition

► Relation 2 : <Department> Table

► Department Schema contains (Deptid, Eid, DeptName).

► So, the above decomposition is a Lossless Join Decomposition, because the two relations contains one common
field that is 'Eid' and therefore join is possible.
► Now apply natural join on the decomposed relations.

Page 159 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossless Decomposition

► Employee ⋈ Department

► Hence, the decomposition is Lossless Join Decomposition.

► If the <Employee> table contains (Eid, Ename, Age, City, Salary) and <Department> table contains (Deptid and
DeptName), then it is not possible to join the two tables or relations, because there is no common column between
them. And it becomes Lossy Join Decomposition.

Page 160 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossy Decomposition

► As the name suggests, when a relation is decomposed into two or more relational schemas, the
loss of information is unavoidable when the original relation is retrieved.

Page 161 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Lossy Decomposition

► Decompose the above table into two tables −

► Now, you won’t be able to join the above tables, since Emp_ID isn’t part of the DeptDetails relation. Therefore, the
above relation has lossy decomposition.

Page 162 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Consider a relation R is decomposed into two sub relations R1 and R2. Then
► If all the following conditions satisfy, then the decomposition is lossless.
► If any of these conditions fail, then the decomposition is lossy.
► Condition-1:
► Union of both the sub relations must contain all the attributes that are present in the original relation R. Thus,
R1 ∪ R2 = R
► Condition-2:
► Intersection of both the sub relations must not be null. In other words, there must be some common attribute
which is present in both the sub relations. Thus, R1 ∩ R2 ≠ ∅
► Condition-3:
► Intersection of both the sub relations must be a super key of either R1 or R2 or both. Thus, R1 ∩ R2 = Super
key of R1 or R2

Page 163 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Problem: Consider a relation schema R ( A , B , C , D ) with the functional dependencies A → B

and C → D. Determine whether the decomposition of R into R1 ( A , B ) and R2 ( C , D ) is
lossless or lossy.
► Solution:
► Condition-1: According to condition-01, union of both the sub relations must contain all the
attributes of relation R. So, we have R1 ( A , B ) ∪ R2 ( C , D ) = R ( A , B , C , D )
► Condition-2: According to condition-02, intersection of both the sub relations must not be null.
So, we have R1 ( A , B ) ∩ R2 ( C , D ) = Φ
► Clearly, intersection of the sub relations is null. So, condition-2 fails. Thus, we conclude that the
decomposition is lossy.

Page 164 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Problem: Consider a relation schema R ( A , B , C , D ) with the following functional dependencies

A → B, B → C, C → D, D → B Determine whether the decomposition of R into R1 ( A , B ) , R2 (
B , C ) and R3 ( B , D ) is lossless or lossy.

► Strategy: Strategy to Solve When a given relation is decomposed into more than two sub-relations, then
► Consider any possible ways in which the relation might have been decomposed into those sub-relations.
► First, divide the given relation into two sub-relations.
► Then, divide the sub-relations according to the sub-relations given in the question.
► As a thumb rule, remember Any relation can be decomposed only into two sub-relations at a time.

Page 165 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Problem: Consider a relation schema R ( A , B , C , D ) with the following functional dependencies

A → B, B → C, C → D, D → B Determine whether the decomposition of R into R1 ( A , B ) , R2 (
B , C ) and R3 ( B , D ) is lossless or lossy.

Page 166 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Problem: Consider a relation schema R ( A , B , C , D ) with the following functional dependencies

A → B, B → C, C → D, D → B Determine whether the decomposition of R into R1 ( A , B ) , R2 (
B , C ) and R3 ( B , D ) is lossless or lossy.
► Decomposition of R ‘(A, B, C, D) into R'(A, B, C) and R3(B, D)-

► Solution:
► Condition-1: Union of both the sub relations must contain all the attributes of relation R. So, we have R' ( A , B , C )
∪ R3 ( B , D ) = R ( A , B , C , D )
► Clearly, union of the sub relations contain all the attributes of relation R. Thus, condition-01 satisfies.
► Condition-2: intersection of both the sub relations must not be null. So, we have
R‘ ( A , B , C ) ∩ R3 ( B , D ) = B
► Clearly, intersection of the sub relations is not null. Thus, condition-2 satisfies.

Page 167 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

► Solution:
► Condition-3: According to condition-3, intersection of both the sub relations must be the super key
of one of the two sub relations or both. So, we have-
R‘ ( A , B , C ) ∩ R3 ( B , D ) = B
► Now, the closure of attribute B is- B+ = { B , C , D }
► Attribute ‘B’ can not determine attribute ‘A’ of sub relation R’. Thus, it is not a super key of the
sub relation R’.
► Attribute ‘B’ can determine all the attributes of sub relation R3. Thus, it is a super key of the sub
relation R3.
► Clearly, intersection of the sub relations is a super key of one of the sub relations.
► So, condition-3 satisfies.
► Thus, we conclude that the decomposition is lossless.

Page 168 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Page 169 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Page 170 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Assume that the relation R(P,Q,S,T,U) with FDs P → S, Q → S, S → T, TU → S, SU → P is decomposed into 5 relations:
R1(P,T), R2(P,Q), R3(Q,U), R4(S,T,U) and R5(P,U). Apply the standard algorithm to test if the decomposition is a lossless-
join decomposition.

P (a1) Q (a2) S (a3) T (a4) U(a5)

R1(P,T)

R2(P,Q)

R3(Q,U)

R4(S,T,U)

R5(P,U)

Page 171 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Assume that the relation R(P,Q,S,T,U) with FDs P → S, Q → S, S → T, TU → S, SU → P is

decomposed into 5 relations: R1(P,T), R2(P,Q), R3(Q,U), R4(S,T,U) and R5(P,U). Apply the standard
algorithm to test if the decomposition is a lossless-join decomposition.
P (a1) Q (a2) S (a3) T (a4) U(a5)

R1(P,T) a1 a4

R2(P,Q) a1 a2

R3(Q,U) a2 a5

R4(S,T,U) a3 a4 a5

R5(P,U) a1 a5

► IF ANY ROW IS COMPLETELY FILLED WITH a SYMBOL,THEN THE DECOMPOSITION IS LOSSLESS

Page 172 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Assume that the relation R(P,Q,S,T,U) with FDs P → S, Q → S, S → T, TU → S, SU → P is

decomposed into 5 relations: R1(P,T), R2(P,Q), R3(Q,U), R4(S,T,U) and R5(P,U). Apply the standard
algorithm to test if the decomposition is a lossless-join decomposition.
P (a1) Q (a2) S (a3) T (a4) U(a5)

R1(P,T) a1 b12 b13 a4 b15

R2(P,Q) a1 a2 b23 b24 b25

R3(Q,U) b31 a2 b33 b34 a5

R4(S,T,U) b41 b42 a3 a4 a5

R5(P,U) a1 b52 b53 b54 a5

Page 173 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

Assume that the relation R(P,Q,S,T,U) with FDs P → S, Q → S, S → T, TU → S, SU → P is

decomposed into 5 relations: R1(P,T), R2(P,Q), R3(Q,U), R4(S,T,U) and R5(P,U). Apply the standard
algorithm to test if the decomposition is a lossless-join decomposition.
► APPLY THE FUNCTIONAL DEPENDENCIES AND REPLACE b with a symbol
P (a1) Q (a2) S (a3) T (a4) U(a5)

R1(P,T) a1 b12 b13a3 a4 b15

R2(P,Q) a1 a2 b23a3 b24a4 b25

R3(Q,U) b31a1 a2 b33a3 b34a4 a5

R4(S,T,U) b41a1 b42 a3 a4 a5

R5(P,U) a1 b52 b53 a3 b54a4 a5

Page 174 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy

P (a1) Q (a2) S (a3) T (a4) U(a5)

R1(P,T) a1 b12 a3 a4 b15

R2(P,Q) a1 a2 a3 a4 b25

R3(Q,U) a1 a2 a3 a4 a5

R4(S,T,U) a1 b42 a3 a4 a5

R5(P,U) a1 b52 a3 a4 a5

► ROW 3 IS COMPLETELY FILLED WITH a SYMBOL, DECOMPOSITION IS LOSSLESS

Page 175 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Tutorial Questions

Page 176
 Determining Whether Decomposition Is Lossless Or Lossy –ques1

Let R = ABCDE, R1 = AD, R2 = AB, R3 = BE, R4 = CDE, and R5 = AE. Let the FDs be: A→C, B→C, C→D, DE→C, CE→A.
Show how to test if the decomposition of R into {R1,R2,R3,R4,R5} is a lossless join decomposition.

A (a1) B (a2) C (a3) D (a4) E(a5)

R1(AD)

R2(AB)

R3(BE)

R4(CDE)

R5(AE)

Page 177 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy-ques2

Given a relation R(A1,A2,A3,A4,A5) with functional dependencies A1→A2A4 and A4→A5, check if the decomposition
R1(A1,A2,A3), R2(A1,A4), R3(A2,A4,A5)is lossless

A 1(a1) A2 (a2) A3 (a3) A4 (a4) A5(a5)

R1(A1,A2,A3),

R2(A1,A4),

R3(A2,A4,A5)

Page 178 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy-question3

Suppose that we decompose the schema R = (A, B, C, D, E) into R1(A, B, C) R2(A, D, E) Test whether the given
decomposition is a lossless-join decomposition, if the following set F of functional dependencies holds in R: F= {A BC, D
E, B  D, E  A}

A (a1) B (a2) C (a3) D (a4) E(a5)

R1(A, B, C)

R2(A, D, E)

Page 179 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Determining Whether Decomposition Is Lossless Or Lossy-quest4

► Let R = ABCDE, R1 = AD, R2 = AB, R3 = BE, R4 = CDE, and R5 = AE. Let the functional
dependencies be: A -> C, B -> C, C -> D, DE -> C, CE -> A
► Test if the decomposition of R into {R1,..,R5} is a lossless join decomposition.
A (a1) B (a2) C (a3) D (a4) E(a5)

Page 180 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Dependency Preservation

Page 181
 Dependency Preservation

Page 182 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Dependency Preservation

Page 183 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Dependency Preservation

Page 184 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Dependency Preservation

Page 185 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Dependency Preservation

Page 186 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Problems

Page 187
 How to find the highest normal form of a relation

► Steps to find the highest normal form of relation:

► Find all possible candidate keys of the relation.

► Divide all attributes into two categories:

► prime attributes and non-prime attributes.
► Check for 1st normal form then 2nd and so on.
► If it fails to satisfy the nth normal form condition, the highest normal form will be n-1.

Page 188 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Normal Forms

► Second Normal Form

► No Partial Dependency, i.e., no non-prime attribute (attributes which are not part of any candidate key) is
dependent on any proper subset of any candidate key of the table.
► Third Normal Form
► If a functional dependency X->Y holds true where Y is not a subset of X then this dependency is called non trivial
Functional dependency.
► A relation is in 3NF if at least one of the following condition holds in every non-trivial function dependency X –>
Y
► X is a super key.
► Y is a prime attribute (each element of Y is part of some candidate key).
► Boyce-Codd Normal Form (BCNF)
► Third Normal Form and for every FD, LHS is super key

Page 189 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example

► Find the highest normal form of a relation R(P, Q, R, S, T) with Functional dependency set as (QR-
>S, PR->QT, Q->T).
► Step 1:
► As the relation (PR)+ = (P, Q, R, S, T) is given, but not a single of its subset can determine all
attributes of relation, So PR will be candidate key. P or R can’t be derived from any other
attribute of the relation, so there will be only one candidate key (PR).
► Step 2:
► The attributes which are part of candidate key (P, R) are Prime attributes.
► The others will be non-prime attributes (Q, S,T).

Page 190 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 ► (P, R) are Prime attributes

Example
► QR->S,
► CK= PR ► PR->QT,
► non-prime attributes (Q, S,T). ► Q->T
► IF subset of CKNPA ,VIOLATES 2NF

► Step 3:
► A Relational Database Management System does not enable multi-valued or composite attribute. So,
the relation R(P, Q, R, S, T) is in 1st normal form.
► QR->S is in 2nd normal form (QR is not a proper subset of candidate key PR) and PR->QT is in 2nd
normal form (PR is candidate key) and
Q->T is in 2nd normal form (Q is not a proper subset of candidate key PR).
So, the relation is in 2nd normal form.
► In QR->S (neither QR is a super key nor S is a prime attribute) and in Q->T (neither Q is a super key nor
T is a prime attribute)
► To satisfy 3rd normal form, either LHS of a Functional Dependency should be super key or RHS should
be prime attribute. So, the relation is not in 3rd normal form.
So, the highest normal form of relation will be 2nd Normal form.

Page 191 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 1

► Find the highest normal form of a relation R(A,B,C,D,E) with FD set {A->D, B->A, BC->D, AC->BE}
► Step 1.
► As we can see, (AC) + ={A, C, B, E, D} but none of its subsets can determine all attributes of relation, So AC will
be the candidate key. (BC) + ={B, C, D, A, E, D} will also be a candidate key
► So there will be two candidate keys {AC, BC}.
► Step 2-
► Step 2. The prime attribute is those attribute which is part of candidate key {A, B, C} in this example and others
will be non-prime {D, E} in this example.

Page 192 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 1

► Find the highest normal form of a relation R(A,B,C,D,E) with FD set {A->D, B->A, BC->D, AC->BE}
► Step 3.
► The relation R is in 1st normal form as a relational DBMS does not allow multi-valued or composite attributes.
► The relation is not in the 2nd Normal form because A->D is partial dependency (A which is a subset of
candidate key AC is determining non-prime attribute D) and the 2nd normal form does not allow partial
dependency.
► So the highest normal form will be the 1st Normal Form.

Page 193 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 2

► Example 2. Find the highest normal form of a relation R(A,B,C,D,E) with FD set as {BC->D, AC-
>BE, B->E}
► Step 1.
► As we can see, (AC)+ ={A,C,B,E,D} but none of its subsets can determine all attributes of relation, So AC will be
the candidate key.
► A or C can’t be derived from any other attribute of the relation, so there will be only 1 candidate key {AC}.
► Step 2-
► The prime attribute is those attribute which is part of candidate key {A,C} in this example and others will be non-
prime {B,D,E} in this example

Page 194 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 ► Candidate Key=AC

Example 2 ►

►
NPA ={B,D,E}
PA ={A,C}

► Example 2. Find the highest normal form of a relation R(A,B,C,D,E) with FD set as {BC->D, AC->BE, B-
>E}
► Step 3.
► The relation R is in 1st normal form as a relational DBMS does not allow multi-valued or composite attributes.
► The relation is in 2nd normal form [CK=AC, NPA= {B,D,E} ,IF subset of CKNPA ,VIOLATES 2NF]
► BC->D is in 2nd normal form (BC is not a proper subset of candidate key AC) and
► AC->BE is in 2nd normal form (AC is candidate key) and
► B->E is in 2nd normal form (B is not a proper subset of candidate key AC).
► The relation is not in 3rd normal form [FOR 3NF ,X –> Y,X is a super key/Y is a prime attribute]
► BC->D (neither BC is a super key nor D is a prime attribute)
► B->E (neither B is a super key nor E is a prime attribute) but to satisfy 3rd normal for, either LHS of an FD should be super key or
RHS should be a prime attribute.
► So the highest normal form of relation will be the 2nd Normal form.

Page 195 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 3

► Find the highest normal form of a relation R(A,B,C,D,E) with FD set {B->A, A->C, BC->D, AC->BE}
► Step 1.
► As we can see, (B)+ ={B,A,C,D,E}, so B will be candidate key.
► B can be derived from AC using AC->B (Decomposing AC->BE to AC->B and AC->E).

► So AC will be super key but (C)+ ={C} and (A)+ ={A,C,B,E,D}.

► So A (subset of AC) will be candidate key. So there will be two candidate keys {A,B}.

► Step 2
► The prime attribute is those attribute which is part of candidate key {A,B} in this example and others will be non-
prime {C,D,E} in this example.
► Step 3.
► The relation R is in 1st normal form as a relational DBMS does not allow multi-valued or composite attributes.

Page 196 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 3
► candidate keys {A,B}
► Prime Attribute: {A,B}
► non-prime {C,D,E}

► Find the highest normal form of a relation R(A,B,C,D,E) with FD set {B->A, A->C, BC->D, AC->BE}
► Step 3.
► The relation R is in 1st normal form as a relational DBMS does not allow multi-valued or composite attributes.
► The relation is in 2nd normal form [IF subset of CKNPA ,VIOLATES 2NF] because B->A is in 2nd normal form
(B is a superkey) and A->C is in 2nd normal form (A is super key) and BC->D is in 2nd normal form (BC is a super
key) and AC->BE is in 2nd normal form (AC is a super key).
► The relation is in 3rd normal form because the LHS of all FD’s is super keys. The relation is in BCNF as all LHS of
all FD’s are super keys. So the highest normal form is BCNF.

Page 197 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 4

► Given a relation R( A, B, C) and Functional Dependency set FD = { A → B, B → C, and C → A},

determine given R is in which normal form?
► Step 1
► A+ = {ABC}, B+ = {BCA}, C+={CAB}
► Hence three Candidate keys are: A B and C

► Step 2
► FD: A → B satisfy the definition of BCNF, as A is Super Key, we check other FD for BCNF
► FD: B → C satisfy the definition of BCNF, as B is Super Key, we check other FD for BCNF
► FD: C → A satisfy the definition of BCNF, as C is Super Key
► Since there were only three FD's and all FD: { A → B, B → C and C → A } satisfy BCNF, hence the highest normal
form is BCNF.
► Therefore R(A, B, C ) is in BCNF.

Page 198 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

► Solution
► Find Candidate key using closure ,CK = {AB, FB, EB, CB}
► Prime Attributes {A,B,C,E,F}
► Non Prime Attributes {D}
► Check the Relation in 2 NF
► AB → C : Full Dependency
► C → D : Partial Dependency (Part of CK(C) determines Non prime attribute D)
► C → E : Full Dependency
► E → F : Full Dependency
► F → A : Full Dependency
► So this relation is not in 2 NF, we have to convert it into 2 NF
Page 199 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

► Solution C → D Violates the property so split it

R( A,B,C,D,E,F)

R1( A,B,E,F) R2( C,D)

Now we are not able to combine these two relations as there is no common attribute between them, so to make it possible we have
to redefine the relation R1

Page 200 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

► Solution C→D
Remove attributes in the RHS
of the violating dependencies from
R( A,B,C,D,E,F) Relation and create a new Relations

R1( A,B,C,E,F) R2( C,D)

Functional Dependencies Functional Dependencies

AB → C, C → E, E → F, F → A C→D

Now the Relation R1 & R2 are in 2 NF

Page 201 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

► Solution
► Check the R1( A,B,C,E,F) R2( C,D) in 3NF
► AB → C : Full Dependency
► C → D : Full Dependency (Now part of R2 where CK is C and D is Non prime attribute)
► C → E: Full Dependency
► E → F: Full Dependency
► F → A: Full Dependency
► So the R1 & R2 in 3NF

Page 202 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

► Solution
► Check R1 & R2 in BCNF(All LHS must be a CK)
► AB → C : AB is CK so this dependency in BCNF
► C → D : C is a CK(in R2) so this dependency is in BCNF
► C → E : C is not a CK so this dependency is not in BCNF
► E → F : E is not a CK so this dependency is not in BCNF
► F → A : F is not a CK so this dependency is not in BCNF

Page 203 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Example 5

► Given a relation R( A,B,C,D,E,F) and Functional Dependency set FD = { AB → C, C → D, C → E, E

→ F, F → A }, Decompose R into 2NF,3NF and then BCNF relations?

AB → C C→E E→F F→A

► Solution
R1( A,B,C,E,F)

R3( A,B,C) R4(C,E) R5(E,F) R6(F,A)

We have common attribute in all relations , so it’s a lossless decomposition

► R2(C,D), R3(A,B,C), R4(C,E), R5(E,F) and R6(F,A) now satisfies the BCNF Conditions

Page 204 Prof. Sarju S,[Link] Jacob, Department of Computer Science and Engineering,
SJCET Palai
 Thank You

Disclaimer - This document contains images/texts from various internet sources. Copyright belongs to the respective content creators. Document is compiled exclusively for
study purpose and shall not be used for commercial purpose.

Page 205 [Link] S,[Link] Jacob,Department of CSE,SJCET,Palai