函数依赖的公理系统.ppt

属性集闭包计算举例U={A,B,C,D};F={AB,ACD};A+=AB.C+=C.(AC)+=ABCD.ACBD显然，AC是候选码思考：哪些属性是L类？（只出现在函数依赖左边）哪些是R类？哪些是LR类？哪些是N类？它们与候选码有什么关系？第21页,共30页，2024年2月25日，星期天候选码的作用例题：已知R(X,Y,Z),F={XY→Z}，请问R为第几范式？（请思考：解题的思路是什么？）XY为候选码，R属于BCNF。练习：R(W,X,Y,Z),F={X→Z,WX→Y}，请问R为第几范式？第22页,共30页，2024年2月25日，星期天Armstrong公理系统的有效性与完备性Armstrong公理的完备性及有效性说明:“蕴含”==“导出”等价的概念F+==由F出发借助Armstrong公理导出的函数依赖的集合第23页,共30页，2024年2月25日，星期天6.函数依赖集等价 定义:如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。第24页,共30页，2024年2月25日，星期天6.最小依赖集定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖X→A，使得F与 F-{X→A}等价。(3)F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。如果函数依赖集F和G等价，并且G是最小集，那么称G是F的一个最小覆盖。第25页,共30页，2024年2月25日，星期天函数依赖集的等价和覆盖求最小函数依赖集的方法：应用分解规则，使F中每一个依赖的右部单一化。去掉各函数依赖左部多余的属性。方法：检查F中左边是非单属性的依赖，如：XY→A，要判定Y是否多余，只要求X闭包，若X闭包A，则Y是多余的，以X→Y代替XY→A。去掉多余的依赖。方法：从第一个依赖开始，若要从F中去掉X→Y，则在剩下的依赖中求X闭包，若X闭包包含Y,则去掉X→Y第26页,共30页，2024年2月25日，星期天最小依赖集或者：1。将函数依赖的右部分解为一个属性；2。确保函数依赖左边是不可分的；3。将具传递性的函数依赖去掉；如：假设一个关系R中具有属性A、B、C、D。F={A→BC,B→C,A→B,AB→C,AC→D}解：（1）A→BC分解为A→B，A→C；（2）由A→C知AB→C是冗余的，去掉；A→C得A→AC，而AC→D，则A→D，所以，AC→D冗余。（3）A→C可由A→B，B→C得，所以A→C要去掉。得到R的最小依赖集F={A→B，B→C，A→D}第27页,共30页，2024年2月25日，星期天求最小函数依赖集练习1关系R{A,B,C,D}，有FD如下：F={AB→C,C→B,BC→D,ACD→B}。求F的最小函数依赖集。2设有关系R{E,F,G,H}，其上的F={E→G,G→E,F→EG,H→EG,FH→E}。求F的最小函数依赖集。（注意此题可以有多个答案）第28页,共30页，2024年2月25日，星期天求最小函数依赖集在数据库设计过程中，实体及属性的冗余可以通过分析确定，而联系的冗余通过函数依赖集的极小化算法查出和消除。第29页,共30页，2024年2月25日，星期天感谢大家观看第30页,共30页，2024年2月25日，星期天关于函数依赖的公理系统数据依赖的公理系统逻辑蕴含 定义:对于满足一组函数依赖F的关系模式RU，F，其任何一个关系r，若函数依赖X→Y都成立,则称F逻辑蕴含X→Y第2页,共30页，2024年2月25日，星期天Armstrong公理系统从已知函数依赖集F要问X→Y是否为F逻辑蕴含，就要一套推理规则，由Armstrong在1974年提出。这套推理规则，是模式分解算法的理论基础。用途从一组函数依赖求得蕴含的函数依赖。求给定关系模式的码。第3页,共30页，2024年2月25日，星期天1.Armstrong公理系统关系模式RU，F来说有以下的推理规则：Al.自反律（Reflexivity）：若Y?X?U，则X→Y为F所蕴含。A2.增广律（Augmentation）：若X→Y为F所