373第6章 关系数据库理论

1、第第6章章 关系数据库理论关系数据库理论v6.1 问题的提出问题的提出v6.2 规范化规范化v6.3 数据依赖的公理系统数据依赖的公理系统v6.4 模式的分解模式的分解v6.5 小结小结6.3 数据依赖的公理系统数据依赖的公理系统v逻辑蕴含逻辑蕴含定义定义6.11 对于满足一组对于满足一组函数依赖函数依赖 的关的关系模式系模式 ，其任何一个关系，其任何一个关系 ，若，若函数依赖函数依赖都成立都成立, 则称则称 逻辑蕴含逻辑蕴含armstrong公理系统公理系统v一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础1. armstrong公理系统公理系统 关系模式关系模式

2、来说有以下的推理规则：来说有以下的推理规则：定理定理 6.l armstrong推理规则推理规则是正确的是正确的（l）自反律自反律:若若 ，则，则 为为 所蕴含所蕴含定理定理6.l (续续)(2)增广律增广律: 若若 为为 所蕴含，且所蕴含，且 ，则，则为为所蕴含。所蕴含。 证：证：设设 为为 所蕴含，且所蕴含，且 。 设设 的任一关系的任一关系 中任意的两个元组中任意的两个元组， ；定理定理6.l （续）（续）(3) 传递律传递律：若：若 及及 为为 所蕴含，则所蕴含，则 为为 所蕴含。所蕴含。2. 导出规则导出规则1.根据根据a1，a2，a3这三条推理规则可以得这三条推理规则可以得到下面三

3、条推理规则：到下面三条推理规则：导出规则导出规则2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理6.1 引理引理6.l 成立的充分必要条成立的充分必要条件是件是 成立（成立（ =l，2， ）。）。3. 函数依赖闭包函数依赖闭包定义定义6.l2 在关系模式在关系模式中为中为 所逻辑蕴含所逻辑蕴含的函数依赖的全体叫作的函数依赖的全体叫作 f的闭包的闭包，记为，记为f+。定义定义6.13 设设 为属性集为属性集 上的一组函数依赖，上的一组函数依赖， ， + = 能由能由根据根据armstrong公理导出公理导出，+称为属性集称为属性集x关于函数依赖集关于函数依赖集f 的闭包的闭包

4、关于闭包的引理关于闭包的引理求闭包的算法求闭包的算法算法算法6.l 求属性集求属性集 （ ）关于）关于 上的函数依上的函数依 赖集赖集的闭包的闭包+ 输入：输入： ，输出：输出：+步骤：步骤：（1）令）令（0）= ， =0（2）求）求 ，这里，这里 = |( )( （i） ；（3）（i+1）= （i） 算法算法 6.l（4）判断）判断（i+1）= （i）吗吗?（5）若相等或）若相等或（i）=则则（i）就是就是+ , 算法终止。算法终止。（6）若否，则）若否，则 = +l，返回第（，返回第（2）步。）步。对于算法对于算法6.l， 令令 =|（i）|，形成一个步长大形成一个步长大于于1的严格递增的

5、序列，序列的上界是的严格递增的序列，序列的上界是 | |，因，因此该算法最多此该算法最多 | | - | 次循环就会终止。次循环就会终止。 u=a, b, c, d; f=a b, bc d;va+ = ab.vc+ = c.v(ac)+ = abcd.实例实例函数依赖闭包函数依赖闭包例例1 已知关系模式已知关系模式 ，其中，其中=；= ， ， ， ， 。求（求（） 。函数依赖闭包函数依赖闭包(2)因为因为x ，所以再找出左部为，所以再找出左部为子子集的那些函数依赖，又得到集的那些函数依赖，又得到 ， ， 于是于是=。(3)因为因为=u，算法终止，算法终止所以（所以（） =。4. armstr

6、ong公理系统的有效性与完备性公理系统的有效性与完备性v有效性：有效性：由由 出发根据出发根据armstrong公理推导出来的公理推导出来的每一个函数依赖一定在每一个函数依赖一定在+中中 /* armstrong正确正确v完备性完备性：+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由 出出发根据发根据armstrong公理推导出来公理推导出来 /* armstrong公理够用，完全公理够用，完全完备性完备性：所有不能用：所有不能用armstrong公理推导出来公理推导出来f, 都不为真都不为真 若若 f 不能用不能用armstrong公理推导出来，公理推导出来， f + 5. 函

7、数依赖集等价函数依赖集等价定义定义6.14 如果如果+=+，就说函数依赖集，就说函数依赖集覆盖覆盖 （ 是是 的覆盖，或的覆盖，或 是是 的覆盖），的覆盖），或或 与与 等价等价。函数依赖集等价的充要条件函数依赖集等价的充要条件引理引理6.3 + = + 的充分必要条件是的充分必要条件是 + ，和，和 + 函数依赖集等价函数依赖集等价v要判定要判定 +，只须逐一对，只须逐一对 中的函数依中的函数依赖赖 ，考察，考察 是否属于是否属于+ 就行了。就行了。因此引理因此引理6.3 给出了判断两个函数依赖集给出了判断两个函数依赖集等价的可行算法。等价的可行算法。 6. 最小依赖集最小依赖集 定义定义6

8、.15 如果函数依赖集如果函数依赖集f满足下列条件，则满足下列条件，则称称f为一个为一个极小函数依赖集极小函数依赖集。亦称为。亦称为最小依赖最小依赖集集或或最小覆盖最小覆盖。 (1) f中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 (2) f中不存在这样的函数依赖中不存在这样的函数依赖xa，使得，使得f与与f-xa等价。等价。 (3) f中不存在这样的函数依赖中不存在这样的函数依赖xa， x有真有真 子集子集z使得使得f-xaza与与f等价。等价。 最小依赖集（续）最小依赖集（续）7. 极小化过程极小化过程定理定理6.3 每一个函数依赖集每一个函数依赖集 均等价于一

9、个极小均等价于一个极小 函数依赖集函数依赖集。此。此称为称为 的最小依赖集的最小依赖集证证:构造性证明，依据定义分三步对构造性证明，依据定义分三步对 进行进行“极小化极小化处理处理”，找出，找出 的一个最小依赖集。的一个最小依赖集。极小化过程（续）极小化过程（续）(2)逐一检查逐一检查 中各函数依赖中各函数依赖： ， 令令 = - ， 若若 +， 则从则从 中去掉此函数依赖。中去掉此函数依赖。 由于由于 与与= - 等价的充要条件是等价的充要条件是 + 因此因此f变换前后是等价的。变换前后是等价的。极小化过程（续）极小化过程（续）(3)逐一取出逐一取出 中各函数依赖中各函数依赖： ， 设设 =

10、12， 逐一考查逐一考查 （ =l，2，），）， 若若 （ - ）+ ， 则以则以 - 取代取代 由于由于 与与 - 等价的充要条等价的充要条件是件是 + ，其中，其中 = - 因此因此f变换前后是等价的。变换前后是等价的。极小化过程（续）极小化过程（续）由定义，最后剩下的由定义，最后剩下的 就一定是极小依赖集。就一定是极小依赖集。 因为对因为对 的每一次的每一次“改造改造”都保证了改造前后都保证了改造前后的两个函数依赖集等价，因此剩下的的两个函数依赖集等价，因此剩下的 与原来与原来的的 等价。等价。 证毕证毕v定理定理6.3的证明过程的证明过程 也是求也是求 极小依赖集极小依赖集的过程的过程

11、极小化过程（续）极小化过程（续）极小化过程（续）极小化过程（续）v极小化过程极小化过程( 定理定理6.3的证明的证明 )也是检验也是检验 是是否为极小依赖集的一个算法否为极小依赖集的一个算法极小化过程（续）极小化过程（续）v在在 中可以用与中可以用与 等价的依赖集等价的依赖集来取代来取代第第6章章 关系数据库理论关系数据库理论v6.1 问题的提出问题的提出v6.2 规范化规范化v6.3 数据依赖的公理系统数据依赖的公理系统v6.4 模式的分解模式的分解v6.5 小结小结6.4 模式的分解模式的分解关系模式分解的标准关系模式分解的标准三种模式分解的等价定义三种模式分解的等价定义 分解具有无损连接

12、性分解具有无损连接性 分解要保持函数依赖分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性分解既要保持函数依赖，又要具有无损连接性模式的分解（续）模式的分解（续）定义定义f+覆盖覆盖 fi模式的分解（续）模式的分解（续）例例: sl（sno， sdept， sloc） f= snosdept,sdeptsloc,snosloc sl2nf 存在插入异常、删除异常、冗余度大和修存在插入异常、删除异常、冗余度大和修改复杂等问题，改复杂等问题，分解方法可以有多种分解方法可以有多种 模式的分解（续）模式的分解（续）sl snosdeptsloc 95001 cs a 95002 is b 9

13、5003 ma c 95004 is b 95005 ph b 模式的分解（续）模式的分解（续）1. sl分解为下面三个关系模式：分解为下面三个关系模式： sn(sno) sd(sdept) so(sloc)分解后的关系为：分解后的关系为： sn sd so sno sdept sloc 95001 cs a 95002 is b 95003 ma c 95004 ph 95005 模式的分解（续）模式的分解（续）分解后的数据库分解后的数据库丢失了许多信息丢失了许多信息 例如无法查询例如无法查询95001学生所在系或所在宿舍。学生所在系或所在宿舍。 如果分解后的关系可以通过自然连接恢复为原如果

14、分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有来的关系，那么这种分解就没有丢失信息丢失信息模式的分解（续）模式的分解（续）2. sl分解为下面二个关系模式：分解为下面二个关系模式： nl(sno, sloc) dl(sdept, sloc)分解后的关系为：分解后的关系为： nl dl sno sloc sdept sloc 95001 a cs a 95002 b is b 95003 c ma c 95004 b ph b 95005 b 模式的分解（续）模式的分解（续）nl dl sno sloc sdept 95001 a cs 95002 b is 95002 b p

15、h 95003 c ma 95004 b is 95004 b ph 95005 b is 95005 b ph 模式的分解（续）模式的分解（续）nl dl比原来的比原来的sl关系多了关系多了3个元组个元组 无法知道无法知道95002、95004、95005 究竟是哪个系的学生究竟是哪个系的学生元组增加了，信息丢失了元组增加了，信息丢失了第三种分解方法第三种分解方法3. 将将sl分解为下面二个关系模式：分解为下面二个关系模式：模式的分解（续）模式的分解（续）nd nl sno sdept sno sloc 95001 cs 95001 a 95002 is 95002 b 95003 ma 9

16、5003 c 95004 is 95004 b 95005 ph 95005 b 模式的分解（续）模式的分解（续） nd nl sno sdept sloc 95001 cs a 95002 is b 95003 ma c 95004 cs a 95005 ph b 与与sl关系一样，因此没有丢失信息关系一样，因此没有丢失信息具有无损连接性的模式分解具有无损连接性的模式分解= r1，r2， ，rn模式的分解（续）模式的分解（续） 第三种分解方法具有无损连接性第三种分解方法具有无损连接性 问题问题: 这种分解方法没有保持原关系中的函数依赖这种分解方法没有保持原关系中的函数依赖 sl中的函数依赖中

17、的函数依赖sdeptsloc 没有投影到关系模式没有投影到关系模式nd、nl上上 保持函数依赖的模式分解保持函数依赖的模式分解第四种分解方法第四种分解方法 将将sl分解为下面二个关系模式：分解为下面二个关系模式： nd(sno, sdept) dl(sdept, sloc) 这种分解方法就保持了函数依赖。这种分解方法就保持了函数依赖。模式的分解（续）模式的分解（续）v如果一个分解具有无损连接性，则它能够保证如果一个分解具有无损连接性，则它能够保证不丢失信息。不丢失信息。v如果一个分解保持了函数依赖，则它可以减轻如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。或解决各种异常情况。v分

18、解具有无损连接性和分解保持函数依赖是两分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。的分解也不一定具有无损连接性。模式的分解（续）模式的分解（续）第一种分解方法既不具有无损连接性，也未保持函第一种分解方法既不具有无损连接性，也未保持函 数依赖，它不是原关系模式的一个等价分解数依赖，它不是原关系模式的一个等价分解第二种分解方法保持了函数依赖，但不具有无损连第二种分解方法保持了函数依赖，但不具有无损连 接性接性第三种分解方法具有无损连接性，但未持函数依赖第三种分解方法具有无损连接性，但未持函数依赖第四种分解方法既具有无损连接性，又保持了函数第四种分解方法既具有无损连接性，又保持了函数 依赖依赖分解算法分解算法v算法算法分解算法分解算法v解解p196 图图6