数据库原理63.ppt

第六章第六章 关系数据理论关系数据理论3授课教师：顾留碗关系模式关系模式规范化的基本步范化的基本步骤 1NF ↓ 消除非主属性对码的部分函数依部分函数依赖消除决定属性 2NF集非码的非平 ↓ 消除非主属性对码的传递函数依函数依赖凡函数依赖 3NF ↓ 消除主属性对码的部分和部分和传递函数依函数依赖 BCNF ↓ 消除非平凡且非函数依赖的多值依赖 4NF本次本次课内容内容1多多值依依赖及第四范式及第四范式2数据依数据依赖的公理系的公理系统§逻辑蕴涵§Armstrong公理系统§函数依赖集的闭包§函数依赖集的等价及最小函数依赖集一、多一、多值依依赖及第四范式及第四范式1）多）多值依依赖（MultiValued Dependency，简记MVD）v定义定义6.9（P179） 设R(U)是一个属性集U上的一个关系模式， X、 Y和Z是U的子集，并且Z＝U－X－Y。

关系模式R(U)中多值依赖多值依赖 X→→Y成立，当且仅当对R(U)的任一关系任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关；例 Teaching（C, T, B） 对于C的每一个值，T有一组值与之对应，而不论B取何值；2 2）第四范式）第四范式v定义定义6.106.10（（P P181181））§关系模式R∈1NF，如果对于R的每个非平凡多值依赖每个非平凡多值依赖X→→Y（Y  X），X X都含有候选码都含有候选码，则R∈4NFv如果R ∈ 4NF， 则R ∈ BCNFn限制关系模式的属性之间不允许有非平凡且非函数依赖的多不允许有非平凡且非函数依赖的多值依赖；值依赖；n允许的是函数依赖（是非平凡多值依赖）n如果一个关系模式是BCNF，而且至少有一个码是由一个属性组成，此关系模式就是4NF;规范化小范化小结v规范化目的范化目的：使结构更合理，消除插入、修改、删除异常，使数据冗余尽量小，便于插入、删除和更新v规范化方法范化方法：将关系模式投影分解成两个或两个以上的关系模式v规范化原范化原则：遵从概念单一化 “一事一地”原则，即一个关系模式描述一个实体或实体间的一种联系。

规范的实质就是概念的单一化v规范化要求范化要求：分解后的关系模式集合应当与原关系模式“等价”，即经过自然联接可以恢复原关系而不丢失信息，并保持属性间合理的联系二、数据依二、数据依赖的公理系的公理系统v问题的提出：在关系模式规范化处理过程中，不仅要知道一个由语义决定的函数依赖集合，还要知道由这个已知的函数依赖集合所蕴含（或推导出）的所有函数依赖集合为此，需要一个有效而完备的公理系统， Armstrong公理系统即是这样的一个系统v相关定义：一个函数依赖可以通过已知的函数依赖推导出来；如利用X→Y和Y→Z可以推导出X →Z，可以说，函数依赖X→Y和Y→Z逻辑蕴含（含（Logical Implication））了X →Z主要内容：主要内容：1、逻辑蕴涵2、Armstrong公理系统3、函数依赖集的闭包4、函数依赖集的等价及最小依赖集1、、逻辑蕴涵涵v定义定义6.116.11对于于满足一足一组函数依函数依赖￿ ￿F 的关系模式的关系模式R ，其任何一个关，其任何一个关系系r，若函数依，若函数依赖X→Y都成立（即都成立（即r中任意两元中任意两元组t、、s，若，若t[X]=s[X]t[X]=s[X]，则，则t[Y]=s[Y]t[Y]=s[Y]），），则称称F逻辑蕴含含X→YX→Y，记为，记为F F⊨ ⊨X→YX→Y；；v例如，设F={ A→B，B→C }，则函数依赖A→C被F逻辑蕴含，记作：F |= A→C。

即函数依赖集 F 逻辑蕴含函数依赖A→C2、、Armstrong公理系统公理系统vArmstrong公理系统：一套推理规则，是模式分解算法的理论基础；v关系模式R 来说有以下的推理规则：§A1.自反律（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所蕴含根据推理根据推理规则导出的出的规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：§ 合并规则：由X→Y，X→Z，有X→YZ （A2， A3）§ 伪传递规则：由X→Y，WY→Z，有XW→Z （A2， A3）§ 分解规则：由X→Y及 Z  Y，有X→Z （A1， A3）2.根据合并规则和分解规则，可得引理6.1； 引理6.l X→A1 A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）3、函数依、函数依赖集的集的闭包包v定义定义6.l26.l2在关系模式R中为F所逻辑蕴含的函数依函数依赖的全体的全体叫作F的的闭包包（（closure）），，记为F +，即F+=｛X→Y|记为F|=X→Y｝。

￿F+={Fi|从阿氏公理中导出的所有函数依赖的集合}v一般情况下，F  F+，如果F =F+，则称F为一个函数依赖的完备集；例例1：： 已知关系模式已知关系模式R（（XYZ），），F={XY, YZ}，求，求F+；；根据阿氏公理可得出：根据阿氏公理可得出：F + ={Xφ,Yφ,Zφ,XYφ, XZφ,YZφ, XYZφ, XX, YY, ZZ,XYX, XZX,YZY, XYZX,XY,Y Z,XYY, XZY,YZZ, XYZY,XZ,YYZ,XYZ, XZZ,YZYZ, XYZZ,XXY,XYXY, XZXY,XYZXY, XXZ,XYYZ, XZXZ,XYZYZ,XYZ,XYXZ, XZXY,XYZXZ,XZYZ,XYXYZ, XZXYZ,XYZXYZ }共计42个FD；vArmstrong公理系统是有效的、完备的：§有效性有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；§完备性完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。

属性集的属性集的闭包包v定义定义6.136.13设F为属性集U上的一组函数依赖，XU，XF+ ={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集属性集X关于函关于函数依数依赖集集F的的闭包v在实际使用中，判定X→Y是否能从已知的F根据阿氏公理导出的问题，就转化为求出XF+ ，然后判定Y是否为XF+的子集的问题v引理引理6.26.2设F为属性集U上的一组函数依赖，X，Y  U，X→Y能由F根据阿氏公理导出的充分必要条件是Y  XF+ v用途用途 将判定X→Y是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题算法算法6.1 求属性集求属性集X（（X   U）关于）关于U上的函数依赖集上的函数依赖集F 的闭包的闭包XF+ ；；输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B = { A |( V)(  W)(V→WF∧V  X（i）∧A W)}；（3）X（i+1）=B∪X（i） （4）判断X（i+1）= X （i）吗?（5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。

6）若否，则 i=i+l，返回第（2）步例例1：： 已知关系模式已知关系模式R，其中，其中U={A，，B，，C，，D，，E}；；F={AB→C，，B→D，，C→E，，EC→B，，AC→B}求（AB））F+ 解 设X（0）=AB；(1) X（1）=AB∪CD=ABCD ；(2) X（0）≠ X（1） X（2）=X（1）∪BE=ABCDE3) X（2）=U，算法终止（（AB））F+ =ABCDE例例2：： 已知关系模式已知关系模式R，其中，其中U={A，，B，，C，，D}；；F={A→B，，B→C，，D→B}求AF+ 、（、（AD））F+ 及（及（BD）） F+ ；；解： 设X（0）=A；(1) X（1）=A∪B=AB；(2) X（0）≠ X（1） X（2）=X（1）∪C=ABC；(3) X（3）= X（2） ，算法终止；AF+ =ABC，， （（AD））F+ = ABCD ，（（BD）） F+ =BCD例例3：已知关系模式：已知关系模式R，其中，其中U={A，，B，，C，，D，，E，，F}；；F={AB→C,BC →AD,D →E,CF →B}。

求（求（AB））F+ 解 设X（0）=AB；(1) X（1）=AB∪C=ABC ；(2) X（0）≠ X（1） X（2）=X（1）∪D=ABCD ；(3) X（3）=ABCD ∪E=ABCDE ；(3) X（4）= X（3） ，算法终止（（AB））F+ =ABCDE例例4：已知关系模式：已知关系模式R(A,B,C,D)，，F={AB→C,C →D,D →A}求：求：蕴含于含于给定函数的所有非平凡函数依定函数的所有非平凡函数依赖；；(1)求关系R的所有单属性的闭包； AF+ = A ，， BF+ = B ，， CF+ = ACD，， DF+ = AD(2)求关系R的所有双属性的闭包；（（AB））F+ =ABCD，， （（AC））F+ =ACD，， （（AD））F+ =AD，，（（BC））F+ =ABCD，， （（ BD ））F+ =ABCD，（，（CD））F+ =ACD(3)求关系R的所有三属性的闭包；（（ABC））F+ =ABCD，， （（ABD ））F+ =ABCD（（ACD））F+ =ACD，，（（BCD））F+ =ABCD(4)求关系R的所有三属性的闭包； （（ABCD））F+ =ABCD根据以上计算，寻找关系R的超码和候选码，列出所有属性闭包：超码：AB,BC,BD,ABC,ABD,BCD,ABCD候选码：AB,BC,BD4、函数依、函数依赖集的等价及最小依集的等价及最小依赖集集v定义定义6.14 设F和G是两个函数依赖集： ①如果F+G+，则称G是F的一个覆盖，或称G覆盖F；②如果F+G+和G+F+同时成立，即F+=G+，则称F和和G等等价价。

v引理引理6.3 F+=G+的充分必要条件是FG+ 和GF+ ；要判定FG+，只须逐一对F中的函数依赖X→Y，考察Y是否属于XG+ 就行了；引理6.3给出了判断两个函数依赖集等价的可行算法v研究函数依赖集等价的目的： 是为了对指定函数依赖集找出它的最小函数依赖等价集，即找出包含函数依赖尽可能少、甚至最少的函数依赖等价集，从而使模式分解简化，分解出最简单的关系模式v定义定义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等价￿v计算最小覆盖的算法：算最小覆盖的算法：给定函数依赖集F，求其最小覆盖的过程如下：§逐一检查F 中各函数依赖X→Y，若Y=A1…Ak， k>=2，则用{X→Aj | j=1,…,k}来取代它；（分解规则）；（分解规则）§逐一检查F中各函数依赖X→A，令G=F-{X→A}，如果A∈XG+ ，则F与G等价，故从F中去掉X→A。

（（FD不包含无关属性）不包含无关属性）§逐一取出F中各函数依赖X→A，若X=B1B2…Bm，m>=2，则逐一考查Bj（j=1,…,m），如果A∈(X-Bi)F+ ，则以X-Bj取代X;（（FD的左部都是唯一出现）的左部都是唯一出现）例例1：：设F是关系模式是关系模式R（（ABC）的）的FD集，集，F=｛｛ A→BC，，B→AC，，C→A｝，｝，试求求Fmin① 先把F中的FD分解为右边是单属性形式： F=｛ A→B，A→C，B →A ，B→C，C→A ｝②去掉F中冗余的函数依赖：判断A→B，设：G1={ A→C，B→A，B→C，C→A}，得：AG1+=AC ∵ BAG1+ ∴ A→B不冗余判断A→C，设：G2={ A→B，B→A，B→C，C→A}，得：AG2+=ABC ∵ CAG2+ ∴ A→C冗余判断B→A，设：G3={ A→B，B→C，C→A}，得：BG3+=BCA ∵ ABG3+ ∴ B→A冗余判断B→C，设：G4={ A→B，C→A}，得：BG4+=B ∵ CBG4+ ∴ B→C不冗余判断C→A，设：G5={ A→B，B→C }，得：CG5+=C ∵ ACG5+ ∴ C→A不冗余Fm={ A→B，，B→C，，C→A}例例2：求：求F={AB→C，，A→B，，B→A}的最小函数依的最小函数依赖集集Fmin。

解：(1)去掉F中冗余的函数依赖：判断AB→C是否冗余设：G1={ A→B，B→A}，得：(AB)G1+=AB ∵ C (AB)G1+ ∴ AB→C不冗余判断A→B是否冗余设：G2={ AB→C，B→A}，得：AG2+=A ∵ BABG2+ ∴ A→B不冗余判断B→A是否冗余设：G3={ AB→C，A→B }，得：BG3+=B ∵ ABG3+ ∴B→A不冗余函数依赖集仍然为F={AB→C，A→B，B→A}；(2) 去掉各函数依赖左部冗余的属性（本题只需考虑AB→C的情况）方法1：在决定因素中去掉B，若CAF+，则以A→C代替AB→C求得：AF+=ABC ∵ CAF+ ∴ 以A→C代替AB→C故：Fm={A→C，A→B，B→A}方法2：在决定因素中去掉A，若CBF+，则以B→C代替AB→C求得：BF+=ABC ∵ CBF+ ∴ 以B→C代替AB→C故：Fm={B→C，A→B，B→A}例例3：：设F是关系模式是关系模式R（（ABC）的）的FD集，集，F=｛｛ A→BC，，B→C，，A→B，，AB→C ｝，｝，试求求Fmin解：① 先把F中的FD分解为右边是单属性形式：F=｛ A→B，A→C，B→C，AB→C ｝② 去掉F中冗余的函数依赖：得F=｛ A→B，AB→C ｝③ 去掉各函数依赖左部冗余的属性：F中AB→C可从A→B和B→C推出，得F=｛ A→B，B→C ｝或F=｛ A→B，A→C ｝ 。

v应当指出：F的最小依赖集Fm不一定是唯一的，它与对各函数依赖Fdi及X→A中X各属性的处置顺序有关v例课本P186 例3F={A →B, B →A, B →C, A →C, C → A}Fm1={A →B, A →C, C → A}若F = {A→B, B→A, A→C, B→C, C→A}则Fm2={A →B, B→C, C → A}若F = {C→A, B →A , A →B, A →C, B →C}则Fm3={B →A, A →B, B → C}……判断：判断：假假设有属性集有属性集U={A,B,C,D,E}，，函数依函数依赖集集F={A→B,B→C,AD→E}函数依函数依赖集集G={A→B,A→C,B→C,AD→E}，，问F和和G是否是最小函数依是否是最小函数依赖集？集？ 答案：F是最小依赖集，G不是最小依赖集练习题1、、设关系模式关系模式R（（ABCDE）上）上FD集集为F，且，且F={A→BC , CD →E ,B →D,E →A}，，试求：求：1） BF+的值；2） (ABC) F+的值；3） R的候选键；4）计算F的最小函数依赖集；2、关系模式、关系模式R（（ A ，，B，，C，，M，，T），根据），根据语义有如下函数依有如下函数依赖集：集：F={B→C，（，（M，，T））→B，（，（M，，C））→T，（，（M，，A））→T，（，（A，，B））→C}，关系模式，关系模式R的的码是（是（ C））A. (M，T)B. (M，C)C. (M，A)D.(A，B)本章本章总结1关系模式中可能存在的异常（示例）§数据冗余、插入异常、删除异常、更新复杂2关系模式中存在异常的原因§数据依赖（定义、分类）、函数依赖3关系模式的规范化§函数依赖（平凡、非平凡、完全、部分及传递函数依赖）§范式：1NF、2NF、3NF、BCNF§多值依赖及4NF4数据依赖的公理系统§阿氏公理§函数依赖集的闭包§函数依赖集的等价及最小函数依赖集v学习本章的目的有两个：§一个是理论方面的，本章用更加形式化的关系数据理论来描述和研究关系模型；§另一个是实践方面的，关系数据理论是我们进行数据库设计的有力工具；。