《课程名称_数据库系统概论》由会员分享，可在线阅读，更多相关《课程名称_数据库系统概论（55页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 关系数据库理论关系数据库理论 vv6.1 6.1 问题的提出问题的提出 vv6.2 6.2 规范化规范化 vv6.3 6.3 数据依赖的公理系统数据依赖的公理系统 vv6.4 6.4 模式的分解模式的分解 vv6.5 6.5 小结小结 6.3 6.3 数据依赖的公理系统数据依赖的公理系统 vv逻辑蕴含逻辑蕴含 定义定义6.116.11 对于满足一组对于满足一组函数依赖函数依赖 F F 的关的关 系模式系模式R R ，其任何一个关系，其任何一个关系 r r ，若，若 函数依赖函数依赖XYXY都成立都成立, , 则称则称 F F逻辑蕴含逻辑蕴含X YX Y ArmstrongArm
2、strong公理系统公理系统 vv一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础 vv用途用途 求给定关系模式的码求给定关系模式的码 从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖 1. Armstrong1. Armstrong公理系统公理系统 关系模式关系模式R 来说有以下的推理规则：来说有以下的推理规则： Al.Al.自反律自反律（ReflexivityReflexivity）：）： 若若Y Y X X U U，则，则X X Y Y为为F F所蕴含。所蕴含。 A2.A2.增广律增广律（AugmentationAugmentation）：若）
3、：若X XY Y为为F F所蕴含，所蕴含， 且且Z Z U U，则，则XZXZYZYZ为为F F所蕴含。所蕴含。 A3.A3.传递律传递律（TransitivityTransitivity）：若）：若X XY Y及及Y YZ Z为为F F所蕴所蕴 含，则含，则X XZ Z为为F F所蕴含。所蕴含。 注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的 使用并不依赖于使用并不依赖于F F 定理定理 6.l6.l ArmstrongArmstrong推理规则推理规则 是正确的是正确的 （l l）自反律自反律: :若若Y Y X X U
4、 U，则，则X X Y Y为为F F所蕴含所蕴含 证证: : 设设Y Y X X U U 对对R 的任一关系的任一关系 r r 中的任意两个元组中的任意两个元组t t，s s： 若若t t X X=s s X X ，由于，由于Y Y X X，有，有t t y y=s s y y ， 所以所以X XY Y成立成立. . 自反律得证自反律得证 定理定理6.l (6.l (续续) ) (2)(2)增广律增广律: : 若若X XY Y为为F F所蕴含，且所蕴含，且Z Z U U，则，则XZXZYZ YZ 为为 F F所蕴含。所蕴含。 证：证：设设X XY Y为为F F所蕴含，且所蕴含，且Z Z U U
5、。 设设R 的任一关系的任一关系 r r 中任意的两个元组中任意的两个元组t t，s s； 若若t t XZXZ=s s XZXZ ，则有，则有t t X X=s s X X 和和t t Z Z=s s Z Z ； 由由X XY Y，于是有，于是有t t Y Y=s s Y Y ，所以，所以t t YZYZ=s s YZYZ ，所以，所以 XZXZYZYZ为为F F所蕴含所蕴含. . 增广律得证。增广律得证。 定理定理6.l 6.l （续）（续） (3) (3) 传递律传递律：若：若X XY Y及及Y YZ Z为为F F所蕴含，则所蕴含，则 X XZ Z为为 F F所蕴含。所蕴含。 证：证：设
6、设X XY Y及及Y YZ Z为为F F所蕴含。所蕴含。 对对R 的任一关系的任一关系 r r中的任意两个元组中的任意两个元组 t t，s s。 若若t t X X=s s X X ，由于，由于X XY Y，有，有 t t Y Y=s s Y Y ； 再由再由Y YZ Z，有，有t t Z Z=s s Z Z ，所以，所以X XZ Z为为F F所蕴含所蕴含. . 传递律得证。传递律得证。 2. 2. 导出规则导出规则 1.1.根据根据A1A1，A2A2，A3A3这三条推理规则可以得这三条推理规则可以得 到下面三条推理规则：到下面三条推理规则： 合并规则合并规则：由：由X XY Y，X XZ Z
7、，有，有X XYZYZ。 （A2A2， A3A3） 伪传递规则伪传递规则：由：由X XY Y，WYWYZ Z，有，有XWXWZ Z 。 （A2A2， A3A3） 分解规则分解规则：由：由X XY Y及及 Z Z Y Y，有，有X XZ Z。 （A1A1， A3A3） 导出规则导出规则 2.2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理6.16.1 引理引理6.l6.l X XA A 1 1 A A 2 2 AA k k 成立的充分必要条成立的充分必要条 件是件是X XA A i i 成立（成立（i i=l=l，2 2，k k）。）。 3. 3. 函数依赖闭包函数依赖闭包
8、定义定义6.l26.l2 在关系模式在关系模式R中为中为F F所逻辑蕴含所逻辑蕴含 的函数依赖的全体叫作的函数依赖的全体叫作 F F的闭包的闭包，记为，记为F F + + 。 定义定义6.136.13 设设F F为属性集为属性集U U上的一组函数依赖，上的一组函数依赖，X X U U， X XF F+ + = = A|XA|XA A能由能由F F 根据根据ArmstrongArmstrong公理导出公理导出 ，X X F F + + 称为属性集称为属性集X X关于函数依赖集关于函数依赖集F F 的闭包的闭包 关于闭包的引理关于闭包的引理 vv引理引理6.26.2 设设F F为属性集为属性集U
9、U上的一组函数依赖，上的一组函数依赖，X X，Y Y U U， X XY Y能由能由F F 根据根据ArmstrongArmstrong公理导出的充分必要公理导出的充分必要 条件是条件是Y Y X X F F + + vv用途用途 将判定将判定X XY Y是否能由是否能由F F根据根据ArmstrongArmstrong公理导出公理导出 的问题，就转化为求出的问题，就转化为求出X X F F + + ，判定，判定Y Y是否为是否为X X F F + + 的的 子集的问题子集的问题 求闭包的算法求闭包的算法 算法算法6.l 6.l 求属性集求属性集X X（X X U U）关于）关于U U上的函数
10、依上的函数依 赖集赖集F F 的闭包的闭包X X F F + + 输入：输入：X X，F F 输出：输出：X X F F + + 步骤：步骤： （1 1）令）令X X（ （0 0）= =X X， ，i i=0=0 （2 2）求）求B B，这里，这里B B = = A A |( |( V)(V)( WW)( )(V VWW F F V V X X（ （i i） A A W)W) ； （3 3）X X（ （i+1i+1）= =B B X X（ （i i） 算法算法 6.l6.l （4 4）判断）判断X X（ （i+1i+1）= = X X （ （i i）吗 吗? ? （5 5）若相等或）若相等或X
11、 X（ （i i）= =U , U , 则则X X（ （i i）就是 就是X X F F + + , , 算法终止。算法终止。 （6 6）若否，则）若否，则 i i= =i i+l+l，返回第（，返回第（2 2）步。）步。 对于算法对于算法6.l6.l， 令令a a i i =| =|X X（ （i i）| |， ， a a i i 形成一个步长大形成一个步长大 于于1 1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是 | | U U | |，因，因 此该算法最多此该算法最多 | |U U| - | - |X|X| | 次循环就会终止。次循环就会终止。 U=A, B, C, D;
12、 F=A B, BC D;U=A, B, C, D; F=A B, BC D; vv A A+ + = AB. = AB. vv C C+ + = C. = C. vv(AC)(AC) + + = ABCD. = ABCD. 实例实例 函数依赖闭包函数依赖闭包 例例1 1 已知关系模式已知关系模式R R，其中，其中 U U=A A， B B ， C C ， D D ，E E ； F F=ABABC C，B BD D，C CE E，ECECB B，ACACB B 。 求（求（ABAB） F F + + 。 解解 设设X X（ （ 0 0 ）= =AB AB； (1)(1)计算计算X X（ （ 1
13、 1 ）: : 逐一的扫描逐一的扫描F F集合中各个函数依赖，集合中各个函数依赖， 找左部为找左部为A A，B B或或ABAB的函数依赖。得到两个：的函数依赖。得到两个： ABABC C，B BD D。 于是于是X X（ （ 1 1 ）= =AB ABCDCD= =ABCDABCD。 。 函数依赖闭包函数依赖闭包 (2)(2)因为因为X X（ （ 0 0 ） X X（ （ 1 1 ） ，所以再找出左部为 ，所以再找出左部为ABCDABCD子子 集的那些函数依赖，又得到集的那些函数依赖，又得到ABABC C，B BD D， C CE E，ACACB B， 于是于是X X（ （ 2 2 ） = =X X （ 1 1 ） BCDEBCDE= =ABCDEABCDE。 (3)(3)因为
