课后习题答案

1. 理解并给出下列术语的定义：函数依赖，部分函数依赖，完全函数依赖，传递依赖，候选码，超码，主码，外码，全码，1NF，2NF，3NF，BCNF，多值依赖，4NF。

• 函数依赖：属性之间的一种联系，若$X\to Y$，则关系r中任意两个元组，若它们在X上的属性值相同，那么在Y上的属性值一定也相同；反映现实世界的语义，且是关系模式在任何时刻的一切关系均需满足的约束条件。
• 部分函数依赖：若$X\to Y$，但存在X的真子集$X^{\prime }\subset X$，使得$X^{\prime }\to Y$，则称Y对X部分函数依赖。
• 完全函数依赖：若$X\to Y$，且对于X的任何一个真子集$X^{\prime }$，都有$X^{\prime }\nrightarrow Y$，则称Y对X完全函数依赖。
• 传递依赖：若$X\to Y$（$Y⊈X$，$Y\nrightarrow X$），$Y\to Z$（$Z⊈Y$），则称Z对X传递函数依赖。
• 候选码：设K为关系模式$R(U,F)$中的属性或属性组，若$K\stackrel{F}{\to }U$，且不存在K的真子集$K^{\prime }$使得$K^{\prime }\stackrel{F}{\to }U$，则K为R的候选码。
• 超码：设K为关系模式$R(U,F)$中的属性或属性组，若$K\stackrel{F}{\to }U$，则K为R的超码（候选码是最小的超码）。
• 主码：从关系模式的多个候选码中选定一个作为主码。
• 外码：设关系模式R中属性或属性组X不是R的码，但X是另一个关系模式的码，则X是R的外码。
• 全码：关系模式的候选码包含所有属性，称为全码。
• 1NF：关系模式R的所有属性都是不可再分的基本数据项，则$R\in 1NF$。
• 2NF：若$R\in 1NF$，且每一个非主属性完全函数依赖于R的候选码，则$R\in 2NF$。
• 3NF：若$R\in 2NF$，且每一个非主属性既不部分依赖于候选码，也不传递依赖于候选码，则$R\in 3NF$。
• BCNF：若关系模式$R\in 1NF$，且对于R的每一个非平凡函数依赖$X\to Y$（$Y⊈X$），X都包含候选码，则$R\in BCNF$。
• 多值依赖：设R(U)是属性集U上的关系模式，X、Y、Z是U的子集，且$Z=U-X-Y$。若对R的任一关系r，给定的一对$(x,z)$值，有一组Y的值与之对应，且这组Y值仅取决于x值而与z值无关，则称$X\to \to Y$为多值依赖。
• 4NF：若关系模式$R\in BCNF$，且对于R的每一个非平凡多值依赖$X\to \to Y$（$Y⊈X$，$X\cup Y\ne U$），X都包含候选码，则$R\in 4NF$。

2. 建立一个包含系、学生、班级、学会等信息的关系数据库（语义：一个系有若干专业，每个专业每年只招一个班，每个班有若干学生；一个系的学生住在同一宿舍区；每个学生可参加若干学会，每个学会有若干学生，学生参加某学会有一个入会年份）。

关系模式

• 学生：$S(\text{SNO},\text{SN},\text{SB},\text{DN},\text{CNO},\text{SA})$
• 班级：$C(\text{CNO},\text{CS},\text{DN},\text{CNUM},\text{CDATE})$
• 系：$D(\text{DNO},\text{DN},\text{DA},\text{DNUM})$
• 学会：$P(\text{PN},\text{DATE1},\text{PA},\text{PNUM})$
• 学生-学会：$SP(\text{SNO},\text{PN},\text{DATE2})$

最小依赖集

• S：$\text{SNO}\to \text{SN}$，$\text{SNO}\to \text{SB}$，$\text{SNO}\to \text{CNO}$，$\text{CNO}\to \text{DN}$，$\text{DN}\to \text{SA}$
• C：$\text{CNO}\to \text{CS}$，$\text{CNO}\to \text{CNUM}$，$\text{CNO}\to \text{CDATE}$，$\text{CS}\to \text{DN}$，$(\text{CS},\text{CDATE})\to \text{CNO}$
• D：$\text{DNO}\to \text{DN}$，$\text{DN}\to \text{DNO}$，$\text{DNO}\to \text{DA}$，$\text{DNO}\to \text{DNUM}$
• P：$\text{PN}\to \text{DATE1}$，$\text{PN}\to \text{PA}$，$\text{PN}\to \text{PNUM}$
• SP：$(\text{SNO},\text{PN})\to \text{DATE2}$

传递函数依赖

• S：$\text{SNO}\to \text{DN}$、$\text{CNO}\to \text{SA}$、$\text{SNO}\to \text{SA}$
• C：$\text{CNO}\to \text{DN}$

多属性函数依赖性质

$(\text{SNO},\text{PN})\to \text{DATE2}$和$(\text{CS},\text{CDATE})\to \text{CNO}$均为完全函数依赖，无部分函数依赖。

候选码、外码、全码

关系模式	候选码	外码	全码
S	SNO	CNO、DN	无
C	CNO、(CS, CDATE)	DN	无
D	DNO、DN	无	无
P	PN	无	无
SP	(SNO, PN)	SNO、PN	无

3. 试由Armstrong公理系统推导出下面三条推理规则：

① 合并规则：若$X\to Z$，$X\to Y$，则有$X\to YZ$

证明：已知$X\to Z$，由增广律得$XY\to YZ$；又$X\to Y$，得$XX\to XY\to YZ$；根据传递律得$X\to YZ$。

② 伪传递规则：由$X\to Y$，$WY\to Z$，有$XW\to Z$

证明：已知$X\to Y$，据增广律得$XW\to WY$；因$WY\to Z$，故$XW\to WY\to Z$；根据传递律得$XW\to Z$。

③ 分解规则：$X\to Y$，$Z\subseteq Y$，有$X\to Z$

证明：已知$Z\subseteq Y$，根据自反律得$Y\to Z$；又$X\to Y$，根据传递律得$X\to Z$。

4. 给定关系模式$R(U,F)$，其中U={A,B,C,D,E}U=\{A, B, C, D, E\}U={A,B,C,D,E}，函数依赖$B\to D$，$DE\to C$，$EC\to B$，列出R中所有的码，并给出主属性、非主属性。

• 候选码：$AEB$、$AEC$、$AED$
• 主属性：A、B、C、D、E
• 非主属性：无

5. 试举出三个多值依赖的实例。

1. 关系模式$MSC(M,S,C)$（M：专业，S：学生，C：必修课）：$M\to \to S$、$M\to \to C$。
2. 关系模式$ISA(I,S,A)$（I：兴趣小组，S：学生，A：活动项目）：$I\to \to S$、$I\to \to A$。
3. 关系模式$RDP(R,D,P)$（R：病房，D：责任医务人员，P：病人）：$R\to \to D$、$R\to \to P$。

6. 考虑关系模式$R(U,F)$，U={A,B,C,D,E}U=\{A, B, C, D, E\}U={A,B,C,D,E}，回答以下问题：

① 若A是R的候选码，R具有函数依赖$BC\to DE$，那么在什么条件下R属于BCNF？

条件：属性$BC$包含码。

② 如果存在函数依赖F={A→B,BC→D,DE→A}F=\{A \to B, BC \to D, DE \to A\}F={A→B,BC→D,DE→A}，列出R的所有码。

候选码：$ACE$、$BCE$、$DCE$。

③ 如果存在函数依赖F={A→B,BC→D,DE→A}F=\{A \to B, BC \to D, DE \to A\}F={A→B,BC→D,DE→A}，R属于3NF还是BCNF？

• R属于3NF；
• R不属于BCNF。

7. 下面的结论哪些是正确的？哪些是错误的？对于错误的结论，请给出理由或给出一个反例说明之。

1. 任何一个二目关系都是属于3NF的。（√）
2. 任何一个二目关系都是属于BCNF的。（√）
3. 任何一个二目关系都是属于4NF的。（√）
4. 当且仅当函数依赖$A\to B$在R上成立，关系$R(A,B,C)$等于其投影$R1(A,B)$和$R2(A,C)$的连接。（×）
   理由：当且仅当多值依赖$A\to \to B$在R上成立，关系$R(A,B,C)$等于其投影$R1(A,B)$和$R2(A,C)$的连接。
5. 若$R.A\to R.B$，$R.B\to R.C$，则$R.A\to R.C$。（√）
6. 若$R.A\to R.B$，$R.A\to R.C$，则$R.A\to R.(B,C)$。（√）
7. 若$R.B\to R.A$，$R.C\to R.A$，则$R.(B,C)\to R.A$。（√）
8. 若$R.(B,C)\to R.A$，则$R.B\to R.A$，$R.C\to R.A$。（×）
   反例：关系模式$SC(\text{SNO},\text{CNO},G)$，$(SNO,CNO)\to G$，但$SNO\nrightarrow G$，$CNO\nrightarrow G$。

8. 证明：

① 如果R是BCNF关系模式，则R是3NF关系模式，反之则不然。

• 证明（R∈BCNF→R∈3NF）：反证法。设$R\in BCNF$但$R\notin 3NF$，则存在候选码X、属性组Y、非主属性Z（$Z⊈Y$），满足$X\to Y$，$Y\nrightarrow X$，$Y\to Z$。因$Y\nrightarrow X$，Y不包含候选码，与$R\in BCNF$矛盾，故$R\in 3NF$。
• 反例（R∈3NF⇏R∈BCNF）：关系模式$STJ(S,T,J)$，函数依赖$(S,J)\to T$、$(S,T)\to J$、$T\to J$，候选码为$(S,J)$、$(S,T)$，STJ是3NF但不是BCNF。

② 如果R是3NF关系模式，则R一定是2NF关系模式。

证明：反证法。设$R\in 3NF$但$R\notin 2NF$，则存在非主属性Z不完全函数依赖于码X，即存在X的真子集Y，$Y\to Z$。因Y是X的真子集，$Y\nrightarrow X$，且Z是非主属性、$Z⊈Y$，与$R\in 3NF$矛盾，故$R\in 2NF$。

9. 为什么直接根据定义6.18去鉴别一个分解的无损连接性是不可能的？

理由：对于关系模式$R(U,F)$，可能的关系实例r原则上有无数多个，无法验证对任意一个r，有$r=m_{\rho }(r)$成立。

补充习题及答案

1. 考虑关系模式$R(U,F)$，U={A,B,C,D}U=\{A, B, C, D\}U={A,B,C,D}，求满足下列函数依赖时R所有的候选码，并给出R属于哪种范式（1NF、2NF、3NF或BCNF）。

(1) F={ABC,BD,BEF}F=\{ABC, BD, BEF\}F={ABC,BD,BEF}

• 候选码：AB
• 范式：1NF

(2) F={A→B,A→C,D→A}F=\{A \to B, A \to C, D \to A\}F={A→B,A→C,D→A}

• 候选码：D
• 范式：2NF

(3) F={BCD→A,A→C}F=\{BCD \to A, A \to C\}F={BCD→A,A→C}

• 候选码：BCD、ABD
• 范式：3NF

(4) F={B→C,B→D,CD→A}F=\{B \to C, B \to D, CD \to A\}F={B→C,B→D,CD→A}

• 候选码：B
• 范式：2NF

(5) F={ABD→C}F=\{ABD \to C\}F={ABD→C}

• 候选码：ABD
• 范式：BCNF

2. 考虑属性集$ABCDEF$和函数依赖集{AB→C,B→D,BC→E,AC→D,E→F,CD→A}\{AB \to C, B \to D, BC \to E, AC \to D, E \to F, CD \to A\}{AB→C,B→D,BC→E,AC→D,E→F,CD→A}，对于属性集$ABC$、$ABCD$、$BCDE$、$CDEF$、$CDF$：

① 写出在属性集上的函数依赖集，说明是否为最小覆盖；② 指出属于哪种范式。

• $ABC$：

1. 函数依赖集：$AB\to C$；是最小覆盖；
2. 范式：BCNF。

• $ABCD$：

1. 函数依赖集：$AB\to C$，$B\to D$，$AC\to D$，$CD\to A$；是最小覆盖；
2. 范式：1NF。

• $BCDE$：

1. 函数依赖集：$B\to D$，$BC\to E$；是最小覆盖；
2. 范式：1NF。

• $CDEF$：

1. 函数依赖集：$E\to F$；是最小覆盖；
2. 范式：1NF。

• $CDF$：

1. 函数依赖集：无；是最小覆盖；
2. 范式：BCNF。

3. 对于属性集$ABCDEF$和函数依赖集{A→BC,CD→E,B→D,BE→F,EF→A}\{A \to BC, CD \to E, B \to D, BE \to F, EF \to A\}{A→BC,CD→E,B→D,BE→F,EF→A}，说明下列分解是否为无损连接分解，以及是否保持函数依赖：

① 分解$U_1=ABCD$，$U_2=EFA$

• 无损连接性：是无损连接分解；
• 保持函数依赖：否。

② 分解$U_1=ABC$，$U_2=BDE$，$U_3=BEF$

• 无损连接性：不是无损连接分解；
• 保持函数依赖：否。

4. 关系R有属性$ABCD$（含指定记录），指出下列函数依赖或多值依赖在R上是否成立：

(1) $A\to B$

不成立

(2) $A\to BC$

不成立

(3) $A\to \to BC$

不确定

(4) $B\to C$

不确定

(5) $BC\to \to A$

不成立

(6) $C\to \to D$

不成立

5. 关系模式$R$(员工编号，日期，零件数，部门名称，部门经理)，假设：每个员工每天只有一个日生产零件数，每个员工只在一个部门工作，每个部门只有一个经理。回答：

① 写出模式R的基本函数依赖和码。

• 函数依赖：(员工编号, 日期)→零件数，员工编号→部门名称，部门名称→部门经理；
• 码：(员工编号, 日期)。

② R是否为2NF，如果不是，把R分解成2NF。

• R不是2NF；
• 分解结果：$R1$(员工编号, 日期, 零件数)、$R2$(员工编号, 部门名称, 部门经理)。

③ 进一步将R分解成3NF。

分解结果：$R1$(员工编号, 日期, 零件数)、$R2$(员工编号, 部门名称)、$R3$(部门名称, 部门经理)。

6. 对于关系模式R(会议，主持人，时间，会议室，会员，职务)，函数依赖F={F=\{F={会议→主持人，(时间, 会议室)→会议，(时间, 主持人)→会议室，(时间, 会员)→会议室，(会议, 会员)→职务$\}$。回答：

① 写出R的所有码。

码：(时间, 会员)。

② 说明给出的函数依赖集F是否为极小函数依赖集。

是极小函数依赖集。

③ 将R分解成具有无损连接和保持函数依赖的3NF，判断是否有违反BCNF的关系。

• 分解结果：$U_1$(会议, 主持人)、$U_2$(时间, 会议室, 会议)、$U_3$(时间, 主持人, 会议室)、$U_4$(时间, 会员, 会议室)、$U_5$(会议, 会员, 职务)；
• 分解后无违反BCNF的关系。

7. 对于下列各个关系模式和依赖，回答是否为4NF，若不是则将关系分解为满足4NF的关系：

① $R(A,B,C)$，存在依赖$A\to \to B$和$A\to C$

• 是否为4NF：否；
• 分解结果：$R(A,B)$、$R(A,C)$。

② $R(A,B,C,D)$，存在依赖$A\to \to C$和$C\to \to BD$

• 是否为4NF：否；
• 分解结果：$R(A,C)$、$R(B,C,D)$。

8. 对给定的关系模式$R(U,F)$，U={A,B,C,D}U=\{A, B, C, D\}U={A,B,C,D}，F={A→B,B→C,C→D,D→A}F=\{A \to B, B \to C, C \to D, D \to A\}F={A→B,B→C,C→D,D→A}，给出函数依赖范畴下关系模式R所满足的最高范式。

最高范式：BCNF。

9. 对给定的关系模式$R(U,F)$，U={C,T,H,R,S,G}U=\{C, T, H, R, S, G\}U={C,T,H,R,S,G}，F={CS→G,C→T,TH→R,HR→C,HS→R}F=\{CS \to G, C \to T, TH \to R, HR \to C, HS \to R\}F={CS→G,C→T,TH→R,HR→C,HS→R}，给出函数依赖范畴下关系模式R所满足的最高范式。

最高范式：2NF。

10. 对于给定的关系模式$R(U,F)$，U={X,Y,Z}U=\{X, Y, Z\}U={X,Y,Z}，F={X→→Y,Y→→Z}F=\{X \to \to Y, Y \to \to Z\}F={X→→Y,Y→→Z}，试证明：$X\to \to Z-Y$。

证明：将$Y\cup Z$分解为$Y-Z$、$Z-Y$、$Y\cap Z$；取R中任意两个元组t、s满足$t[X]=s[X]$，由$X\to \to Y$交换t、s在Y上的值得到元组$t^{\ast }$、$s^{\ast }$；再由$Y\to \to Z$交换t、$s^{\ast }$在Z上的值，可得交换t、s在$Z-Y$上的值后得到的元组仍属于R，故$X\to \to Z-Y$。

11. 关系模式R(员工编号，日期，零件数，部门名称，部门经理)，回答：

① 写出该模式R的函数依赖、码、主属性、非主属性。

• 函数依赖：(员工编号, 日期)→零件数，员工编号→部门名称，员工编号→部门经理，部门名称→部门经理；
• 码：(员工编号, 日期)；
• 主属性：员工编号，日期；
• 非主属性：零件数，部门名称，部门经理。

② 请给出R满足的最高范式。

最高范式：1NF。

③ 给出关系模式R设计中存在的问题（必须给出实例说明）。

• 插入异常：新员工入职未工作时，无法插入员工信息；
• 删除异常：某部门所有员工离职时，部门信息也被删除；
• 数据冗余：每个员工记录都重复存储部门名称、部门经理；
• 修改复杂：修改部门经理时，需修改该部门所有员工的记录。

④ 将R分解为2个或2个以上的关系模式，使得分解后的每个关系模式均满足3NF范式。

分解结果：$R_1$(员工编号, 日期, 零件数)、$R_2$(员工编号, 部门名称)、$R_3$(部门名称, 部门经理)。

12. 证明题：关于多值依赖的另一种定义（给定$R(X,Y,Z)$，Yxz={r.Y∣r.X=x∧r.Z=z∧r∈R}Y_{xz}=\{r.Y | r.X=x \land r.Z=z \land r \in R\}Yxz​={r.Y∣r.X=x∧r.Z=z∧r∈R}，当且仅当$Y_{xz}=Y_{x{z}^{\prime }}$对每一组$(x,z,z^{\prime })$成立，则$X\to \to Y$）与《概论》定义6.9等价。

证明：

• 若新定义成立：取r中任意元组s、t满足$s[X]=t[X]$，则对任意z值，Y的取值仅依赖x，交换s、t在Y上的值后元组仍属于r，符合定义6.9。
• 若定义6.9成立：交换s、t在Y上的值后元组仍属于r，说明任意z值对应相同的Y值，即$Y_{xz}=Y_{x{z}^{\prime }}$对每一组$(x,z,z^{\prime })$成立，符合新定义。
• 综上，两个定义等价。