## Exercises on Normalization, Indexing and Tuning

Read carefully the topics under Normalization (keys, normal forms, etc) discussed in this blog for answering Section A.

__SECTION A__
Q1. Consider the following schema STUDENT;

STUDENT( RegNo, SName, DOB, Advisor,
DeptNo, Semester, CoruseCode, Grade )

Assume that the table satisfies
the following set of functional dependencies:

RegNo → SName DOB Advisor DeptNo

Advisor → DeptNo

RegNo DeptNo CourseCode Semester → Grade

a) Is the table STUDENT in 3NF?

b) If your answer is NO, then perform decomposition to develop
3NF normalized tables.

Q2. Assume that the relation
schema R (A, B, C, D, E, F, G, H) holds the following set of functional
dependencies:

(1) AB → C,

(2) C → F

(3) DE → CF

(4) E → G

(5) G → D

a) Explain why the relation is not in 3NF?

b) Convert R into 3NF.

Q3. Consider
the following relation R (A,B,C,D,E,F) with the following functional dependencies:

(1) CDE → A

(2) DEF → B

(3) AEF → C

(4) B → A

(5) C → D

a)
What are the candidate keys of R?

b) Is the given relation in 2NF?

Q4. Assume
a relation R(A, B, C, D, E) with the following functional dependencies:

(1) A → BC

(2) C → A

(3) E → A

(4) B→ D

a)
What are the candidate keys for R?

b) Normalize the table into 3NF.

Q5. Write and explain the steps of an algorithm for finding Primary key of any relation.

__SECTION B__
Q1. Consider the following query
which is important and frequent query. This simple query is executed slowly due
to some reasons. Assume that the Employee table has a non-clustering index on Age
attribute. Identify the reason and rectify the problem in executing the given
query.

SELECT * FROM
Employee WHERE Age/2=30;

Q2. Why do we need to avoid
Indexes on small relations?

Q3. Consider a relation schema Student(

__RegNo__, SName, Age, Gender, Branch) where Primary key attribute is underlined. For the following query on this relation what would be wrong? Write your reasons.
SELECT DISTINCT RegNo
FROM Student WHERE Branch = ‘CSE’;

Q4. Let relations r1(A, B,C) and
r2(C, D, E) have the following properties: r1 has 20,000 tuples, r2 has 45,000
tuples, 25 tuples of r1 fit on one disk block, and 30 tuples of r2 fit on one disk
block. Assume that the size of the memory is less than or equal to the size of
relation r. Estimate the number of block transfers and seeks required using nested
loop join strategy for r1 and r2.

Q5. Assume a relation Employee(

__EmpNo__, Name, Dept, Address, Salary) with 500,000 tuples. Each disk block can hold upto 20 records, or 40 index entries. The index is built on the primary key field EmpNo of the relation and the file is sorted according to the key. Answer the following questions.
1. For having a dense index on
the key of this relation, how many disk blocks we need?

2. For having a sparse index on
the key of the relation, how many disk blocks do we need?

“He, who
learns but does not think, is lost! He who thinks but does not learn is in
great danger.”Confucius |