Exercises - Normalization, Indexing and Tuning

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