Homework 4
CS3010301, Spring 2025

Due: Friday, June 5, 2026.

Please turn in an electronic copy of your solutions (in PDF, HTML, or MS DOC format) on Moodle. Everything has to be typed and submitted electronically.

---

0. Read Chapter 14, 17, 18, 20, 21 and 22 of the textbook.

1.(15pt) Exercise 14.24.

2.(15pt) Exercise 14.27.

3.(15pt) Exercise 14.30.

4. (20%) Suppose you are given a relation R with four attributes ABCD. For each of the following sets of FDs, assuming those are the only dependencies that hold for R, do the following: (a) Identify the candidate key(s) for R. (b) Identify the best normal form that R satisfies (1NF, 2NF, 3NF, or BCNF). (c) If R is not in BCNF, decompose it into a set of BCNF relations that preserve the dependencies.

a. C → D, C → A, B → C

b. AB → C, AB → D, C → A, D → B

5.(20pt) Exercise 22.27.

6. (15pt) Consider the following SQL query:

SELECT P.Pname, E.Fname, E.Lname

FROM EMPLOYEE E, PROJECT P, WORK_ON W

WHERE W.Hours < 40 AND E.Ssn = W.Essn AND W.Pno = P.Pnumber AND E.Sex = ‘F’;

(a) (5%) Draw the query graph.

(b) (5%) Draw the initial query tree.

(c) (5%) Draw the optimized query tree using heuristic optimization.