关系数据库设计 背景 RDB设计工程方法的代表:E-R图方法
绘制 E-R E − R → R D B E-R\rightarrow RDB E − R → R D B 模式模式优化 RDB设计工程方法的问题
E-R质量和设计人员能力水平相关 E-R质量难以保证,致使E-R方法设计质量难以保证 其它RDB模式工程设计方法存在类似问题 模式规范化方法的研究状况
提出了模式规范化的标准:为决定因素1NF,2NF,3NF,BCNF,4NF,5NF,6NF 给出了泛关系分解到具体范式的算法 算法多为Np算法,无法实际执行 规范化方法学习价值
理解不同范式的优缺点 理解相应的模式改进方法 作为重要指导思想指导模式设计 本章讲述关系模式规范化理论、方法
好的关系设计特点
不必存储不必要的重复信息,同时又可以方便地获取信息 同数据本质结构相吻合 第一范式 如果某个域的元素被认为是不可再分的单元,那么这个域就是原子的(atomic)。如果一个关系模式R的所有的属性域都是原子的,我们称关系模式R属于第一范式(first normal form, 1NF)
关系数据库中的所有关系模式均应该满足1NF
原子域 域元素被认为是不可分的单元,称域是原子的
域原子性分析示例:
函数依赖 U U U 是所有属性的集合,α , β \alpha,\beta α , β 是属性的集合。
设 R ( U ) R(U) R ( U ) 是属性集 U U U 上的关系模式, α , β ⊆ U \alpha,\beta \subseteq U α , β ⊆ U , r r r 是 R ( U ) R(U) R ( U ) 上的任意一个关系实例 ,如果有
对 ∀ t , s ∈ r \forall t, s \in r ∀ t , s ∈ r ,若 t [ α ] = s [ α ] t[\alpha] = s[\alpha] t [ α ] = s [ α ] ,则 t [ β ] = s [ β ] t[\beta] = s[\beta] t [ β ] = s [ β ]
那么称 “α \alpha α 函数决定 β \beta β ”,或“ β \beta β 函数依赖于α \alpha α ”,记作 α → β \alpha \rightarrow \beta α → β
称 α \alpha α 为决定因素, β \beta β 为被决定因素
平凡函数依赖 如果 α → β \alpha \rightarrow \beta α → β ,但 β ⊄ α \beta \not\subset \alpha β ⊂ α ,则称其为非平凡的函数依赖,否则(即 β ⊆ α \beta \subseteq \alpha β ⊆ α )称为平凡(trivial
)的函数依赖
如 ( s n o , s n a m e ) → s n a m e (sno,sname)\rightarrow sname ( s n o , s nam e ) → s nam e 是平凡的函数依赖
平凡的函数依赖永远成立
部分函数依赖 在关系模式 R ( U ) R(U) R ( U ) 中,如果 α → β \alpha\rightarrow\beta α → β ,且对于任意 α \alpha α 的真子集α ′ \alpha ' α ′ ,都有 α ′ ↛ β \alpha'\not\rightarrow\beta α ′ → β ,则称 β \beta β 对 α \alpha α 完全函数依赖,也就是说,α \alpha α 缺少任一属性都无法唯一确定 β \beta β ,记作α → f β \alpha \overset f \rightarrow \beta α → f β 。否则称为 β \beta β 对 α \alpha α 部分函数依赖,记作α → p β \alpha \overset p \rightarrow \beta α → p β (也就是说α \alpha α 的部分属性就可以唯一确定 β \beta β )
例如:
( s n o , c n o ) → f s c o r e (sno,cno)\overset f \rightarrow score ( s n o , c n o ) → f score
( s n o , c n o ) → p s n a m e (sno,cno)\overset p \rightarrow sname ( s n o , c n o ) → p s nam e
传递函数依赖 在关系模式 R ( U ) R(U) R ( U ) 中,如果 α → β , β → γ , β ↛ α , β ⊄ α \alpha\rightarrow\beta,\,\beta\rightarrow\gamma,\,\beta\not\rightarrow\alpha,\,\beta\not\subset\alpha α → β , β → γ , β → α , β ⊂ α ,则称 γ \gamma γ 对 α \alpha α 传递函数依赖。
函数依赖与码 设 K K K 为 R < U , F > R< U, F > R < U , F > 的属性组,若 K → U K\rightarrow U K → U ,则称 K K K 为 R R R 的超码 设 K K K 为 R < U , F > R< U, F > R < U , F > 的超码,若 K → f U K\overset f \rightarrow U K → f U ,则称 K K K 为 R R R 的候选码 包含在任意一个候选码 中的属性,称作主属性 函数依赖的推理规则 逻辑蕴涵 定义 关系模式 R R R ,F F F 是其函数依赖集,如果从 F F F 的函数依赖能够推出 α → β \alpha\rightarrow\beta α → β ,则称 F F F 逻辑蕴涵 α → β \alpha\rightarrow\beta α → β ,记作 F ├ α → β F├ \,\,\alpha\rightarrow\beta F ├ α → β
另一种描述:给定关系模式 R R R ,如果某一个满足 F F F 的关系实例 r r r 也满足 f f f ,则 R R R 上函数依赖 f f f 被 R R R 上的函数依赖集 F F F 逻辑蕴涵, F ├ f F├ \,f F ├ f
被 F F F 所逻辑蕴涵的函数依赖的全体所构成的集合称作 F F F 的函数依赖集的闭包 (closure
),记作:
F + = { α → β ∣ F ├ α → β } F^+=\{\alpha\rightarrow\beta\,|\,F├ \,\,\alpha\rightarrow\beta\,\} F + = { α → β ∣ F ├ α → β } R ( U , F ) R(U, F) R ( U , F ) (关系模式), U = X , Y U = {X, Y} U = X , Y (属性集), F = X → Y F = {X\rightarrow Y} F = X → Y (函数依赖集)
Armstrong公理系统与正确性证明 所有希腊字母都是属性集,所有英文字母都是单个属性。
S 1 = { f ∣ 可用 A r m s t r o n g 公理从 F 中导出的函数依赖 f } S1 = \{ f \,|\,可用Armstrong公理从F中导出的函数依赖f \} S 1 = { f ∣ 可用 A r m s t ro n g 公理从 F 中导出的函数依赖 f }
S 2 = { f ∣ 被 F 所逻辑蕴涵的所有函数依赖 f } S2 = \{ f \,|\,被F所逻辑蕴涵的所有函数依赖f \} S 2 = { f ∣ 被 F 所逻辑蕴涵的所有函数依赖 f }
α , β , γ , δ \alpha,\beta,\gamma,\delta α , β , γ , δ 是属性集
r r r 是 R < U , F > R<U, F> R < U , F > 上的任一关系,t , s ∈ r t,s \in r t , s ∈ r ,(t , s t,s t , s 是 r r r 的两个元组)
自反律(reflexivity
) 若 β ⊆ α \beta\subseteq\alpha β ⊆ α ,则 α → β \alpha\rightarrow\beta α → β
不妨假设 t [ α ] = s [ α ] t[\alpha]=s[\alpha] t [ α ] = s [ α ] ,我们只需要证明 t [ β ] = s [ β ] t[\beta]=s[\beta] t [ β ] = s [ β ] , 下面的证明类似,就不再写该假设,而是直接当成条件使用。
∵ t [ α ] = s [ α ] , β ⊆ α \because t[\alpha]=s[\alpha]\,,\,\beta\subseteq\alpha ∵ t [ α ] = s [ α ] , β ⊆ α
∴ t [ β ] = s [ β ] \therefore t[\beta]=s[\beta] ∴ t [ β ] = s [ β ]
∴ α → β \therefore \alpha\rightarrow\beta ∴ α → β
增广律(augmentation
) 若 α → β \alpha\rightarrow\beta α → β ,则 α γ → β γ \alpha\gamma\rightarrow\beta\gamma α γ → β γ
∵ 不妨假设 t [ α γ ] = s [ α γ ] \because 不妨假设\, t[\alpha\gamma] = s[\alpha\gamma] ∵ 不妨假设 t [ α γ ] = s [ α γ ]
∴ t [ α ] = s [ α ] , t [ γ ] = s [ γ ] \therefore t[\alpha]=s[\alpha],t[\gamma]=s[\gamma] ∴ t [ α ] = s [ α ] , t [ γ ] = s [ γ ]
∵ α → β \because \alpha\rightarrow\beta ∵ α → β
∴ t [ β ] = s [ β ] \therefore t[\beta] = s[\beta] ∴ t [ β ] = s [ β ]
∴ t [ β γ ] = s [ β γ ] \therefore t[\beta\gamma]=s[\beta\gamma] ∴ t [ β γ ] = s [ β γ ]
∴ α γ → β γ \therefore \alpha\gamma\rightarrow\beta\gamma ∴ α γ → β γ
传递律(transitivity
) 若 α → β , β → γ \alpha\rightarrow\beta,\,\beta\rightarrow\gamma α → β , β → γ ,则 α → γ \alpha\rightarrow\gamma α → γ
∵ α → β , 假设 t [ α ] = s [ α ] \because \alpha\rightarrow\beta,假设\,t[\alpha]=s[\alpha] ∵ α → β , 假设 t [ α ] = s [ α ]
∴ t [ β ] = s [ β ] \therefore t[\beta]=s[\beta] ∴ t [ β ] = s [ β ]
∵ β → γ \because\beta\rightarrow\gamma ∵ β → γ
∴ t [ γ ] = s [ γ ] \therefore t[\gamma] = s[\gamma] ∴ t [ γ ] = s [ γ ]
∴ α → β \therefore \alpha\rightarrow\beta ∴ α → β
合并律(union rule
) 若 α → β \alpha \rightarrow \beta α → β , α → γ \alpha\rightarrow\gamma α → γ ,则 α → β γ \alpha\rightarrow\beta\gamma α → β γ
∵ 假设 t [ α ] = s [ α ] \because 假设\,t[\alpha]=s[\alpha] ∵ 假设 t [ α ] = s [ α ]
∴ t [ β ] = s [ β ] , t [ γ ] = s [ γ ] \therefore t[\beta]=s[\beta],\,t[\gamma]=s[\gamma] ∴ t [ β ] = s [ β ] , t [ γ ] = s [ γ ]
∴ t [ β γ ] = s [ β γ ] \therefore t[\beta\gamma]=s[\beta\gamma] ∴ t [ β γ ] = s [ β γ ]
∴ α → β γ \therefore \alpha\rightarrow\beta\gamma ∴ α → β γ
或者使用增广律和传递律:
∵ α → β , α → γ \because \alpha \rightarrow \beta, \alpha\rightarrow\gamma ∵ α → β , α → γ
∴ α → α β , α β → β γ \therefore \alpha\rightarrow\alpha\beta,\alpha\beta\rightarrow\beta\gamma ∴ α → α β , α β → β γ
∴ α → β γ \therefore\alpha\rightarrow\beta\gamma ∴ α → β γ
分解律(decomposition rule
) 若 α → β γ \alpha\rightarrow\beta\gamma α → β γ ,则 α → β \alpha\rightarrow\beta α → β 且 α → γ \alpha\rightarrow\gamma α → γ
∵ γ ⊆ β γ \because\gamma\subseteq\beta\gamma ∵ γ ⊆ β γ
∴ β γ → γ \therefore \beta\gamma\rightarrow\gamma ∴ β γ → γ (自反律)
∵ α → β γ \because \alpha\rightarrow\beta\gamma ∵ α → β γ
∴ α → γ \therefore \alpha\rightarrow\gamma ∴ α → γ (传递律)
同理 α → β 同理\,\alpha\rightarrow\beta 同理 α → β
伪传递律(pseudotransitivity rule
) 若 α → β \alpha \rightarrow \beta α → β ,γ β → δ \gamma\beta \rightarrow \delta γ β → δ ,则 γ α → δ \gamma\alpha \rightarrow \delta γ α → δ
∵ α → β \because \alpha\rightarrow\beta ∵ α → β
∴ α γ → γ β \therefore \alpha\gamma\rightarrow\gamma\beta ∴ α γ → γ β (增广律)
∵ γ β → δ \because \gamma\beta\rightarrow\delta ∵ γ β → δ
∴ γ α → δ \therefore \gamma\alpha\rightarrow\delta ∴ γ α → δ (传递律)
Armstrong公理与闭包问题 一般来说,F ⊂ F + F\subset F^+ F ⊂ F + ,我们希望通过Armstrong公理和 F F F 找出 F + F^+ F +
但这其实是一个NP问题,也就是说,对于 α → β ∈ F + \alpha\rightarrow\beta\in F^+ α → β ∈ F + ,对于所有n个属性,该属性可能在属性集 α \alpha α 中,也可能在属性集 β \beta β 中,或者都不在。也就是说,α , β \alpha,\beta α , β 各有 2 n 2^n 2 n 种可能性,然后在搜索过程中我们要将所有可能的属性集进行排列组合,一共就有 2 n × 2 n = 2 2 n 2^n\times2^n=2^{2n} 2 n × 2 n = 2 2 n 种可能性。显然,指数级的时间复杂度。
属性集的闭包(Attribute Closure) 令 α \alpha α 为属性集,将函数依赖集 F F F 下 被 α \alpha α 函数确定的所有属性的集合 称作 F F F 下 α \alpha α 的闭包,记作 α F + \alpha^+_F α F +
a F + = { A ∣ a → A 能由 F 出发根据 A r m s t r o n g 公理导出 } a^+_F= \{ A \,|\, a \rightarrow A能由F出发根据Armstrong公理导出 \} a F + = { A ∣ a → A 能由 F 出发根据 A r m s t ro n g 公理导出 }
示例 :
R < U , F > R< U, F > R < U , F > , 属性集 U = { A , B , C } U=\{A,B,C\} U = { A , B , C } ,
函数依赖集 F = { A → B , B → C } F=\{A \rightarrow B,B \rightarrow C\} F = { A → B , B → C }
则
A F + = { A , B , C } A^+_F = \{A,B,C\} A F + = { A , B , C }
B F + = { B , C } B^+_F = \{B,C\} B F + = { B , C }
C F + = { C } C^+_F = \{C\} C F + = { C }
函数依赖集的闭包转化为属性集的闭包 判定 α → β \alpha\rightarrow \beta α → β 是否能由 F F F 根据Armstrong公理导出,可转化为求 α F + \alpha^+_F α F + ,判定 β ⊆ α F + \beta \subseteq \alpha^+_F β ⊆ α F + 是否成立
算法(计算基于函数依赖集 F F F 的属性集 α \alpha α 的闭包) 属性集闭包算法的完备性(算法能够找出 a F + a^+_F a F + 中的全部属性)
在算法执行过程中,如果存在某个属性应该属于 a F + a^+_F a F + ,但是不属于result,则必定存在函数依赖 β → γ ( b ⊆ r e s u l t ) \beta \rightarrow \gamma(b \subseteq result) β → γ ( b ⊆ res u lt ) 并且 γ \gamma γ 中至少有一个属性不在result中。
当算法结束时,所有函数依赖均已被处理过,γ \gamma γ 中的属性都已经加到result中。因此我们可以确定 a F + a^+_F a F + 中的所有属性都在result中。
示例 R < U , F > , U = ( A , B , C , G , H , I ) , F = { A → B , A → C , C G → H , C G → I , B → H } R< U, F >, U = (A, B, C, G, H, I), F = \{A\rightarrow B, A\rightarrow C, CG\rightarrow H, CG\rightarrow I, B\rightarrow H\} R < U , F > , U = ( A , B , C , G , H , I ) , F = { A → B , A → C , CG → H , CG → I , B → H } ,计算 ( A G ) F + (AG)^+_F ( A G ) F +
R < U , F > , U = ( C , T , H , R , S ) , F = { C → T , H R → C , H T → R , H S → R } R< U, F >, U = (C, T, H, R, S),F = \{C\rightarrow T, HR\rightarrow C, HT\rightarrow R, HS\rightarrow R\} R < U , F > , U = ( C , T , H , R , S ) , F = { C → T , H R → C , H T → R , H S → R }
问题:HR是候选码吗?HS呢?
( H R ) F + = { H R C T } (HR)^+_F=\{HRCT\} ( H R ) F + = { H RCT } ,所以HR不是候选码。
( H S ) F + = { H S R C T } (HS)^+_F=\{HSRCT\} ( H S ) F + = { H SRCT } 且 H F + = { H } , S F + = { S } H^+_F=\{H\},S^+_F=\{S\} H F + = { H } , S F + = { S } ,所以HS是候选码
Armstrong公理完备性证明 Armstrong公理完备性的含义:F + F^+ F + 中的每一个函数依赖,必定可以从 F F F 出发,根据Armstrong公理推导出来。
要证明完备性,首先计算 F + F^+ F + ,但是计算 F + F^+ F + ,是一个NP问题。因此需要用到属性集的闭包。
Armstrong公理完备性证明:证明完备性的的逆否命题 :即如果函数依赖性 α → β \alpha\rightarrow\beta α → β 不能从 F F F 出发根据Armstrong公理推出,则 α → β \alpha\rightarrow\beta α → β 一定不能为 F F F 所逻辑蕴含 。证明分三步。
证明如下:
若 V → W V\rightarrow W V → W 成立,且 V ⊆ α F + V\subseteq \alpha_F^+ V ⊆ α F + ,则 W ⊆ α F + W\subseteq \alpha_F^+ W ⊆ α F +
证明:因为:α → α + , V ⊆ α F + \alpha \rightarrow \alpha^+,V\subseteq \alpha_F^+ α → α + , V ⊆ α F + ,所以 α → V \alpha \rightarrow V α → V 成立;V → W V\rightarrow W V → W ,所以 α → W \alpha \rightarrow W α → W 成立,所以 W ⊆ α F + W\subseteq \alpha_F^+ W ⊆ α F + 。 构造一张二维表 r r r ,它由两个元组构成,可以证明 r r r 必定是关系模式 R < U , F > R<U,F> R < U , F > 的一个关系实例 ,即 F F F 中的所有函数依赖在 r r r 上成立。(U是属性集)
a F + a_F^+ a F + U − a F + U - a_F^+ U − a F +
11……….1 00……….0
11……….1 11……….1
假设 r r r 不是 R < U , F > R<U,F> R < U , F > 的关系实例。必定由于 V → W ∈ F V\rightarrow W\in F V → W ∈ F 且 V → W V\rightarrow W V → W 在 r r r 上不成立导致的。由于 r r r 的特殊构造,如果 V → W V\rightarrow W V → W 在 r r r 上不成立,只能 V ⊆ F + V\subseteq F^+ V ⊆ F + ,而 W W W 不是 a F + a_F^+ a F + 的子集,可是由上一步得知,W ⊈ F + W\not\subseteq F^+ W ⊆ F + 。所以r必定是关系模式 R < U , F > R<U,F> R < U , F > 的一个关系实例。
若 α → β \alpha\rightarrow\beta α → β 不能从 F F F 出发由Armstrong公理推出,则 β \beta β 不是 a F + a_F^+ a F + 的子集,因此,必有 β \beta β 的真子集 β ’ \beta’ β ’ 满足 β ⊆ U − a F + \beta \subseteq U - a_F^+ β ⊆ U − a F + ,则 α → β \alpha\rightarrow\beta α → β 在 r r r 中不成立,即 α → β \alpha\rightarrow\beta α → β 必不为 F F F 所逻辑蕴含。 补充:候选码的求解理论和算法 属性集的闭包包含了所有属性,则说明这是超码,只有当其所有可能的真子集都不是超码,这才是候选码。这是一个NP
问题。
如何判断一个属性集是否候选码。
下面我们给出简易的方法:
对于给定的关系模式 R ( U , F ) R(U,F) R ( U , F ) ,可将其属性分为4类:
L
类:仅出现在F的函数依赖左部 的属性
R
类:仅出现在F的函数依赖右部 的属性
N
类:在F的函数依赖两边均未出现 的属性
LR
类:在F的函数依赖两边均出现 的属性
定理1:对于给定的关系模式 R ( U , F ) R(U,F) R ( U , F ) ,若 α ( α ⊆ U ) \alpha (\alpha \subseteq U) α ( α ⊆ U ) 是L
类属性,则 α \alpha α 必为 R R R 的任意一个候选码的成员。
例:设关系模式 R ( U , F ) , U = { A , B , C , D } , F = { D → B , B → D , A D → B , A C → D } R(U,F),U = \{A,B,C,D\},F = \{D \rightarrow B,B \rightarrow D,AD \rightarrow B,AC \rightarrow D\} R ( U , F ) , U = { A , B , C , D } , F = { D → B , B → D , A D → B , A C → D } ,求R的候选码
解:A A A 、C C C 是 L
类属性, A C AC A C 必是 R R R 的一个候选码的成员,( A C ) F + = { A C D B } (AC)_F^+ = \{ACDB\} ( A C ) F + = { A C D B } ,( A ) F + = { A } (A)_F^+ = \{A\} ( A ) F + = { A } ,( C ) F + = { C } (C)_F^+ = \{C\} ( C ) F + = { C } ,所以 A C AC A C 是 R R R 的唯一候选码。(唯一性的确定可以参考下面的推论)
推论:对于给定的关系模式 R ( U , F ) R(U,F) R ( U , F ) ,若 α ( α ⊆ U ) \alpha (\alpha \subseteq U) α ( α ⊆ U ) 是L类属性,且 α F + \alpha_F^+ α F + 包含了U中的全部属性,则 α \alpha α 一定是R ( U , F ) R(U,F) R ( U , F ) 的唯一候选码
定理2:对于给定的关系模式 R ( U , F ) R(U,F) R ( U , F ) ,若 α ( α ⊆ U ) \alpha (\alpha \subseteq U) α ( α ⊆ U ) 是R类属性,则 α \alpha α 不包含在 R ( U , F ) R(U,F) R ( U , F ) 任何候选码中
定理3:对于给定的关系模式 R ( U , F ) R(U,F) R ( U , F ) ,若 α ( α ⊆ U ) \alpha (\alpha \subseteq U) α ( α ⊆ U ) 是N类属性,则 α \alpha α 必包含在 R ( U , F ) R(U,F) R ( U , F ) 的任意一个候选码中
示例1:设有关系模式 R ( U , F ) , U = { A , B , C , D , E , P } , F = { A → D , E → D , D → B , B C → D , D C → A } R(U,F),U = \{A,B,C,D,E,P\},F = \{A \rightarrow D,E \rightarrow D,D \rightarrow B,BC \rightarrow D,DC \rightarrow A\} R ( U , F ) , U = { A , B , C , D , E , P } , F = { A → D , E → D , D → B , BC → D , D C → A } ,求 R R R 的候选码
解:C E CE CE 是 L
类属性,C E CE CE 必在候选码中,P P P 是 N
类属性,P P P 也必须在候选码中,因为 ( C E P ) F + = { A B C D E P } (CEP)_F^+ = \{ABCDEP\} ( CEP ) F + = { A BC D EP } ,且C E P CEP CEP 的真子集都不是超码, 所以 C E P CEP CEP 是唯一的候选码
示例2:假设有关系模式 R ( U , F ) , U = { A , B , C , D , E } , F = { A → D , E → D , D → B , B C → D , D C → A } R(U,F),U = \{A,B,C,D,E\},F = \{A \rightarrow D,E \rightarrow D,D \rightarrow B,BC \rightarrow D,DC \rightarrow A\} R ( U , F ) , U = { A , B , C , D , E } , F = { A → D , E → D , D → B , BC → D , D C → A } ,求关系模式 R R R 的候选码
解:C E CE CE 未在函数依赖的右侧出现,C E CE CE 一定是候选码属性,( C E ) F + = { A B C D E } (CE)_F^+ = \{ABCDE\} ( CE ) F + = { A BC D E } ,且 C E CE CE 的真子集都不是超码,C E CE CE 是关系模式 R R R 的唯一候选码
示例3:假设有关系模式R ( U , F ) , U = { A , B , C , D , E } , F = { A → B C , C D → E , B → D , E → A } R(U,F),U = \{A,B,C,D,E\},F = \{A \rightarrow BC,CD \rightarrow E,B \rightarrow D,E \rightarrow A\} R ( U , F ) , U = { A , B , C , D , E } , F = { A → BC , C D → E , B → D , E → A } ,求 R R R 的所有候选码
解:A B C D E ABCDE A BC D E 在 F F F 的各个函数依赖的左侧和右侧均出现过(都是LR
),因此,候选码可能包含 A B C D E ABCDE A BC D E
可以除去 A B C D ABCD A BC D 属性,组成候选码的属性可能是 E E E ,( E ) F + = { A B C D E } (E)_F^+ = \{ABCDE\} ( E ) F + = { A BC D E } ,E E E 是候选码 因为 C D → E CD\rightarrow E C D → E ,所以可除去ABE,候选码的属性可能是CD,( C D ) F + = { A B C D E } (CD)_F^+ = \{ABCDE\} ( C D ) F + = { A BC D E } ,C F + = { C } , D F + = { D } C_F^+ = \{C\},D_F^+ = \{D\} C F + = { C } , D F + = { D } ,C D CD C D 是候选码 可除去 A D E ADE A D E ,候选码的可能属性是 B C BC BC ,( B C ) F + = { A B C D E } (BC)_F^+ = \{ABCDE\} ( BC ) F + = { A BC D E } ,B F + = { B D } B_F^+ = \{BD\} B F + = { B D } , C F + = { C } C_F^+ = \{C\} C F + = { C } ,B C BC BC 是候选码 还可除去 B C D E BCDE BC D E ,候选码为 A A A 这道题的主要收获就是我们往往可以通过一个确定的候选码以及与这个候选码相关的函数依赖来推断其他的候选码。如做这道题时我先确定了 C D CD C D ,这个是最显然的,然后依据 B → D B\rightarrow D B → D 推知 B C BC BC 也是候选码,然后由A → B C A\rightarrow BC A → BC 知 A A A 是候选码,又由 E → A E\rightarrow A E → A 知 E E E 是候选码。 正则覆盖 假设在一个关系模式上有一个函数依赖集 F F F 。当用户对于关系进行更新时,数据库系统将保证此操作不会破坏任何一个函数依赖
可以通过测试与给定函数依赖集有相同闭包的简化集的方式,来降低检测的开销
函数依赖集的等价和覆盖 函数依赖集 F , G F,G F , G ,若 F + = G + F^+= G^+ F + = G + ,则称 F F F 与 G G G 等价 。
若 F F F 与 G G G 等价,则称 F F F 是 G G G 的一个覆盖, G G G 是 F F F 的一个覆盖。
F + = G + ⟺ F ⊆ G + , G ⊆ F + F^+ = G^+ \iff F \subseteq G^+,G \subseteq F^+ F + = G + ⟺ F ⊆ G + , G ⊆ F +
如果去除一个函数依赖中的属性,不会改变该函数依赖集的闭包,则称该属性是无关的(extraneous)
对于函数依赖集 F F F 及 F F F 中函数依赖 α → β α\rightarrowβ α → β 。属性 A A A 在 α \alpha α 中是无关的,如果 A ∈ α A∈α A ∈ α ,并且 F ├ ( F – { α → β } ) ∪ { ( α − A ) → β } F├ (F – \{\alpha\rightarrow\beta\})∪\{(\alpha- A) \rightarrow \beta\} F ├ ( F – { α → β }) ∪ {( α − A ) → β } 。也就是说能由 F F F 推出 ( F – { α → β } ) ∪ { ( α − A ) → β } (F – \{α\rightarrowβ\})∪\{(α- A) \rightarrowβ\} ( F – { α → β }) ∪ {( α − A ) → β }
为什么不考虑( F – { α → β } ) ∪ { ( α − A ) → β } ├ F (F – \{α\rightarrowβ\})∪\{(α- A) \rightarrowβ\}├ F ( F – { α → β }) ∪ {( α − A ) → β } ├ F ? 我们假设右面的函数依赖集为 G G G ,那么对于 F F F ,F { − , − , α → β , − , − } F\{-,-,\alpha \rightarrow\beta,-,-\} F { − , − , α → β , − , − } ,对于G,G { − , − , ( α − A ) → β , − , − } G\{-,-,(\alpha-A)\rightarrow\beta,-,-\} G { − , − , ( α − A ) → β , − , − } ,显然如果 ( α − A ) → β (\alpha-A)\rightarrow\beta ( α − A ) → β ,那么一定有 α → β \alpha\rightarrow\beta α → β 对于函数依赖集 F F F 及 F F F 中函数依赖 α → β α\rightarrowβ α → β 。属性 A A A 在 β \beta β 中是无关的,如果 A ∈ β A∈\beta A ∈ β ,并且 ( F – { α → β } ) ∪ { α → ( β − A ) } ├ F (F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\}├\,F ( F – { α → β }) ∪ { α → ( β − A )} ├ F 。也就是说能由 ( F – { α → β } ) ∪ { α → ( β − A ) } (F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\} ( F – { α → β }) ∪ { α → ( β − A )} 推出 F F F
为什么不考虑 F ├ ( F – { α → β } ) ∪ { α → ( β − A ) } F├ (F – \{α\rightarrowβ\})∪\{α \rightarrow (β-A)\} F ├ ( F – { α → β }) ∪ { α → ( β − A )} 同上,α → β \alpha\rightarrow\beta α → β ,A ∈ β A\in \beta A ∈ β ,则必有 α → ( β − A ) \alpha\rightarrow (\beta-A) α → ( β − A ) 无关属性的核心:能够被函数依赖集 F F F 逻辑蕴涵的函数依赖,不必出现在F中
示例 F 1 = { A B → C , A → C } F_1 = \{AB \rightarrow C,A \rightarrow C\} F 1 = { A B → C , A → C } 中
F 2 = { A B → C D , A → C } F_2 = \{AB \rightarrow CD, A \rightarrow C\} F 2 = { A B → C D , A → C } 中
请找出上述两个函数依赖集中的无关属性
在 F 1 F_1 F 1 中,B B B 在 A B → C AB \rightarrow C A B → C 中是无关属性。
在 F 2 F_2 F 2 中,C C C 在 A B → C D AB \rightarrow CD A B → C D 中是无关属性。
检验无关属性的方法 考虑 α → β α\rightarrow β α → β 中的属性 A A A
如果 A ∈ α A\in α A ∈ α ,令 γ = α − { A } \gamma = α- \{A\} γ = α − { A } ,并计算 γ → β \gamma\rightarrow β γ → β 是否可以由 F F F 推出,即计算在函数依赖集 F F F 下的 γ F + \gamma_F^+ γ F + ,如果 γ F + \gamma_F^+ γ F + 包含 β β β 的所有属性,则 A A A 在 α α α 中是无关的 如果 A ∈ β A\in β A ∈ β ,F ’ = ( F − { α → β } ) ∪ { α → ( β − A ) } F’= ( F - \{α\rightarrow β\})∪\{α\rightarrow (β - A) \} F ’ = ( F − { α → β }) ∪ { α → ( β − A )} 检验 α → A α\rightarrow A α → A 是否能由 F ’ F’ F ’ 推导出,即计算函数依赖集F ’ F’ F ’ 下的 α F ’ + α_{F’}^+ α F ’ + ,如果 α F ’ + α_{F’}^+ α F ’ + 包含 A,则A在 β β β 中是无关的 注意处理无关属性的时候一次只处理一个函数依赖。 小技巧:若 α → β γ , β → γ \alpha\rightarrow\beta\gamma,\beta\rightarrow\gamma α → β γ , β → γ ,那么显然对于第一个式子, γ \gamma γ 是无关属性,因为 α → γ \alpha\rightarrow\gamma α → γ 是可以推导出来的。
若 α → β γ , α β → . . . \alpha\rightarrow\beta\gamma,\alpha\beta\rightarrow... α → β γ , α β → ... 可以考虑 β \beta β 是无关属性
样例 F = { A B → C D , A → E , E → C } F=\{AB \rightarrow CD, A \rightarrow E, E \rightarrow C\} F = { A B → C D , A → E , E → C } ,C C C 在 A B → C D AB \rightarrow CD A B → C D 上是否是无关属性?
F ’ = { A B → D , A → E , E → C } F’=\{AB \rightarrow D, A \rightarrow E, E \rightarrow C\} F ’ = { A B → D , A → E , E → C } 下A B AB A B 的属性闭包为 { A B C D E } \{ABCDE\} { A BC D E } ,包含 C C C ,因此C在 A B → C D AB \rightarrow CD A B → C D 上是无关属性
或者,显然 A → C A\rightarrow C A → C ,那么 A B → C AB\rightarrow C A B → C ,因此 C C C 在 A B → C D AB \rightarrow CD A B → C D 上是无关属性
正则覆盖(Canonical Cover) 满足下列条件的函数依赖集 F F F 称为正则覆盖,记作 F c F_c F c :
注意:正则覆盖未必唯一
计算算法 算法—计算函数依赖集 F F F 的正则覆盖 F c F_c F c
F c = F F_c = F F c = F
REPEAT
使用合并律将 F c F_c F c 中 α → β α\rightarrow β α → β 和 α → γ α\rightarrow \gamma α → γ 合并为 α → β γ α \rightarrow β\gamma α → β γ (保证左半边是唯一的)
找出在含无关属性的函数依赖 α → β α\rightarrow β α → β ,删除 α → β α\rightarrow β α → β 中的无关属性
UNTIL F c F_c F c 不再改变
注意:
检查无关属性是基于当前函数依赖集合中的函数依赖,而不是原始的 F F F
也就是说,检查无关属性的属性集是基于上一次的属性集的处理结果 不能同时讨论一个函数依赖中的两个属性的无关性,一次只能讨论一个属性
如果一个函数依赖的右半部只包含一个属性,例如, A → C A \rightarrow C A → C ,并且右边的属性是无关的,那么将得到一个右部为空的函数依赖,这样的函数依赖应该删除
从某种意义上说,F c F_c F c 是最小的,它不含无关属性,并且具有相同左半部的函数依赖都已经被合并,所以验证 F c F_c F c 比验证 F F F 本身更容易
最小覆盖 最小覆盖定义(补充):
关系模式 R ( U , F ) R(U,F) R ( U , F ) ,F F F 的最小覆盖记为 F m F_m F m ,F m F_m F m 满足: F m ⟺ F Fm\iff F F m ⟺ F ,并且:
F m F_m F m 不含无关属性
F m F_m F m 中函数依赖右端属性是唯一的
示例: R ( U , F ) , U = { A , B , C } , F = { A → B C , B → A C , C → A B } R(U,F) , U = \{A,B,C\},F=\{A→BC,B→AC,C→AB\} R ( U , F ) , U = { A , B , C } , F = { A → BC , B → A C , C → A B }
F c / F m : A → B , B → C , C → A F_c/F_m:A\rightarrow B,B\rightarrow C,C\rightarrow A F c / F m : A → B , B → C , C → A
F c / F m : A → C , C → B , B → A F_c/F_m : A→C,C→B,B→A F c / F m : A → C , C → B , B → A
F c : A → B C , B → A , C → A F_c : A\rightarrow BC,B\rightarrow A,C\rightarrow A F c : A → BC , B → A , C → A
F m : A → B , A → C , B → A , C → A F_m : A\rightarrow B, A\rightarrow C,B\rightarrow A,C\rightarrow A F m : A → B , A → C , B → A , C → A
正则覆盖样例 F = { A → B C , B → C , A → B , A B → C } F = \{A \rightarrow BC,B\rightarrow C,A\rightarrow B,AB\rightarrow C\} F = { A → BC , B → C , A → B , A B → C } ,计算 F c F_c F c
合并 A → B C A\rightarrow BC A → BC 和 A → B A\rightarrow B A → B 为 A → B C A\rightarrow BC A → BC
F 1 = { A → B C , B → C , A B → C } F_1 = \{A\rightarrow BC,B\rightarrow C,AB\rightarrow C\} F 1 = { A → BC , B → C , A B → C } B B B 在 A B → C AB\rightarrow C A B → C 中是无关的
F 2 = { A → B C , B → C , A → C } F_2 = \{A\rightarrow BC,B\rightarrow C,A\rightarrow C\} F 2 = { A → BC , B → C , A → C } 合并 A → B C A\rightarrow BC A → BC 和 A → C A\rightarrow C A → C 为 A → B C A\rightarrow BC A → BC
F 3 = { A → B C , B → C } F_3 = \{A\rightarrow BC,B\rightarrow C\} F 3 = { A → BC , B → C } C C C 在 A → B C A\rightarrow BC A → BC 中是无关的
F c = { A → B , B → C } F_c = \{A\rightarrow B,B\rightarrow C\} F c = { A → B , B → C } 示例2
F = { A B → C E , A → C , G P → B , E P → A , C D E → P , H B → P , D → H G , A B C → P G } F=\{AB \rightarrow CE,A \rightarrow C,GP \rightarrow B,EP \rightarrow A,CDE \rightarrow P,HB \rightarrow P,D \rightarrow HG,ABC \rightarrow PG\} F = { A B → CE , A → C , GP → B , EP → A , C D E → P , H B → P , D → H G , A BC → PG } ,求F c F_c F c
没有可以合并的函数依赖
在 A B → C E AB \rightarrow CE A B → CE 中,因为 A → C A \rightarrow C A → C ,所以C是无关属性
F 1 = { A B → E , A → C , G P → B , E P → A , C D E → P , H B → P , D → H G , A B C → P G } F_1 = \{AB \rightarrow E,A \rightarrow C,GP \rightarrow B,EP \rightarrow A,CDE \rightarrow P,HB \rightarrow P,D \rightarrow HG,ABC \rightarrow PG\} F 1 = { A B → E , A → C , GP → B , EP → A , C D E → P , H B → P , D → H G , A BC → PG } 因为 A → C , A B C → P G A \rightarrow C, ABC \rightarrow PG A → C , A BC → PG 中C是无关的
F c = { A B → E , A → C , G P → B , E P → A , C D E → P , H B → P , D → H G , A B → P G } F_c = \{AB \rightarrow E,A \rightarrow C,GP \rightarrow B,EP \rightarrow A,CDE \rightarrow P,HB \rightarrow P,D \rightarrow HG,AB \rightarrow PG\} F c = { A B → E , A → C , GP → B , EP → A , C D E → P , H B → P , D → H G , A B → PG }
示例3
模式 R ( U , F ) , U = { A , B , C } , F = { A → B C , B → A C , C → A B } R(U,F),U = \{A,B,C\},F=\{A→BC, B→AC, C→AB\} R ( U , F ) , U = { A , B , C } , F = { A → BC , B → A C , C → A B }
正则覆盖有多个:
F c 1 = { A → B , B → C , C → A } F_{c1}=\{A→B, B→C, C→A\} F c 1 = { A → B , B → C , C → A }
F = { A → B C , B → A C , C → A B } F=\{A→BC, B→AC, C→AB\} F = { A → BC , B → A C , C → A B }
F 1 = { A → B , B → A C , C → A B } F_1=\{A→B, B→AC, C→AB\} F 1 = { A → B , B → A C , C → A B }
F 2 = { A → B , B → C , C → A B } F_2=\{A→B, B→C, C→AB\} F 2 = { A → B , B → C , C → A B }
F c = { A → B , B → C , C → A } F_c=\{A→B, B→C, C→A\} F c = { A → B , B → C , C → A }
F c 2 = { A → B , B → A C , C → B } F_{c2}=\{A→B, B→AC, C→B\} F c 2 = { A → B , B → A C , C → B }
F c 3 = { A → C , C → B , B → A } F_{c3}=\{A→C, C→B , B→A\} F c 3 = { A → C , C → B , B → A }
F c 4 = { A → C , B → C , C → A B } F_{c4}=\{A→C, B→C, C→AB\} F c 4 = { A → C , B → C , C → A B }
F c 5 = { A → B C , B → A , C → A } F_{c5} = \{A→BC, B→A, C→A\} F c 5 = { A → BC , B → A , C → A }
示例4
F = { E → G , G → E , F → E G , H → E G , F H → E } F=\{E → G,G → E,F → EG,H → EG,FH → E\} F = { E → G , G → E , F → EG , H → EG , F H → E } ,计算 F c F_c F c
1、无需合并
2、在 F H → E FH → E F H → E 中,F F F 是无关属性,因此,F 1 = { E → G , G → E , F → E G , H → E G } F_1=\{E → G,G → E,F → EG,H → EG\} F 1 = { E → G , G → E , F → EG , H → EG }
3、在 F 1 F_1 F 1 中, F → E G F → EG F → EG 和 H → E G H → EG H → EG 中,E G EG EG 均为无关属性
最终: F c 1 = { E → G , G → E , F → G , H → G } F_{c1}= \{E → G,G → E,F → G,H → G\} F c 1 = { E → G , G → E , F → G , H → G }
F c 2 = { E → G , G → E , F → G , H → E } F_{c2}= \{E → G,G → E,F → G,H → E\} F c 2 = { E → G , G → E , F → G , H → E }
F c 3 = { E → G , G → E , F → E , H → E } F_{c3}= \{E → G,G → E,F → E,H → E\} F c 3 = { E → G , G → E , F → E , H → E }
F c 4 = { E → G , G → E , F → E , H → G } F_{c4}= \{E → G,G → E,F → E,H → G\} F c 4 = { E → G , G → E , F → E , H → G }
示例5
关系模式 R , U = { A , B , C , D , E } R,U = \{A,B,C,D,E\} R , U = { A , B , C , D , E } ,有两个函数依赖集 F F F 和 G G G ,F = { A → B , A B → C , D → A C , D → E } F = \{A → B,AB → C,D → AC,D → E\} F = { A → B , A B → C , D → A C , D → E } 和 G = { A → B C , D → A E } G = \{A → BC,D → AE\} G = { A → BC , D → A E } ,F F F 和 G G G 是否等价?
关系模式的设计问题 示例 考虑为管理职工的级别和工资信息而设计一个关系模式(主码:职工姓名,假设职工不重名)
信息的不可表示问题
插入异常 :如果没有职工具有8级工资,则8级工资的工资数额就难以插入删除异常 :如果仅有职工赵明具有4级工资,如果将赵明删除,则有关4级工资的工资数额信息也随之删除了信息的冗余问题
数据冗余 :职工很多,工资级别有限,每一级别的工资数额反复存储多次更新异常 :如果将5级工资的工资数额调为650,则需要找到每个具有5级工资的职工,逐一修改解决之道:分解 模式分解 模式分解的定义 函数依赖集合 F_i = \{\alpha \rightarrow \beta \,|\, \alpha \rightarrow \beta \in F^+ \and (\alpha\, \beta) \subseteq U_i\}称为 F F F 在 U i U_i U i 上的投影
关系模式 R < U , F > R<U , F> R < U , F > 的一个分解是指 ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > , … , R n < U n , F n > } \rho = \{R_1<U_1 , F_1> , R_2<U_2 , F_2>, … , R_n<U_n , F_n>\} ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > , … , R n < U n , F n > }
其中 U = U 1 ∪ U 2 ∪ … ∪ U n U= U_1 \cup U_2 \cup … \cup U_n U = U 1 ∪ U 2 ∪ … ∪ U n ,并且没有 U i ⊆ U j , 1 ≤ i , j ≤ n U_i \subseteq U_j,1≤i,j ≤n U i ⊆ U j , 1 ≤ i , j ≤ n , F i F_i F i 是 F F F 在 U i U_i U i 上的投影,称为限定(restriction)
分解的基本代数运算
分解的要求
无损连接分解(分解的底线,必须保证) 保持函数依赖(尽量保持) 模式分解中的问题 有损与无损 原来的关系得不到正确的还原。
函数依赖的保持 某些关系丢失(如 B → C B\rightarrow C B → C 丢失)
无损连接分解 关系模式 R < U , F > , U = U 1 ∪ U 2 ∪ … ∪ U n R<U , F> , U = U_1 \cup U_2 \cup … \cup U_n R < U , F > , U = U 1 ∪ U 2 ∪ … ∪ U n
ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > , … , R n < U n , F n > } \rho = \{R_1<U_1 , F_1> , R_2<U_2 , F_2>, … , R_n<U_n , F_n>\} ρ = { R 1 < U 1 , F 1 > , R 2 < U 2 , F 2 > , … , R n < U n , F n > } 是 R < U , F > R<U , F> R < U , F > 的一个分解,ρ \rho ρ 是 R < U , F > R<U , F> R < U , F > 的一个关系实例,定义 m ρ ( r ) = ⋈ i = 1 n ∏ U i ( r ) m_{\rho}(r) = \overset {n} {\mathop{\bowtie } \limits_{i=1} }∏U_i(r) m ρ ( r ) = i = 1 ⋈ n ∏ U i ( r ) ,若对于 R < U , F > R<U , F> R < U , F > 的任一个关系实例 r r r ,都有 r = m ρ ( r ) r = m_{\rho}(r) r = m ρ ( r ) ,则称 r r r 是 R < U , F > R<U , F> R < U , F > 的一个无损连接分解。
无损连接分解判断-表格法 设关系模式 R ( U , F ) , U = A 1 , … , A n R(U,F),U = {A_1,…,A_n} R ( U , F ) , U = A 1 , … , A n ,R R R 的一个分解 ρ = { R 1 , … , R k } \rho = \{R_1,…,R_k\} ρ = { R 1 , … , R k } 。无损连接分解表格法的判断步骤如下:
构造一张 k k k 行 n n n 列的表格,每列对应一个属性 A j ( 1 ≤ j ≤ n ) A_j(1≤j≤n) A j ( 1 ≤ j ≤ n ) ,每行对应一个模式 R i ( 1 ≤ i ≤ k ) R_i(1≤i≤k) R i ( 1 ≤ i ≤ k ) 。如果 A j A_j A j 在 R i R_i R i 中,那么在表格的第 i i i 行第 j j j 列处填上符号 a j a_j a j ,否则填上符号 b i j b_{ij} b ij 。
把表格看成模式 R R R 的一个关系实例,反复检查 F F F 中每个 f f f 在表格中是否成立,若不成立,则修改表格中的元素。修改方法如下:
对于 F F F 中一个 f : α → β f: \alpha \rightarrow \beta f : α → β ,如果表格中有多行在 α \alpha α 分量上相等,在 β \beta β 分量上不相等,那么把这些行在 β \beta β 分量上改成相等:如果 β \beta β 的分量中有一个是 a j a_j a j ,那么另一个也改成 a j a_j a j ;如果没有 a j a_j a j ,那么用其中的一个 b i j b_{ij} b ij 替换另一个(尽量把 i j ij ij 改成较小的数,亦即取 i i i 值较小的那个)。 若在修改的过程中,发现表格中有一行全是 α \alpha α ,即 α 1 , α 2 , … , α n \alpha_1,\alpha_2,…,\alpha_n α 1 , α 2 , … , α n ,那么可立即断定分解 r r r 相对于 F F F 是无损连接分解,此时不必再继续修改。若经过多次修改直到表格不能修改时,发现表格中不存在有一行全是 α \alpha α 的情况,那么分解就是有损的。
示例 已知 R < U , F > , U = { A , B , C , D , E } , F = { A → C , B → C , C → D , D E → C , C E → A } R<U,F>,U = \{A,B,C,D,E\},F = \{A→C,B→C,C→D,DE→C,CE→A\} R < U , F > , U = { A , B , C , D , E } , F = { A → C , B → C , C → D , D E → C , CE → A } ,R R R 的一个分解为 R 1 ( A D ) , R 2 ( A B ) , R 3 ( B E ) , R 4 ( C D E ) , R 5 ( A E ) R_1(AD),R_2(AB),R_3(BE),R_4(CDE),R_5(AE) R 1 ( A D ) , R 2 ( A B ) , R 3 ( BE ) , R 4 ( C D E ) , R 5 ( A E ) ,判断这个分解是否具有无损连接性。
表格初始化如上图,对于 A → C A \rightarrow C A → C ,在 R 1 , R 2 , R 5 R_1,R_2,R_5 R 1 , R 2 , R 5 上属性 A A A 列的值都是 a 1 a_1 a 1 ,则将对应属性C C C 那一列的值改成一样的,列中没有 a a a ,所以将这三行在该列上的值都改为 b 13 b_{13} b 13 。
改完后如下。
对于 B → C B \rightarrow C B → C , 在 R 2 , R 3 R_2,R_3 R 2 , R 3 上属性 B B B 列的值都是 a 2 a_2 a 2 ,则将对应属性C C C 那一列的值改成一样的,列中没有 a a a ,所以将这两行在该列上的值都改为 b 13 b_{13} b 13 。
改完后如下。
以此类推。
改完后:
说明分解是无损的。
无损连接分解判断-快速法 前提:分解后的关系模式只有两个
在函数依赖约束下,是必要条件 ,可能有多值依赖
关系模式 R ( U , F ) R(U,F) R ( U , F ) 的分解 ρ = { R 1 , R 2 } \rho=\{R_1,R_2\} ρ = { R 1 , R 2 } ,则 ρ \rho ρ 是一个无损连接分解的充分条件是R 1 ∩ R 2 → R 1 R_1∩R_2\rightarrow R_1 R 1 ∩ R 2 → R 1 或 R 1 ∩ R 2 → R 2 R_1∩R_2\rightarrow R_2 R 1 ∩ R 2 → R 2 成立,或:R 1 ∩ R 2 → R 1 − R 2 R_1∩R_2\rightarrow R_1 - R_2 R 1 ∩ R 2 → R 1 − R 2 或 R 1 ∩ R 2 → R 2 − R 1 R_1∩R_2\rightarrow R_2 - R_1 R 1 ∩ R 2 → R 2 − R 1
(R 1 , R 2 R_1,R_2 R 1 , R 2 表示两个关系模式中的属性)
示例 R ( U , F ) , U = { A , B , C } , F = { A → B } , r = { R 1 ( A B ) , R 2 ( A C ) } R(U,F),U = \{A, B, C\}, F=\{A \rightarrow B\}, r=\{R_1(AB), R_2(AC)\} R ( U , F ) , U = { A , B , C } , F = { A → B } , r = { R 1 ( A B ) , R 2 ( A C )}
R 1 ∩ R 2 = A , R 1 - R 2 = B R_1∩R_2 = A, R_1-R_2 = B R 1 ∩ R 2 = A , R 1 - R 2 = B
由 A → B A \rightarrow B A → B ,得到 ρ \rho ρ 是无损连接分解
保持函数依赖的分解 给定关系模式 R ( U , F ) R(U,F) R ( U , F ) ,γ \gamma γ 是 U U U 的子集,函数依赖集合 F F F 在 γ \gamma γ 上的投影定义为
\Pi_{\gamma}(F) =\{\alpha \rightarrow \beta \,|\, \alpha\rightarrow \beta \in F^+ \and \alpha\beta \subseteq \gamma\}设 ρ = { R 1 , R 2 , … , R n } \rho = \{R_1, R_2, …, R_n\} ρ = { R 1 , R 2 , … , R n } 是关系模式 R < U , F > R<U , F> R < U , F > 的一个分解,如果 F + = ( ∏ R 1 ( F ) ∪ … ∪ ∏ R n ( F ) ) + F^+ = (∏R_1 (F)\cup … \cup ∏R_n (F))^+ F + = ( ∏ R 1 ( F ) ∪ … ∪ ∏ R n ( F ) ) + (两个闭包相等),则称 ρ \rho ρ 是保持函数依赖的分解
判定保持依赖 通过检查 F F F 中的每一个函数依赖都在分解后的某一个关系上成立,可以判断这个分解是否是保持依赖的。
但是,有时分解是保持依赖的,但是 F F F 上的一个依赖不在分解后的任何一个关系上成立,也有可能是保持依赖的分解 。只要 F + = ( ∏ R 1 ( F ) ∪ … ∏ R n ( F ) ) + F^+ = (∏R_1 (F)\cup … ∏R_n (F))^+ F + = ( ∏ R 1 ( F ) ∪ … ∏ R n ( F ) ) + 即可。因此这个验证只能是充分条件,必须寻找其他的判断方法。
为了避免计算 F + F^+ F + ,给出一种更有效的算法。思想如下:通过使用修改后的属性闭包的形式,判断 F F F 上的每一个函数依赖 α → β α\rightarrow β α → β 在分解中是否被保持 。
例如对于 R ( U , F ) , U = { A , B , C } , F = { A → B , B → C } R(U,F),U = \{A, B, C\},F= \{A\rightarrow B , B\rightarrow C\} R ( U , F ) , U = { A , B , C } , F = { A → B , B → C } 的分解 ρ { < { A B } , { A → B } > , < { A C } , { A → C } > } \rho\{<\{AB\},\{A\rightarrow B\}>,<\{AC\},\{A\rightarrow C\}>\} ρ { < { A B } , { A → B } > , < { A C } , { A → C } > }
我们只需要判断:B → C ∈ { A → B , A → C } + B\rightarrow C\in \{A\rightarrow B, A\rightarrow C\}^+ B → C ∈ { A → B , A → C } + 是否成立
也就是判断 C ∈ B { A → B , A → C } + C\in B^+_{\{A\rightarrow B, A\rightarrow C\}} C ∈ B { A → B , A → C } + ,也就是属性 B B B 在该属性集下的闭包是否包含 C C C
算法 模式分解示例 示例1:设关系模式 R < U , F > R<U, F> R < U , F > ,其中 U = { A , B , C , D , E } , F = { A → B C , C → D , B C → E , E → A } U=\{A, B, C, D, E\},F=\{A→BC,C→D,BC→E,E→A\} U = { A , B , C , D , E } , F = { A → BC , C → D , BC → E , E → A } ,则分解 ρ = { R 1 ( A B C E ) , R 2 ( C D ) } ρ=\{R_1(ABCE),R_2(CD)\} ρ = { R 1 ( A BCE ) , R 2 ( C D )} 满足以下哪一条?
–A.具有无损连接性、保持函数依赖
–B.不具有无损连接性、保持函数依赖
–C.具有无损连接性、不保持函数依赖
–D.不具有无损连接性、不保持函数依赖
A
示例2:给定关系模式 R < U , F > , U = { A , B , C , D , E } , F = { B → A , D → A , A → E , A C → B } R<U, F>,U=\{A, B, C, D, E\},F=\{B→A,D→A,A→E,AC→B\} R < U , F > , U = { A , B , C , D , E } , F = { B → A , D → A , A → E , A C → B } ,其候选码为?则分解 ρ = { R 1 ( A B C E ) , R 2 ( C D ) } ρ=\{R_1(ABCE),R_2(CD)\} ρ = { R 1 ( A BCE ) , R 2 ( C D )} 满足?
候选码为 C D CD C D ,不具有无损连接性、不保持函数依赖
B → A , A → E , A C → B B→A,A→E,AC→B B → A , A → E , A C → B 在 R 1 R_1 R 1 上成立,D → A D→A D → A 在 R 1 R_1 R 1 和 R 2 R_2 R 2 上都不成立,因此需做进一步判断。
对于 D → A D→A D → A 应用保持依赖算法:
Result = D
对R 1 R_1 R 1 ,r e s u l t ∩ R 1 = ∅ result∩R_1 = \emptyset res u lt ∩ R 1 = ∅ ,t t t 为 ∅ \emptyset ∅ ,result = D
再对 R 2 R_2 R 2 ,r e s u l t ∩ R 2 = D result∩R_2 = D res u lt ∩ R 2 = D ,( D ) + = { A D E } , t = ( D ) + ∩ R 2 = D (D)^+ = \{ADE\} ,t = (D)^+ ∩R_2 = D ( D ) + = { A D E } , t = ( D ) + ∩ R 2 = D ,result = D
一个循环后result未发生变化,因此最后result = D,并未包含 A A A ,所以 D → A D→A D → A 未被保持,该分解不是保持依赖的。
示例3:给定关系模式 R ( U , F ) , U = { A , B , C , D , E , F } , F = { A → B C , C D → E , B → D , B E → F , E F → A } R(U, F),U =\{A,B,C,D,E,F\},F = \{A → BC, CD → E, B → D, BE → F, EF → A\} R ( U , F ) , U = { A , B , C , D , E , F } , F = { A → BC , C D → E , B → D , BE → F , EF → A } ,请说明下列分解是否是无损连接分解?是否是保持依赖的分解?ρ = { R 1 ( A B C D ) , R 2 ( E F A ) } ρ= \{R_1(ABCD),R_2(EFA)\} ρ = { R 1 ( A BC D ) , R 2 ( EF A )}
判断无损连接分解:R 1 ∩ R 2 = { A } , A F + = { A , B , C , D , E , F } R_1 ∩ R_2 = \{A\},A^+_F = \{A, B, C, D, E, F\} R 1 ∩ R 2 = { A } , A F + = { A , B , C , D , E , F } ,而 A → R 1 A → R_1 A → R 1 ,所以是无损连接分解
判断保持依赖的分解:观察 C D → E CD → E C D → E 和 B E → F BE → F BE → F 是否被保持?C D → E CD → E C D → E 和 B E → F BE → F BE → F 没有被保持
示例4:给定关系模式 R ( U , F ) , U = { A , B , C , D , E , F } , F = { A → B C , C D → E , B → D , B E → F , E F → A } R(U, F),U =\{A,B,C,D,E,F\},F = \{A → BC, CD → E, B → D, BE → F, EF → A\} R ( U , F ) , U = { A , B , C , D , E , F } , F = { A → BC , C D → E , B → D , BE → F , EF → A } ,请说明下列分解是否是无损连接分解?是否是保持依赖的分解?ρ = { ( A B C ) , ( B D ) , ( B E F ) } ρ = \{(ABC),(BD),(BEF)\} ρ = {( A BC ) , ( B D ) , ( BEF )}
非无损
判断保持依赖的分解:观察 C D → E CD → E C D → E 和 E F → A EF →A EF → A 是否被保持?C D → E CD → E C D → E 和 E F → A EF → A EF → A 没有被保持
范式 范式(1NF等)指该范式的定义,同时也代表满足该范式的关系模式的集合,比如 2 N F ⊂ 1 N F , R ∈ 1 N F 2NF \subset 1NF,R\in 1NF 2 NF ⊂ 1 NF , R ∈ 1 NF
1NF 关系中每一分量不可再分。即不能以集合、序列等作为属性值。
2NF 样例 关系模式 S ( s n o , s n a m e , d n o , d e a n , c n o , s c o r e ) S(sno, sname, dno, dean, cno, score) S ( s n o , s nam e , d n o , d e an , c n o , score )
主码:sno, cno
不良特性插入异常:如果学生没有选课,关于他的个人信息及所在学院的信息就无法插入 删除异常:如果删除学生的选课信息,则有关他的个人信息及所在学院的信息也随之删除 更新异常:如果学生转专业,若他选修了k门课,则需要修改k次 数据冗余:如果一个学生选修了k门课,则有关他的所在学院的信息重复 改造 属性有两种,一种完全依赖于候选码,一种部分依赖于候选码。
将S分解为:
S C ( s n o , c n o , s c o r e ) SC(sno , cno , score) SC ( s n o , c n o , score ) ,主码:s n o , c n o sno,cno s n o , c n o
S _ S D ( s n o , s n a m e , d n o , d e a n ) S\_SD(sno, sname, dno, dean) S _ S D ( s n o , s nam e , d n o , d e an ) ,主码:s n o sno s n o
定义 若 R ∈ 1 N F R\in 1NF R ∈ 1 NF ,且每个属性满足下列准则之一:
它出现在一个候选码中 它没有部分依赖于一个候选码 (也就是说不存在候选码的一部分决定该属性的情况)则 R ∈ 2 N F R\in 2NF R ∈ 2 NF
核心就是消除非主属性对候选码的部分依赖
上面的例子中,s n a m e , d n o sname,dno s nam e , d n o 不出现在候选码中,且部分依赖候选码
3NF 样例 S _ S D ( s n o , s n a m e , d n o , d e a n ) S\_SD(sno, sname, dno, dean) S _ S D ( s n o , s nam e , d n o , d e an )
不良特性插入异常:如果学院没有学生,则有关学院的信息就无法插入 删除异常:如果学生全部毕业了,则在删除学生信息的同时有关学院的信息也随之删除了 更新异常:如果学生转专业,不但要修改dno,还要修改dean,如果换院长,则该学院每个学生元组都要做相应修改 数据冗余:每个学生存储了所在院长的信息 S S D ∉ 3 N F S_SD \not \in3NF S S D ∈ 3 NF ,因为有 s n o → d n o , d n o → d e a n sno\rightarrow dno,dno\rightarrow dean s n o → d n o , d n o → d e an
改造 将S_SD分解为 S ( s n o , s n a m e , d n o ) S (sno, sname, dno) S ( s n o , s nam e , d n o ) ,D ( d n o , d e a n ) D (dno, dean) D ( d n o , d e an )
定义 关系模式 R < U , F > R<U , F> R < U , F > 中,F + F^+ F + 中所有函数依赖 α → β α\rightarrow β α → β ,至少有以下之一成立 :
α → β α\rightarrow β α → β 是平凡的函数依赖 ;α α α 是超码 ;β − α β - α β − α (集合做差)的每一个属性 A A A 都包含在 R R R 的候选码 中,则称 R ∈ 3 N F R\in 3NF R ∈ 3 NF 。注意:并不要求集合之差在同一个 候选码当中 注意候选码是要保证完全依赖的,否则是超码 关系模式 R < U , F > R< U , F > R < U , F > 中,若不存在这样的某一个码 X X X ,属性组 Y Y Y 及非主属性 Z ( Z ⊄ Y ) Z(Z \not \sub Y) Z ( Z ⊂ Y ) ,使得下式成立: X → Y , Y → Z , Y ↛ X X\rightarrow Y , Y\rightarrow Z , Y\not\rightarrow X X → Y , Y → Z , Y → X ,(构成了一个传递依赖) 则称 R ∈ 3 N F R\in 3NF R ∈ 3 NF
主属性:包含在候选码 中的属性 即 R R R 中没有非主属性 Z Z Z 传递依赖于 R R R 的某一个码 PS.作为判断3NF时的一种优化,可以只考虑 F F F 上的函数依赖,而不是 F + F^+ F + ,也可以分解 F F F 上的函数依赖,让它们的右半部只包含一个属性,并用这个结果代替 F F F
关系模式分解算法 简单算法 分解后的关系要达到3NF且保持函数依赖的分解
输入:关系模式 R ( U , F ) R(U,F) R ( U , F )
计算 F F F 的正则覆盖 F c F_c F c
若有 α → β ∈ F c α\rightarrow β\in F_c α → β ∈ F c ,且 α ∪ β = U α\cup β = U α ∪ β = U ,则算法终止
对 F c F_c F c 按具有相同左部 的原则进行分组 (设为k组),每一组函数依赖所涉及的属性全体为 U i U_i U i ,令 F i F_i F i 为 F c F_c F c 在 U i U_i U i 上的投影 ,则 ρ = { R 1 < U 1 , F 1 > , … , R k < U k , F k > } \rho = \{R_1<U_1 , F_1> , … , R_k<U_k , F_k>\} ρ = { R 1 < U 1 , F 1 > , … , R k < U k , F k > } 是 R < U , F > R<U , F> R < U , F > 的一个保持函数依赖的分解,并且每个R i < U i , F i > ∈ 3 N F R_i<U_i , F_i> \in 3NF R i < U i , F i >∈ 3 NF
返回 ρ \rho ρ
示例1 R ( U , F ) , U = { s n o , d n o , d e a n , c n o , s c o r e } R(U,F),U=\{sno,dno,dean,cno,score\} R ( U , F ) , U = { s n o , d n o , d e an , c n o , score }
F = { s n o → d n o , s n o → d e a n , d n o → d e a n , ( s n o , c n o ) → s c o r e } F=\{sno\rightarrow dno,sno\rightarrow dean,dno\rightarrow dean,(sno,cno)\rightarrow score\} F = { s n o → d n o , s n o → d e an , d n o → d e an , ( s n o , c n o ) → score }
F C = { s n o → d n o , d n o → d e a n , ( s n o , c n o ) → s c o r e } F_C=\{sno\rightarrow dno,dno\rightarrow dean ,(sno,cno)\rightarrow score\} F C = { s n o → d n o , d n o → d e an , ( s n o , c n o ) → score }
分组
R 1 { ( s n o , d n o ) , s n o → d n o } R_1 \{(sno,dno),sno\rightarrow dno\} R 1 {( s n o , d n o ) , s n o → d n o }
R 2 { ( d n o , d e a n ) , d n o → d e a n } R_2 \{(dno,dean),dno\rightarrow dean\} R 2 {( d n o , d e an ) , d n o → d e an }
R 3 { ( s n o , c n o , s c o r e ) , ( s n o , c n o ) → s c o r e } R_3 \{(sno,cno,score), (sno,cno)\rightarrow score\} R 3 {( s n o , c n o , score ) , ( s n o , c n o ) → score }
可以验证,这是无损分解。
显然候选码是AB,因为这两个是L类属性而C是R类属性。
由于A或B都不是超码,而且C不在候选码中,所以不属于3NF。
R 1 ∩ R 2 = { A } , A → C , A → R 1 R_1\cap R_2=\{A\},A\rightarrow C,A\rightarrow R_1 R 1 ∩ R 2 = { A } , A → C , A → R 1 ,所以是无损连接。按函数依赖,显然有损
解决上面的问题:3NF合成算法 输入关系模式 R ( U , F ) R(U,F) R ( U , F ) ,在前面算法的基础上
1、ρ = { R 1 < U 1 , F 1 > , … , R k < U k , F k > } \rho = \{R_1<U_1 , F_1> , … , R_k<U_k , F_k>\} ρ = { R 1 < U 1 , F 1 > , … , R k < U k , F k > } 是 R < U , F > R<U , F> R < U , F > 的一个保持函数依赖 的3NF分解
2、设 α \alpha α 为 R < U , F > R<U , F> R < U , F > 的任意候选码 ,若有某个 U i U_i U i , α ⊆ U i \alpha \subseteq U_i α ⊆ U i ,则 ρ \rho ρ 即为达到3NF且同时保持无损连接与函数依赖的分解,否则令 τ = ρ ∪ { R ∗ < α , F α > } τ = \rho∪\{R* < \alpha ,F_{\alpha}>\} τ = ρ ∪ { R ∗ < α , F α > }
返回 τ τ τ
教材算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 令Fc为F的一个正则覆盖 i = 0 for each Fc中的函数依赖α-β(用-代替右箭头) i := i + 1; Ri := αβ; if 模式Rj, j = 1,2,…,i 都不包含R的候选码 then i := i + 1; Ri := R的任意候选码; repeat/*删除冗余关系模式*/ //下面是相对上面算法多出的部分 if 模式 Rj 包含于另一个模式Rk中 then Rj := Ri; i := i – 1; Until 没有可以删除的Rj return (R1,R2,…Ri)
算法比较
合成算法的算法正确性分析 三个条件:保持依赖、无损、分解结果的关系是3NF
保持依赖 无损连接 通过保证至少有一个模式包含了被分解模式的候选码 ,该算法保证了分解是一个无损连接分解。证明如下:
注意:有损分解一定是多了一些元组。
那么就不存在这样的 t t t ,那就一定是无损的(没有多出来的元组)
注意第三点:元组t t t 是由 r r r 中投影得来的,所以一定有 t [ α ] ∈ r i t[\alpha]\in r_i t [ α ] ∈ r i ,而且注意其候选码上的值相等,则就是同一个元组。 每个关系模式都是3NF 如果关系模式 R i R_i R i 在由3NF综合算法产生的分解中,则 R i ∈ 3 N F R_i∈3NF R i ∈ 3 NF ,考虑 R i R_i R i 上的任意函数依赖 γ → B \gamma \rightarrow B γ → B (此处 B B B 满足右侧单一属性)满足3NF的定义 。证明如下:
假定综合算法中产生 R i R_i R i 的函数依赖是 α → β ( α → β ∈ F c ) α\rightarrow β (α\rightarrow β ∈ F_c) α → β ( α → β ∈ F c ) (那么U i = α β U_i=\alpha\beta U i = α β ),B ∈ R i B∈ R_i B ∈ R i ,则 B ∈ α B∈α B ∈ α 或者 B ∈ β B∈β B ∈ β ,考虑下列三种情况:
B ∈ α ∧ B ∈ β B∈α∧B∈β B ∈ α ∧ B ∈ β :因为B在 β β β 中是无关属性(比如 A B → B C AB \rightarrow BC A B → BC ),所以 α → β α\rightarrow β α → β 不会出现在 F c F_c F c 中(正则覆盖保证无无关属性),这种情况不成立
B ∉ α ∧ B ∈ β B\not\in α∧B∈β B ∈ α ∧ B ∈ β :
γ \gamma γ 是一个超码,则 R i ∈ 3 N F R_i∈3NF R i ∈ 3 NF 注意到 α \alpha α 是 R i R_i R i 唯一的候选码,那么 R i R_i R i 的任意超码都要包含 α \alpha α 。如果γ \gamma γ 不是一个超码,则 α α α 中一定包含一些不在 γ \gamma γ 中的属性。因为 γ → B \gamma \rightarrow B γ → B 在 F + F^+ F + 中,通过 B ∈ γ F c + B∈ \gamma^+_{F_c} B ∈ γ F c + 得到的。 γ → B \gamma \rightarrow B γ → B 的推导不会用到 α → β α\rightarrow β α → β ,否则 α ∈ γ F c + α∈ \gamma^ +_{F_c} α ∈ γ F c + ,因为假定 γ \gamma γ 不是超码(如果用到 α → β α\rightarrow β α → β ,就会得到 γ → α \gamma\rightarrow \alpha γ → α ,说明 γ \gamma γ 是超码),所以上述结论是不成立的。现在,使用 α → ( β − { B } ) α\rightarrow (β- \{B\}) α → ( β − { B }) 和 γ → B \gamma \rightarrow B γ → B ,得到 α → B α\rightarrow B α → B ,这表明 B B B 在 α → β α\rightarrow β α → β 中是右无关属性,这也是不可能的(因为 α → β α\rightarrow β α → β 是 F c F_c F c 中的函数依赖,不存在无关属性)。所以,如果 B ∈ β B∈β B ∈ β ,则 γ \gamma γ 一定是超码。 B ∈ α ∧ B ∉ β B∈ α∧B \not\in β B ∈ α ∧ B ∈ β :因为 α α α 是候选码,3NF的第三个条件满足。
示例 设有关系模式 R ( U , F ) , U = { A B C D E F G H I } , F = { A B → C , A → D E , B → G H , D → I } R(U,F),U= \{ABCDEFGHI\},F=\{AB→C,A→DE,B→GH,D→I\} R ( U , F ) , U = { A BC D EFG H I } , F = { A B → C , A → D E , B → G H , D → I } ,试求:
R R R 的候选码;
将 R R R 分解成属于3NF,并且具有保持依赖性和无损连接。
1.候选码:ABF
2.首先求出F的正则覆盖F c = { A B → C , A → D E , B → G H , D → I } , F_c=\{AB→C,A→DE,B→GH,D→I\}, F c = { A B → C , A → D E , B → G H , D → I } ,
得了 τ = ( { A B C } , { A D E } , { B G H } , { D I } , { A B F } ) τ =(\{ABC\}, \{ADE\}, \{BGH\}, \{DI\}, \{ABF\}) τ = ({ A BC } , { A D E } , { BG H } , { D I } , { A BF })
BCNF 样例 关系模式 S T C ( U , F ) STC(U,F) STC ( U , F ) ,每位老师只教授一门课。其中
U = { s n o , t n o , c n o } U=\{sno , tno , cno\} U = { s n o , t n o , c n o }
F = { t n o → c n o , ( s n o , t n o ) → c n o , ( s n o , c n o ) → t n o } F=\{tno \rightarrow cno, (sno,tno)\rightarrow cno, (sno,cno)\rightarrow tno\} F = { t n o → c n o , ( s n o , t n o ) → c n o , ( s n o , c n o ) → t n o }
( s n o , t n o ) , ( s n o , c n o ) (sno,tno),(sno,cno) ( s n o , t n o ) , ( s n o , c n o ) 为候选码。
不良特性 插入异常:如果没有学生选修某位老师的任课,则该老师担任课程的信息就无法插入
删除异常:删除学生选课信息,会删除掉老师的任课信息
更新异常:如果老师所教授的课程有所改动,则所有选修该老师课程的学生元组都要做改动
数据冗余:每位学生都存储了有关老师所教授的课程的信息
原因
改造
将STC分解为:( s n o , t n o ) , ( t n o , c n o ) (sno,tno),(tno,cno) ( s n o , t n o ) , ( t n o , c n o )
定义 关系模式 R < U , F > R< U , F > R < U , F > 中,所有的形如 α → β α\rightarrow β α → β 的函数依赖 ( α ⊆ U , β ⊆ U ) ( α\subseteq U,β\subseteq U ) ( α ⊆ U , β ⊆ U ) ,下面至少有一个成立
如 S T C ∉ B C N F STC \not\in BCNF STC ∈ BCNF ,因为 t n o → c n o tno \rightarrow cno t n o → c n o ,而 t n o tno t n o 不是超码
BCNF的本质 判断关系模式是否属于BCNF 检查非平凡的函数依赖 α → β α\rightarrow β α → β 是否违反BCNF,即检查 α + α^+ α + ,并验证它是否包含了 R R R 上的所有属性,判断 α α α 是否是 R R R 的超码
检查关系模式 R R R 是否属于BCNF,仅需要检查给定集合 F F F 上的函数依赖,不需要检查 F + F^+ F + 。因为如果 F F F 上没有函数依赖违反BCNF,则 F + F^+ F + 上也不会有函数依赖违反BCNF 当关系模式被分解后,需要根据 F + F^+ F + 判断一个 R i R_i R i 是否属于BCNF,不属于的话需要再次分解
例如:R ( U , F ) , U = { A B C D E } , F = { A → B , B C → D } 。将 R 分解为 R 1 和 R 2 , U 1 = { A B } , U 2 = { A C D E } R(U,F),U = \{ABCDE\}, F = \{A \rightarrow B, BC \rightarrow D\}。将R分解为R1和R2,U1 =\{AB\},U2 = \{ACDE\} R ( U , F ) , U = { A BC D E } , F = { A → B , BC → D } 。将 R 分解为 R 1 和 R 2 , U 1 = { A B } , U 2 = { A C D E }
R 2 R_2 R 2 中没有来自于 F F F 中的函数依赖,但是 A C → D ∈ F + AC \rightarrow D∈F^+ A C → D ∈ F + ,所以 R 2 R_2 R 2 不属于BCNF。需要再分解 R2
因此,计算分解后的关系模式是否属于BCNF是NP的
分解算法 注意 此算法只能产生无损连接分解,若要求分解保持函数依赖,那么分解后的模式总可以达到3NF,但不一定能达到BCNF
当我们用 ( R i − β ) (R_i - β) ( R i − β ) 和 ( α β ) (αβ) ( α β ) 代替模式 R i R_i R i 时,保持依赖 α → β α\rightarrow β α → β ,而且 ( R i − β ) ∩ ( α β ) = α (R_i - β) ∩ (αβ)=α ( R i − β ) ∩ ( α β ) = α
如果我们没有要求 α ∩ β = ∅ α\cap β=\emptyset α ∩ β = ∅ ,那么 α ∩ β α∩β α ∩ β 中的那些属性就不会出现在模式 ( R i − β ) (R_i - β) ( R i − β ) 中,而依赖 α → β α\rightarrow β α → β 也不成立,因此不保证无损连接分解
如果 α ∩ β < > ∅ α∩β<>\emptyset α ∩ β <> ∅ ,α α α 中的属性 { A , B , C } \{A,B,C\} { A , B , C } ,β β β 中的属性 { C , D , E } \{C,D,E\} { C , D , E } ,R i R_i R i 中的属性{ A , B , C , D , E , F , G } \{A,B,C,D,E,F,G\} { A , B , C , D , E , F , G } , R i – β = { A , B , F , G } R_i – β=\{A,B,F,G\} R i – β = { A , B , F , G } , α β = { A , B , C , D , E } αβ=\{A,B,C,D,E\} α β = { A , B , C , D , E } ,( R i – β ) ∩ ( α β ) = { A , B } ( R_i – β)∩ (αβ)=\{A,B\} ( R i – β ) ∩ ( α β ) = { A , B } ,则 ( R i – β ) ∩ ( α β ) → β ( R_i – β)∩ (αβ) \rightarrow β ( R i – β ) ∩ ( α β ) → β 不成立,这就说明我们得到的不是无损分解
多值依赖 样例 关系模式 T E A C H ( c n o , t n o , b n o ) TEACH(cno,tno,bno) TE A C H ( c n o , t n o , bn o ) ,一门课程由多名老师担任,同一门课程的不同老师可以使用相同的一套参考书;一位老师可以承担多门课。 它的候选码是 ( c n o , t n o , b n o ) (cno,tno,bno) ( c n o , t n o , bn o ) ,所以属于BCNF
不良特性 插入异常:当某门课程增加一名教师时,该门课程有多少本参考书就必须插入多少个元组;同样当某门课程需要增加一本参考书时,它有多少个教师就必须插入多少个元组
删除异常:当删除一门课程的某个教师或者某本参考书时,需要删除多个元组
更新异常:当一门课程的教师或参考书作出改变时,需要修改多个元组
数据冗余:同一门课的教师与参考书的信息被反复存储多次
定义 描述型 :关系模式 R ( U ) R(U) R ( U ) ,α 、 β 、 γ ⊂ U \alpha、\beta、\gamma \subset U α 、 β 、 γ ⊂ U ,并且 γ = U – α – β \gamma = U – \alpha – \beta γ = U – α – β ,多值依赖 α → → β \alpha \rightarrow\rightarrow \beta α →→ β 成立当且仅当对 R ( U ) R(U) R ( U ) 的任一关系实例 r r r ,给定的一对 ( α 1 , γ 1 ) (\alpha_1,\gamma_1) ( α 1 , γ 1 ) 值,有一组 β \beta β 的值,这组值仅仅决定于 α \alpha α 值而与 γ \gamma γ 值无关 注意,是”有一组 β \beta β 的值“,而不是一个 如在关系模式TEACH中,对(c1 , b1)有一组tno值(t1 , t2),对(c1 , b2)也有一组tno值(t1 , t2),这组值仅取决于cno的取值,而与bno的取值无关。因此,tno多值依赖于cno,记作 c n o → → t n o cno\rightarrow \rightarrow tno c n o →→ t n o ,同样有 c n o → → b n o cno\rightarrow \rightarrow bno c n o →→ bn o
形式化 :关系模式 R ( U ) R(U) R ( U ) ,α 、 β 、 γ ⊂ U \alpha、\beta、\gamma \subset U α 、 β 、 γ ⊂ U ,并且 γ = U – α – β \gamma = U – \alpha – \beta γ = U – α – β ,对于 R ( U ) R(U) R ( U ) 的任一关系实例 r r r ,若存在元组 t 1 , t 2 t1,t2 t 1 , t 2 ,使得 t 1 [ α ] = t 2 [ α ] t1[\alpha] = t2[\alpha] t 1 [ α ] = t 2 [ α ] ,那么就必然存在元组 t 3 , t 4 t3,t4 t 3 , t 4 ,使得:t 3 [ α ] = t 4 [ α ] = t 1 [ α ] = t 2 [ α ] t3[\alpha] = t4[\alpha] = t1[\alpha] = t2[\alpha] t 3 [ α ] = t 4 [ α ] = t 1 [ α ] = t 2 [ α ]
t 3 [ β ] = t 1 [ β ] , t 3 [ γ ] = t 2 [ γ ] t3[\beta] = t1[\beta], t3[\gamma] = t2[\gamma] t 3 [ β ] = t 1 [ β ] , t 3 [ γ ] = t 2 [ γ ]
t 4 [ β ] = t 2 [ β ] , t 4 [ γ ] = t 1 [ γ ] t4[\beta] = t2[\beta] , t4[\gamma] = t1[\gamma] t 4 [ β ] = t 2 [ β ] , t 4 [ γ ] = t 1 [ γ ]
则称 β \beta β 多值依赖于 α \alpha α 。
性质