B.

Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

UNIT – III RELATIONAL DATABASE DESIGN & NORMALIZATION

ER and EER- to- Relational mapping – Update anomalies – Functional Dependencies –
Inference rules – Minimal Cover – Properties of relational – Normalization ( up to BCNF )

Two Marks

1.What are the problems caused by redundancy?

Problems caused by Redundancy: Following problems can be caused by

redundancy -

i. Redundant Storage: Some information is stored repeatedly.

ii. Update Anomalies: If one copy of such repeated data is updated then
inconsistency is created unless all other copies are similarly updated.
iii. Insertion Anomalies: Due to insertion of new record repeated
information get added to the relation schema.
iv. Deletion Anomalies: Due to deletion of particular record some other
important information associated with the deleted record get deleted and
thus we may lose some other important information from the schema.

2.Define functional dependency.

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
TI.P = T2.P, then TI.Q = T2Q
Where notation T1.P projects the tuple TI onto the attribute in P.

3 .Why certain functional dependencies are called trivial functional

dependencies?

 A functional dependency FD:XY is called trivial if Y is a subset of X.

This kind of dependency is called trivial because it can be derived from
conumon sense. If one "side" is a subset of the other, it's considered
trivial. The left side is considered the determinant and the right the
dependent.

1
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

 For example (A,B) B is a trivial functional dependency because B is a

subset of AB Since (A,B) B includes B, the value of 8 can be
determined. It's a trivial functional dependency because determining B is
satisfied by its relationship to A,B

4.Define inference rules (Armstrong’s Axioms)

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 all functional dependency can be computed using basic
three rules which are also called as Armstrong's Axioms

5.Define Minimal cover.

A set of functional dependencies E is said to covered by F if every FD in

Eis Ft. Le every dependency in F can be inferred from E and vice versa.
Two sets of FDs E and F are equivalent if E-F
If E and F are equivalent only if both E-P
1) E covers F 2) F covers Eholds

4.Define normalization.

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
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

2) data dependencies are logical (all related data items are stored
together)

5.State anomalies of INF.

All the insertion, deletion and update anomalies are in INF relation.

Define First Normal Form

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

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

 Values stored in a column should be of the same domain
 All the columns in a table should have unique names.
 And the order in which data is stored, does not matter.

6.Write about 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

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

8.Give the Concept of Transitive Dependency

A functional dependency is said to be transitive if it is indirectly formed
by two functional dependencies.For exampe

3
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

For example - X Z is a transitive dependency if the following functional

dependencies hold true:
XY
YZ
8.Give 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.

9.Write about 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

11.Define 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.
For a table to be in BCNF, following conditions must be satisfied:
i) R must be in 3rd Nohnal Form
ii) For each functional dependency ( X ~ Y ), X should be a
super Key.

4
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

In simple words if Y is a prime attribute then X can not be non

prime

12. Show that if a relation is in BCNF, then it is also in 3NF.

 Boyce and Codd Normal Form is a higher version of the Third Normal
form.
 A 3NF table which does not have multiple overlapping candidate keys is
said to be in BCNF.
When the table is in BCNF then it doesn't have partial functional
dependency as well as transitive dependency.
Hence it is true that if relation is in BCNF then it is also in 3NF.

13.What is decomposition? or Properties of Relational Decomposition

Decomposition is the process of breaking down one table into multiple

tables.
Formal definition of decomposition is.
A decomposition of relation schema R consists of replacing the relation
schema by two relation schema that each contain a subset of attributes
of R. and together include all attributes of R by storing projections of the
instance.

14.Why it is necessary to decompose a relation?

Decomposition is the process of breaking down one table into multiple

tables
The decomposition is used for eliminating redundancy.

15.Explain at least two desirable properties of decomposition.

There are two properties associated with decomposition and those are-

1) Loss-less Join or non Loss Decomposition: When all information

found in the original database is preserved after decomposition, we call it
as loss less or non loss decomposition.

2) Dependency Preservation: This is a property in which the

constraints on the original table can be maintained by simply enforcing
some constraints on each of the smaller relations.
5
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

16.Define 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.
For a table to be in BCNF, following conditions must be satisfied:
iii) R must be in 3rd Nohnal Form
iv) 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

17.What is the differences between 3NF and BCNF?

Sr.No 3NF BCNF
1 3NF stands for Third Normal Form. CNF stands for Boyce Codd Normal
Form.

2 he table is in 3NF if it is in 2NF and for he table is in BCNF if it is in 3rd

each functional dependency X->Y at normal form and for each relation X-
least following condition hold: >Y X should be super key.
(i) X is a superkey,
(ii) Y is prime attribute of table.

3 3NF can be obtained without sacrificing all Dependencies may not be preserved
dependencies. BCNF.

4 Lossless decomposition can be achieved Lossless decomposition is hard to

in 3NF. obtain in BCNF.

5 3NF can be achieved without loosing any For obtaining BCNF we may loose
information from the old table. some information from old table.

6
 B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Part A & B Questions

1. Discuss the corresponding between the ER model construct and the
relational model constructs. Show how each ER model construct can be
mapped to the relational model. Discuss the option for mapping EER
model.

I. Mapping of Entity Set to Relationship

 An entity set is mapped to a relation in a straightforward way.

 Each attribute of entity set becomes an attribute of the table.
 The primary key attribute of entity set becomes an entity of the table.
 For example - Consider following ER diagram.

The converted employee table is as follows

The SQL statement captures the information for above ER diageam as follows-

CREATE TABLE Employee EmpID CHAR(11),

EName CHAR(30),
Salary INTEGER,
PRIMARY KEY(EmpID))

7
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

II.Mapping Relationship Sets(without Constraints) to Tables

 Create a table for the relationship set.

 Add all primary keys of the participating entity sets as fields of the table.
 Add a field for each attribute of the relationship.
 Declare a primary key using all key fields from the entity sets
 Declare foreign key constraints for all these fields from the entity sets.

For example - Consider following ER model

The SQL statement captures the information for relationship present in above
ER diagram as follows-

CREATE TABLE Works_In (EmpID CHAR(11).

DeptID CHAR(11).
EName CHAR(30),
Salary INTEGER,
DeptName CHAR(20),
Building CHAR(10).
PRIMARY KEY(EmpID,DeptID),
FOREIGN KEY (EmpID) REFERENCES Employee,
FOREIGN KEY (DeptID) REFERENCES Department
)

III.Mapping Relationship Sets (With Constraints) to Tables

 If a relationship set involves n entity sets and some m of them are linked
via arrows in the ER diagram, the key for anyone of these m entity sets
constitutes a key for the relation to which the relationship set is mapped.
 Hence we have m candidate keys, and one of these should be designated
as the primary key.
 There are two approaches used to convert a relationship sets with key
constraints into table.

 Approach 1:

8
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

By this approach the relationship associated with more than one entities
is separately represented using a table. For example - Consider following
ER diagram. Each Dept has at most one manager, according to the key
constraint on Manages.

Here the constraint is each department has at the most one manager to manage
it Hence no two tuples can have same DeptID. Hence there can be a separate
table named Manages with DeptID as Primary Key. The table can be defined
using following SQL statement

CREATE TABLE Manages (EmpID CHAR(11),

Since DATE,
DeptID INTEGER, PRIMARY KEY(DeptID),
FOREIGN KEY (EmpID) REFERENCES Employees,
FOREIGN KEY (DeptID) REFERENCES Departments)

Approach 2:

o In this approach, it is preferred to translate a relationship set with key

constraints.

o It is a superior approach because, it avoids creating a distinct table for the

relationship set.

o The idea is to include the information about the relationship set in the
table corresponding to the entity set with the key, taking advantage of the
key constraint.

o This approach eliminates the need for a separate Manages relation, and
queries asking for a department's manager can be answered without
combining information from two relations.

o The only drawback to this approach is that space could be wasted if several
departments have no managers.

9
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

o The following SQL statement, defining a Dep_Mgr relation that captures

the information in both Departments and Manages, illustrates the second
approach to translating relationship sets with key constraints:

CREATE TABLE Dep_Mgr (DeptID INTEGER,

DName CHAR(20),
Budget REAL,
EmpID CHAR (11),
since DATE,
PRIMARY KEY (DeptID),
FOREIGN KEY (EmpID) REFERENCES Employees)

IV.Mapping Weak Entity Sets to Relational Mapping

A weak entity can be identified uniquely only by considering the primary key of
der (owner) entity. Following steps are used for mapping Weka Entity Set to
Relational Mapping

 Create a table for the weak entity set.

 Make each attribute of the weak entity set a field of the table.
 Add fields for the primary key attributes of the identifying owner.
 Declare a foreign key constraint on these identifying owner fields.
 Instruct the system to automatically delete any tuples in the table for
which there are no owners

For Example-Consider following ER model

Following SQL. Statement illustrates this mapping

CREATE TABLE Department (DeptID CHAR(11),

DeptName CHAR(20). Bldg_No CHAR(5),

10
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

PRIMARY KEY (DeptID, Bldg No),

FOREIGN KEY(Bldg_No) References Buildings on delete cascade
)

V.Mapping of Specialization / Generalization (EER Construct) to Mapping

The Specialization / Generalization relationship(Enhanced ER Construct) can be

mapped to database tables(relations) using three using three methods. To
demonstrate the methods, we will take the-Inventoryltem, Book, DVD

Method 1: All the entities in the relationship are mapped to individual tables

InventoryItem(ID, name)
Book(ID Publisher)
DVD(ID, Manufacturer)

Method 2: Only subclasses are mapped to tables. The attributes in the superdas
are duplicated in all subclasses. For example-

Book(ID name Publisher)

DVD(ID, name, Manufacturer)

Method 3: Only the superclass is mapped to a table. The attributes in the

subclasses are taken to the superclass. For example-

Inventoryitem(ID, name, Publisher Manufacturer)

This method will introduce null values. When we insert a Book record in the
table the Manufacturer column value will be null. In the same way, when we
insert a DVD record in the table, the Publisher value will be null.

11
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

2.Write about Update Anomalies in detail

Definition: Redundancy is a condition created in database in which same

piece
of data is held at two different places.

Redundancy is at the root of several problems associated with

relational schemas.

Problems caused by redundancy

Following problems can be caused by redundancy-

i. Redundant storage: Some information is stored

repeatedly.

ii. Update anomalies: If one copies of such repeated data is

updated then inconsistency is created unless all other copies
are similarly updated.

iii. Insertion anomalies: Due to insertion of new record repeated

information get added to the relation schema.

iv. Deletion anomalies: Due to deletion of particular record

some other important information associated with the deleted
record get deleted and thus we may lose some other important
information from the schema.

Example

Following example illustrates the above discussed anomalies of

redundancy problems Consider following Schema in which all possible
information about Employee stored.


Redundancy
1) Redundant storage: Note that the information about DeptID, DeptName and
Deptloc is repeated.

12
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

2) Update anomalies:
In above table if we change DeptLoc of Pune to Chenna then
it will result inconsistency as for DeptID 101 the DeptLoc is
Pune. G otherwise, we need to update multiple copies of
DeptLoc from Pune to Chennai Hence this is an update
anomaly.

3) Insertion anomalies:
For above table if we want to add new tuple say (5,
EEE,50000) for DeptID 101 then it will cause repeated
information of (101, XYZ, Pune) will occur.

4) Deletion anomalies:
For above table, if we delete a record for EmpID 4, then
automatically information about the DeptID 102, DeptName
PQR and Deptloc Mumbai will get deleted and one may not be
aware about DeptID 102. This causes deletion anomaly.
--------------------------------------------------------------------------------------------------------
3.Discuss about Functional Dependencies with an example

Definition:
A functional dependency A->B in a relation holds if two tuples
having same value of attribute A also have the same value for
attribute B. It is denoted by A>B where A is called determinant and
B is called dependent.

For Example-Consider Student table as follows-

Roll Name City

1 AAA Mumbai
2 BBB Pune
3 CCC Gandhinagar

Here

Roll->Name hold
But
Name->City does not hold

 In above table, student roll number is unique hence each student's

name and city can be uniquely identified using his roll number.

13
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

 But using name we cannot uniquely identify his/her city because

there can be same names of the students. Similarly using city name
we can not identify the student uniquely. As in the same city may
belong to multiple students.

Another 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->N

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

Trivial FD:
The functional dependency A>B is trivial if B is a subset of A.
For example {A,B}->A

Non Trivial FD:

The functional dependency AB is non trivial if B is not a subset of A
For example {A.B}->C

14
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Example

For the given below relation R(A,B,C,D,E) and its instance, check whether FDs
given hold or not. Give reasons.

i)A->B ii) B->C iii) D->E iv) CD->E

A B C D E

a1 b1 c1 d1 e1

a1 b2 c1 d1 e1

a2 b2 c1 d2 e3

a2 b3 c3 d2 e2

Solution: Association among attributes is known as Functional Dependencies

(FD). AFD XY require that the value of X uniquely determines the value of Y
where X and Y are se of attributes.

For example,

Roll_No ->Name: the value of Roll_No uniquely determines the Name.

Now from, the given relation and its instance -

i. The FD A>B does not hold because al has two different values bl and b2.
Similarly, a2 has two different values and those are b2 and b3.
ii. The FD B->C holds true.
iii. D->E does not hold true because d2 gives two different values e3 and e2.
iv. CD->E hold true as (cl,d1) gives el, (cl,d2) gives e3 and (c3,d2) gives e2. All
are uniquely identified.

15
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

4.Explain about the Inference Rules (Armstrong's Axioms) in Functional

Dependencies with an example

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 all functional dependency can be computed using basic
three rules which are also called as Armstrong's

Let us understand how to apply Armstrong's axioms for finding the closure
of set of functional dependencies-

Example -1

Given FD's for relation R{A,B,C,D,E,F}, Find closure of FD set by applying

Armstrong's Axioms.

AB, AC, CDE, CDF, BE

Solution:

Step1:
A  gives A attribute itself by reflexivity. It is called trivial production.
A B and AC, Hence by union rule A BC
AB and B E, Hence by transitivity rule A  E
(A)+={A,B,C,E}

Step2: B gives B itself And B E

 (B)+= (B,E)

Step 3: CD gives CD itself. It is trivial.

CDE, CD F, Hence by union rule CD EF

16
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

 (CD)+= {C,D,E,F}

So by omitting trivial productions, we get

F+={ABC, AE, BE, CD EF}

Example -2

Compute the closure of the following set F of functional dependencies for

relational schema R = {A,B,C,D,E} ABC, CDE, BD, E→A

Solution: The closure of F is denoted by F' and it can be computed in

following steps

Step 1: As ABC is given we get

A Band AC By decomposition rule

Step 2: As

AB (Refer step 1)

BD (given)
AD (transitivity rule)

Step 3:

ACD because A C and A D (From step 1 and Step 2 applying

union rule)

Step 4:

CDE (given)
A E (transitive rule as ACD,
CDE hence AE)

Step 5:

Since AA, we have (reflexive) from the above

steps(union)
AABCDE

Step 6:

Since EA, E ABCDE (transitive)

17
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Step 7:

Since CDE, CDABCDE (transitive)

Step 8:

Since BD and BCCD, BC ABCDE (augmentative, transitive)

Step 9:

Also, CC, DD, BDD

Thus any functional dependency with A, E, BC, or CD on the left hand side
of the arrow is in F+

Example-3

Give Armstrong's axioms and using it find the closure of following FD set
AB, ABC, DAC, DE

Solution

Step 1:
Consider the rules DAC and DE
D →ACE (Union rule)

Step 2: Consider AB C then we get

A Cand B→C (decomposition rule)

Thus F+ ={AC, BC,D ACE}

18
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

5.Explain about Normalization in detail

o Normalization is the process of reorganizing data in a database

so that it
o 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.
o The normalization is important because it allows database
to take up
less disk space.
o It also helps in increasing the performance.

1.First Normal Form

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

 It should only have single (atomic) valued

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

sid sname Phone

11111
1 AAA
22222
2 BBB 33333
44444
3 CCC
55555
Student

As there are multiple values of phone number for sid 1 and 3,

the above table is not in INF. We can make it in 1NF. The
conversion is as follows –

19
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

sid snam Phon

e e
1 AAA 1111
1
1 AAA 2222
2
2 BBB 3333
3
3 CCC 4444
4
3 CCC 5555
5

2.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}
nce (A.B) are prime attributes and (C,D) are non prime
attribute. In AC, the no prime attribute C is dependent upon A
which is actually a part of candidate key A 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

20
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

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

sid snam cid cnam

e e
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 INF.
Step 2: Here sname and sid are associated similarly cid and
ename 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
sid sname cid
1 AAA 101
2 BBB 102
--> Here candidate key is (sid,cid)
3 CCC 101
4 DDD 103
Course
cid cname
101 C
102 C++
101 C Here candidate key is cid
103 Java

21
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

6. Explain the Third Before Normal Form in detail

Before understanding the third normal form let us first discuss the concept of
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 exampe

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

22
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

{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:

23
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Student

zipcode cityname state

11111 Pune Maharashtra
22222 Surat Gujarat
33333 Chennai Tamilnadu
44444 Jaipur Rajastan
55555 Mumbai Maharashtra
zip

sid sname zipcode

1 AAA 11111
2 BBB 22222
3 CCC 33333
4 DDD 44444
5 EEE 55555

7. Give the concept about 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:

a. R must be in 3rd Normal Form

b. For each functional dependency (XY), 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-

24
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Enrollment Table

sid course Teacher

1 C Arun
1 Java Ankita
2 C Arun
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

25
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

sid Teacher
1 Arun
1 Ankita
2 Arun
3 Supriya
4 Archana

Teacher course
Arun C
Ankita Java
Arun C
Supriya C++
Archana C

26
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

8. Write about Properties of Relational Decomposition with an example

Decomposition is the process of breaking down one table into multiple tables.

Formal definition of decomposition is-

A decomposition of relation schema R consists of replacing the relation schema

by two relation schema that each contain a subset of attributes of R and
together include all attributes of R by storing projections of the instance.

• For example-Consider the following table

Eid Ename Age City Salary Debtid Depname

E001 Arun 29 Pune 20000 D001 Finance

E002 Balu 30 Pune 30000 D002 Prodution

E003 Dinesh 25 Mumbai 5000 D003 Sales

E004 Exhil 24 Mumbai 4000 D004 Marketing

E005 Faruk 32 Hyderabad 25000 D005 Human

Resource

We can decompose the above relation Schema into two relation schemas as
Employee (Eid, Ename, Age, City, Salary) and Department (Deptid, Eid,
DeptName) as follows

Eid Ename Age City Salary

E001 Arun 29 Pune 20000

E002 Balu 30 Pune 30000

27
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

E003 Dinesh 25 Mumbai 5000

E004 Exhil 24 Mumbai 4000

E005 Faruk 32 Hyderabad 25000

Department Table
Debtid Eid Depname

D001 E001 Finance

D002 E002 Prodution

D003 E003 Sales

D004 E004 Marketing

D005 E005 Human

Resource

The decomposition is used for eliminating redundancy.

For example:
consider following relation Schema R in which we assume that the grade
determines the salary, the redundancy is caused
Schema R

28
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

Hence, the above table can be decomposed into two schema S and T as follow
Schema S
Name eid deptname Grade

AAA 121 ACCOUNTS 2

AAA 132 SALES 3

BBB 101 MARKETING 4

CCC 106 PURCHASE 2

Schema T
Grade Salary

2 8000

3 7000

4 7000

2 8000

Problems related to decomposition:

Following are the potential problems to consider:

1. Some queries become more expensive.

2. Given instances of the decomposed relations, we may not be able
to reconstruct the corresponding instance of the original relation!
3. Checking some dependencies may require joining the instances of
the decomposed relations
4. There may be loss of information during decomposition.

Properties associated with decomposition

There are two properties associated with decomposition and those are-
1) Loss-less join or non-loss decomposition:

29
B.Tech – AIDS II year/III Sem AD3391 DBDM –Unit-III

When all information found in the original database is preserved after

decomposition, we call it as loss less or non loss decomposition.

2) Dependency preservation:

This is a property in which the constraints on the original table can be

maintained by simply enforcing some constraints on each of the smaller
relations.

Lossless 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) U Att(R2) = Att(R)

ii) Intersection of attributes of R1 and R2 must not be NULL

30