NYU Tandon School of Engineering

CS-GY 6083, Principles of Database Systems, Spring 2024 Prof Phyllis Frankl

HOMEWORK #4

Problem 1

Suppose we design a database with only one table schema as shown below to model the payroll system for a company

Payroll(eID, dept, position, month, year, branchID, wage, hoursWorked, branchCity, branchState)

We have the following detailed specifications for the database system:

Branches are identified by a branchID, besides, the system also records associated branchCity and branchState information. Employees are identified by an eID, also necessary information like department the employee is working for (dept), current position in the department and working for which branch (branchID) is recorded. Any employees with the same position have the same wage. Besides, the system also records the hours worked by each employee in each month of each year, and no employee changes department, working branch, or position during the period covered by any payroll table.

1. Write the following SQL queries:

a. Count the number of employees who work for branches in Brooklyn, NY.

b. Select the employee and correspondent working hours in March, 2024 with the

highest total wage (hoursWorked * wage)

c. Output the average salary of each department. (You may get the average salary

of each employee throughout this employee’s career first)

2. Give an example of a trivial functional dependency in this schema. (Recall that a functional dependency alpha α → β is trivial if β ⊆ α )

3. List the functional dependencies corresponding to each of the following parts of the data description:

a. Branches are identified by a branchID, besides, the system also records associated branchCity and branchState information

b. Besides, the system also records the hours worked by each employee in each month of each year.

c. No employee changes department, working branch, or position during the period covered by any payroll table.

4. Derive a collection F of functional dependencies such that F+ is the closure of the set of functional dependencies implied by the description of the data. F+ should include the functional dependencies in (3) and any others that are implied by the textual description of the data.

 5. Is your answer to (4) a canonical cover? If not, simplify it to derive a canonical cover.

6. Derive all candidate keys for this table.

7. Show that the Payroll schema is not in BCNF

8. Decompose Payroll into a collection of schemas each of which is in BCNF. Show your

work.

9. Illustrate that your decomposition is a lossless join decomposition as follows:

a. Show a table on Payroll with a few rows of data including some redundancy due to the functional dependencies

b. Project your table onto the decomposed schemas (showing tables on each of the decomposed schemas)

c. Join them back together and comment on whether they are the same as the origins table

[This does not prove that the decomposition is a lossless join, but will

demonstrate some understanding of the concept]

10. Is the decomposition in (8) dependency-preserving? Why or why not?

11. Rewrite the queries in (1) using the decomposed database schema in (7).

12. Suppose the company updated its wage system, now the wage will depend on position,

the branch city, and the branch state.

a. Write a functional dependency that characterizes this

b. Which of the original functional dependencies from (5) no longer hold?

c. Is your result in (8) still dependency-preserving? Justify your answer.

d. Optionally, decompose Payroll into a collection of schemas that are in 3NF and

compare the pros and cons of this decomposition, compared to the one in (8). This is not for extra credit, just for practice with 3NF if you’re interested.

Problem 2

Suppose we have a B+ tree of order 6, with the following initialized situation: The root is node R.

Node R has two children: A and B.

A has four children: C, D, E, F

B has three children: G, H, I Key values:

R: 42

A: 32,35,38

B: 50,56

C: 10,22,30

D: 32,33,34

E: 35,36,37

F: 38,39,41

G: 42,43,44,47,49 H: 50,54,55

I: 56,70,90

 Describe the tree after each of the following operations. Please highlight the changes (or only describe/show the changes) to make it easier for the grader to check your work. For example, if you're splitting node F, you could say "split node F into F and F'. Node F has keys ... and F' has keys ..." You must use the algorithms presented in the textbook/lecture 10

1. Insert 48

2. Insert 51 and then Insert 52

Suppose the tree now becomes: Node R has two children: A and B. A has four children: C, D, E, F

B has six children: G, H, I, J, K, L

R: 42

A: 32,35,38

B: 47,50,53,56,78

C: 10,22,30

D: 32,33,34

E: 35,36,37

F: 38,39,41

G: 42,43,44,45,46

H: 47,48,49

I: 50,51,52

J: 53,54,55

K: 56,59,62,66,70

L: 78,84,90

Similar to the previous question, show the tree after each of the following operations:

1. Insert 63

2. Delete 62

3. Delete 46 then delete 55