数据库模式分解：如何判定“保持函数依赖”？

文章目录数据库模式分解如何判定“保持函数依赖”一、先搞懂什么叫“保持函数依赖”二、判定保持函数依赖的标准思路第一步列出原函数依赖集F FF第二步对每个子模式求“投影依赖”第三步合并所有子模式的依赖集第四步检查F FF中每个依赖是否都能被G GG推导出来三、考试常用“快速判断法”四、严格判定用“跨子模式闭包扩展”算法五、用一个例子串起来1. 看每个依赖落在哪里2. 合并依赖集3. 判定结果六、容易踩的三个坑坑 1把“保持函数依赖”当成“无损连接”坑 2依赖被拆开就直接判“不保持”坑 3只检查“直接出现”不做闭包推导七、做题模板数据库模式分解如何判定“保持函数依赖”关系模式分解里有两个最容易混的概念无损连接拆完表后能不能通过自然连接把数据完整拼回去。保持函数依赖拆完表后原来的业务约束是否还能被“找回来”。这篇只讲后者怎么判定一个分解是否保持函数依赖。一、先搞懂什么叫“保持函数依赖”设关系模式是R ( U , F ) R(U, F)R(U,F)其中U UU是属性集F FF是原函数依赖集把R RR分解成若干子模式R 1 , R 2 , … , R k R_1, R_2, \dots, R_kR1​,R2​,…,Rk​。如果F FF中的每个函数依赖都能由分解后各子模式上的函数依赖推导出来那么这个分解就是保持函数依赖的。通俗一点说原来的规则拆表之后不能丢。要么某个依赖完整地落在某张子表里要么虽然被拆开了但通过各子表的依赖联合推导仍然能恢复出来。注意保持函数依赖 ≠ 无损连接。一个分解可以保持依赖但不是无损连接也可以无损连接但不保持依赖。二、判定保持函数依赖的标准思路判定流程可以分成四步。第一步列出原函数依赖集F FF先把题目给出的所有函数依赖写清楚例如F { A → B , A → C , C → D , A E → G } F \{A \rightarrow B,\ A \rightarrow C,\ C \rightarrow D,\ AE \rightarrow G\}F{A→B,A→C,C→D,AE→G}后面每一步都要围绕这个集合检查。第二步对每个子模式求“投影依赖”对每个子模式R i R_iRi​找出那些左右属性都落在R i R_iRi​中的函数依赖。例如若R 1 ( A , B , C , D ) R_1(A, B, C, D)R1​(A,B,C,D)原依赖中有A → B A \rightarrow BA→B、A → C A \rightarrow CA→C、C → D C \rightarrow DC→D那么这些依赖都可以在R 1 R_1R1​上保持。如果某个依赖的左边或右边属性不在R i R_iRi​中它就不能直接归入R i R_iRi​的投影依赖集。第三步合并所有子模式的依赖集把所有子模式能“认领”的依赖合并起来记为G ⋃ i 1 k F i G \bigcup_{i1}^{k} F_iGi1⋃k​Fi​其中F i F_iFi​是F FF在R i R_iRi​上的投影依赖集。第四步检查F FF中每个依赖是否都能被G GG推导出来对F FF中的每个依赖X → Y X \rightarrow YX→Y判断Y ⊆ X G Y \subseteq X_G^Y⊆XG​也就是说用合并后的依赖集G GG计算X XX的闭包看能否推出Y YY。如果所有依赖都能被推出则分解保持函数依赖只要有一个推不出就不保持。三、考试常用“快速判断法”做选择题时通常可以先用这个简化判断如果一个函数依赖的左右属性都完整出现在某个子模式中那它一定被保持。如果某个依赖被拆到不同子模式里且无法通过其他依赖推导出来那它就可能丢失。但要注意被拆开 ≠ 一定不保持。因为可能存在传递推导。例如R 1 ( A B ) R_1(AB)R1​(AB)上有A → B A \rightarrow BA→BR 2 ( B C ) R_2(BC)R2​(BC)上有B → C B \rightarrow CB→C那么A → C A \rightarrow CA→C虽然不在任何单张子表中但可以通过A → B A \rightarrow BA→B、B → C B \rightarrow CB→C推导出来因此仍可能被保持。所以严格判定还是要看闭包。四、严格判定用“跨子模式闭包扩展”算法当某个依赖被拆散时不能直接判“不保持”需要用更通用的方法。对F FF中的每个依赖X → Y X \rightarrow YX→Y初始化r e s u l t X result XresultX对每个子模式R i R_iRi​计算t e m p r e s u l t ∩ R i temp result \cap R_itempresult∩Ri​求t e m p temptemp关于原依赖集F FF的闭包t e m p temp^temp取回落在R i R_iRi​内的属性t t e m p ∩ R i t temp^ \cap R_ittemp∩Ri​更新r e s u l t r e s u l t ∪ t result result \cup tresultresult∪t重复第 2 步直到r e s u l t resultresult不再变化。最后判断如果Y ⊆ r e s u l t Y \subseteq resultY⊆result则X → Y X \rightarrow YX→Y被保持否则不保持。这个算法的本质是利用每个子模式内部能推出的属性逐步扩大左部能决定的范围看最终能不能覆盖右部。五、用一个例子串起来设U { A , B , C , D , E , G } U \{A, B, C, D, E, G\}U{A,B,C,D,E,G}F { A → B , A → C , C → D , A E → G } F \{A \rightarrow B,\ A \rightarrow C,\ C \rightarrow D,\ AE \rightarrow G\}F{A→B,A→C,C→D,AE→G}分解为R 1 ( A , B , C , D ) R_1(A, B, C, D)R1​(A,B,C,D)R 2 ( A , E , G ) R_2(A, E, G)R2​(A,E,G)1. 看每个依赖落在哪里A → B A \rightarrow BA→B属性都在R 1 R_1R1​保持。A → C A \rightarrow CA→C属性都在R 1 R_1R1​保持。C → D C \rightarrow DC→D属性都在R 1 R_1R1​保持。A E → G AE \rightarrow GAE→G属性都在R 2 R_2R2​保持。2. 合并依赖集合并后得到G { A → B , A → C , C → D , A E → G } G \{A \rightarrow B,\ A \rightarrow C,\ C \rightarrow D,\ AE \rightarrow G\}G{A→B,A→C,C→D,AE→G}这和原依赖集完全一致。3. 判定结果因为F FF中每个依赖都能由G GG直接推出所以该分解保持函数依赖。六、容易踩的三个坑坑 1把“保持函数依赖”当成“无损连接”保持依赖看的是规则有没有丢无损连接看的是数据能不能拼回去。两者要分别判定。坑 2依赖被拆开就直接判“不保持”比如A → C A \rightarrow CA→C没有直接出现在任何子表中但如果子表中有A → B A \rightarrow BA→BB → C B \rightarrow CB→C那么A → C A \rightarrow CA→C仍可能被推导出来。坑 3只检查“直接出现”不做闭包推导严格做法是对每个X → Y X \rightarrow YX→Y计算X XX在合并依赖集下的闭包看是否包含Y YY。七、做题模板以后遇到“是否保持函数依赖”的题可以按这个顺序写写出原函数依赖集F FF。对每个子模式R i R_iRi​写出它能保持的依赖F i F_iFi​。合并得到G ⋃ F i G \bigcup F_iG⋃Fi​。对F FF中每个X → Y X \rightarrow YX→Y判断Y ⊆ X G Y \subseteq X_G^Y⊆XG​。全部成立 → 保持函数依赖有一个不成立 → 不保持函数依赖。如果是选择题通常可以先用“左右属性是否完整落在某个子模式中”快速排除遇到跨表依赖再用闭包扩展法确认。