【数据挖掘】国科大苏桂平老师数据库新技术课程作业 —— 第二次作业

1

设 F = { A B → C , B → D , C D → E , C E → G H , G → A } F=\{AB\rightarrow C,B\rightarrow D, CD\rightarrow E, CE\rightarrow GH, G\rightarrow A \} F={AB→C,B→D,CD→E,CE→GH,G→A}，用推理的方法证明 $F|=AB\to G$。

① 已知 $B\to D$，则 $AB\to AD$（增广律）

② 已知 $AB\to AD$，则 $AB\to D$ （分解规则）

③ 已知 $AB\to C$，$AB\to D$，则 $AB\to CD$ （合成规则）

④ 已知 $AB\to CD$，$CD\to E$，则 $AB\to E$ （传递律）

⑤ 已知 $AB\to E$，$AB\to C$，则 $AB\to CE$ （合成规则）

⑥ 已知 $CE\to GH$，则 $CE\to G$ （分解规则）

⑦ 已知 $AB\to CE$，$CE\to G$，则 $AB\to G$ （传递律）

注意区别”传递律“与”传递函数依赖“。

2

设关系模式 $R(A,B,C,D)$，其函数依赖集为 F = { A → B , B → C , A → D , D → C } F=\{A\rightarrow B, B\rightarrow C, A\rightarrow D, D\rightarrow C\} F={A→B,B→C,A→D,D→C}，$R$ 的一个分解 ρ = { R 1 ( A , B ) , R 2 ( A , C ) , R 3 ( A , D ) } \rho = \{R_1(A,B), R_2(A,C), R_3(A,D)\} ρ={R1​(A,B),R2​(A,C),R3​(A,D)}。

（1）求 $F$ 在 $\rho$ 的每个模式上的投影

$F$ 在关系模式 $R_1(A,B)$ 上的投影为 { A → B } \{A\rightarrow B\} {A→B}；$F$ 在关系模式 $R_2(A,C)$ 上的投影为 { A → C } \{A\rightarrow C\} {A→C}；$F$ 在关系模式 $R_3(A,D)$ 上的投影为 { A → D } \{A\rightarrow D\} {A→D}。

（2）$\rho$ 相对于 $F$ 是无损连接吗？

A	B	C	D
a1	a2	b13→a3	b14→a4
a1	b22→a2	a3	b24→a4
a1	b32→a2	b33→a3	a4

其中，红色对应 $F$ 中的 $A\to B$，蓝色对应 $F$ 中的 $B\to C$，绿色对应 $F$ 中的 $A\to D$，此时 $F$ 中的 $D\to C$ 不影响表格。

由于存在某一行全为 $a$，所以 $\rho$ 相对于 $F$ 是无损连接。

当分解只包括两个关系模式时，可以使用定理”分解 ρ = { R 1 , R 2 } \rho=\{R_1, R_2\} ρ={R1​,R2​}，若 $F|=(R_1\cap R_2)\to (R_1-R_2)$ 或者 $F|=(R_1\cap R_2)\to (R_2-R_1)$，则 $\rho$ 具有无损连接性“判断是否为无损连接。

（3）$\rho$ 保持函数依赖吗？

$A^{+}=ABCD$，$B^{+}=BC$，$C^{+}=C$，$D^{+}=CD$。

考察 $A\to B$，$A\subset R_1$， A + ∩ R 1 − A = { B } A^+ \cap R_1-A=\{B\} A+∩R1​−A={B}， G = { A → B } G = \{A\rightarrow B\} G={A→B}；同理 $A\subset R_2$， G = G ∪ { A → C } G = G\cup \{A\rightarrow C\} G=G∪{A→C}，$A\subset R_3$， G = G ∪ { A → D } G = G\cup \{A\rightarrow D\} G=G∪{A→D}。 G = { A → B , A → C , A → D } G = \{A\rightarrow B,A\rightarrow C,A\rightarrow D\} G={A→B,A→C,A→D}。

考察 $B\to C$，$B\subset R_1$，$B^{+}\cap R_1-B=\varphi$，$G$ 不变。

考察 $A\to D$ 类似于 $A\to B$， G = G ∪ { A → B , A → C , A → D } G = G\cup \{A\rightarrow B,A\rightarrow C,A\rightarrow D\} G=G∪{A→B,A→C,A→D}，$G$ 不变。

考察 $D\to C$，$D\subset R_3$，$D^{+}\cap R_1-D=\varphi$，$G$ 不变。

最终 G = { A → B , A → C , A → D } G = \{A\rightarrow B,A\rightarrow C,A\rightarrow D\} G={A→B,A→C,A→D}。

显然 $G$ 不蕴含 $F$ 中的函数依赖 $B\to C$ 和 $D\to C$，所以 $\rho$ 没有保持函数依赖。

3

1NF、2NF、3NF 和 BCNF 的定义：

1NF：如果一个关系模式 $R$ 中的每个属性 $A$ 的域值都是原子的，即属性值是不可再分的，则关系模式 $R$ 属于第一范式，简记为$R\in 1NF$。

2NF：如果 $R\in 1NF$ 且所有的非主属性完全依赖于 $R$ 的每个键，则 $R\in 2NF$。

3NF：如果 $R\in 1NF$ 且在 $R$ 中没有非主属性传递依赖于 $R$ 的键，则 $R\in 3NF$。

BCNF：如果 $R\in 1NF$ 且 $R$ 中没有任何属性传递依赖于 $R$ 的任何一个键，则 $R\in \mathrm{Boyce}-\mathrm{Codd}$ 范式（BCNF）。

注意，传递依赖的定义：设关系模式 $R$，$X$、$Y$、$Z$ 是 $R$ 的属性子集，若函数依赖 $X\to Y$，$Y\nrightarrow X$，$Y\to z$，则有 $X\to Z$。

指出下列关系模式是第几范式，并说明理由。

（1）$R(A,B,C)$，其函数依赖集为 F = { B → C , A C → B } F=\{B\rightarrow C, AC\rightarrow B\} F={B→C,AC→B}

确定 $R$ 的键，$A^{+}=A$，$B^{+}=BC$，$C^{+}=C$；$(AB{)}^{+}=ABC$，$(AC{)}^{+}=ABC$，所以键为 $AB$ 和 $AC$。关系模式 $R$ 无非主属性，因此 $R\in 2NF$，$R\in 3\mathrm{NF}$。但是由于 $AC\to B$，$B\nrightarrow AC$，$B\to C$ ，存在传递依赖，故 $R\notin \mathrm{BCNF}$。

（2）$R(A,B,C)$，其函数依赖集为 F = { A B → C } F=\{AB\rightarrow C\} F={AB→C}

$(AB{)}^{+}=ABC$，显然 $R$ 的键为 $AB$，即 $A$ 和 $B$ 为主属性，$C$ 为非主属性。$AB\to C$，$C$ 完全依赖于键 $AB$，$R\in 2\mathrm{NF}$。不存在传递依赖，$R\in 3\mathrm{NF}$，$R\in \mathrm{BCNF}$。

（3）$R(A,B,C)$，其函数依赖集为 F = { A → B , A → C } F=\{A\rightarrow B, A\rightarrow C\} F={A→B,A→C}

$R$ 的键为 $A$，$A$ 为主属性，$B$ 和 $C$ 为非主属性。$B$ 和 $C$ 完全依赖于 $A$，$R\in 2NF$。不存在传递依赖，，$R\in 3\mathrm{NF}$，$R\in \mathrm{BCNF}$。

（4）$R(A,B,C,D)$，其函数依赖集为 F = { A → C , A D → B } F=\{A\rightarrow C, AD\rightarrow B\} F={A→C,AD→B}

$R$ 的键为 $AD$，$A$ 和 $D$ 为主属性，$B$ 和 $C$ 为非主属性。$B$ 完全依赖于键 $AD$，但是 $C$ 部分依赖于键 $AD$，所以 $R\notin 2\mathrm{NF}$。

（5）$R(A,B,C)$，其函数依赖集为 F = { B → C , B → A , A → B C } F=\{B\rightarrow C, B\rightarrow A, A\rightarrow BC\} F={B→C,B→A,A→BC}

$A^{+}=B^{+}=ABC$，所以键为 $A$ 和 $B$，$C$ 为非主属性。根据分解规则可知 $A\to C$，$C$ 完全依赖于 $A$，又 $B\to C$，$C$ 完全依赖于 $B$，所以 $R\in 2\mathrm{NF}$。因为 $A\to B$，$B\to A$，尽管 $A\to C$（或 $B\to C$），但是不满足传递依赖的定义，所以不存在传递依赖，故 $R\in 3\mathrm{NF}$，$R\in \mathrm{BCNF}$。