SDSC5003 - Question of Assignment 2

#assignment #sdsc5003

原文

NOTE: The university policy on academic dishonesty and plagiarism (cheating) will be taken very seriously in this course. Everything submitted should be your own writing or coding. You must not let other students copy your work. Discussions of the assignment are okay, e.g. understanding the concepts involved. This assignment is an individual one. Upload your work as a single archive file with name A2-XXXX-YYYY.zip where XXXX is your name and YYYY is your student ID. Remember to include all files in the archive file.

---

Part I. Relational Algebra (35 points)

Consider the following relational schema:

• Emp(eid: integer, ename: string, age: integer, salary: real)

• Works(eid: integer, did: integer, pct_time: integer)

• Dept(did: integer, dname: string, budget: real, managerid: integer)

Write the following queries in relational algebra:

a. Print the names and ages of each employee who works in both the Hardware department and the Software department. (7 points)
b. Print the name of each employee whose salary exceeds the budget of all the departments that he or she works in. To illustrate, if the employee works in 3 departments, whose budgets are 1000, 2000 and 3000 respectively, then the maximum budget of all the departments that he/she works in is 3000. (7 points)
c. Find the ename, age of managers who manage only departments with budgets greater than $1 million. (7 points)
d. Find the enames of managers who manage the departments with the greatest budgets. To illustrate, suppose there are three departments like this: department 1 with a budget of $1 million, department 2 with a budget of $2 million, department 3 with a budget of $2 million. Then departments 2 and 3 have the greatest budgets. (14 points)

---

Part II. SQL Queries (40 points)

Copy all SQL queries into one SQL file called part2.sql. For each query, please provide the comment as -- part2a for the first query.
All screenshots should be submitted together as a single PDF file called part2.pdf.
Upload your submissions as a single archive file called part2.zip.

Consider the relational schema for company in Part I, write SQL queries for each request in Part I and one extra request in the following. Your queries should be executable in SQLite.

In this part, you also need to use the “A2.db” (please download “A2.db” from course files) database in DB Browser for SQLite to give a screenshot for each query’s result.

a. Corresponding to Part I-a (8 points)
b. Corresponding to Part I-b (6 points)
c. Corresponding to Part I-c (7 points)
d. Corresponding to Part I-d (9 points)
e. For each department with more than 20 full-time-equivalent employees (i.e., the total pct_time of the part-time and full-time employees add up to at least 2000 hrs, assuming that the pct_time of a full-time employee is 100 hrs), print the did together with the number of employees that work in that department. (10 points)

---

Part III. Design Theory (25 points)

Suppose we have a relation schema $R(A1,A2,A3,A4)$ with Functional Dependencies (FDs):

1. $A3 \rightarrow A1$

2. $A4 \rightarrow A2$

3. $A1,A2 \rightarrow A3$

4. $A1,A2 \rightarrow A4$

5. List all candidate keys of $R$. (6 points)

6. The main requirement for BCNF means that the lefthand-side of an FD is a superkey. Do any FDs listed above violate the main requirement? Please explain for each FD. (6 points)

7. The secondary requirement for 3NF means that for an FD $X \rightarrow Y$, $Y$ is a part of a candidate key. Do any FD’s listed above violate the secondary requirement? Please explain for each FD. (4 points)

8. Give a BCNF decomposition of $R$ that is lossless and has as few tables as possible. (9 points)

注意： 本课程将严肃对待大学关于学术不端行为和抄袭（作弊）的政策。所有提交的内容必须是您自己的写作或编码。您不得让其他学生抄袭您的作业。可以讨论作业内容，例如理解相关概念。本作业为个人作业。请将作业打包为单个压缩文件上传，文件名为 A2-XXXX-YYYY.zip，其中 XXXX 是您的姓名，YYYY 是您的学号。请确保压缩文件中包含所有必需文件。

---

第一部分：关系代数（35分）

考虑以下关系模式：

• Emp(eid: integer, ename: string, age: integer, salary: real)

• Works(eid: integer, did: integer, pct_time: integer)

• Dept(did: integer, dname: string, budget: real, managerid: integer)

用关系代数编写以下查询：

a. 列出同时在硬件部门（Hardware）和软件部门（Software）工作的员工的姓名和年龄。（7分）
b. 列出薪资超过其所在所有部门预算的员工的姓名。例如，若某员工在3个部门工作，部门预算分别为1000、2000和3000，则其薪资需超过3000。（7分）
c. 查找仅管理预算超过100万美元的部门的经理的姓名和年龄。（7分）
d. 查找管理预算最高部门的经理的姓名。例如，假设有3个部门：部门1预算100万美元，部门2和部门3预算均为200万美元，则部门2和3的预算最高。（14分）

---

第二部分：SQL查询（40分）

将所有SQL查询保存在名为 part2.sql 的SQL文件中。每个查询前需添加注释，如第一题注释为 -- part2a。
所有查询结果的截图需合并为一个PDF文件 part2.pdf。
将提交内容打包为单个压缩文件 part2.zip。

基于第一部分的关系模式，用SQL编写以下查询（查询需在SQLite中可执行），并使用提供的 A2.db 数据库验证结果：

a. 对应第一部分的a题（8分）
b. 对应第一部分的b题（6分）
c. 对应第一部分的c题（7分）
d. 对应第一部分的d题（9分）
e. 对于每个全职等效员工数超过20人的部门（即员工总工作时间≥2000小时，假设全职员工工作时间为100小时），输出部门编号（did）及该部门员工数。（10分）

---

第三部分：设计理论（25分）

设关系模式 $R(A1,A2,A3,A4)$ 满足以下函数依赖（FDs）：

1. $A3 \rightarrow A1$

2. $A4 \rightarrow A2$

3. $A1,A2 \rightarrow A3$

4. $A1,A2 \rightarrow A4$

5. 列出$R$的所有候选键。（6分）

6. BCNF的主要要求是FD的左部必须是超键。上述FD是否违反该要求？请逐一说明。（6分）

7. 3NF的次要要求是对于FD $X \rightarrow Y$，$Y$必须是候选键的一部分。上述FD是否违反该要求？请逐一说明。（4分）

8. 给出$R$的一个无损且表数最少的BCNF分解。（9分）

---

第一部分：关系代数（35分）

a. 列出同时在硬件部门（Hardware）和软件部门（Software）工作的员工的姓名和年龄。（7分）

$$\pi_{\text{ename}, \text{age}} \left( \text{Emp} \bowtie_{\text{eid}} \left( \pi_{\text{eid}} \left( \text{Works} \bowtie_{\text{did}} \sigma_{\text{dname} = \text{'Hardware'}}(\text{Dept}) \right) \cap \pi_{\text{eid}} \left( \text{Works} \bowtie_{\text{did}} \sigma_{\text{dname} = \text{'Software'}}(\text{Dept}) \right) \right) \right)$$

b. 列出薪资超过其所在所有部门预算的员工的姓名。（7分）

$$\begin{aligned} S &= \text{Emp} \bowtie_{eid} \text{Works} \bowtie_{did} \text{Dept} \\ \text{Bad\_eids} &= \pi_{eid} \left( \sigma_{salary \leq budget}(S) \right) \\ \text{All\_eids} &= \pi_{eid}(\text{Emp}) \\ \text{Good\_eids} &= \text{All\_eids} - \text{Bad\_eids} \\ \text{Result} &= \pi_{ename} \left( \text{Good\_eids} \bowtie_{eid} \text{Emp} \right) \\ \end{aligned}$$

c. 查找仅管理预算超过100万美元的部门的经理的姓名和年龄（7分）

$$\begin{aligned} \text{All\_managers} &= \pi_{managerid}(\text{Dept}) \\ \text{Bad\_managers} &= \pi_{managerid} \left( \sigma_{budget \leq 1000000}(\text{Dept}) \right) \\ \text{Good\_managers} &= \text{All\_managers} - \text{Bad\_managers} \\ \text{Result} &= \pi_{ename, age} \left( \text{Good\_managers} \bowtie_{managerid = eid} \text{Emp} \right) \\ \end{aligned}$$

d. 查找管理预算最高部门的经理的姓名（14分）

$$\begin{aligned} D1 &= \rho_{D1}(\text{Dept}), \quad D2 = \rho_{D2}(\text{Dept}) \\ \text{NonMax\_did} &= \pi_{D1.did} \left( \sigma_{D2.budget > D1.budget}(D1 \times D2) \right) \\ \text{MaxDept\_did} &= \pi_{did}(\text{Dept}) - \text{NonMax\_did} \\ \text{Manager\_ids} &= \pi_{managerid} \left( \text{MaxDept\_did} \bowtie_{did} \text{Dept} \right) \\ \text{结果} &= \pi_{ename} \left( \text{Manager\_ids} \bowtie_{managerid = eid} \text{Emp} \right) \\ \end{aligned}$$

---

第二部分：SQL查询（40分）

-- part2a
SELECT DISTINCT E.ename, E.age
FROM Emp E
WHERE E.eid IN (
    SELECT W.eid
    FROM Works W
    JOIN Dept D ON W.did = D.did
    WHERE D.dname = 'Hardware'
) AND E.eid IN (
    SELECT W.eid
    FROM Works W
    JOIN Dept D ON W.did = D.did
    WHERE D.dname = 'Software'
);

-- part2b
SELECT E.ename
FROM Emp E
WHERE E.salary > (
    SELECT MAX(D.budget)
    FROM Works W
    JOIN Dept D ON W.did = D.did
    WHERE W.eid = E.eid
);

-- part2c
SELECT E.ename, E.age
FROM Emp E
WHERE E.eid IN (
    SELECT managerid
    FROM Dept
    WHERE budget > 1000000
) AND E.eid NOT IN (
    SELECT managerid
    FROM Dept
    WHERE budget <= 1000000
);

-- part2d
SELECT E.ename
FROM Emp E
JOIN Dept D ON E.eid = D.managerid
WHERE D.budget = (
    SELECT MAX(budget)
    FROM Dept
);

-- part2e
SELECT W.did, COUNT(DISTINCT W.eid) AS employee_count
FROM Works W
GROUP BY W.did
HAVING SUM(W.pct_time) >= 2000;

---

第三部分：设计理论（25分）

关系模式 $R(A1,A2,A3,A4)$ 满足函数依赖（FDs）：

1. $A3 \rightarrow A1$

2. $A4 \rightarrow A2$

3. $A1,A2 \rightarrow A3$

4. $A1,A2 \rightarrow A4$

1. 列出 $R$ 的所有候选键。（6分）

计算属性闭包：

• $\{A1,A2\}^+ = \{A1,A2,A3,A4\}$（由FD3和FD4）

• $\{A1,A4\}^+ = \{A1,A4,A2\}$（由FD2），然后 $\{A1,A2\}^+ = \{A1,A2,A3,A4\}$（由FD3和FD4）

• $\{A2,A3\}^+ = \{A2,A3,A1\}$（由FD1），然后 $\{A1,A2\}^+ = \{A1,A2,A3,A4\}$（由FD3和FD4）

• $\{A3,A4\}^+ = \{A3,A4,A1,A2\}$（由FD1和FD2）

2. BCNF的主要要求是FD的左部必须是超键。上述FD是否违反该要求？请逐一说明。（6分）

BCNF要求：对每个非平凡FD $X \rightarrow Y$，$X$ 必须是超键。

• FD1 $A3 \rightarrow A1$：$A3$ 不是超键（$A3^+ = \{A1,A3\}$，不包含所有属性）。违反BCNF。

• FD2 $A4 \rightarrow A2$：$A4$ 不是超键（$A4^+ = \{A2,A4\}$，不包含所有属性）。违反BCNF。

• FD3 $A1,A2 \rightarrow A3$：$\{A1,A2\}$ 是候选键（超键）。不违反BCNF。

• FD4 $A1,A2 \rightarrow A4$：$\{A1,A2\}$ 是候选键（超键）。不违反BCNF。

3. 3NF的次要要求是对于FD $X \rightarrow Y$，$Y$ 必须是候选键的一部分。上述FD是否违反该要求？请逐一说明。（4分）

• FD1 $A3 \rightarrow A1$：$A3$ 不是超键，但 $A1$ 是主属性（包含于候选键 $\{A1,A2\}$ 和 $\{A1,A4\}$ 中）。不违反3NF。

• FD2 $A4 \rightarrow A2$：$A4$ 不是超键，但 $A2$ 是主属性（包含于候选键 $\{A1,A2\}$ 和 $\{A2,A3\}$ 中）。不违反3NF。

• FD3 $A1,A2 \rightarrow A3$：$A1,A2$ 是超键。不违反3NF。

• FD4 $A1,A2 \rightarrow A4$：$A1,A2$ 是超键。不违反3NF。

所有FD均满足3NF要求，无违反。

4. 给出 $R$ 的一个无损且表数最少的BCNF分解。（9分）

由于FD1和FD2违反BCNF，需分解。最小表数为3（因为属性间依赖关系无法用2个表满足BCNF）。以下是一个无损连接分解：

• $R1(A1, A3)$，FD $A3 \rightarrow A1$，候选键 $\{A3\}$（BCNF）。

• $R2(A2, A4)$，FD $A4 \rightarrow A2$，候选键 $\{A4\}$（BCNF）。

• $R3(A1, A2)$，无非平凡FD（除键依赖），候选键 $\{A1,A2\}$（BCNF）。