第12讲函数依赖的理论

第5章关系模式的规范化设计——函数依赖的理论数据库原理与应用第12讲函数依赖的理论关系模式的规范化设计•所要解决的问题–什么是“好”的关系数据模式–如何评价一个好的关系数据模式–如何设计一个“好”的关系数据模式第12讲函数依赖的理论关系模式的规范化设计•主要内容–关系模式的设计问题–关系模式规范化的基本概念和理论–关系模式分解的理论基础和算法第12讲函数依赖的理论回顾1NF2NF3NFBCNF去除非主属性对于候选键的部分函数依赖去除非主属性对于候选键的传递函数依赖去除主属性对于候选键的部分和传递函数依赖去除不被候选键所蕴涵的非平凡的多值依赖4NF－－－－消除决定因素非码的非平凡函数依赖第12讲函数依赖的理论•理论研究的必要性–对于应用所表达的语义用一组函数依赖是否能充分表达模式属性间的约束关系，即得到一个给定的关系模式的完整函数依赖集F？–能否将完整函数依赖集F缩小到一个可管理的范围?即找到一个远远小于F的集合T，蕴含集合F的所有函数依赖，则DBMS只要实现函数依赖集T，函数依赖集F中的所有函数依赖会自动实现。函数依赖的理论第12讲函数依赖的理论•主要内容–Armstrong公理•逻辑蕴含•函数依赖集F的闭包F+•Armstrong公理推理规则•属性集闭包•函数依赖集等价和最小函数依赖集–候选码及其求解方法函数依赖的理论第12讲函数依赖的理论【例】设有关系模式R（A，B，C），及其函数依赖集F={A→B，B→C}，判断A→C是否成立。Armstrong公理解：对于关系模式R的任一实例r的任意元组ti、tj，i≠j，若ti[A]=tj[A]，根据函数依赖的定义由A→B可推出ti[B]=tj[B]又由B→C可推出ti[C]=tj[C]因此，若ti[A]=tj[A]，可推出ti[C]=tj[C]根据函数依赖的定义，则可得出A→C。第12讲函数依赖的理论•逻辑蕴含–设F是关系模式R上的函数依赖集，X→Y是R上的一个函数依赖，若对于R的每个满足F的关系r也满足X→Y，则称F逻辑蕴含X→Y记为：F┝X→Y。Armstrong公理第12讲函数依赖的理论【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩}，F={学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}Armstrong公理•逻辑蕴含第12讲函数依赖的理论【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩}，F={学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}Armstrong公理•逻辑蕴含学生学号→学生学号,学生学号→系主任（学生学号，所在系）→学生学号（学生学号，所在系）→所在系（学生学号，课程名称）→所在系（学生学号，所在系）→系主任（学生学号，课程名称）→(学生学号，学生姓名，所在系，系主任，课程名称，成绩)第12讲函数依赖的理论•函数依赖集F的闭包F+–F逻辑蕴含的所有函数依赖的集合称为函数依赖集F的闭包，并记为F+F+={X→Y│F┝X→Y}Armstrong公理第12讲函数依赖的理论•Armstrong公理推理规则–通过推理规则，可以从给定的函数依赖中推出其所蕴含的新的函数依赖。–假设U为关系模式R的属性集，F是U上的函数依赖集，X、Y、Z是U的任意子集，并采用把子集X、Y的并集记为XY的方式，对关系模式RU，F来说有以下的推理规则：•基本规则（3条）•扩充规则（3条）Armstrong公理第12讲函数依赖的理论•Armstrong公理推理规则–基本规则Al.自反律（Reflexivity）若YXU，则X→Y为F所蕴含。A2.增广律（Augmentation）若X→Y为F所蕴含，且ZU，则XZ→YZ为F所蕴含。A3.传递律（Transitivity）若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。Armstrong公理第12讲函数依赖的理论•Armstrong公理推理规则–扩充规则合并规则由X→Y，X→Z，有X→YZ。（A2，A3）伪传递规则由X→Y，WY→Z，有XW→Z。（A2，A3）分解规则由X→Y及ZY，有X→Z。（A1，A3）Armstrong公理第12讲函数依赖的理论•Armstrong公理推理规则根据合并规则和分解规则：引理1：X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）Armstrong公理第12讲函数依赖的理论•Armstrong公理推理规则Armstrong公理【例】设有关系R，它的属性集U={A,B,C,D,E,F}，R满足下列函数依赖：F={A→BC,B→E,CD→EF}，试证AD→F证明：∵A→BC（已知）∴AD→BCD（增广律）∵BCD→CD（自反律）∵CD→EF（已知）∴BCD→EF（传递律）∴AD→EF（传递律）∴AD→F（分解规则）第12讲函数依赖的理论•Armstrong公理的有效性–从F中的已有函数依赖关系利用Armstrong公理推出的每一个函数依赖X→Y∈F+•Armstrong公理的完备性–给定函数依赖集F,该函数依赖集所蕴含的函数依赖，即F+中的每一个函数依赖都可以利用Armstrong公理推导出来。Armstrong公理推出的所有函数依赖为真可以推出所有的函数依赖第12讲函数依赖的理论•函数依赖集F的闭包F+Armstrong公理【例】计算函数依赖集F={A→B,B→C}的闭包F+􀂾F中的所有函数依赖都是其闭包中的元素，即：A→B∈F+B→C∈F+􀂾根据自反规则，下述函数依赖也是其闭包中的元素A→AB→BC→CAB→AAB→BAB→ABAC→AAC→CAC→ACBC→BBC→CBC→BCABC→AABC→BABC→CABC→ABABC→ACABC→BCABC→ABC第12讲函数依赖的理论•函数依赖集F的闭包F+Armstrong公理【例】计算函数依赖集F={A→B,B→C}的闭包F+􀂾A→B,B→C及传递规则：A→C􀂾A→B,A→C及合并规则：A→BC􀂾A→B及增广规则：A→ABAC→BCAC→ABC􀂾B→C及增广规则：AB→ACB→BCAB→ABC􀂾A→C及增广规则：A→ACAB→BC􀂾A→BC及增广规则：A→ABCAB→B,B→C及传递规则：AB→C􀂾AC→A,A→B及传递规则：AC→B……第12讲函数依赖的理论•属性集闭包设F是属性集U上的一组函数依赖，XU，则属性集X关于函数依赖集F的闭包XＦ＋定义为：XF+={Ai|AiU且X→Ai可由F经Armstrong公理导出}即XF+={Ai|X→Ai∈F+，AiU}XF+就是可由函数依赖集F经Armstrong公理导出的所有“函数依赖于属性集X的所有属性的集合。Armstrong公理+FX+FX第12讲函数依赖的理论•属性集闭包引理1：X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）Armstrong公理引理2：设F为属性集U上的一组函数依赖，X、YU，X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+第12讲函数依赖的理论•属性集闭包引理2：设F为属性集U上的一组函数依赖，X、YU，X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+Armstrong公理用途：将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题。第12讲函数依赖的理论•属性集闭包Armstrong公理算法1求XF+的一个算法。输入：属性集X和函数依赖集F。输出：XF+算法：XF+:=X;repeatoldXF+:=XF+;foreachfunctionaldependencyY→ZinFdoifYXF+thenXF+:=XF+∪Z;until(oldXF+=XF+）第12讲函数依赖的理论•属性集闭包Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+解：{B}F+={B}第一遍循环1）X={B}F+={B}2）f1的决定因素是{B}F+的一个子集，所以{B}F+={B}F+∪{C,D}={B,C,D}3）f2的决定因素不是{B}F+的子集,因此f2不影响本次循环的计算结果4）f3的决定因素是{B}F+的一个子集，所以{B}F+={B}F+∪{A}={A,B,C,D}5）X≠{B}F+,返回开始执行第二遍循环第12讲函数依赖的理论•属性集闭包Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+第二遍循环1）X={B}F+={A,B,C,D}2）f1、f2、f3的决定因素均是{B}F+的子集,所以{B}F+={B}F+∪{C,D}∪{A}∪{E}={A,B,C,D,E}3）X≠{B}F+,返回开始执行第三遍循环第12讲函数依赖的理论•属性集闭包Armstrong公理【例】设F={(f1)B→CD,(f2)AD→E,(f3)B→A}，计算{B}F+第三遍循环1）X={B}F+={A,B,C,D,E}2）F中的所有函数依赖都已处理过（其依赖因素都已经被并入到{B}F+中）3）因此在本次循环中X={B}F+，算法执行结束返回结果{B}F+=ABCDE第12讲函数依赖的理论•属性集闭包Armstrong公理【例】F={A→BC，E→CF，B→E，CD→EF}，求(AB)F+解：X（0）=AB;∵A→BC,B→E，∴X（1）=AB∪BC∪E=ABCE又∵A→BC、B→E和E→CF∴X（2）=ABCE∪BC∪E∪CF=ABCEF又∵A→BC、B→E、E→CF，则X（3）=ABCEF∪BC∪E∪CF=ABCEFX（3）=X（2）∴(AB)F+=ABCEF第12讲函数依赖的理论•函数依赖集等价和最小函数依赖集定义：设F、G为两个函数依赖集，若F+=G+，则称F和G是等价的，也可称F和G互相覆盖。引理：F+=G+的充分必要条件是F⊆G+，G⊆F+。Armstrong公理要判定F⊆G+，只需逐一对F中的函数依赖X→Y，考察Y是否属于XＧ＋就行了。第12讲函数依赖的理论•函数依赖集等价和最小函数依赖集定义：函数依赖集F当且仅当满足下列条件时，称为最小函数依赖集，或极小函数依赖集，或最小覆盖。1）F中每个函数依赖的右部为单一属性。（右部不可约）2）F中不存在这样的函数依赖X→A，使得F-{X→A}与F等价。3）F中不存在这样的函数依赖X→A，使得Z⊂X，且F-{X→A}∪{Z→A}与F等价。（左部不可约）Armstrong公理引理：任一函数依赖集F总可以为一右部恒为单属性的函数依赖集所覆盖。第12讲函数依赖的理论•函数依赖集等价和最小函数依赖集定理：每一个函数依赖集F都等价于一个最小函数依赖集Fm。Armstrong公理第12讲函数依赖的理论•函数依赖集等价和最小函数依赖集Armstrong公理进行构造性的证明：1）对F中的每个函数依赖X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|j=1,2,…,k}来取代X→Y。2）对F中的每个函数依赖X→A，令G=F-{X→A}，若A∈XG+，说明X→A为F-{X→A}所蕴含，F与F-{X→A}等价，则从F中去掉此函数依赖X→A。3）对F中的每个函数依赖X→A，设X=B1B2…Bk，对每个Bi（i=1,2,…,k）若A∈(X-Bi)F+，说明(X-Bi)→A为F所蕴含，函数依赖X→A是左部可约的，F与F-{X→A}∪{(X-Bi)→A}等价，则以X-Bi取代X。第12讲函数依赖的理论•函数依赖集等价和最小函数依赖集Armstrong公理【例】设F={A→BC,B→AC,C→A},求Fm。1)函数依赖右边属性单一化F={A→B,A→C,B→A,B→C,C→A}2)去掉冗余的函数依赖判断A→B是否冗余：G1={A→C,B→A,B→C,C→A}AＧ1＋=AC,B不属于AＧ1＋，A→B不冗余；判断A→C是否冗余：G2={A→B,B→A,B→C,C→A}AＧ2＋=ABC，C∈AＧ2＋，A→C冗余F={