UNIT 2 : Database Design

ER Diagrams
An E-R diagram can express the overall logical structure of a database graphically.E-R diagrams are
used to model real-world objects like a person, a car, a company and the relation between these
real-world objects.

Features of ER model

i) E-R diagrams are used to represent E-R model in a database, which makes them easy to be
converted into relations (tables).

ii) E-R diagrams provide the purpose of real-world modeling of objects which makes
them intently useful.

iii) E-R diagrams require no technical knowledge and no hardware support. iv) These
diagrams are very easy to understand and easy to create even by a naive user. v) It gives a
standard solution of visualizing the data logically.

Various Components used in ER Model are -

Component Symbol Example

Entity : Any real-world

object can be
represented as an entity
about which data can be
stored in a database. All
the real world objects
like a book, an
organization, a product,
a car, a person are the
examples of an entity.

Relationship : Rhombus
is used to setup
relationships between
two or more entities.
 Attribute : Each entity
has a set of properties.
These properties of each
entity are termed as
attributes. For example,
a car entity would be
described by attributes
such as price,
registration number,
model number, color etc

Derived attribute :
Derived attributes are
those which are derived
based on other
attributes, for example,
age can be derived from
date of birth.

To represent a derived
attribute, another
dotted ellipse is created
inside the

main ellipse

Multivalued attribute :
An attribute that can
hold multiple values is
known as multivalued
attribute. We represent
it with double ellipses in
an E-R Diagram. E.g. A
person can have more
than one phone
numbers so the phone
number attribute is
multivalued.

Total participation :
Each entity is involved in
the relationship. Total
participation is
represented by double
lines.

Mapping Cardinality Representation using ER Diagram

There are four types of relationships that are considered for key constraints.

i) One to one relation : When entity A is associated with at the most one entity B then it shares one
to one relation. For example - There is one project manager who manages only one project.

ii) One to many : When entity A is

associated with more than one entities at a time then there is one to many relation. For example -
One customer places order at a time.

ii) Many to one : When more than

one entities are associated with only one entity then there is is many to one relation. For example -
Many student take a ComputerSciCourse.

Alternate representation can be

iii) Many to many : When more than one entities are associated with more than one entities. For
example -Many teachers can teach many students.

Alternate representation can be

Ternary Relationship
The relationship in which three entities are involved is called ternary relationship. For example -
Binary and Ternary Relationships
• Although binary relationships seem natural to most of us, in reality it is sometimes
necessary to connect three or more entities. If a relationship connects three entities, it is
called ternary or "3-ary."

• Ternary relationships are required when binary relationships are not sufficient to
accurately describe the semantics of an association among three entities.

• For example - Suppose, you have a database for a company that contains the
entities, PRODUCT, SUPPLIER, and CUSTOMER. The usual relationships might be PRODUCT/
SUPPLIER where the company buys products from a supplier - a normal binary relationship.
The intersection attribute for PRODUCT/SUPPLIER is wholesale_price

A binary relationship of PRODUCT and

SUPPLIER and an intersection attribute, wholesale_price

• Now consider the CUSTOMER entity, and that the customer buys products. If all
customers pay the same price for a product, regardless of supplier, then you have a simple
binary relationship between CUSTOMER and PRODUCT. For the CUSTOMER/ PRODUCT
relationship, the intersection attribute is retail_price.
A binary relationship of PRODUCT and CUSTOMER

and an Intersection attribute, retail_price

• Single ternary relation : Now consider a different scenario. Suppose the customer
buys products but the price depends not only on the product, but also on the supplier.
Suppose you needed a customerID, a productID, and a supplierID to identify a price. Now
you have an attribute that depends on three things and hence you have a relationship
between three entities (a ternary relationship) that will have the intersection attribute,
price.

Ternary relation

Weak Entity Set

• A weak entity is an entity that cannot be uniquely identified by its attributes alone.
The entity set which does not have sufficient attributes to form a primary key is called as
weak entity set.

Weak entity set

• Strong Entity Set

The entity set that has primary key is called as strong entity set

Weak entity rules

• A weak entity set has one or more many-one relationships to other (supporting)
entity sets.

• The key for a weak entity set is its own underlined attributes and the keys for the
supporting entity sets. For example - player-number and team-name is a key for Players.

Difference between Strong and Weak Entity Set

Sr. No. Strong entity set Weak entity set

1 It has its own primary key. It does not have sufficient attribute
to form a primary key on its own.

2. It is represented by rectangle It is represented by double

rectangle.

3. It represents the primary key It represents the partial key or

which is underlined. discriminator which is represented
by dashed underline.

4. The member of strong entity set The member of weak entity set is
is called as dominant entity set called subordinate entity set.

5. The relationship between two The relationship between strong

strong entity sets is represented entity set and weak entity set is
by diamond symbol. represented by double diamond
symbol.

6. The primary key is one of the The primary key of weak entity set
attributes which uniquely is a combination of partial key and
identifies its member. primary key of the strong entity
set.

Functional Dependencies
Definition : Let P and Q be sets of columns, then: P functionally determines Q, written P → Q if and
only if any two rows that are equal on (all the attributes in) P must be equal on (all the attributes in)
Q.

In other words, the functional dependency holds if

T1.P = T2.P, then T1.Q=T2.Q

Where notation T1.P projects the tuple T1 onto the attribute in P.

For example : Consider a relation in which the roll of the student and his/her name is stored as
follows :

R N

1 AAA

2 BBB

3 CCC

4 DDD

5 EEE

Table which holds functional dependency i.e. R->B

Here, R->N is true. That means the functional dependency holds true here. Because for every
assigned RollNuumber of student there will be unique name. For instance : The name of the Student
whose RollNo is 1 is AAA. But if we get two different names for the same roll number then that
means the table does not hold the functional dependency. Following is such table -

R N

1 AAA

2 BBB

3 CCC

1 XXX

2 YYY

Table which does not hold functional dependency

In above table for RollNumber 1 we are getting two different names - “AAA” and “XXX”. Hence here
it does not hold the functional dependency.

Computing Closure Set of Functional Dependency

The closure set is a set of all functional dependencies implied by a given set F. It is denoted by F+

The closure set of functional dependency can be computed using basic three rules which are also
called as Armstrong’s Axioms.
These are as follows -

i) Reflexivity : If X

ii) Augmentation : iv) Transitivity :

In addition to above axioms some additional rules for computing closure set of functional
dependency are as follows -

• Union :

• Decomposition :

Example 2.8.1 Compute the closure of the following set of functional dependencies for a relation
scheme R(A,B,C,D,E), F={A->BC, CD->E, B->D, E->A)

Solution : Consider F as follows

A->BC CD->E

B->D E->A

The closure can be written for each attribute of relation as follows

• (A)+ = Step 1 : {A} -> the attribute itself

Step 2 : {ABC} as A->BC

Step 3 : {ABCD} as B->D

Step 4 : {ABCDE} as CD->E

Step 5 : {ABCDE} as E->A and A is already present

Hence (A)+ ={ABCDE}

• (B)+ = Step 1:{B}

Step 2 : {BD} as B->D

Step 3 : {BD} as there is no BD pair on LHS of F

Hence (B)+ ={BD}

• (C)+ = Step 1 :{C}

Step 2 : {C} as there is no single C on LHS of F

Hence (C)+ ={C}

• (D)+ = Step 1 : {D}

Step 3 : {D} as there is no BD pair on LHS of F

Hence (D)+ ={D}

• (E)+ = Step 1 : {E}

Step 2 : {EA} as E->A

 Step 3 : {EABC} as A->BC

Step 4 : {EABCD} as B->D

Step 5 : {EABCD} as CD->E and E is already present

By rearranging we get {ABCDE}

Hence (E)+ ={ABCDE}

• (CD)+ = Step 1:{CD}

Step 2 :{CDE}

Step 3 :{CDEA}

Step 4 :{CDEAB}

By rearranging we get {ABCDE}

Hence (CD)+ ={ABCDE}

Example Compute the closure of the following set of functional

dependencies for a relation scheme R(A,B,C,D,E), F={A->BC, CD->E,
key. B->D, E->A) and Find the candidate

Solution : For finding the closure of functional dependencies - Refer example 2.8.1.

We can identify candidate from the given relation schema with the help of functional dependency.
For that purpose we need to compute the closure set of attribute. Now we will find out the closure
set which can completely identify the relation R(A,B,C,D).

Let, (A)+ = {ABCDE}

(B)+ = {BD}

(C)+ = {C}

(D)+ = {D}

(E)+ = {ABCDE}

(CD)+ = {ABCDE}

Clearly, only (A)+,(E)+ and (CD)+ gives us {ABCD} i.e. complete relation R. Hence these are the
candidate keys.

Canonical Cover or Minimal Cover

Formal Definition : A minimal cover for a set F of FDs is a set G of FDs such that :

1) Every dependency in G is of the form X->A, where A is a single attribute.

2) The closure F+ is equal to the closure G+.

 3) If we obtain a set H of dependencies from G by deleting one or more dependencies
or by deleting attributes from a dependency in G, then F+ H+.

Concept of Extraneous Attributes

Definition : An attribute of a functional dependency is said to be extraneous if we can remove it

without changing the closure of the set of functional dependencies. The formal definition of
extraneous attributes is as follows:

• Attribute A is extraneous in , and F logically implies (F – ∪ –

• Attribute A is extraneous in if A and the set of functional

dependencies (F – ∪ – A) } logically implies F.

Algorithm for computing Canonical Cover for set of functional Dependencies F

Fc = F repeat

Use the union rule to replace any dependencies in Fc of the form

/* The test for extraneous attributes is done using Fc, not F */

c .

until (Fc does not change)

Example 2.8.3 Consider the following functional dependencies over the attribute set R(ABCDE) for
finding minimal cover FD = {A->C, AC->D, B->ADE} Solution :

Step 1 : Split the FD such that R.H.S contain single attribute. Hence we get

A->C

AC->D

B->A

B->D

B->E

Step 2 : Find the redundant entries and delete them. This can be done as follows - o For A->C : We
find (A)+ by assuming that we delete A->C temporarily. We get (A)+={A}. Thus from A it is not possible
to obtain C by deleting A->C.

This means we can not delete A->C o For AC->D : We find (AC)+ by assuming that we delete AC->D
temporarily. We get (AC)+={AC}. Thus by such deletion it is not possible to obtain D. This means we
can not delete AC->D
 o For B->A : We find (B)+ by assuming that we delete B->A temporarily. We get
(B)+={BDE}. Thus by such deletion it is not possible to obtain A. This means we can not
delete B->A

o For B->D : We find (B)+ by assuming that we delete B->D temporarily. We get
(B)+={BEACD}. This shows clearly that even if we delete B->D we can obtain D. This
means we can delete B->A. Thus it is redundant.

o For B->E : We find (B)+ by assuming that we delete B->E temporarily. We get
(B)+={BDAC}. Thus by such deletion it is not possible to obtain E. This means we can
not delete B->E To summarize we get now

A->C

AC->D

B->A

B->E

Thus R.H.S gets simplified.

Step 3 : Now we will simplify L.H.S.

Consider AC->D. Here we can split A and C. For that we find closure set of A and C.

(A)+ = (AC)

(C)+ = (C)

Thus C can be obtained from both A as well as C. That also means we need not have to have AC on
L.H.S. Instead, only A can be allowed and C can be eliminated. Thus after simplification we get

A->D

To summarize we get now

A->C

A->D

B->A

B->E

Thus L.H.S gets simplified.

Step 3 : The simplified L.H.S. and R.H.S can be combined together to form

A->CD

B->AE

This is a minimal cover or Canonical cover of functional dependencies.

Non-loss Decomposition or Loss-less Join

The lossless join can be defined using following three conditions :

i) Union of attributes of R1 and R2 must be equal to attribute of R. Each attribute of R must be either
in R1 or in R2. Att(R1) Att(R2) = Att(R) ii) Intersection of attributes of R1 and R2 must not be NULL.
Att(R1) ∩ Att(R2) ≠ Φ

iii) Common attribute must be a key for at least one relation (R1 or R2) Att(R1) ∩ Att(R2) ->
Att(R1) or Att(R1) ∩ Att(R2) -> Att(R2)

Example 2.10.1 Consider the following relation R(A,B,C,D)and FDs A->BC, is the decomposition of R
into R1(A,B,C), R2(A,D). Check if the decomposition is lossless join or not.

Solution :

Step 1 : Here Att(R1) Att(R2) = Att(R) i.e R1(A,B,C) R2(A,D)=(A,B,C,D) i.e R. Thus first condition
gets satisfied.

Step 2 :
satisfied.

Step 3 : Att(R1) ∩ Att(R2) -> {A}. Now (A)+

satisfied.

This shows that the given decomposition is a lossless join.

Example Consider the following relation R(A,B,C,D,E,F) and FDs A->BC, C->A,
D->E, F->A, E->D is the decomposition of R into R1(A,C,D), R2(B,C,D),
and R3(E,F,D).
Check for
lossless.

Solution :

Step 1 : R1 R2 R3=R. Here the first condition for checking lossless join is satisfied as (A,C,D) (B,C,D)
(E,F,D)={A,B,C,D,E,F} which is nothing but R.

Step 2 :
gets satisfied.

Step 3 : Now, consider R1(A,C,D) and R2(B,C,D). We find R1∩R2={CD}

(CD)+ ossless join for R1 and

R2 gets satisfied.

Step 4 : Now, consider R2(B,C,D) and R3(E,F,D) . We find R2∩R3={D}.

(D)+={D,E} which is neither complete set of attributes of R2 or R3.[Note that F is missing for being
attribute of R3].

Hence it is not lossless join decomposition. Or in other words we can say it is a lossy
decomposition.
 Example 2.10.3 Suppose that we decompose schema R=(A,B,C,D,E) into (A,B,C) (C,D,E) Show that it
is not a lossless decomposition.

Solution :

Step 1 : Here we need to assume some data for the attributes A, B, C, D, and E. Using this data we
can represent the relation as follows –

Relation R

A B C D E

a 1 x p q

b 2 x r s

Relation R1 = (A,B,C)

A B C

a 1 x

b 2 x

Relation R2 = (C,D,E)

C D E

x p q

x r s

Step 2 : Now we will join these tables using natural join, i.e. the join
based on A B C D E common attribute C. We get R1 R2 as

a 1 x p q

a 1 x r s
Here we get more rows or tuples than original relation R

Clearly R1 R2 b 2 x p q R. Hence it is not lossless decomposition.

b 2 x r s

Normal Forms AU : Dec.-14, 15, May-18, Marks 16

• Normalization is the process of reorganizing data in a database so that it meets two

basic requirements:

1) There is no redundancy of data (all data is stored in only one place), and
 2) data dependencies are logical (all related data items are stored together)

• The normalization is important because it allows database to take up less disk space.

• It also help in increasing the performance.

First Normal Form

The table is said to be in 1NF if it follows following rules -

i) It should only have single (atomic) valued attributes/columns.

ii) Values stored in a column should be of the same domain iii) All the columns in a table
should have unique names. iv) And the order in which data is stored, does not matter. Consider
following Student table

Student

sid sname Phone

1 AAA 11111

22222

2 BBB 33333

3 CCC 44444

55555

As there are multiple values of phone number for sid 1 and 3, the above table is not in

1NF. We can make it in 1NF. The conversion is as follows -

sid sname Phone

1 AAA 11111

1 AAA 22222

2 BBB 33333

3 CCC 44444

3 CCC 55555

Second Normal Form

Before understanding the second normal form let us first discuss the concept of partial functional
dependency and prime and non prime attributes.

Concept of Partial Functional Dependency

Partial dependency means that a nonprime attribute is functionally dependent on part of a
candidate key.

For example : Consider a relation R(A,B,C,D) with functional dependency {AB->CD,A-

>C}

Here (AB) is a candidate key because

(AB)+ = {ABCD}={R}

Hence {A,B} are prime attributes and {C,D} are non prime attribute. In A->C, the non prime attribute
C is dependent upon A which is actually a part of candidate key AB. Hence due to A->C we get partial
functional dependency.

Prime and Non Prime Attributes

• Prime attribute : An attribute, which is a part of the candidate-key, is known as a

prime attribute.

• Non-prime attribute : An attribute, which is not a part of the prime-key, is said to be

a non-prime attribute.

• Example : Consider a Relation R={A,B,C,D} and candidate key as AB, the Prime
attributes : A, B

Non Prime attributes : C, D

The Second Normal Form

For a table to be in the Second Normal Form, following conditions must be followed i) It should be in
the First Normal form.

ii) It should not have partial functional dependency.

For example : Consider following table in which every information about a the Student is maintained
in a table such as student id(sid), student name(sname), course id(cid) and course name(cname).

Student_Course

sid sname cid cname

1 AAA 101 C

2 BBB 102 C++

3 CCC 101 C

4 DDD 103 Java

This table is not in 2NF. For converting above table to 2NF we must follow the following steps -

Step 1 : The above table is in 1NF.

Step 2 : Here sname and sid are associated similarly cid and cname are associated with each other.
Now if we delete a record with sid=2, then automatically the course C++ will also get deleted. Thus,
sid->sname or cid->cname is a partial functional dependency, because {sid,cid} should be
essentially a candidate key for above table. Hence to bring the above table to 2NF we must
decompose it as follows :

Student Here candidate key is

sid sname cid (sid,cid)
Course and
1 AAA 101
(sid,cid)->sname
2 BBB 102

Thus now table is in 2NF as 3 CCC 101 there is

no partial functional 4 DDD 103
dependency

cid cname
Here candidate key is
Third Normal Form 101 C cid

102 C++ Here cid->cname

Before understanding the third normal
101 C
form let us first discuss the
concept of transitive 103 Java
dependency, super key and candidate key

Concept of Transitive Dependency

A functional dependency is said to be transitive if it is indirectly formed by two functional

dependencies. For example -

X -> Z is a transitive dependency if the following functional dependencies hold true :

X->Y

Y->Z

Concept of Super key and Candidate Key

Superkey : A super key is a set or one of more columns (attributes) to uniquely identify rows in a
table.

Candidate key : The minimal set of attribute which can uniquely identify a tuple is known as
candidate key. For example consider following table

RegID RollNo Sname

101 1 AAA

102 2 BBB

103 3 CCC

104 4 DDD

Superkeys

• {RegID}
 • {RegID, RollNo}

• {RegID,Sname}

• {RollNo,Sname}

• {RegID, RollNo,Sname}

Candidate Keys

• {RegID}

• {RollNo}

Third Normal Form

A table is said to be in the Third Normal Form when,

i) It is in the Second Normal form.(i.e. it does not have partial functional dependency) ii) It doesn't
have transitive dependency.

Or in other words

In other words 3NF can be defined as : A table is in 3NF if it is in 2NF and for each functional
dependency X-> Y at least one of the following conditions hold : i) X is a super key of table ii) Y is a
prime attribute of table

For example : Consider following table Student_details as follows -

sid sname zipcode cityname state

1 AAA 11111 Pune Maharashtra

2 BBB 22222 Surat Gujarat

3 CCC 33333 Chennai Tamilnadu

4 DDD 44444 Jaipur Rajastan

5 EEE 55555 Mumbai Maharashtra

Here

Super keys : {sid},{sid,sname},{sid,sname,zipcode}, {sid,zipcode,cityname}… and so on.

Candidate keys : {sid}

Non-Prime attributes : {sname,zipcode,cityname,state} The dependencies can be denoted as

sid->sname sid->zipcode zipcode->cityname
cityname->state

The above denotes the transitive dependency. Hence above table is not in 3NF. We can convert it
into 3NF as follows :

Student
 sid sname zipcode

1 AAA 11111

2 BBB 22222

3 CCC 33333

4 DDD 44444

5 EEE 55555

Zip

zipcode cityname state

11111 Pune Maharashtra

22222 Surat Gujarat

33333 Chennai Tamilnadu

44444 Jaipur Rajasthan

55555 Mumbai Maharashtra

Example Consider the relation R = {A, B, C, D, E, F, G, H, I, J} and the set of cies F=

{{A, B} C, A {D, E}, B F, F {G, H}, D {I, J} } . What is the key for R ?
functional
Demonstrate it using the inference rules.
dependen
. Decompose R into 2NF, then 3NF relations.
1

Solution : Let,

As

Using union rule we get

As

we get

Using augmentation rule we compute AB

But

s also true

Similarly ∵

Thus now using union rule

The table can be converted to 2NF as

R1 = (A, B, C)

R2 = (A, D, E, I, J)

R3 = (B, F, G, H)

The above 2NF relations can be converted to 3NF as follows

R1 = (A, B, C)

R2 = (A, D, E)

R3 = (D, I, J)

R4 = (B, E)

R5 = (E, G, H).

University Questions

1. What is database normalization ? Explain the first normal form, second normal
form and third normal form. AU : May-18, Marks 13; Dec.-15, Marks
16

2. What are normal forms. Explain the types of normal form with an example.

AU :
Dec.-14, Marks 16

Dependency Preservation
• Definition : A Decomposition D = {R1, R2, R3….Rn} of R is dependency preserving for
a set F of Functional dependency if - (F1 F2 … Fm) = F.
 • If decomposition is not dependency-preserving, some dependency is lost in the
decomposition.

Example 2.10.4 Consider the relation R (A, B, C) for functional dependency set {A -> B and B -> C}
which is decomposed into two relations R1 = (A, C) and R2 = (B, C). Then check if this decomposition
dependency preserving or not.

Solution : This can be solved in following steps :

Step 1 : For checking whether the decomposition is dependency preserving or not we need to
check

following condition

F+ = (F1 F2)+

Step 2 : We have with us the F+ ={ A->B and B->C }

Step 3 : Let us find (F1)+ for relation R1 and (F2)+ for relation R2

R1(A,C) R2(B,C)

A->A Trivial B->B Trivial

C->C Trivial C->C Trivial

A->C In (F)+A->B->C and it is B->C In (F)+ B->C and it is Non-Trivial

Nontrivial AC->AC Trivial
BC->BC Trivial
A->B but is not useful as B is not part
We can not obtain C->B
of R1 set

We can not obtain C->A

Step 4 : We will eliminate all the trivial relations and useless relations. Hence we can obtain R1
and R2 as

R1(A,C) R2(B,C)

A->C Nontrivial

B->C Non-Trivial

(F1∪ F2)+ = {A->C, B->C} {A->B, B->C} i.e.(F)+

Thus the condition specified in step 1 i.e. F+=(F1 F2)+ is not true. Hence it is not dependency
preserving decomposition.
Example 2.10.5 Let relation R(A,B,C,D) be a relational schema with following functional
dependencies {A->B, B->C,C->D, and D->B}. The decomposition of R into (A,B), (B,C) and (B,D). Check
whether this decomposition is dependency preserving or not.

Solution :

Step 1 : Let (F)+ = {A->B, B->C, C->D,D->B}.

Step 2 : We will find (F1)+, (F2)+, (F3)+ for relations R1(A,B) , R2(B,C) and R3(B,D) as follows -

R1(A,B) R2(B,C) R3(B,D)

A->A Trivial B->B Trivial B->B Trivial

B->B Trivial C->C Trivial D->D Trivial

A->B ∵ (F)+ B->C ∵ (F)+ and it’s B-> D ∵ (F)+ as and

and it’s non Trivial non Trivial
B->C->D and it’s non
B->A can not be C->B ∵ In (F)+ and Trivial
obtained
C->D->C and it is D->B ∵ (F)+ and it’s
AB->AB Nontrivial non Trivial

BC->BC Trivial BD->BD Trivial

Step 3 : We will eliminate all the trivial relations and useless relations. Hence we can obtain R1 ∪
R2 ∪ R3 as

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

A->B B->C B-> D

C->B D->B

Step 4 : As from above FD’s we get

Step 5 : This proves that F =(F1 F3) . Hence given decomposition is

dependency preserving.

University Question

1. Differentiate between lossless join decomposition and dependency preserving decomposition.

Boyce / Codd Normal Form (BCNF)
Boyce and Codd Normal Form is a higher version of the Third Normal form. This form deals with
certain type of anomaly that is not handled by 3NF.

A 3NF table which does not have multiple overlapping candidate keys is said to be in BCNF.

Or in other words,

For a table to be in BCNF, following conditions must be satisfied : i) R must be in 3rd Normal Form

ii) For each functional dependency ( X → Y ), X should be a super Key. In simple words if Y is a prime
attribute then X can not be non prime attribute.

For example - Consider following table that represents that a Student enrollment for the course -

Enrollment Table

sid course Teacher

1 C Ankita

1 Java Poonam

2 C Ankita

3 C++ Supriya

4 C Archana

From above table following observations can be made :

• One student can enroll for multiple courses. For example student with sid=1 can enroll for C
as well as Java.

• For each course, a teacher is assigned to the student.

• There can be multiple teachers teaching one course for example course C can be taught by
both the teachers namely - Ankita and Archana.

• The candidate key for above table can be (sid,course), because using these two columns we
can find

• The above table holds following dependencies o (sid,course)->Teacher o Teacher->course

• The above table is not in BCNF because of the dependency teacher->course. Note that the
teacher is not a superkey or in other words, teacher is a non prime attribute and course is a
prime attribute and non-prime attribute derives the prime attribute.

• To convert the above table to BCNF we must decompose above table into Student and
Course tables

Student
 sid Teacher

1 Ankita

1 Poonam

2 Ankita

3 Supriya

4 Archana

Course

Teacher course

Ankita C

Poonam Java

Ankita C

Supriya C++

Archana C

Now the table is in BCNF

Example Consider a relation(A,B,C,D) having following FDs.{AB->C, AB->D, the

normal form of R.
C->A, B->D}.
Find out

Solution :

Step 1 : We will first find out the candidate key from the given FD.

(AB)+ = {ABCD} = R

(BC)+ = {ABCD} = R

(AC) + = {AC} R

There is no involvement of D on LHS of the FD rules. Hence D can not be part of any candidate key.
Thus we obtain two candidate keys (AB)+ and (BC)+. Hence prime attributes = {A,B,C}

Non prime attributes = {D}

Step 2 : Now, we will start checking from reverse manner, that means from BCNF, then 3NF, then
2NF.

Step 3 : For R being in BCNF for X->Y the X should be candidate key or super key.

From above FDs consider C->D in which C is not a candidate key or super key. Hence given relation
is not in BCNF.
 Step 4 : For R being in 3NF for X->Y either i) the X should be candidate key or super key or ii) Y
should be prime attribute. (For prime and non prime attributes refer step 1) o For AB->C or AB->D
the AB is a candidate key. Condition for 3NF is satisfied.

o Consider C->A. In this FD the C is not candidate key but A is a prime attribute.
Condition for 3NF is satisfied.

o Now consider B->D. In this FD, the B is not candidate key, similarly D is not a prime
attribute. Hence condition for 3NF fails over here. Hence given relation is not in 3NF.

Step 5 : For R being in 2NF following condition should not occur.

Let X->Y, if X is a proper subset of candidate key and Y is a non prime attribute. This is a case of
partial functional dependency.

For relation to be in 2NF there should not be any partial functional dependency.

o For AB->C or AB->D the AB is a complete candidate key. Condition for 2NF is
satisfied.

o Consider C->A. In this FD the C is not candidate key. Condition for 2NF is satisfied.

o Now consider B->D. In this FD, the B is a part of candidate key(AB or BC), similarly D
is not a prime attribute. That means partial functional dependency occurs here.
Hence condition for 2NF fails over here. Hence given relation is not in 2NF.

Therefore we can conclude that the given relation R is in 1NF.

Example 2.12.2 Consider a relation R(ABC) with following FD A->B, B->C and C->A.

What is the normal form of R ?

Solution :

Step 1 : We will find the candidate key

(A)+ = {ABC} =R (B)+ = {ABC} =R

(C)+ = {ABC} =R

Hence A, B and C all are candidate keys

Prime attributes = {A,B,C}

Non prime attribute{}

Step 2 : For R being in BCNF for X->Y the X should be candidate key or super key.

From above FDs o Consider A->B in which A is a candidate key or super key. Condition for BCNF is
satisfied. o Consider B->C in which B is a candidate key or super key. Condition for BCNF is satisfied.
o Consider C->A in which C is a candidate key or super key. Condition for

BCNF is satisfied.

This shows that the given relation R is in BCNF.

Example Prove that any relational schema with two attributes is in BCNF.
Solution : Here, we will consider R={A,B} i.e. a relational schema with two attributes. Now various
possible FDs are A->B, B->A.

From the above FDs o Consider A->B in which A is a candidate key or super key. Condition for BCNF
is satisfied.

o Consider B->A in which B is a candidate key or super key. Condition for BCNF is
satisfied.

o Consider both A->B and B->A with both A and B is candidate key or super key.
Condition for BCNF is satisfied. o No FD holds in relation R. In this {A,B} is candidate
key or super key. Still condition for BCNF is satisfied.

This shows that any relation R is in BCNF with two attributes.

Multivalued Dependencies and Fourth Normal Form

AU : May-14, Dec.-16, Marks 16

Concept of Multivalued Dependencies

• A table is said to have multi-valued dependency, if the following conditions are true,

1) For a dependency A multiple values of B exists, then

the table may have multi-values dependency.

2) Also, a table should have at-least 3 columns for it to have a multi-valued

dependency.

3) And, for a relation R(A,B,C), if there is a multi-valued dependency between, A and B,

then B and C should be independent of each other.

If all these conditions are true for any relation(table), it is said to have multi-valued dependency.

• In simple terms, if there are two columns A and B - and for column A if there are multiple
values of column B then we say that MVD exists between A and B

• The multivalued dependency is denoted by

• If there exists a multivalued dependency then the table is not in 4th normal form.

• For example : Consider following table for information about student

Student

sid Course Skill

1 C C++ English

German
 2 Java English

French

Here sid =1 leads to multiple values for courses and skill. Following table shows this

sid Course Skill

1 C English

1 C++ German

1 C German

1 C++ English

2 Java English

2 Java French

Here sid and course are dependent but the Course and Skill are independent. The multivalued
dependency is denoted as : sid Course sid Skill

Fourth Normal Form

Definition : For a table to satisfy the Fourth Normal Form, it should satisfy the following
two conditions :

1) It should be in the Boyce-Codd Normal Form(BCNF).

2) And, the table should not have any multi-valued dependency.

For example : Consider following student relation which is not in 4NF as it contains multivalued
dependency.

Student Table

sid Course Skill

1 C English

1 C++ German

1 C German

1 C++ English

2 Java English

2 Java French
Now to convert the above table to 4NF we must decompose the table into following two tables.

Student_Course Table

Key : (sid,Course)

sid Course

1 C

1 C++

2 Java

Student_Skill Table

Key : (sid,Skill)

sid Skill

1 English

1 German

2 English

2 French

Thus the tables are now in 4NF.

University Questions

1. Explain first normal form, second normal form, third normal form and BCNF
with example.

AU :
Dec.-16, Marks 13

2. Explain Boyce Codd Normal form and fourth normal form with suitable
example.

AU : May-14, Marks 16

Join Dependencies and Fifth Normal Form

Concept of Join Dependencies

o Join decomposition is a further generalization of Multivalued dependencies.

o If the join of R1 and R2 over C is equal to relation R, then we can say that a Join
Dependency (JD) exists.
 o Where R1 and R2 are the decompositions R1(A, B, C) and R2(C, D) of a given
relations R (A, B, C, D).

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

o A JD {R1, R2,..., Rn} is said to hold over a relation R if R1, R2,....., Rn is a lossless-
join decomposition.

o 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.

o Here, *(R1, R2, R3) is used to indicate that relation R1, R2, R3 and so on are a JD of
R.

Concept of Fifth Normal Form The database is said to be in 5NF if -

i) It is in 4th Normal Form

ii) If we can decompose table further to eliminate redundancy and anomalies and
when we rejoin the table we should not be losing the original data or get a new record(join
Dependency Principle)

The fifth normal form is also called as project join normal form

For example - Consider following table

Seller Company Product

Rupali Godrej Cinthol

Sharda Dabur Honey

Sharda Dabur HairOil

Sharda Dabur Rosewater

Sunil Amul Icecream

Sunil Britania Biscuits

Here we assume the keys as{Seller, Company, Product}

The above table has multivalued dependency as

Seller {Company, Product}. Hence table is not in 4th Normal Form. To make the above table in 4th
normal form we decompose above table into two tables as

Seller_Company
Seller Company Seller Product

Rupali Godrej Rupali Cinthol

Sharda Dabur Sharda Honey

Seller_Product
 Sunil Amul Sharda HairOil

Sunil Britania Sharda RoseWater

Sunil Icecream

Sunil Biscuits

is not in 5 th normal form because if we join the above two table we may get
Seller Company Product
Rupali Godrej Cinthol
Sharda Dabur Honey
Sharda Dabur HairOil
Sharda Dabur Rosewater
Sunil Amul Icecream
Sunil Amul Biscuits
Sunil Britania Icecream
Sunil Britania Biscuits
Newly added records
which are not present in
original table

To avoid the above problem we can decompose the tables into three tables as
The above table is in 4th Normal Form as there is no multivalued dependency. But it

Seller_Company, Seller_Product, and Company Product table

Seller_Company
Seller_Product Seller Product Company Product
Company_Product
Rupali Cinthol Godrej Cinthol

Sharda Honey Dabur Honey

Sharda HairOil Dabur HairOil

Sharda RoseWater Dabur RoseWater

Sunil Icecream Amul Icecream

Thus the table in in 5th normal Sunil Biscuit Britania Biscuit form.
Seller Company

Rupali Godrej

Sharda Dabur

Sunil Amul

Sunil Britania