数据库6版讲稿第八章---关系数据库设计

1、提纲提纲l给出一个关系模式，是不是好？l给出一个表，怎么找出其中的函数依赖？l给出一个关系模式，如何判断属于nNF ？l1NF、2NF、3NF、BCNF的异同点？l分解后，无损与保持依赖如何判断？l分解算法l多值依赖确定方法是什么？l4NF分解算法l范式之间如何证明包含关系？8.1 好的关系设计的特点好的关系设计的特点l四种异常现象四种异常现象l引例：设计一个学生管理信息系统，模式设计两种方案：l方案一l学生学生=（学号，（学号，姓名，性别，年龄，系别，系主任名，系办公电话，课程号，课程名，先行课号，成绩）l码是学号，课程号8.1 好的关系设计的特点好的关系设计的特点l方案二l学生=（学号，姓

2、名，性别，年龄，系别），码：学号l系=（系别，系主任名，系办公电话），码：系别l课程=（课程号，课程名，先行课号，学分） 码：课程号l选课=（学号，课程号，成绩），码：学号，课程号8.1 好的关系设计的特点好的关系设计的特点l1. 冗余度l方案一：假若每个学生选40门课程，其姓名、性别、年龄、系别、系主任、系办公电话、课名，先行课号要在库中出现40次，数据冗余度大。l方案二：l以上的数据只在库中出现一次，冗余度小。8.1 好的关系设计的特点好的关系设计的特点l2. 插入异常l若向库中插入一门新课程，而该课程还没有学生选。l方案一： 由于模式的码是学号，课程号，实体完整性要求主属性不能为空，现在

3、学号为空，无法插入库内。8.1 好的关系设计的特点好的关系设计的特点l方案二：l直接插入课程关系中。l同理，方案一，建立一个新系，还没有学生，也会插入异常。方案二，直接插入系表中。l 3. 删除异常l如果选修某门课程的学生都毕业，其对应记录将从库中删掉。8.1 好的关系设计的特点好的关系设计的特点l方案一：方案一：l对应的课程信息也全部删掉。称为删除对应的课程信息也全部删掉。称为删除异常异常。l方案二：l只删选课表中的记录，课程表中的信息不受影响。l同理，方案一，一个系的学生全部删除，也会删除异常。方案二，直接删除学生表中的记录，系表不受影响。 8.1 好的关系设计的特点好的关系设计的特点l4

4、 更新异常l若数据库课程名改为数据库原理。l方案一：l所有选修该课程的的记录都要改，漏改一个，就会出现更新异常。l方案二：l只需在课程关系中修改一次。l同理，系主任名等属性值修改也如此 8.1 好的关系设计的特点好的关系设计的特点l引例考虑为管理职工的工资信息而设计一个关系模式 职工 级别 工资 赵明 4 500 钱广 5 600 孙志 6 700 李开 5 600 周祥 6 700 8.1 好的关系设计的特点好的关系设计的特点l插入异常：如果没有职工具有8级工资，则8级工资的工资数额就难以插入l删除异常：如果仅有职工赵明具有4级工资，如果将赵明删除，则有关4级工资的工资数额信息也随之删除了l

5、数据冗余：职工很多，工资级别有限，每一级别的工资数额反复存储多次l更新异常：如果将5级工资的工资数额调为620，则需要找到每个具有5级工资的职工，逐一修改8.1 好的关系设计的特点好的关系设计的特点l四种异常现象的原因l导致四中异常现象的原因是构造关系模式过程中，忽视了属性之间存在着相互关联，相互依赖，相互制约的联系，盲目地把依赖不紧密的属性硬凑在一起依赖不紧密的属性硬凑在一起。l 关系模式设计中， 方案二比方案一优越，方案二所属范式高于方案一。l 如系办公电话与成绩并没有联系。 8.1 好的关系设计的特点好的关系设计的特点l解决之道-分解 职工 级别 赵明 4 钱广 5 孙志 6 李开 5

6、周祥 6 级别工资4500560067008.2 第一范式第一范式l范式的概念l范式是关系模式的集合集合。一个关系模式R达到某种级别，记为RnNF。l目前有六种主要范式：第一范式，第二范式，第三范式，BC范式，第四范式和第五范式。l低级范式通过关系分解，达到更高一级的范式，过程称作规范化。8.2 第一范式第一范式l各范式集之间存在如下关系：1NF2NF3NF4NFBCNF5NF8.2 第一范式第一范式l 第一范式(1NF)l 定义 如果关系模式R的所有属性都是不可分的基本数据项，则R1NF。l 第一范式是二维表的要求，排斥了属性值为元组、数组或某种复合数据的可能性。不满足第一范式的数据库不能称

7、为关系数据库。l 满足第一范式的关系模式往往会出现异常。1NFl定义关系中每一分量不可再分。即不能以集合、序列等作为属性值C1，C2，C3S1C#S#C3S1C2S1C1S1C#S#8.3 函数依赖的分解函数依赖的分解l函数依赖的概念函数依赖的概念l定义一：l设R=(U)表示一个关系模式，属性集合U=A1,A2,An，X和Y是U的子集，对R=(U)下的任一个关系r的任意两个元组t1，t2，如果t1X=t2X，则t1Y=t2Y，称属性集X与属性集Y存在函数依赖。l记作XY。8.3 函数依赖的分解函数依赖的分解l叫作“X函数确定Y”或“Y函数依赖于X”， X为决定因素，Y为依赖因素。l如果Y不函数

8、依赖X，则记作X- Y。l如果XY且YX，则X与Y是一一对应函数依赖，记作XY。l定义：R下的所有函数依赖组成R的函数依赖集，记为F。8.3 函数依赖的分解函数依赖的分解l对函数依赖的理解对函数依赖的理解l(1) XY的判断按离散数学的逻辑蕴涵运算确定结果。l当t1X=t2X时，只有t1Y=t2Y时，满足定义；l当t1Xt2X时，直接满足定义。l (2) 如果两属性集X，Y的属性值之间有l 1 1的联系，则XY8.3 函数依赖的分解函数依赖的分解l n 1的联系，则XYl m n的联系，则X-Y，Y-Xl(3) 码R的所有属性。 因为任意两个元组t1，t2， 有 t1码t2码l（4）函数依赖指

9、R(U)下的所有关系r均要满足定义条件。l (5) 函数依赖概念属于语义范畴，是现实世界的反映。 8.3 函数依赖的分解函数依赖的分解l例如，学生学生=（学号，（学号，姓名，性别，年龄，系别），码：学号l学号学号姓名l学号学号学号姓名性别年龄系别l如果设计者强行规定所有学生都不重名，则l姓名学号学号l姓名性别年龄系别l姓名学号学号姓名性别年龄系别。8.3 函数依赖的分解函数依赖的分解l函数依赖的类型函数依赖的类型l1平凡函数依赖平凡函数依赖l如果Y X ，按定义，则XY，称平凡函平凡函数依赖，否则为非平凡函数依赖数依赖，否则为非平凡函数依赖 l2 . 完全函数依赖与部分函数依赖完全函数依赖与部

10、分函数依赖l 如果XY，且不存在X X ，使XY，则称Y完全函数依赖完全函数依赖 X,否则称Y部分函数依部分函数依赖赖 l（注意：不是Y的一部分依赖于X），8.3 函数依赖的分解函数依赖的分解l3. 传递函数依赖传递函数依赖l如果XY，Y-X，YZ，则称Z对X是传递函数依赖传递函数依赖 l例 ：学生学生=（学号，（学号，姓名，性别，年龄，系别，系主任名，系办公电话，课程号，课程名，先行课号，成绩）l学号课程号成绩 ,是完全依赖。l学号课程号年龄，是部分依赖，因为学号年龄8.3 函数依赖的分解函数依赖的分解l学号系别l系别系主任名，系主任名-系别，规定可以在多个系担任系主任，所以有传递依赖：l学

11、号系主任名，是传递依赖l4候选码候选码、超码、全码超码、全码l候选码：候选码：KU， K完全决定完全决定U，候选码的，候选码的任何真子集都不函数决定任何真子集都不函数决定U。8.3 函数依赖的分解函数依赖的分解l超码：超码：KU， K部分决定部分决定U，K真子集真子集函数决定函数决定U。l全码：全码： R=(U)中不存在任何依赖，所有属中不存在任何依赖，所有属性组成全码性组成全码l例如：学生例如：学生=（学号，姓名，性别，年龄，（学号，姓名，性别，年龄，系别，系主任名，系办公电话，课程号，系别，系主任名，系办公电话，课程号，课程名，先行课号，成绩）课程名，先行课号，成绩）l学号课程号学号课程号

12、学号姓名性别年龄系别系主学号姓名性别年龄系别系主任名系办公电话，课程号课程名先行课号任名系办公电话，课程号课程名先行课号成绩，学号课程号是候选码成绩，学号课程号是候选码8.3 函数依赖的分解函数依赖的分解l学号课程号系别学号课程号系别学号姓名性别年龄系学号姓名性别年龄系别系主任名系办公电话，课程号课程名别系主任名系办公电话，课程号课程名先行课号成绩，学号课程号系别是超码先行课号成绩，学号课程号系别是超码l例如：教学参考书例如：教学参考书=（教师名，课程名，（教师名，课程名，参考书名），参考书名），M：N：P联系联系l教学参考书模式中没有任何依赖教学参考书模式中没有任何依赖l全码：教师名课程名参

13、考书名全码：教师名课程名参考书名8.3 函数依赖的分解函数依赖的分解l5. 主属性与非主属性主属性与非主属性l主属性主属性 ：所有候选码中的属性为主属：所有候选码中的属性为主属性。性。l非主属性非主属性 ： 不在候选码中的属性。不在候选码中的属性。l 6. 第二范式第二范式(2NF)l定义：若关系模式定义：若关系模式1NF并且每个非并且每个非主属性都完全函数依赖于主属性都完全函数依赖于R的码，则的码，则R2NF。 8.3 函数依赖的分解函数依赖的分解l例 学生=（学号，姓名，性别，年龄，系别，系主任名，系办公电话，课程号，课程名，先行课号，成绩）l候选码：学号课程号l主属性：学号、课程号l非主

14、属性：姓名、性别、年龄、系别、系主任名、系办公电话、课程名、先行课号、成绩8.3 函数依赖的分解函数依赖的分解l存在非主属性部分依赖于码：存在非主属性部分依赖于码：l学号学号姓名姓名 等，等，l课程号课程号课程名课程名 等等l学生学生1NFl注意：注意：l（1）如果关系模式的每个侯选码只含一）如果关系模式的每个侯选码只含一个属性，那么一定属于个属性，那么一定属于2NF。 l（2）2NF模式存在异常现象模式存在异常现象8.3 函数依赖的分解函数依赖的分解l例例 学生学生=（学号，姓名，性别，年龄，系（学号，姓名，性别，年龄，系别，系主任名，系办公电话别，系主任名，系办公电话l课程课程=（课程号，

15、课程名，先行课号（课程号，课程名，先行课号l选课选课=（学号，课程号，成绩）（学号，课程号，成绩）l对于学生表，候选码：学号对于学生表，候选码：学号l主属性：学号主属性：学号l非主属性：姓名、性别、年龄、系别、系非主属性：姓名、性别、年龄、系别、系主任名、系办公电话主任名、系办公电话l学生学生2NF2NFl插入异常：如果系中没有学生，则系的信息就无法插入l删除异常：如果学生全部毕业了，则在删除学生信息的同时系的信息也随之删除了l更新异常：如果学生转系，或换系主任，则该系每个学生元组都要做相应修改l数据冗余：每个学生存储了所在系的信息8.4 函数依赖理论函数依赖理论l 函数依赖集的逻辑蕴涵函数依

16、赖集的逻辑蕴涵l1引例引例l给定给定R=(A，B，C)，F=AB,BC，由传递函数依赖定义，由传递函数依赖定义，AC也成立。也成立。l 给定给定R=(U)，通过语义说明可以得到函数，通过语义说明可以得到函数依赖集依赖集F，通过推理规则可以得到，通过推理规则可以得到F之外的之外的函数依赖。因此说，函数依赖。因此说，F只是只是R=(U)全部函数全部函数依赖的一部分。依赖的一部分。 8.4 函数依赖理论函数依赖理论l2函数依赖集的逻辑蕴涵定义函数依赖集的逻辑蕴涵定义l设设F是关系模式是关系模式R的一个函数依赖集，的一个函数依赖集，X、Y是是R的属性子集，如果从的属性子集，如果从F中的函数依赖中的函数

17、依赖能够推出能够推出XY，则称，则称F逻辑蕴涵逻辑蕴涵XY。l3 . 函数依赖的推理规则函数依赖的推理规则 l设设R=(U)，F是是R的函数依赖集，的函数依赖集，X、Y、Z均是均是U的子集，推理规则如下：的子集，推理规则如下：l A1：自反律：自反律(reflexivity)l如果如果 Y X U，则，则F 蕴涵蕴涵XY。 8.4 函数依赖理论函数依赖理论l说明：平凡依赖，说明：平凡依赖，l证：如果证：如果t1X=t2X,则因则因 Y X ，有有t1Y=t2Y，故，故XY成立。成立。l例例 学号姓名学号姓名学号，学号姓名学号，学号姓名姓名姓名 ，学号姓名学号姓名学号姓名学号姓名 lA2：增补律

18、：增补律l如果如果XY，且，且Z U，则，则XZYZ成立。成立。(XZ代表代表XZ)8.4 函数依赖理论函数依赖理论l证：如果证：如果t1XZ=t2XZ,则有则有t1X=t2X,t1Z=t2Z。 已知已知XY成立，因此可得成立，因此可得t1Y=t2Y,由上可知由上可知t1YZ=t2YZ，故，故XZYZ成立。成立。l例：学号例：学号姓名，姓名， 则则l学号年龄学号年龄姓名年龄，姓名年龄，l学号姓名学号姓名姓名，姓名，l学号学号学号姓名学号姓名8.4 函数依赖理论函数依赖理论l A3：传递律：传递律l如果如果XY和和YZ，则，则XZ成立。成立。l证：如果证：如果t1X=t2X,则则t1Y=t2Y；

19、如果；如果t1Y=t2Y,则则t1Z=t2Z由上可得，如果由上可得，如果t1X=t2X,则则t1Z=t2Z，故，故XZ成立。成立。l例：学号例：学号系别，系别系别，系别系主任名，则系主任名，则 学学号号系主任名系主任名 8.4 函数依赖理论函数依赖理论l A4：合并规则：合并规则(the union rule)l如果如果XY，XZ，则有，则有XYZ。l证：如果证：如果XY，则由增补律，则由增补律 XXY l 如果如果XZ，则由增补律，则由增补律 XYYZ l 通过传递律得通过传递律得XYZl推论：如果推论：如果XAi (i=1,2，k)，则，则l XA1,A2,Ak成立。成立。 8.4 函数依

20、赖理论函数依赖理论lA5：分解规则：分解规则l 如果如果XY，且，且 Z Y ，则，则XZ成立。成立。l 证：如果证：如果Z Y ，则由自反律得，则由自反律得 YZ l 已知已知XY ，由传递律得，由传递律得XZl推论：如果推论：如果XA1,A2,Ak，则，则XAi (i=1,2,k)成立。成立。l例：学号课程号例：学号课程号U，则学号课程号，则学号课程号年年龄，学号课程号龄，学号课程号年龄系主任名。年龄系主任名。8.4 函数依赖理论函数依赖理论l注意：注意：l候选码决定每一个属性。候选码决定每一个属性。 lA6： 伪传递规则伪传递规则l如果如果XY，WYZ，则，则XWZ。l证：证： 如果如果

21、XY，则由增补律，则由增补律 XWWY l 已知已知WYZ ，l 由传递律得由传递律得 WXZ 8.4 函数依赖理论函数依赖理论l 4. 函数依赖集的闭包函数依赖集的闭包l定义：关系模式定义：关系模式R=(U)中，中，F及及F所蕴涵的所蕴涵的全体函数依赖称为全体函数依赖称为F的闭包，记为的闭包，记为F+。l如果如果F=F+，则称，则称F是函数依赖的完备集。是函数依赖的完备集。l一般情况下，一般情况下，F F+l5属性闭包属性闭包 8.4 函数依赖理论函数依赖理论l F+往往是一个十分庞大的集合，求往往是一个十分庞大的集合，求F+是一是一个个NP问题，虽然推理规则给出了求法，但问题，虽然推理规则

22、给出了求法，但直接由直接由F推出推出F+，有时是不现实的，也无，有时是不现实的，也无必要。为此引入属性闭包的概念。必要。为此引入属性闭包的概念。l定义：定义： 设设 X U ，则属性集，则属性集X关于函数依关于函数依赖集赖集F的属性闭包为的属性闭包为l X+F =AAU且且XA能由能由F 根据根据推理规则推出推理规则推出8.4 函数依赖理论函数依赖理论l说明：闭包是一个属性集合，由定义知说明：闭包是一个属性集合，由定义知lX X+F成立，成立， X+F最大等于最大等于U，是有限，是有限的。的。l由自反律知由自反律知X X+F 。l闭包的意义在于把判断闭包的意义在于把判断XY是否属于是否属于F+

23、，转化为判断，转化为判断Y是否属于是否属于X+F ， F+不不易求，易求， X+F不难求。不难求。 8.4 函数依赖理论函数依赖理论l例例: 设设R=(A，B，C)，F=AB，BC，求，求A+F，B+F，AB+F。l 解：由自反律，解：由自反律，AA，已知，已知AB，由，由传递律，传递律，AC，则，则A+F=A,B,Cl 由自反律，由自反律，BB，已知，已知BC，则，则lB+F =B,Cl由自反律，由自反律，ABAB，ABB，已知，已知BC，由传递律，由传递律ABC，则，则l AB+F=A,B,C 8.4 函数依赖理论函数依赖理论l对于对于A+F =A,B,C，可知，可知，lAA，AB，AC，

24、AAB，AAC，ABC， AABC都属于都属于F+。l例例: 设有设有R(A,B,C)，函数依赖集，函数依赖集F=AB，BC，l求证求证ACB F+l证：证：AC+F =A,B,C，因此，因此 ACB+F。 8.4 函数依赖理论函数依赖理论l 6属性闭包的求解算法属性闭包的求解算法l算法：计算属性集算法：计算属性集X关于关于F的属性闭包的属性闭包X+Fl 输入：属性集输入：属性集X，函数依赖集，函数依赖集Fl 输出：输出：X+Fl方法：按下列方法计算属性集序列方法：按下列方法计算属性集序列X(0),X(1),X(i),l (1) 初始化初始化 X(0)=X;i=0。l (2) 求属性集求属性集

25、lB=A( V)( W)(V X(i)VWFAW)l 8.4 函数依赖理论函数依赖理论l(3) X(i+1)=BX(i),l(4) 判断判断X(i+1)=U或或X(i+1)=X(i)，若成立，若成立，X+F=X(i+1)结束；否则结束；否则i=i+1,转转(2)。l算法关键是第算法关键是第(2)步，考察步，考察X(i)的每个子集的每个子集V作为决定因素，看看是否有函数依赖存作为决定因素，看看是否有函数依赖存在于在于F中，若存在，则依赖属性纳入中，若存在，则依赖属性纳入X(i+1)中。中。l例：例： 设设 R=（A，B，C，D，E，G）lF=ABC,DEG,CA,BEC,BCD,CGBD,ACD

26、B,CEAG 8.4 函数依赖理论函数依赖理论l求求BD+Fl解：令解：令X(0)=BDl考察考察X(0)的所有子集的所有子集BD,B,D，有，有DEG,将将EG纳入纳入X(1)，得，得X(1)= BDEGl考察考察X(1)的所有子集，有的所有子集，有DEF,BEC，得：，得：X(2)=BCDEGl考察考察X(2)子集的依赖：子集的依赖：DEG，CA，BEC，BCD，CGBD，CEAG，得：，得：X(3)=ABCDEG=U，结束。，结束。lBD+F =ABCDEG 8.4 函数依赖理论函数依赖理论l7候选码的求法候选码的求法l 一个属性集函数决定一个属性集函数决定U，若它的任一个，若它的任一个

27、子集都不能函数决定子集都不能函数决定U，则属性集可作为，则属性集可作为候选码。候选码。l 例例 ：设：设 R=（A，B，C，D，E，G）lF=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG,l求证求证BD是一个候选码。是一个候选码。 8.4 函数依赖理论函数依赖理论l解：解：BD+F =ABCDEGlB+F = B，D+F=DEGl因此因此BD是关系模式的候选码。是关系模式的候选码。l 注意：候选码从箭头左边的属性中找。仅注意：候选码从箭头左边的属性中找。仅在箭头左边的属性一定在候选码中。在箭头左边的属性一定在候选码中。l例，设例，设 R=（A，B，C，D，E，G）lF=A

28、B,CG,EA,CED,l求所有候选码。求所有候选码。 8.4 函数依赖理论函数依赖理论l解解 ： 从从A、C、E中找，检查中找，检查A、C、E、AC、AE、CE、ACElCE+F=CEDABlCE为码为码l8 函数依赖集的等价函数依赖集的等价l 定义定义 设设R=(U)的两个函数依赖集的两个函数依赖集F和和G，如果如果F+=G+，则称，则称F和和G是等价的，如果是等价的，如果F和和G是等价的，则称是等价的，则称F覆盖覆盖G且且G覆盖覆盖F。8.4 函数依赖理论函数依赖理论l F和和G是否等价的方法：是否等价的方法：l检查检查F中的每个函数依赖中的每个函数依赖XY，检查，检查Y是是否属于否属于

29、X+G。l检查检查G中的每个函数依赖中的每个函数依赖XY，检查，检查Y是是否属于否属于X+F。l 例例 设设 R=(A,B,C,D,E,H)l F=ABE，ACH，ADB，BC，CDl G=ADBEH,BC,CD 8.4 函数依赖理论函数依赖理论l判定判定F是否等价是否等价G。l 解：对解：对F中的依赖中的依赖l AB+G=ABCDEH, 则则EAB+G， AC+G=ACDBEH, 则则HAC+Gl AD+G=ADBEHC, 则则BAD+G， B+G=BCD, 则则CB+Gl C+G=CD, 则则DC+Gl对对G中的依赖。中的依赖。l AD+F=ADBCHE, 则则 BCH AD+F， B+F

30、=BCD, 则则CB+F8.4 函数依赖理论函数依赖理论l C+F=CD, 则则DC+Fl因此，因此，F与与G等价。等价。l l9正则覆盖（极小函数依赖集）正则覆盖（极小函数依赖集）l 定义定义 FC满足下列条件称为正则覆盖：满足下列条件称为正则覆盖：l (1) FC中每个函数依赖的右部为单一属性；中每个函数依赖的右部为单一属性；l (2) FC中不存在函数依赖中不存在函数依赖XA，使得，使得FC -XA与与FC等价；等价；8.4 函数依赖理论函数依赖理论l(3) 在在FC中不存在中不存在XA，使得，使得FC -XAZA与与FC等价，其中等价，其中XZ。l特点：每个函数依赖的右端是一个属性；特

31、点：每个函数依赖的右端是一个属性；l函数依赖集没有多余的依赖；函数依赖集没有多余的依赖；l每个函数依赖左端决定因素没有多余属性。每个函数依赖左端决定因素没有多余属性。l “极小化处理极小化处理”：l (1) 根据分解规则，把函数依赖右端变成根据分解规则，把函数依赖右端变成单属性，得单属性，得F1。8.4 函数依赖理论函数依赖理论l (2) 对对F1中各依赖中各依赖XA，令，令G=F1-XA，若若AX+G ，将，将XA从从F1中去掉，得中去掉，得F2。l (3) 对对F2中左端是多属性的函数依赖中左端是多属性的函数依赖XA, 设设X=B1,B2,Bm，l若若A(X-Bi)+F2 ，则将，则将Bi

32、从从X中去掉。得中去掉。得F3为正则覆盖为正则覆盖FC 。l此处只需判断此处只需判断A(X-Bi) )+F2 ？8.4 函数依赖理论函数依赖理论l例例 求求F=ABC,BD,CE,ECB,ACB的的正则覆盖。正则覆盖。l 解：解：(1) F1=ABC,BD,CE,ECB,ACBl(2) 先判先判ABC是否多余是否多余,求下边两个依赖求下边两个依赖集的等价性集的等价性lF1=ABC,BD,CE,ECB,ACBlF1= F1-ABC = BD,CE,ECB,ACB8.4 函数依赖理论函数依赖理论lAB+F1 -ABC = ABD, C不在不在A,B,D中，中，两个依赖集不等价，所以保留两个依赖集不

33、等价，所以保留ABCl同理，同理，B+F1 -BD =B, D不在不在B，保，保留留BD l C+F1- CE =C, E不在不在C，保留，保留CE l EC+F1- ECB = EC, BC不在不在E,C，保留，保留ECB 8.4 函数依赖理论函数依赖理论l AC+F1-ACB = ACEBD, BA,B,C,D,E，取掉取掉ACB，则，则lF2=ABC,BD,CE,ECBl (3) (AB-A) +F2 = B +F2 =BD, l C不在不在B,D ，保留，保留AB中的中的A l (AB-B) +F2 = A +F2 = A, l C不在不在A，保留，保留AB中的中的Bl (EC-E)

34、+F2 = C +F2 = CEB,l BC,E,B 取掉取掉EC中的中的E 8.4 函数依赖理论函数依赖理论l则则F3=ABC,BD,CE,CBl得得FC = F3 = ABC,BD,CE,CB。l给定给定F后，后，FC不一定是唯一的，检查顺序不一定是唯一的，检查顺序不一样，可能导致不同的结果。不一样，可能导致不同的结果。l例：例： F=AB,BA,BC,AC,CA，l按从前到后顺序判断多余的以来，可以求按从前到后顺序判断多余的以来，可以求出出 ：l FC =AB,BC,CA 8.4 函数依赖理论函数依赖理论l若从第三个依赖开始判断，可以求出：若从第三个依赖开始判断，可以求出：l FC =A

35、B,BA,AC,CAl 求正则覆盖的目的是进行模式分解。求正则覆盖的目的是进行模式分解。 l 10 第三范式（第三范式（3NF）l定义定义 l关系模式关系模式R=(U)的每个非主属性都不部分的每个非主属性都不部分依赖也不传递依赖于码，则称依赖也不传递依赖于码，则称R满足第三满足第三范式，记为范式，记为R3NF。8.4 函数依赖理论函数依赖理论lR=(U) 3NF的条件是：的条件是：F+ 的每个的每个属属于三种情况之一：于三种情况之一： l（1）是平凡依赖；是平凡依赖；l（2）是超码，决定因素是超码的依赖允是超码，决定因素是超码的依赖允许存在。许存在。l（3）-中的每个属性中的每个属性A都包含在

36、都包含在R的一的一个候选码中，个候选码中， 8.4 函数依赖理论函数依赖理论l解释：对于（解释：对于（1），是自然的，但没有实），是自然的，但没有实际意义际意义l 对于（对于（2），当），当是超码时，主属性、非是超码时，主属性、非主属性都可以直接依赖主属性都可以直接依赖 ，由传递律意味，由传递律意味着主属性、非主属性都可以直接依赖于候着主属性、非主属性都可以直接依赖于候选码。选码。l 对于（对于（3），当），当不是超码时，不是超码时，的依的依赖因素是三部分，赖因素是三部分，8.4 函数依赖理论函数依赖理论l第一部分是第一部分是（-）（）（独有的），是独有的），是平凡依赖，由（平凡依赖，由（1）

37、是允许。）是允许。l第二部分是第二部分是（）（共有部分），）（共有部分），是平凡依赖，由（是平凡依赖，由（1）是允许的；）是允许的；l第三部分第三部分（-）（）（独有的）只允许独有的）只允许是主属性，意味着主属性可以依赖于码或是主属性，意味着主属性可以依赖于码或非码。非码。8.4 函数依赖理论函数依赖理论l如果有非主属性部分依赖于候选码，则必如果有非主属性部分依赖于候选码，则必依赖于候选码的一部分，该部分不是码，依赖于候选码的一部分，该部分不是码，因此（因此（3）不满足；）不满足；l当非主属性传递依赖于候选码，则必有依当非主属性传递依赖于候选码，则必有依赖于中间的属性（组），该属性（组）不赖于

38、中间的属性（组），该属性（组）不是码，因此（是码，因此（3）不满足。）不满足。l3NF的判断的判断l (1) 确定确定R的候选码，主属性，非主属性，的候选码，主属性，非主属性，决定因素。决定因素。 8.4 函数依赖理论函数依赖理论l(2) 如果如果R的每个属性都是基本数据项，则的每个属性都是基本数据项，则R1NF。l(3) 如果如果R1NF,检查所有非主属性是否对检查所有非主属性是否对所有候选码都不存在部分函数依赖。若是，所有候选码都不存在部分函数依赖。若是，R2NF。当候选码都是单一属性时，。当候选码都是单一属性时，R必必然属于然属于2NF。l(4) 如果如果R2NF，检查所有非主属性是否，

39、检查所有非主属性是否对所有候选码都不存在传递函数依赖，若对所有候选码都不存在传递函数依赖，若是，是，R3NF。当。当R没有非主属性时，没有非主属性时，R必必属于属于3NF。8.4 函数依赖理论函数依赖理论l步骤的关键是确定候选码。步骤的关键是确定候选码。 l例 ：设 R = (A,B,C,D,E)，F=ABCE,EAB,CD，问R是否属于3NF。l 解：求码，单一属性中，E+F =EABCD ，E为码，其它单属性不是。l两个属性中， AB+F=ABCED， 因为A不是码，B不是码，所以AB是码。l主属性为A，B，E，非主属性为C，D。8.4 函数依赖理论函数依赖理论l不存在非主属性对候选码的部

40、分函数依赖，因此R2NF。存在D对AB码的传递函数依赖，R不属于3NF。l例：R = (S，C，Z)，其中S：街道名，C：城市名，Z：邮编。语义说明：lZ与S是m n联系，一个邮编对应几条街道，而同是“中山”路，上海的和青岛的对应不同的邮编；S与C也是m n的联系；Z与C是n 1的联系；(S，C) 与Z是n 1的联系。得出R的函数依赖如下：8.4 函数依赖理论函数依赖理论lF=SCZ, ZCl（2）求码、主属性、非主属性：）求码、主属性、非主属性：lSC+F = SCZ， SZ+F = SZC，候选码为，候选码为(S，C)，（，（S，Z）主属性为）主属性为S、C、Z，无，无非主属性。非主属性。

41、l （3）三个属性是基本数据项，所以）三个属性是基本数据项，所以R1NF。l （4）无非主属性，所以）无非主属性，所以R2NF且且R3NF 8.4 函数依赖理论函数依赖理论l3NF是理想的，基本上消除了异常现象，是理想的，基本上消除了异常现象，通常工程实施中，一般要求是达到通常工程实施中，一般要求是达到3NF。l11. BCNF 范式范式 l一、引例一、引例l关系模式STC=(S，T，C)。S：学生名；T：教师名，C：课程名。l语义说明：教师任一门课，每门课若干教师上，学生的一门课固定一个教师。lF=SCT，STC，TC8.4 函数依赖理论函数依赖理论l候选码：候选码：SC, ST，没有非主属

42、性，没有非主属性，STC属属于于3NF。l但仍存在异常现象：但仍存在异常现象：l (1) 冗余度大：虽然一个教师只教一门课，冗余度大：虽然一个教师只教一门课，但要随选修学生的人数多次出现。但要随选修学生的人数多次出现。l (2) 插入异常：新生尚未选修课程，因主插入异常：新生尚未选修课程，因主属性不能为空，所以该生不能存入库。属性不能为空，所以该生不能存入库。l (3) 删除异常：选修某门课的学生毕业，删除异常：选修某门课的学生毕业，删除同时，相应教师开课信息也被删掉。删除同时，相应教师开课信息也被删掉。8.4 函数依赖理论函数依赖理论l(4) 更新异常：某教师开设课的课程名变更新异常：某教师

43、开设课的课程名变换后，所有选该课的元组都要改变。换后，所有选该课的元组都要改变。l定义定义l 如果关系模式如果关系模式R=(U)的所有非平凡函数依的所有非平凡函数依赖赖， 部分都包含部分都包含R的一个候选码，的一个候选码，则称则称R属于属于BC范式，记作范式，记作RBCNF。 8.4 函数依赖理论函数依赖理论l说明：说明：l(1）是平凡依赖时是允许的；是平凡依赖时是允许的；l(2) 是超码，决定因素是超码的依赖允是超码，决定因素是超码的依赖允许存在。决定因素不是超码不允许许存在。决定因素不是超码不允许l(3) 3NF与与BCNF的差别：的差别：3NF 要消除的要消除的是非主属性对码的部分依赖和

44、传递依赖，是非主属性对码的部分依赖和传递依赖，而而BCNF要消除的是主属性对码的部分依要消除的是主属性对码的部分依赖或传递依赖。如果赖或传递依赖。如果R3NF，检查所有，检查所有决定因素是否都包含候选码，若是，决定因素是否都包含候选码，若是，RBCNFG 8.4 函数依赖理论函数依赖理论l(4) 如果一个关系模式属于如果一个关系模式属于BCNF，在函，在函数依赖范畴内，已实现了模式的彻底分解，数依赖范畴内，已实现了模式的彻底分解，达到了最高的规范化程度。达到了最高的规范化程度。l 例例 STC中，决定因素中，决定因素T不包含候选码，不包含候选码，所以所以STC不属于不属于BCNF。分解成。分解

45、成l=R1=（T，C），），R2=（S，T） l例：例：SCP=(S，C，P),S：学生，：学生，C：课程，：课程，P：考试名次。：考试名次。8.4 函数依赖理论函数依赖理论l语义说明：每个学生每门课程都有一个确定的名次，每门课程的名次只有一个学生。l由语义得以下函数依赖l F=SCP， CPSl候选码为SC和CP，主属性为S，C，P，因此SCP3NF，决定因素都是码，SCPBCNF8.5 分解算法分解算法l模式分解的基本概念模式分解的基本概念l定义定义l设有关系模式设有关系模式R=(U)，若用一关系模式，若用一关系模式集合集合=R1=(U1),R2=(U2),Rk=(Uk)来取来取代代R ，

46、其中，其中U=U1U2Uk且没有且没有UiUj（1i,jk） ，则称关系模式集合，则称关系模式集合为为R的一个分解，的一个分解， 8.5 分解算法分解算法l分解特点分解特点l关系模式分解是规范化过程关系模式分解是规范化过程 l是投影分解。是投影分解。l分解不是唯一。分解不是唯一。l例如，设有关系模式例如，设有关系模式W =(工号，工种，定工号，工种，定额额)，lF=工号工号工种，工种工种，工种定额定额，l候选码为工号，候选码为工号，W2NF。8.5 分解算法分解算法l现在将现在将W进行规范化处理。有如下：进行规范化处理。有如下： l （1）W1(工号，工种工号，工种) 工号工号工种工种l W2

47、(工种，定额工种，定额) 工种工种定额定额l （2）W1(工号，工种工号，工种) 工号工号工种工种l W2(工号，定额工号，定额) 工号工号定额定额l （3）W1(工号，定额工号，定额) 工号工号定额定额l W2(工种，定额工种，定额) 工种工种定额定额 8.5 分解算法分解算法l显然分解的效果并不一样，直观地看：显然分解的效果并不一样，直观地看：l第三种方案：若两个工种的定额一样，就第三种方案：若两个工种的定额一样，就无法确定一个工号的工种。丢失信息无法确定一个工号的工种。丢失信息l第二种方案：如果一个工人改变了工种，第二种方案：如果一个工人改变了工种，W1，W2都要修改，不独立。都要修改，

48、不独立。l第一种方案：理想。第一种方案：理想。 8.5 分解算法分解算法l 分解的准则分解的准则l (1) 分解具有分解具有“无损连接性无损连接性”l (2) 分解要分解要“保持函数依赖保持函数依赖”l (3) 分解既分解既“保持函数依赖保持函数依赖”，又具有，又具有“无损连接性无损连接性”。l无损连接分解的判断无损连接分解的判断l 1.定义定义 设设=R1=（U1）,R2=（U2）,Rk=（Uk）是是R的一分解，如的一分解，如果对于果对于R的任一个关系的任一个关系r满足满足 8.5 分解算法分解算法lr=U1(r) U2(r) Uk(r)l则称则称是无损连接分解或简称无损分解。是无损连接分解

49、或简称无损分解。l事实：关系分解后的投影做自然连接，事实：关系分解后的投影做自然连接，有可能多出许多元组。有可能多出许多元组。l例如例如 R=(A,B,C)，l分解为分解为l = R1=(A，B)，R2=(B，C) 8.5 分解算法分解算法l r rr1r1r2r2r1r1r2r2A AB BC CA AB BB BC CA AB BC Ca1a1b1b1c1c1a1a1b1b1b1b1c1c1a1a1b1b1c1c1a2a2b1b1c2c2a2a2b1b1b1b1c2c2a1a1b1b1c2c2a1a1b1b1c2c2a2b1b1c1c1a2b1b1c2c28.5 分解算法分解算法R(A,

50、B, C)R(A, B, C)122211CBA2211BA1221CB122211CBAAB(R)BC(R)AB(R)BC(R)R(A, B, C)212111CBA1211BA2111CB211112212111CBAAB(R)BC(R)AB(R)BC(R)有损分解有损分解无损分解无损分解8.5 分解算法分解算法l判断算法判断算法l算法算法: 判别一个分解是否是无损分解判别一个分解是否是无损分解l输入：输入：l关系模式关系模式R=(A1，A2，An)lR上的函数依赖集上的函数依赖集F；lR上的分解上的分解=R1=（U1）,R2=（U2）,Rk=（Uk）l输出：输出：是否无损分解。是否无损分

51、解。8.5 分解算法分解算法l方法：方法：(1) 构造构造n列（属性），列（属性），k行（子模行（子模式）的矩阵式）的矩阵Ml aj 若若AjUi，列下标，列下标l Mi,j=l bij 若若AjUil(2) 逐个检查逐个检查F中函数依赖中函数依赖XY,修改表中修改表中的元素。过程如下：按的元素。过程如下：按X列值相等确定各列值相等确定各行，修改行，修改Y列对应行的值；如果基中之一列对应行的值；如果基中之一为为aj，则全改为，则全改为aj，否则全改为，否则全改为bmj，m为为这些行中的最小行号。这些行中的最小行号。8.5 分解算法分解算法l(3) 对对F的每个函数依赖按的每个函数依赖按(2)处

52、理一遍后，处理一遍后，若有某一行为若有某一行为a1,a2,an则判定分解是无则判定分解是无损分解。算法终止。否则按损分解。算法终止。否则按(2)的过程再来的过程再来一遍，直到一行为一遍，直到一行为a1,a2,an，判定为无，判定为无损分解，或者损分解，或者M矩阵没有变化，判定为不矩阵没有变化，判定为不是无损连接。是无损连接。l例例 R=(A，B，C，D，E)l=R1=(A,D),R2=(A,B),R3=(B,E),R4=(C,D,E),R5=(A,E),lF=AC,BC,CD,DEC,CEA 8.5 分解算法分解算法l解：解：(1) 构造初始矩阵构造初始矩阵M A AB BC CD DE ER

53、1R1a1a1b12b12b13b13a4a4b15b15R2R2a1a1a2a2b23b23b24b24b25b25R3R3b31b31a2a2b33b33b34b34a5a5R4R4b41b41b42b42a3a3a4a4a5a5R5R5a1a1b52b52b53b53b54b54a5a58.5 分解算法分解算法l (2) 检查检查F的函数依赖，并修改的函数依赖，并修改Ml对于对于AC，A列确定同值的行列确定同值的行1，行，行2，行，行5(为为a1)，修改，修改C列的行列的行1，行，行2，行，行5的值的值为为b13 (没有没有a3， b13的行号最小的行号最小) l (3) 同样，对于同样

54、，对于BC，修改，修改M l 对于对于CD，修改，修改Ml 对于对于DEC，修改，修改Ml 对于对于CEA，修改，修改M 8.5 分解算法分解算法l(3) M的行的行3变为变为a1,a2,a3,a4,a5算法终止，算法终止，是无损分解。是无损分解。 l分解为两个子模式的无损连接判断算法分解为两个子模式的无损连接判断算法l定理定理 设设=R1=(U1),R2=(U2)，则，则为无为无损分解的充要条件为损分解的充要条件为 l(U1U2)(U1-U2)F+ 或或l(U1U2)(U2-U1)F +8.5 分解算法分解算法l证：构造初始矩阵证：构造初始矩阵Ml U1U2 U1-U2 U2-U1lR1 a

55、aaaa aaaaa bbbbblR2 aaaaa bbbbb aaaaa lU1U2属性是属性是R1、R2共有的属性，全填共有的属性，全填a（下标省去）；（下标省去）；lU1-U2属性是属性是R1独有的，全填独有的，全填a，是，是R2没有没有的，全填的，全填blU2-U1属性是属性是R1没有的，全填没有的，全填b，是，是R2独有独有的，全填的，全填a8.5 分解算法分解算法l例例 R=(A，B，C)，F=AB,CB,l1=R1=(A,B),R2=(B,C), 2=R1=(A,C),R2=(B,C),l判定判定1, 2是否无损分解是否无损分解l 解解: 对于对于1，U1=AB，U2=BC，U1

56、U2=B，U1-U2=A ，U2-U1=Cl 对于对于BA, BC, B+F=B, BA不不属于属于F+，BC不属于不属于F +l因此因此1不是无损分解。不是无损分解。 8.5 分解算法分解算法l对于对于2，lU1U2=C，U1-U2=A，U2-U1=Bl对于对于CB，C + F=CB，所以，所以CBF +l因此因此2是无损分解。是无损分解。 8.5 分解算法分解算法l保持函数依赖分解的判断保持函数依赖分解的判断l定义定义 F在子模式在子模式Ri=（Ui）上的投影为：）上的投影为：l Ri (F)=XYXYF+XY属于属于Uil注意：从注意：从F +中找。中找。l例例 R(A，B，C)，F=A

57、B，BCl=R1=（A,B）,R2=（A,C）,R3=（B,C） ,则则:lR1(F)=AB, R2(F)=AC, R3(F)=BC。 8.5 分解算法分解算法l定义 设是R的一个分解，F是R的函数依赖集，如果l G= R1(F)R2(F) Rk(F)l逻辑蕴涵F，则称是保持函数依赖分解，或简称保持依赖。l 注意：只检查G 是否包含了F，不检查F是否包含G，意义在于分解后，F中的依赖是否还存在。 8.5 分解算法分解算法l不保持函数依赖的分解也不是一个好的分解，因为F中的函数依赖可以看成R的属性完整性约束，若分解破坏了这种约束，就是破坏了属性之间的联系。l 例 R=(A，B，C)，l F=AB

58、,CB,l =R1=(A,B),R2=(A,C)，l判定是否保持依赖。 8.5 分解算法分解算法l解解 U1(F)=AB,U2(F)=，U1(F)U2(F)=AB没能逻辑蕴涵没能逻辑蕴涵F,所所以以不是保持依赖的分解。不是保持依赖的分解。 8.5 分解算法分解算法l 保持依赖分解的判断算法保持依赖分解的判断算法l 输入：分解输入：分解=R1,R2,Rk和和F。l 输出：输出：是否保持是否保持F。l 方法：令方法：令G=R1(F) R2(F) . Rk(F) l对对F中的每一函数依赖中的每一函数依赖XY，检查，检查Y是否是否包含在包含在X+G中，中， 若都满足，若都满足，是保持依赖是保持依赖的分

59、解。的分解。8.5 分解算法分解算法l例例 R=(A,B,C,D),lF=AB,BC,CD,DA，l试判断分解试判断分解=R1=(A,B),R2=(B,C),R3=(C,D)是否保是否保持依赖。持依赖。l 解：解：R1(F)=AB，BA,l R2(F)=BC， CB， R3(F)=CD，DC , 8.5 分解算法分解算法lG=R1(F)R2(F)R3(F)l=AB, BA ，BC, CB ，CD，DC ,l 可知，可知，F中的每个依赖都存在与中的每个依赖都存在与G中，中， 是保持依赖的分解。是保持依赖的分解。l例如，例如，W =(工号，工种，定额工号，工种，定额)，l F=工号工号工种，工种工

60、种，工种定额定额， 8.5 分解算法分解算法l（1）1 =W1=(工号，工种工号，工种)，l W2=(工种，定额工种，定额) l（2）2 =W1=(工号，工种工号，工种)，l W2=(工号，定额工号，定额) l（3）3 =W1=(工号，定额工号，定额)，l W2=(工种，定额工种，定额) l无损连接判断：无损连接判断： 8.5 分解算法分解算法l1：工种：工种工号，工种工号，工种定额，有一个成定额，有一个成立，是。立，是。 l2：工号：工号工种，工号工种，工号定额，有一个成定额，有一个成立，是。立，是。l3：定额：定额工号，定额工号，定额工种，都不成立，工种，都不成立，不是。不是。 l保持依赖