Functional Dependency

 Functional dependency (FD) is a set of constraints between two

attributes in a relation.
 Functional dependency says that if two tuples have same values
for attributes A1, A2,..., An, then those two tuples must have to
have same values for attributes B1, B2, ..., Bn.
 Functional dependency is represented by an arrow sign (→) that
is, X→Y, where X functionally determines Y. The left-hand side
attributes determine the values of attributes on the right-hand side.
 Assume we have an employee table with attributes: Emp_Id,
Emp_Name, Emp_Address. Here Emp_Id attribute can uniquely
identify the Emp_Name attribute of employee table because if we
know the Emp_Id, we can tell that employee name associated with
it. Functional dependency can be written as:
Emp_Id → Emp_Name. We can say that Emp_Name is
functionally dependent on Emp_Id.
12-03-2021 Side 1
Types of Functional Dependency

12-03-2021 Side 2
Types of Functional Dependency
Trivial Functional Dependency
 If a functional dependency (FD) X → Y holds, where Y is a
subset of X, then it is called a trivial FD. Trivial FDs always
hold.
 A → B has trivial functional dependency if B is a subset of A.
 The A → A, B → B dependencies are also trivial FDs.
 Consider a table with two columns Employee_Id and
Employee_Name.
 {Employee_id, Employee_Name} → Employee_Id is a trivial
functional dependency as Employee_Id is a subset of
{Employee_Id, Employee_Name}.
 Also, Employee_Id → Employee_Id and Employee_Name →
Employee_Name are trivial dependencies too.
12-03-2021 Side 3
Types of Functional Dependency
Non-trivial Functional Dependency
 If an FD X → Y holds, where Y is not a subset of X, then it
is called a non-trivial FD.
 A → B has a non-trivial functional dependency if B is not a
subset of A.
 When A intersection B is NULL, then A → B is called as
complete non-trivial.
 Examples: ID → Name, Name → DOB

12-03-2021 Side 4
Armstrong's Axioms
 If F is a set of functional dependencies then the closure of
F, denoted as F+, is the set of all functional dependencies
logically implied by F.
 Armstrong's Axioms are a set of rules, when applied
repeatedly, generates a closure of functional dependencies.
 The Armstrong's axioms are the basic inference rule.
 Armstrong's axioms are used to conclude functional
dependencies on a relational database.
 The inference rule is a type of assertion. It can apply to a
set of FD(functional dependency) to derive other FD.
 Using the inference rule, we can derive additional
functional dependency from the initial set.
 The Functional dependency has 6 types of inference rule:
12-03-2021 Side 5
Armstrong's Axioms
1. Reflexive Rule (IR1)

In the reflexive rule, if Y is a subset of X, then X determines Y.

If X ⊇ Y then X → Y
Example:
X = {a, b, c, d, e}
Y = {a, b, c} then X → Y
2. Augmentation Rule (IR2)

The augmentation is also called as a partial dependency. In

augmentation, if X determines Y, then XZ determines YZ for
any Z. If X → Y then XZ → YZ.
Example:
For R(ABCD), if A → B then AC → BC
12-03-2021 Side 6
Armstrong's Axioms
3. Transitive Rule (IR3)

In the transitive rule, if X determines Y and Y determines Z, then X

must also determine Z.
If X → Y and Y → Z then X → Z

4. Union Rule (IR4)

Union rule says, if X determines Y and X determines Z, then X must

also determine Y and Z.
If X → Y and X → Z then X → YZ
Proof:
X→Y(given), X → Z (given)
X → XY (using IR2 on 1 by augmentation with X. Where XX = X)
XY → YZ (using IR2 on 2 by augmentation with Y)
X → YZ (using IR3 on 3 and 4)
12-03-2021 Side 7
Armstrong's Axioms
5. Decomposition Rule (IR5)
 Decomposition rule is also known as project rule. It is the
reverse of union rule.
 This Rule says, if X determines Y and Z, then X determines Y
and X determines Z separately.
 Example: If X → YZ then X → Y and X → Z
Proof:
1. X → YZ (given)
2. YZ → Y (using IR1 Rule)
3. X → Y (using IR3 on 1 and 2)
12-03-2021 Side 8
Armstrong's Axioms
6. Pseudo transitive Rule (IR6)

In Pseudo transitive Rule, if X determines Y and YZ determines

W, then XZ determines W.

If X → Y and YZ → W then XZ → W
Proof:
1. X → Y (given)
2. YZ → W (given)
3. XZ → YZ (using IR2 on 1 by augmenting with Z)
4. XZ → W (using IR3 on 3 and 2)
12-03-2021 Side 9
Normalization
 Normalization is a database design technique that reduces data
redundancy and eliminates undesirable characteristics like
Insertion, Update and Deletion Anomalies.
 Normalization is used to minimize the redundancy from a
relation or set of relations. It is also used to eliminate the
undesirable characteristics like Insertion, Update and Deletion
Anomalies.
 Normalization divides the larger table into the smaller table and
links them using relationship.

 The normal form is used to reduce redundancy from the

database table.
12-03-2021 Side 10
Types of Normal Form

12-03-2021 Side 11
Types of Normal Form
Normal Form Description

1NF A relation is in 1NF if it contains an atomic value.

2NF A relation will be in 2NF if it is in 1NF and all non-key

attributes are fully functional dependent on the primary key.

3NF A relation will be in 3NF if it is in 2NF and no transition

dependency exists.

4NF A relation will be in 4NF if it is in Boyce Codd normal

form and has no multi-valued dependency.

5NF A relation is in 5NF if it is in 4NF and not contains any join

dependency and joining should be lossless.
12-03-2021 Side 12
Normalization
If a database design is not perfect, it may contain anomalies, which are
like a bad dream for any database administrator. Managing a database
with anomalies is next to impossible.
 Update anomalies − If data items are scattered and are not linked to
each other properly, then it could lead to strange situations. For
example, when we try to update one data item having its copies
scattered over several places, a few instances get updated properly
while a few others are left with old values. Such instances leave the
database in an inconsistent state.
 Deletion anomalies − We tried to delete a record, but parts of it was
left undeleted because of unawareness, the data is also saved
somewhere else.
 Insert anomalies − We tried to insert data in a record that does not
exist at all.
 Redundancy
12-03-2021 Side 13
First Normal Form (1NF)
 A relation will be in 1NF if it contains an atomic value.

 It states that an attribute of a table cannot hold multiple

values. It must hold only single-valued attribute.

 First normal form disallows the multi-valued attribute,

composite attribute, and their combinations.

12-03-2021 Side 14
Examples of 1NF
EMPLOYEE:
EMP_ID EMP_NAME EMP_PHONE EMP_STATE

14 John 7272826385, 9064738238 UP

20 Harry 8574783832 Bihar

12 Sam 7390372389, 8589830302 Punjab

Relation EMPLOYEE is not in 1NF because of multi-valued attribute

EMP_PHONE. The decomposition of the EMPLOYEE table into 1NF has
been shown below:
EMP_ID EMP_NAME EMP_PHONE EMP_STATE

14 John 7272826385 UP
14 John 9064738238 UP
20 Harry 8574783832 Bihar
12 Sam 7390372389 Punjab
12 Sam 8589830302 Punjab
12-03-2021 Side 15
Examples of 1NF

Here you see Movies Rented column has multiple values. Not in 1NF.

12-03-2021 Side 16
Second Normal Form (2NF)
A relation is said to be in 2NF if it is in 1NFand all non-key attributes are
fully functional dependent on the primary key i.e there is no partial
dependency.
Example: Let's assume, a school can store the data of teachers and the
subjects they teach. In a school, a teacher can teach more than one subject.
Teacher Table:
TEACHER_ID SUBJECT TEACHER_AGE

25 Chemistry 30
25 Biology 30
47 English 35
83 Math 38
83 Computer 38
In the given table, non-prime attribute TEACHER_AGE is dependent on
TEACHER_ID which is a proper subset of a candidate key. That's why it
violates the rule for 2NF.To convert the given table into 2NF, we decompose
it into two tables:
12-03-2021 Side 17
Second Normal Form (2NF)
Candidate Keys: {teacher_id, subject}, Non prime attribute: teacher_age
TEACHER_DETAIL table:
TEACHER_ID TEACHER_AGE

25 30
47 35
83 38
TEACHER_SUBJECT table:
TEACHER_ID SUBJECT

25 Chemistry

25 Biology

47 English

83 Math

83 Computer

12-03-2021 Side 18
Second Normal Form (2NF)
Member Details

Movies Rented

12-03-2021 Side 19
Third Normal Form (3NF)
 A relation will be in 3NF if it is in 2NF and not contain any transitive
dependency.
 3NF is used to reduce the data duplication. It is also used to achieve the data
integrity.
 If there is no transitive dependency for non-prime attributes, then the relation
must be in third normal form.
 A relation is in third normal form if it holds at least one of the following
conditions for every non-trivial function dependency X → Y.
 X is a super key.
 Y is a prime attribute, i.e., each element of Y is part of some candidate key.
Example
EMPLOYEE_DETAIL table:
EMP_ID EMP_NAME EMP_ZIP EMP_STATE EMP_CITY

222 Harry 201010 UP Noida

333 Stephan 02228 US Boston

444 Lan 60007 US Chicago

555 Katharine 06389 UK Norwich

666 John 462007 MP Bhopal

12-03-2021 Side 21
Third Normal Form (3NF)
Super key in the table above:
1.{EMP_ID}, {EMP_ID, EMP_NAME}, {EMP_ID, EMP_NAME, EMP_ZI
P}....so on

Candidate key: {EMP_ID}

Non-prime attributes: In the given table, all attributes except EMP_ID are
non-prime.

Here, EMP_STATE & EMP_CITY dependent on EMP_ZIP and EMP_ZIP

dependent on EMP_ID. The non-prime attributes (EMP_STATE, EMP_CITY)
transitively dependent on super key(EMP_ID). It violates the rule of third
normal form.

That's why we need to move the EMP_CITY and EMP_STATE to the new
<EMPLOYEE_ZIP> table, with EMP_ZIP as a Primary key.

12-03-2021 Side 21
Third Normal Form (3NF)
EMPLOYEE table:
EMP_ID EMP_NAME EMP_ZIP

222 Harry 201010

333 Stephan 02228

444 Lan 60007

555 Katharine 06389

666 John 462007

EMPLOYEE_Zip table:
EMP_ZIP EMP_STATE EMP_CITY

201010 UP Noida
02228 US Boston
60007 US Chicago
06389 UK Norwich
462007 MP Bhopal
12-03-2021 Side 22
Third Normal Form (3NF)
Suppose a company wants to store the complete address of each employee,
they create a table named employee_details that looks like this:

emp_id emp_name emp_zip emp_state emp_city emp_district

1001 John 282005 UP Agra Dayal Bagh

1002 Ajeet 222007 TN Chennai M-City

1006 Lora 282007 TN Chennai Urrapakkam

1101 Lilly 292008 UK Pauri Bhagwan

1201 Steve 222999 MP Gwalior Ratan

12-03-2021 Side 23
Third Normal Form (3NF)
Employee table:
emp_id emp_name emp_zip
1001 John 282005
1002 Ajeet 222008
1006 Lora 282007
1101 Lilly 292008
1201 Steve 222999

Employee_Zip table:
emp_zip emp_state emp_city emp_district
282005 UP Agra Dayal Bagh
222008 TN Chennai M-City
282007 TN Chennai Urrapakkam
292008 UK Pauri Bhagwan
222999 MP Gwalior Ratan

12-03-2021 Side 24
Third Normal Form (3NF)
Super keys: {emp_id}, {emp_id, emp_name}, {emp_id,
emp_name, emp_zip}…so on

Candidate Keys:{emp_id}

Non-prime attributes: all attributes except emp_id are non-

prime as they are not part of any candidate keys.

Here, emp_state, emp_city & emp_district dependent on

emp_zip. And, emp_zip is dependent on emp_id that makes
non-prime attributes (emp_state, emp_city & emp_district)
transitively dependent on super key (emp_id). This violates
the rule of 3NF.To make this table complies with 3NF we have
to break the table into two tables to remove the transitive
dependency:
12-03-2021 Side 25
Boyce Codd normal form (BCNF)
 BCNF is the advance 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.
Example: Let's assume there is a company where employees work in
more than one department.

EMPLOYEE table:
EMP_ID EMP_COUNTRY EMP_DEPT DEPT_TYPE EMP_DEPT_NO

264 India Designing D394 283

264 India Testing D394 300
364 UK Stores D283 232
364 UK Developing D283 549
12-03-2021 Side 26
Boyce Codd normal form (BCNF)
In the above table Functional dependencies are as follows:
1. EMP_ID → EMP_COUNTRY
2. EMP_DEPT → {DEPT_TYPE, EMP_DEPT_NO}
Candidate key: {EMP-ID, EMP-DEPT}
The table is not in BCNF because neither EMP_DEPT nor EMP_ID alone
are keys.
To convert the given table into BCNF, we decompose it into three tables:

EMP_COUNTRY table:
EMP_ID EMP_COUNTRY

264 India
264 India

12-03-2021 Side 27
Boyce Codd normal form (BCNF)
EMP_DEPT table:
EMP_DEPT DEPT_TYPE EMP_DEPT_NO

Designing D394 283

Testing D394 300
Stores D283 232
Developing D283 549

EMP_DEPT_MAPPING table:
EMP_ID EMP_DEPT

D394 283
D394 300
D283 232
D283 549

12-03-2021 Side 28
Boyce Codd normal form (BCNF)
Example 2:
Consider a relation given below:
SP (Sno, Sname, Pno, Qty), Here Sname is considered unique for
each Sno. So, FD of above relation is:
(Sno, Pno) → Qty, (Sname, Pno) → Qty, Sno →Sname
Sname → Sno. Is this relation in 3NF? Check for it to be in BCNF?
How can you solve this problem?

Solution: There are two overlapping candidate keys.

(Sno, Pno) and (Sname, Pno) ie
(Pno, Sno) → (Qty, Sname) and (Pno, Sname) → (Qty, Sno)
Both the relations are in 3NF because every nonkey attribute is nont-
ransitively fully functional dependent on the primary key.
12-03-2021 Side 29
Boyce Codd normal form (BCNF)
SP is not in BCNF because it has four determinants:
(Sno, Pno), (Sname, Pno), Sno, Sname. Out of these four
determinants, two determinants (Sno, Pno) and (Sname, Pno) are
unique but Sno and Sname determinants are not candidate keys.
Now to make this relation in BCNF, we have to non-loss decompose
this relation into two projections:

SN (Sno, Sname)
SPP (Sno, Pno, Qty).
Here, SN relation has two determinants, and both are unique.
SPP has one determinant (Sno, Pno) and is also unique.
Thus, all the anomalies are removed.

12-03-2021 Side 30
Fourth normal form (4NF)
 A relation will be in 4NF if it is in Boyce Codd normal form and has no multi-
valued dependency.
 For a dependency A → B, if for a single value of A, multiple values of B exists,
then the relation will be a multi-valued dependency.
STUDENT
STU_ID COURSE HOBBY

21 Computer Dancing
21 Math Singing
34 Chemistry Dancing
74 Biology Cricket
59 Physics Hockey

 The given STUDENT table is in 3NF, but the COURSE and HOBBY are two
independent entity. Hence, there is no relationship between COURSE and
HOBBY.
 In the STUDENT relation, a student with STU_ID, 21 contains two
courses, Computer and Math and two hobbies, Dancing and Singing. So, there
is a Multi-valued dependency on STU_ID, which leads to unnecessary
12-03-20r21epetition of data. Side 33
Fourth normal form (4NF)
So, to make the above table into 4NF, we can decompose it into two tables:
STUDENT_COURSE
STU_ID COURSE

21 Computer

21 Math

34 Chemistry

74 Biology

59 Physics

STUDENT_HOBBY
STU_ID HOBBY

21 Dancing

21 Singing

34 Dancing

74 Cricket

59 Hockey
12-03-2021 Side 32
Fifth normal form (5NF)
 A relation is in 5NF if it is in 4NF and not contains any join
dependency and joining should be lossless.
 5NF is satisfied when all the tables are broken into as many tables as
possible in order to avoid redundancy.

 5NF is also known as Project-join normal form (PJ/NF).

Example
SUBJECT LECTURER SEMESTER

Computer Anshika Semester 1

Computer John Semester 1
Math John Semester 1
Math Akash Semester 2
Chemistry Praveen Semester 1
12-03-2021 Side 33
Fifth normal form (5NF)
 In the above table, John takes both Computer and Math class for Semester 1
but he doesn't take Math class for Semester 2. In this case, combination of
all these fields required to identify a valid data.
 Suppose we add a new Semester as Semester 3 but do not know about the
subject and who will be taking that subject, so we leave Lecturer and Subject
as NULL. But all three columns together acts as a primary key, so we can't
leave other two columns blank.
 So, to make the above table into 5NF, we can decompose it into three
relations P1, P2 & P3:
P1
SEMESTER SUBJECT

Semester 1 Computer
Semester 1 Math
Semester 1 Chemistry
Semester 2 Math
12-03-2021 Side 34
P2
Fifth normal form (5NF)
SUBJECT LECTURER

Computer Anshika
Computer John
Math John
Math Akash
Chemistry Praveen

P3
SEMSTER LECTURER

Semester 1 Anshika
Semester 1 John
Semester 1 John
Semester 2 Akash
Semester 1 Praveen
12-03-2021 Side 35
Relational Decomposition
 When a relation in the relational model is not in appropriate normal
form then the decomposition of a relation is required.
 In a database, it breaks the table into multiple tables.
 If the relation has no proper decomposition, then it may lead to
problems like loss of information.
 Decomposition is used to eliminate some of the problems of bad
design like anomalies, inconsistencies, and redundancy.
Types of Decomposition

12-03-2021 Side 36
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.
EMPLOYEE_DEPARTMENT table
EMP_ID EMP_NAME EMP_AGE EMP_CITY DEPT_ID DEPT_NAME

22 Denim 28 Mumbai 827 Sales

33 Alina 25 Delhi 438 Marketing
46 Stephan 30 Bangalore 869 Finance
52 Katherine 36 Mumbai 575 Production
60 Jack 40 Noida 678 Testing

12-03-2021 Side 37
Lossless Decomposition
The above relation is decomposed into two relations EMPLOYEE & DEPARTMENT.
EMPLOYEE table
EMP_ID EMP_NAME EMP_AGE EMP_CITY

22 Denim 28 Mumbai

33 Alina 25 Delhi

46 Stephan 30 Bangalore

52 Katherine 36 Mumbai

60 Jack 40 Noida

DEPARTMENT table
DEPT_ID EMP_ID DEPT_NAME

827 22 Sales

438 33 Marketing

869 46 Finance

575 52 Production

678 60 Testing

12-03-2021 Side 38
Lossless Decomposition
Now, when these two relations are joined on the common column "EMP_ID",
then the resultant relation will look like:

Employee ⋈ Department
EMP_ID EMP_NAME EMP_AGE EMP_CITY DEPT_ID DEPT_NAME

22 Denim 28 Mumbai 827 Sales

33 Alina 25 Delhi 438 Marketing

46 Stephan 30 Bangalore 869 Finance

52 Katherine 36 Mumbai 575 Production

60 Jack 40 Noida 678 Testing

Hence, the decomposition is Lossless join decomposition.

12-03-2021 Side 39
Dependency Preserving
 It is an important constraint of the database.

 In the dependency preservation, at least one decomposed table must satisfy

every dependency.

 If a relation R is decomposed into relation R1 and R2, then the dependencies

of R either must be a part of R1 or R2 or must be derivable from the
combination of functional dependencies of R1 and R2.

 For example, suppose there is a relation R (A, B, C, D) with functional

dependency set (A->BC). The relation R is decomposed into R1(ABC) and
R2(AD) which is dependency preserving because FD A->BC is a part of
relation R1(ABC).

12-03-2021 Side 40
Multivalued Dependency
 Multivalued dependency occurs when two attributes in a table are
independent of each other but, both depend on a third attribute.
 A multivalued dependency consists of at least two attributes that are
dependent on a third attribute that's why it always requires at least three
attributes. Suppose there is a bike manufacturer company which produces
two colours (white and black) of each model every year.

BIKE_MODEL MANUF_YEAR COLOR

M2011 2008 White

M2001 2008 Black

M3001 2013 White

M3001 2013 Black

M4006 2017 White

M4006 2017 Black

12-03-2021 Side 41
Multivalued Dependency
 Here columns COLOR and MANUF_YEAR are dependent on
BIKE_MODEL and independent of each other.

 In this case, these two columns can be called as multivalued dependent

on BIKE_MODEL. The representation of these dependencies is shown
below:

BIKE_MODEL → → MANUF_YEAR

BIKE_MODEL → → COLOR

 This can be read as "BIKE_MODEL multidetermined

MANUF_YEAR" and "BIKE_MODEL multidetermined COLOR".

12-03-2021 Side 42
Join Dependency
 Join decomposition is a further generalization of Multivalued
dependencies.
 If the join of R1 and R2 over C is equal to relation R, then we can say
that a join dependency (JD) exists.
 Where R1 and R2 are the decompositions R1(A, B, C) and R2(C, D) of a
given relations R (A, B, C, D).

 Alternatively, R1 and R2 are a lossless decomposition of R.

 A JD ⋈ {R1, R2,..., Rn} is said to hold over a relation R if R1, R2,.....,
Rn is a lossless-join decomposition.
 The *(A, B, C, D), (C, D) will be a JD of R if the join of join's attribute
is equal to the relation R.

 Here, *(R1, R2, R3) is used to indicate that relation R1, R2, R3 and so
on are a JD of R.
12-03-2021 Side 45
Inclusion Dependency
 Multivalued dependency and join dependency can be used to guide database design
although they both are less common than functional dependencies.
 Inclusion dependencies are quite common. They typically show little influence on
designing of the database.
 The inclusion dependency is a statement in which some columns of a relation are
contained in other columns.
 The example of inclusion dependency is a foreign key. In one relation, the referring
relation is contained in the primary key column(s) of the referenced relation.
 Suppose we have two relations R and S which was obtained by translating two entity
sets such that every R entity is also an S entity.
 Inclusion dependency would be happen if projecting R on its key attributes yields a
relation that is contained in the relation obtained by projecting S on its key attributes.
 In inclusion dependency, we should not split groups of attributes that participate in an
inclusion dependency.
 In practice, most inclusion dependencies are key-based that is involved only keys.
12-03-2021 Side 44
Canonical Cover
 In the case of updating the database, the responsibility of the system
is to check whether the existing functional dependencies are getting
violated during the process of updating.
 In case of a violation of functional dependencies in the new database
state, the rollback of the system must take place.
 A canonical cover or irreducible a set of functional dependencies FD
is a simplified set of FD that has a similar closure as the original set
FD.

12-03-2021 Side 45