chp关系数据理论＋－new.pptVIP

An Introduction to Database System 保持函数依赖的模式分解 设关系模式RU,F被分解为若干个关系模式 R1U1,F1，R2U2,F2，…，RnUn,Fn （其中U=U1∪U2∪…∪Un，且不存在Ui ? Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency） */240 An Introduction to Database System 模式的分解（续） 4. 将SL分解为下面二个关系模式： ND(Sno, Sdept) DL(Sdept, Sloc) 这种分解方法就保持了函数依赖 */240 An Introduction to Database System 函数依赖集等价 判断两个函数依赖集等价的可行算法: 1、要判定F ? G+：逐一对F中的函数依赖X→Y，考察 X→Y 是否为G+所蕴涵 ，即考察Y 是否属于XG+ 。 2、要判定G ? F+：逐一对G中的函数依赖X→Y，考察 X→Y 是否为F+所蕴涵 ，即考察Y 是否属于XF+ 。 */240 An Introduction to Database System 举例（函数依赖集等价） F1={A → B,B → C} F2={A → B, B → C ， A → C } 判断F1和F2是否等价？ 1、判定F1 ? F2 +：逐一对F1中的函数依赖X→Y，考察 X→Y 是否为F2 +所蕴涵(X→Y能否由F2 根据Armstrong公理导出) ，即考察Y 是否属于XF2+ √ 2、判定F2 ? F1 +：逐一对F2中的函数依赖X→Y，考察 X→Y 是否为F1 +所蕴涵(X→Y能否由F1 根据Armstrong公理导出) ，即考察Y 是否属于XF1+ A → C能否由F1 根据Armstrong公理导出,即考察C 是否属于AF2+ F1和F2是等价的 */240 An Introduction to Database System 举例（函数依赖集等价） 结论:F与G =F-{X→A}等价的充要条件是A?XG+(即X→A能由G根据Armstrong公理系统导出) */240 An Introduction to Database System 7. 最小依赖集 定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价。 (3) F中不存在这样的函数依赖X→A， X有真子集Z使得F-{X→A}∪{Z→A}与F等价。 */240 An Introduction to Database System 最小依赖集 [例2] 关系模式SU，F，其中： U={ Sno，Sdept，Mname，Cno，Grade }， F={ Sno→Sdept，Sdept→Mname，(Sno，Cno)→Grade } 设F’={Sno→Sdept，Sno→Mname，Sdept→Mname， (Sno，Cno)→Grade，(Sno，Sdept)→Sdept} F是最小覆盖，而F’不是。 因为：F ’ - {Sno→Mname}与F ’等价 F ’ - {(Sno，Sdept)→Sdept}也与F ’等价 */240 An Introduction to Database System 8. 极小化过程 定理6.3 每一个函数依赖集F均等价于一个极小函数依赖 集Fm。此Fm称为F的最小依赖集。 证明: 构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。 */240 An Introduction to Database System 极小化过程（续） (1)逐一检查F中各函数依赖FDi：X→Y，若Y=A1A2 …Ak，k 2，则用 { X→Aj |j=1，2，…， k} 来取代X→Y。 引理6.1保证了F变换前后的等价性。 最小函数依赖集中的所有函数依赖都有最简单的形式，右端没有多余属性； (2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若A?XG+ (说明X→A能由G根据Armstrong公理系统推出) ，