《数据库原理与应用教程NO.ppt》由会员分享，可在线阅读，更多相关《数据库原理与应用教程NO.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 关系模式的分解关系模式的分解*4.3.1 模式分解问题模式分解问题定义定义4.11 设有关系模式设有关系模式R(U)，属性集为，属性集为U，R1、Rk都是都是U的子集，并且有的子集，并且有R1R2RkU。关系模式关系模式R1、Rk的集合用的集合用表示，表示，=R1，Rk。用用代替代替R的过程称为关系模式的分解。这里的过程称为关系模式的分解。这里称为称为R的一个分解，也称为数据库模式。的一个分解，也称为数据库模式。泛关系模式泛关系模式Rr泛关系泛关系数据库模式数据库模式=R1，Rk=r1，rk数据库实例数据库实例(数据库数据库)这里就有两个问题：这里就有两个问题：和和r r是否等价是否等
2、价?用用“无损分解无损分解”表示。表示。FF1 1,F,Fk k 与与F F是否等价是否等价?用用“保持依赖保持依赖”表示。表示。计算机中的数据并不是存储在泛关系计算机中的数据并不是存储在泛关系r r中，而是存储在数据库中，而是存储在数据库中。中。R上有函数依赖集上有函数依赖集F，每一个每一个Ri 上有一个上有一个函数依赖集函数依赖集 Fi，F1，Fk4.3.2 无损连接分解无损连接分解 定义定义4.12：设：设R是一个关系模式，是一个关系模式，F是是R上的一上的一个个FD集。集。R分解成数据库模式分解成数据库模式=R1，Rk。如果对如果对R中满足中满足F的每一个关系的每一个关系r，都有，都有
3、r=R1（r）R2（r）Rk（r）那么称分解那么称分解相对于相对于F是是“无损连接分解无损连接分解”（lossless join decomposition），简称），简称为为“无损分解无损分解”，否则称为，否则称为“损失分解损失分解”（lossy decomposition）。）。例例4.10（1）未丢失信息的分解：未丢失信息的分解：r r1 1 r r2 2=r=r （2）丢失信息的分解丢失信息的分解：r r1 1r r2 2rr211211111111CAr2BAr1CBAr32142131131213214114111411CBAr r1 1 r r2 2CAr2BAr1CBAr多出来
4、的元组称为多出来的元组称为寄生元组（额外元组）寄生元组（额外元组）丢失的元组称为丢失的元组称为悬挂元组悬挂元组。在泛关系模式在泛关系模式R R分解成数据库模式分解成数据库模式=R1，Rk时时，泛泛关关系系r r在在的的每每一一模模式式Ri（1in）上上投投影影后后再再连连接接起起来来，比比原原来来r中中多多出出来来的的元元组组，称称为为“寄寄生生元元组组”（SpuriousTuple）。）。实际上，寄生元组表示着错误的信息。寄生元实际上，寄生元组表示着错误的信息。寄生元组也就是节模式设计准则组也就是节模式设计准则4 4中提到的额外元组中提到的额外元组(在上节在上节NO15NO15中）中）。无损
5、的无损的损损指的是指的是信息丢失信息丢失而不是而不是元组丢失元组丢失.如果一个分解不具有如果一个分解不具有无损无损的性质，那么泛的性质，那么泛关系在投影连接后就可能产生寄生元组。寄生关系在投影连接后就可能产生寄生元组。寄生元组表示着错误的信息元组表示着错误的信息r的投影连接表达式的投影连接表达式R1（r）Rk（r）用）用符号符号m（r）表示，即）表示，即m（r）=Ri（r）。）。设设=R1，Rk 是是关关系系模模式式R的的一一个个分分解解，r是是R的任一关系，的任一关系，ri=Ri（r）（）（1ik），），那么有下列性质：那么有下列性质：r m(r)；若若s=m(r)，则，则Ri(s)=ri；
6、m(m(r)=m(r)，这个性质称为幂等性，这个性质称为幂等性（idempotent）。）。r r=m m(r)(r)时就是无损连接分解时就是无损连接分解4.3.3 无损分解的测试算法（算法无损分解的测试算法（算法4.3）构造一张构造一张k行行n列的表格，每列对应一个属性列的表格，每列对应一个属性Aj，每行，每行对应一个模式对应一个模式Ri。如果。如果Aj在在Ri中，那么在表格的第中，那么在表格的第i行行第第j列处填上符号列处填上符号aj，否则填上，否则填上bij。把表格看成模式把表格看成模式R的一个关系，反复检查的一个关系，反复检查F中每个中每个FD在在表格中是否成立，若不成立，则修改表格中
7、的值。表格中是否成立，若不成立，则修改表格中的值。修改方法如下：对函数依赖修改方法如下：对函数依赖XY,找找X相等的行，相等的行，改改Y的分量值：如果的分量值：如果Y值中有一个是值中有一个是aj，那么另一个也，那么另一个也改成改成aj；如果没有；如果没有aj，那么用其中一个，那么用其中一个bij替换另一个替换另一个值（尽量把下标值（尽量把下标ij改成较小的数）。一直到表格不能修改成较小的数）。一直到表格不能修改为止。（这个过程称为改为止。（这个过程称为追踪追踪chase过程）过程）若修改的最后一张表格中有一行是全若修改的最后一张表格中有一行是全a，即，即a1a2an，那么称，那么称相对于相对于
8、F是无损分解，否则称损失分解。是无损分解，否则称损失分解。例例4.11 4.11 设关系模式设关系模式R(ABCD)R(ABCD)，R R分解成分解成=AB,BC,CD=AB,BC,CD。如果如果R R上成立的函数依赖集上成立的函数依赖集F F1 1=BABA，CDCD，那么那么相对于相对于F F1 1是否无损分解？是否无损分解？(无损分解无损分解)a a4 4 a a3 3b b3232b b3131CDa a4 4 a a3 3b b3232b b3131CDa a4 4 a a3 3a a2 2a a1 1BCb b2424 a a3 3a a2 2b b2121BCb b1414 b
9、b1313a a2 2a a1 1ABb b1414 b b1313a a2 2a a1 1ABDCBADCBA续例续例4.11 4.11 设关系模式设关系模式R(ABCD)R(ABCD)，R R分解成分解成=AB,BC,CD=AB,BC,CD。如果如果R R上成立的函数依赖集上成立的函数依赖集F F1 1=ABAB，CDCD，那么那么相对于相对于F F1 1是否无损分解？是否无损分解？(损失分解损失分解)a a4 4 a a3 3b b3232b b3131CDa a4 4 a a3 3b b3232b b3131CDa a4 4 a a3 3a a2 2b b2121BCb b2424 a
10、 a3 3a a2 2b b2121BCb b1414 b b1313a a2 2a a1 1ABb b1414 b b1313a a2 2a a1 1ABDCBADCBA再看例再看例4-124-12（P153)P153)A B C D E例：设例：设R=(ABCDE)分解成分解成 AD,AB,BE,CDE,AE 函数依赖函数依赖F=AC，BC，CD，DEC，CEA 判断是否无损连接分解。判断是否无损连接分解。解：按条件给出初始表解：按条件给出初始表 a1 b12 b13 a4 b15 a1 b12 b13 a4 b15AD a1 a2 b23 b24 b25 a1 a2 b23 b24 b2
11、5 b31 a2 b33 b34 a5 b31 a2 b33 b34 a5 b41 b42 a3 a4 a5 b41 b42 a3 a4 a5 a1 b52 b53 b54 a5 a1 b52 b53 b54 a5ABBECDEAEA B C D E a1 b12 b13 a4 b15 a1 b12 b13 a4 b15AD a1 a2 b13 a4 b25 a1 a2 b13 a4 b25 a1 a2 a3 a4 a5 a1 a2 a3 a4 a5 a1 b42 a3 a4 a5 a1 b42 a3 a4 a5 a1 b52 a3 a4 a5 a1 b52 a3 a4 a5ABBECDEAE
12、通过追踪过程（通过追踪过程（CHASE）最终得表：）最终得表：由于第由于第3行全为行全为a,所以该分解是无损连接分解。所以该分解是无损连接分解。定理定理4.6 设设=R1，R2 是关系模式是关系模式R的一的一个分解，个分解，F是是R上成立的上成立的FD集，那么分解集，那么分解相对相对于于F是无损分解的充分必要条件是是无损分解的充分必要条件是（R1R2）（R1R2）或（或（R1R2）（R2R1）。）。（可用（可用CHASE(CHASE(追踪追踪)算法证明）算法证明）定理定理4.7 如果如果FD XY在模式在模式R上成立，且上成立，且XY=，那么，那么R分解成分解成=RY，XY 是无损是无损分解。
13、分解。4.3.4 保持函数依赖的分解保持函数依赖的分解 定义定义4.13：设设F是属性集是属性集U上的上的FD集，集，Z是是U的的子集，子集，F在在Z上的投影用上的投影用Z（F）表示，定义）表示，定义为为 Z(F)=XY|XYF+，且，且XY Z设设=R1，Rk 是是R的一个分解，的一个分解，F是是R上上的的FD集集 如果有如果有(Ri(F)+=F+，那么称分解那么称分解保持函数依赖集保持函数依赖集F的分解。的分解。根据定义，测试一个根据定义，测试一个 分解是否保持分解是否保持FD,比较可比较可行的方法是逐步验证行的方法是逐步验证F中的每个中的每个FD是否被是否被(Ri(F)+=F+蕴涵蕴涵两
14、个数据库模式的等价问题，这种等价包括数据等价和两个数据库模式的等价问题，这种等价包括数据等价和依赖等价两个方面。依赖等价两个方面。数据等价数据等价是指两个数据库实例应表示同样的信息内容，是指两个数据库实例应表示同样的信息内容，用用“无损分解无损分解”衡量。如果是无损分解，那么对泛关衡量。如果是无损分解，那么对泛关系反复的投影和连接都不会丢失信息。系反复的投影和连接都不会丢失信息。依赖等价依赖等价是指两个数据库模式应有相同的依赖集闭包。是指两个数据库模式应有相同的依赖集闭包。在依赖集闭包相等情况下，数据的语义是不会出差错在依赖集闭包相等情况下，数据的语义是不会出差错的。的。违反数据等价或依赖等价
15、的分解不是一个好的模违反数据等价或依赖等价的分解不是一个好的模式设计。式设计。一个无损连接分解不一定是保持函数依赖的一个无损连接分解不一定是保持函数依赖的一个保持函数依赖的分解也不一定是无损连接的一个保持函数依赖的分解也不一定是无损连接的 没有必然联系（见下例）没有必然联系（见下例）例：例：设关系模式设关系模式R(ABC)，=AB,AC是是R的一个的一个分解。试分析分别在各种分解。试分析分别在各种FD的情况下，的情况下，是否具有是否具有无损分解和保持无损分解和保持FD的分解特性。的分解特性。解：解：相对于相对于F1=AB，分解，分解是无损分解，是无损分解，且保持且保持FD的分解。的分解。相对于
16、相对于F2=AC,BC，分解，分解是无损分解，是无损分解，但不保持但不保持FD集集(丢失了丢失了BC)。相对于相对于F3=BA，分解，分解是损失分解，是损失分解，但保持但保持FD集的分解。集的分解。相对于相对于F4=CB,BA，分解，分解是损失分解，是损失分解，且不保持且不保持FD集集(丢失了丢失了CB)。保持保持FD分解分解相对于相对于F=AB，ACBA=AB，ACBA=AB，ACAC=AB，ACABabaACbaaAB丢失丢失CB损损失失CBA(4)F4=CB,BAabaACbaaAB保持保持损损失失CBA(3)F3=BAabaACbaaAB丢失丢失BC无无损损CBA(2)F2=AC,BC
17、abaACbaaAB保持保持无无损损CBA(1)F1=AB4.4 关系模式的范式关系模式的范式 关系模式的好与坏，用什么标准衡量？这个标准关系模式的好与坏，用什么标准衡量？这个标准就是模式的范式（就是模式的范式（Normal Forms，简记为，简记为NF）。范式的种类与数据依赖有着直接的联系。）。范式的种类与数据依赖有着直接的联系。范式的概念由于范式的概念由于1971年提出。（发展过程见年提出。（发展过程见P155）1NF是关系模式的基础；是关系模式的基础；在数据库设计中最常用的是在数据库设计中最常用的是3NF和和BCNF。各种范式之间的关系各种范式之间的关系 4.4.1 第一范式第一范式(
18、1NF)定义定义4.14:如果关系模式如果关系模式R所有的属性均为简单属性，所有的属性均为简单属性，即每个属性都是不可再分的，则称即每个属性都是不可再分的，则称R属于第一范式，属于第一范式，简称简称1NF，记作，记作R1NF。1NF是关系模式应具备的最起码的条件。是关系模式应具备的最起码的条件。第一范式可能具有大量的数据冗余，具有插入异常、第一范式可能具有大量的数据冗余，具有插入异常、删除异常和更新异常等弊端。删除异常和更新异常等弊端。例如关系模式例如关系模式SCD属于属于1NF，它既存在完全函数依赖，它既存在完全函数依赖，又存在部分函数依赖和传递函数依赖又存在部分函数依赖和传递函数依赖。克服
19、这些弊端的方法是用投影运算将关系分解，去掉克服这些弊端的方法是用投影运算将关系分解，去掉过于复杂的函数依赖关系，向更高一级的范式进行过于复杂的函数依赖关系，向更高一级的范式进行转换。转换。4.4.2 第二范式第二范式(2NF)定义定义4.15:如果关系模式如果关系模式R是是1NF，且每个，且每个非主非主属性属性完全函数依赖于完全函数依赖于候选键，那么称候选键，那么称R是第二范是第二范式（式（2NF）的模式。）的模式。如果数据库模式中每个关系模式都是如果数据库模式中每个关系模式都是2NF，则称数据库模式为则称数据库模式为2NF的数据库模式。的数据库模式。（即（即.没有对候选键的部分函数依赖）没有
20、对候选键的部分函数依赖）从从1NF1NF中消除非主属性对主键（主码）的部中消除非主属性对主键（主码）的部分函数依赖得到分函数依赖得到2NF.2NF.分解时遵循分解时遵循“一事一地一事一地”的基本原则：的基本原则：一个关系只描述一个实体或联系。一个关系只描述一个实体或联系。属性集属性集X非主非主属性属性A键键违反违反2NF的局部依赖的情况示意图：的局部依赖的情况示意图：本章开始例：教学管理数据库（本章开始例：教学管理数据库（P137）SCD(SNo,SN,Age,Dept,MN,CNo,Score)SNo SN Age Dept MN CNo Score S1 赵亦赵亦 17 计算机计算机 刘伟
21、刘伟 C1 90S1 赵亦赵亦 17 计算机计算机 刘伟刘伟 C2 85 S2 钱尔钱尔 18 信息信息 王平王平 C557S2 钱尔钱尔 18 信息信息 王平王平 C680S2钱尔钱尔18信息信息王平王平C7 主键：主键：(SNO,CNO)，存在数据冗余、修改、删除、插，存在数据冗余、修改、删除、插入异常的弊病。原因之一是存在部分函数依赖。入异常的弊病。原因之一是存在部分函数依赖。如果把如果把SCD分解成分解成:(将部分函数依赖分离出来）将部分函数依赖分离出来）SD(SNo,SN,Age,Dept,MN)C(SNo，CNo，SCORE)SD 与与 C 都是都是2NF模式。模式。部分函数依赖消
22、失，分数关系部分函数依赖消失，分数关系C不存在冗余、不存在冗余、修改、删除、插入异常。修改、删除、插入异常。但还是有系、系主任的冗余和操作异常。说明但还是有系、系主任的冗余和操作异常。说明2NF不是理想的模式分解。不是理想的模式分解。算法算法4.5 分解成分解成2NF模式集的算法模式集的算法设关系模式设关系模式R(U)，主键是，主键是W，R上还存在上还存在FD：XZ，并且，并且Z是非主属性，是非主属性，XW，那么，那么WZ就是一个部就是一个部分函数依赖。此时应把分函数依赖。此时应把R分解成两个模式分解成两个模式R1（XZ），主键是），主键是X；（将部分依赖分解出来）；（将部分依赖分解出来）R2
23、（Y），其中），其中Y=U-Z，主键仍是，主键仍是W，外键是外键是 X(REFERENCES参照参照 R1)。利用外键和主键的连接可以从利用外键和主键的连接可以从R1和和R2重新得到重新得到R。如果如果R1和和R2还不是还不是2NF，则重复上述过程，一直到数，则重复上述过程，一直到数据库模式中每一个关系模式都是据库模式中每一个关系模式都是2NF为止。为止。定义定义4.16：如果关系模式如果关系模式R是是1NF，且每个，且每个非非主属性主属性都不都不传递函数依赖传递函数依赖于于R的候选键，那么称的候选键，那么称R属于第三范式（属于第三范式（3NF）的模式。如果数据库模）的模式。如果数据库模式中每
24、个关系模式都是式中每个关系模式都是3NF，则称其为，则称其为3NF的数的数据库模式。据库模式。4.4.3 第三范式（第三范式（3NF)例例:在上边在上边例例中，中，SD(SNo,SN,Age,Dept,MN)主键主键SNO,无部分函数依赖，是无部分函数依赖，是2NF模式。模式。SD中存在函数依赖中存在函数依赖 SNODept 和和 DeptMN，那么那么SNO MN 就是一个传递依赖，就是一个传递依赖，SD不是不是3NF模式。模式。此此时时也也会会出出现现冗冗余余和和异异常常操操作作。譬譬如如一一个个系系有有500学学生生，那么系和系主任就会重复那么系和系主任就会重复500次。还有操作异常。次
25、。还有操作异常。若将若将SD分解成分解成S（SNo,SN,Age,Dept）和和D（Dept,MN）已已无无传传递递函函数数依依赖赖，S、D都都是是3NF模模式式，冗冗余余和和操操作作异异常消失。常消失。算法算法4.6 分解成分解成3NF模式集的算法模式集的算法设关系模式设关系模式R（U），主键是），主键是W，R上还存在上还存在FD XZ。并且。并且Z是非主属性，是非主属性，Z X，X不是候选键，不是候选键，这样这样WZ就是一个传递依赖。此时应把就是一个传递依赖。此时应把R分解成两分解成两个模式：个模式：R1（XZ），主键是），主键是X；（将传递依赖分解出来）；（将传递依赖分解出来）R2（Y）
26、，其中），其中Y=U-Z，主键仍是，主键仍是W，外键是外键是 X (REFERENCES参照参照 R1)。利用外键和主键相匹配机制，利用外键和主键相匹配机制，R1和和R2通过连接可以通过连接可以重新得到重新得到R。如果如果R1和和R2还不是还不是3NF，则重复上述过程，一直到，则重复上述过程，一直到数据库模式中每一个关系模式都是数据库模式中每一个关系模式都是3NF为止。为止。由定义可看出：局部依赖必定蕴涵传递依赖的存在由定义可看出：局部依赖必定蕴涵传递依赖的存在定理定理4.84.8：如果如果R R是是3NF3NF模式，那么模式，那么R R也是也是2NF2NF模式。模式。证证明明：只只要要证证明
27、明模模式式中中部部分分依依赖赖的的存存在在蕴蕴涵涵着着传传递递依依赖赖即即可可。设设A A是是R R的的一一个个非非主主属属性性，K K是是R R的的一一个个候候选选键键，且且KAKA是一个部分依赖。那么是一个部分依赖。那么R R中必存在某个中必存在某个 K K K K，有有K KAA成成立立。由由于于A A是是非非主主属属性性，因因此此AKKAKK=。从从K K K K，可可知知 K KKK，但但KKKK成成立立。因而从因而从KKKK 和和K KAA可知可知KAKA是一个传递依赖。是一个传递依赖。部部分分依依赖赖和和传传递递依依赖赖是是模模式式产产生生冗冗余余和和异异常常的的两两个个重重要要
28、原原因因。由由于于3NF3NF模模式式中中不不存存在在非非主主属属性性对对候候选选键键的的部部分分依依赖赖和和传传递递依依赖赖，因因此此消消除除了了很很大大一一部部分分存存储储异异常常，具有较好的性能。具有较好的性能。4.4.4 BCNF(BoyceCodd NF)定定义义4.174.17：如如果果关关系系模模式式R1NF，且且所所有有的的函函数数依依赖赖XY（YX），决决定定因因素素X都都包包含含了了R的的一一个个候候选选键键，则则称称R属于属于BC范式，范式，记记作作RBCNF。(3NF不一定是不一定是BCNF)例例4-19 设有关系模式设有关系模式SNC（SNo，SN，CNo，Score
29、）假设学生无重名，假设学生无重名，SNo SN。候选键：候选键：(SNo,CNo)，（，（SN，CNo）唯一非主属性唯一非主属性Score不存在对键的部分函数依赖及传递函不存在对键的部分函数依赖及传递函数依赖，所以数依赖，所以 是是 3NF但存在着主属性对键的部分函数依赖：但存在着主属性对键的部分函数依赖：（SNo，CNo）SN，（，（SN，CNo）SNo，所以，所以SNC不是不是BCNF。定理定理:如果如果R是是BCNF模式，那么模式，那么R也是也是3NF模模式。式。证明：设证明：设R是是BCNF，但不是，但不是3NF，那么，那么R上上必存在传递依赖必存在传递依赖XY，YA，这里，这里X是是
30、R的键，的键，AY，YX。显然。显然Y不包含不包含R的键，否则的键，否则YX也成立。因此也成立。因此YA违反了违反了BCNF的定义，的定义，与假设与假设R是是BCNF矛盾。矛盾。无损分解成无损分解成BCNF模式集的算法模式集的算法（1）令）令=R。（2）如果）如果中所有模式都是中所有模式都是BCNF，则转（，则转（4）。）。（3）如果）如果中有一个关系模式中有一个关系模式S不是不是BCNF，则，则S中必能找到一个函数依赖中必能找到一个函数依赖XA且且X不是不是S的的候选键，且候选键，且A不属于不属于X，设，设S1=XA，S2=S-A，用分解用分解S1，S2代替代替S，转（，转（2）。）。（4）
31、分解结束，输出）分解结束，输出。这个算法是从泛关系模式这个算法是从泛关系模式R出发，去寻找一个满足条出发，去寻找一个满足条件的件的BCNF模式集，因此称为模式集，因此称为“分解算法分解算法”。这个算法能保证把这个算法能保证把 R 无损分解成无损分解成，但不一定能保证，但不一定能保证能保持能保持FD。F=SNoSN，SNSNo，(SNo，CNo)Score，(SN，CNo)Score前例：前例：关系模式关系模式SNC（SNo，SN，CNo，Score）假设学生无重名，假设学生无重名，SNo SN。候选键：候选键：(SNo,CNo)，（，（SN，CNo）（1）令）令=SNC(SNo，SN，CNo，
32、Score)。（2）经过前面分析可知，）经过前面分析可知，中关系模式不属中关系模式不属于于BCNF。（3）考虑）考虑SNoSN，由于，由于SNo不是候选键，不是候选键，且且SN不属于不属于SNo .用分解用分解S1(SNo，SN)，S2(SNo，CNo，Score)代替代替SNC。（4）分解结果为：）分解结果为：S1(SNo，SN)描述学生描述学生实体；实体；S2(SNo，CNo，Score)描述学生与描述学生与课程的联系。课程的联系。都属于都属于BCNF.（1）如果）如果Fmin中有一函数依赖中有一函数依赖XA，且，且XA=R，则输出，则输出=R，转（，转（4）。）。（2）如果）如果R中某些
33、属性与中某些属性与Fmin中所有依赖中所有依赖的左部和右部都无关，则将它们构成关系模的左部和右部都无关，则将它们构成关系模式，从式，从R中将它们分出去，单独构成一个模中将它们分出去，单独构成一个模式。式。（3）对于）对于Fmin中的每一个函数依赖中的每一个函数依赖XA，都单独构成一个关系子模式都单独构成一个关系子模式XA。若。若Fmin中中有有XA1，XA2，XAn，则可以用，则可以用模式模式XA1A2An取代取代n个模式个模式XA1，XA2，XAn。（4）停止分解，输出）停止分解，输出。看例看例4-16：（：（P159）算法算法4.6 把一个关系模式分解为把一个关系模式分解为3NF，使它具有
34、保，使它具有保持函数依赖性。持函数依赖性。算法算法4.7 把一个关系模式分解为把一个关系模式分解为3NF，使它既具有无损，使它既具有无损连接性又具有保持函数依赖性。连接性又具有保持函数依赖性。（1）根据算法）根据算法4.6求出保持函数依赖的分解：求出保持函数依赖的分解：=R1，R2，Rk。（2）判定）判定是否具有无损连接性，若是，转（是否具有无损连接性，若是，转（4）。）。（3）令）令=X=R1，R2，Rk，X，其中，其中X是是R的候选键。的候选键。（4）输出）输出。见例见例4-17（P160）例：例：设关系模式设关系模式R(ABCDE)R(ABCDE)，R R的最小依赖集为的最小依赖集为AB
35、AB，CDCD。从依赖集可知从依赖集可知R R的候选键为的候选键为ACEACE。（。（L L、N N类计算）类计算）按按算算法法4-64-6，根根据据最最小小依依赖赖集集，保保持持函函数数依依赖赖的分解的分解 =AB,CD =AB,CD。按算法按算法4-7 4-7，再加入由候选键组成的模式，再加入由候选键组成的模式ACEACE。因因此此最最后后结结果果=AB,CD,ACE=AB,CD,ACE是是一一个个3NF3NF模模式式集集且且相相对对于于该该依依赖赖集集是是无无损损分分解解且且保保持持FDFD。关关系系模模式式R R相相对对于于函函数数依依赖赖集集F F分分解解成成数数据据库库模模式式R
36、R1 1，R Rk k，一般应具有三个特性：，一般应具有三个特性：是是BCNFBCNF模式集，或模式集，或3NF3NF模式集；模式集；无损分解，即对于无损分解，即对于R R上任何上任何满足满足F F的泛关系应满足的泛关系应满足r=mr=m(r)(r)；保持函数依赖集保持函数依赖集F F，即，即(RiRi(F)(F)F F。数据库设计者在进行关系数据库设计时，应作权衡，数据库设计者在进行关系数据库设计时，应作权衡，尽可能使数据库模式保持最好的特性。一般尽可能设尽可能使数据库模式保持最好的特性。一般尽可能设计成计成BCNFBCNF模式集。如果设计成模式集。如果设计成BCNFBCNF模式集时达不到保
37、模式集时达不到保持持FDFD的特点，那么只能降低要求，设计成的特点，那么只能降低要求，设计成3NF3NF模式集，模式集，以求达到保持以求达到保持FDFD和无损分解的特点。和无损分解的特点。一个好的模式设计方法应符合三条原则：表达性、分一个好的模式设计方法应符合三条原则：表达性、分离性和最小冗余性。离性和最小冗余性。4.4.5 多值依赖与第四范式多值依赖与第四范式 多值依赖的定义 假设学校中一门课程可由多名教师讲授，教学中他们使用相同的一套参考书。课程课程C 教师教师T 参考书参考书B 数据库原数据库原理理数据结构数据结构 吴胜吴胜利利陈陈晨晨王王平平张京张京生生 数据库原理与应数据库原理与应用
38、用数据库系统数据库系统SQL Server 2000算法与数据结构算法与数据结构数据结构教程数据结构教程 关系关系CTB CTB转化成规范化的关系如下图所示：转化成规范化的关系如下图所示：课程课程C教师教师T参考书参考书B数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据库原理数据结构数据结构数据结构数据结构数据结构数据结构数据结构数据结构 吴胜利吴胜利吴胜利吴胜利吴胜利吴胜利陈晨陈晨陈晨陈晨陈晨陈晨王平王平王平王平张京生张京生张京生张京生 数据库原理与应用数据库原理与应用数据库系统数据库系统SQL Server2000数据库原理
39、与应用数据库原理与应用数据库系统数据库系统SQL Server2000算法与数据结构算法与数据结构数据结构教程数据结构教程算法与数据结构算法与数据结构数据结构教程数据结构教程 数据冗余大数据冗余大 插入异常插入异常 删除异常删除异常 C与与T间的联系被称为间的联系被称为多值依赖多值依赖 多个多个T对应一个对应一个C 一个确定的一个确定的C值，与其所对应的一组值，与其所对应的一组T值与值与B值无关值无关 例：设关系模式例：设关系模式 R（DN,TN,SN)分别代表系名，教师名，学生名分别代表系名，教师名，学生名 教师与系有直接联系，但与学生无直接联系。学教师与系有直接联系，但与学生无直接联系。学
40、生与系有直接联系。生与系有直接联系。教师与学生之间的联系是教师与学生之间的联系是间接联系间接联系。将间接联系的属性放在一个关系里出问题。若系将间接联系的属性放在一个关系里出问题。若系里有里有50个教师，个教师，500名学生，则关系中将出现名学生，则关系中将出现25000条记录。条记录。一个系有多名教师（一对多），多名学生（一对一个系有多名教师（一对多），多名学生（一对多），教师与学生无直接联系。多），教师与学生无直接联系。系与教师之间、系与学生之间的联系被称为系与教师之间、系与学生之间的联系被称为多值依多值依赖赖。定义定义4.18 设有关系模式设有关系模式R（U），），U是属性全是属性全集，集
41、，X、Y、Z是属性集是属性集U的子集，的子集，且且Z=UXY，如果对于，如果对于R的任一关系，的任一关系，对于对于X的一个确定值，存在的一个确定值，存在Y的一组值与之的一组值与之对应，且对应，且Y的这组值仅仅决定于的这组值仅仅决定于X的值而与的值而与Z值无关，此时称值无关，此时称Y多值依赖于多值依赖于X，或，或X多值决多值决定定Y，记作，记作XY。若若XY且且Z=UXY，则称，则称XY是非平凡的多值依赖是非平凡的多值依赖(Multivalued Dependence MVD)，否则称为平凡的，否则称为平凡的多值依赖多值依赖。多值依赖公理及其推论多值依赖公理及其推论 多值依赖公理多值依赖公理 增
42、广律：如果增广律：如果XY，V W U，则，则WXVY。传递律：如果传递律：如果XY，YZ，则，则XZ-Y。补余律：如果补余律：如果XY，则，则XU-X-Y。函数依赖公理与多值依赖混合公理函数依赖公理与多值依赖混合公理 复制规则：从复制规则：从FD导出导出MVD，如果，如果XY，则，则XY。接合规则：从接合规则：从MVD导出导出FD：如果：如果XY，ZY，且存在，且存在WU有有WY=，WZ，则，则XZ。多值依赖推论多值依赖推论 合并律：如果合并律：如果XY，XZ，则，则XYZ。伪传递律：如果伪传递律：如果XY，WYZ，则，则XW(Z-W-Y)。分解律：如果分解律：如果XY，XZ，则，则X（YZ
43、），），X(Y-Z)，X(Z-Y)。混合伪传递律：如果混合伪传递律：如果XY，XYZ，则，则X(Z-Y)。第四范式（第四范式（4NF）定义）定义 定义定义4.19 设有一关系模式设有一关系模式R（U），），U是其属是其属性全集，性全集，X、Y是是U的子集，的子集，D是是R上的数据依上的数据依赖集。如果对于任一多值依赖赖集。如果对于任一多值依赖XY，此多，此多值依赖是平凡的，或者值依赖是平凡的，或者X包含了包含了R的一个候选的一个候选关键字，则称关键字，则称R是第四范式的关系模式，记为是第四范式的关系模式，记为R4NF。一个一个BCNFBCNF的关系模式不一定是的关系模式不一定是4NF4NF 4
44、NF 4NF是是BCNFBCNF的推广的推广 一个一个BCNFBCNF的关系模式不一定是的关系模式不一定是4NF4NF 第四范式（第四范式（4NF）的分解）的分解（1）令）令=R。（2）如果）如果中所有模式中所有模式Ri都是都是4NF，则转，则转（4）。）。（3）如果）如果中有一个关系模式中有一个关系模式S不是不是4NF，则，则S中必能找到一个多值依赖中必能找到一个多值依赖XY且且X不包含不包含S的候选键，的候选键，Y-X，XYS，令，令Z=Y-X，设，设S1=XZ，S2=S-Z，用分解，用分解S1，S2代替代替S，由于，由于S1S2=X，S1-S2=Z，所以有，所以有(S1S2)(S1-S2
45、)，分解具有无损连接性，分解具有无损连接性，转（转（2）。）。（4）分解结束，输出）分解结束，输出。4.5 关系模式的规范化关系模式的规范化 一个低一级范式的关系模式，通过模式分一个低一级范式的关系模式，通过模式分解转化为若干个高一级范式的关系模式的集合，解转化为若干个高一级范式的关系模式的集合，这种分解过程叫作关系模式的这种分解过程叫作关系模式的规范化规范化。关系模式规范化的目的和原则关系模式规范化的目的和原则 规范化的目的就是使结构合理，消除存储规范化的目的就是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和异常，使数据冗余尽量小，便于插入、删除和更新。更新。规范化的基本原则就
46、是遵循规范化的基本原则就是遵循“一事一地一事一地”的原则。的原则。4.5.2 关系模式规范化的步骤关系模式规范化的步骤规范化过程规范化过程 1NF 2NF 3NF BCNF 消除决定属性消除决定属性不是候选键的不是候选键的非平凡的函数非平凡的函数依赖依赖消除非主属性对键的部分函数依赖消除非主属性对键的部分函数依赖消除非主属性对键的传递函数依赖消除非主属性对键的传递函数依赖消除主属性对键的部分和传递函数依赖消除主属性对键的部分和传递函数依赖4NF 消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖4.5.3 关系模式规范化的要求关系模式规范化的要求 本章讨论如何设计关系模式问题。关
47、系模式本章讨论如何设计关系模式问题。关系模式设计得好与坏，直接影响到数据冗余度、数设计得好与坏，直接影响到数据冗余度、数据一致性等问题。要设计好的数据库模式，据一致性等问题。要设计好的数据库模式，必须有一定的理论为基础。这就是模式规范必须有一定的理论为基础。这就是模式规范化理论。化理论。在数据库中，数据冗余是指同一个数据存储在数据库中，数据冗余是指同一个数据存储了多次，由数据冗余将会引起各种操作异常。了多次，由数据冗余将会引起各种操作异常。通过把模式分解成若干比较小的关系模式可通过把模式分解成若干比较小的关系模式可以消除冗余。以消除冗余。函数依赖函数依赖XY是数据之间最基本的一种联系，是数据之
48、间最基本的一种联系，在关系中有两个元组，如果在关系中有两个元组，如果X值相等那么要求值相等那么要求Y值也相等。值也相等。FD有一个完备的推理规则集。有一个完备的推理规则集。关系模式在分解时应保持关系模式在分解时应保持“等价等价”，有，有数据数据等价等价和和语义等价语义等价两种，分别用两种，分别用无损分解无损分解和和保保持依赖持依赖两个特征来衡量。前者能保持泛关系两个特征来衡量。前者能保持泛关系在投影连接以后仍能恢复回来，而后者能保在投影连接以后仍能恢复回来，而后者能保证数据在投影或连接中其语义不会发生变化，证数据在投影或连接中其语义不会发生变化，也就是不会违反也就是不会违反FD的语义。但无损分
49、解与保的语义。但无损分解与保持依赖两者之间没有必然的联系。持依赖两者之间没有必然的联系。范式是衡量模式优劣的标准，范式表达了模范式是衡量模式优劣的标准，范式表达了模式中数据依赖之间应满足的联系。如果关系式中数据依赖之间应满足的联系。如果关系模式模式R是是3NF，那么，那么R上成立的非平凡上成立的非平凡FD都应都应该左边是超键或右边是非主属性。如果关系该左边是超键或右边是非主属性。如果关系模式模式R是是BCNF，那么，那么R上成立的非平凡的上成立的非平凡的FD都应该左边是超键。范式的级别越高，其数都应该左边是超键。范式的级别越高，其数据冗余和操作异常现象就越少。据冗余和操作异常现象就越少。分解成
50、分解成BCNF模式集的算法能保持无损分解，模式集的算法能保持无损分解，但不一定能保持但不一定能保持FD集。而分解成集。而分解成3NF模式集模式集的算法既能保持无损分解，又能保持的算法既能保持无损分解，又能保持FD集。集。关系模式的规范化过程实际上是一个关系模式的规范化过程实际上是一个“分解分解”过程：把逻辑上独立的信息放在独立的关过程：把逻辑上独立的信息放在独立的关系模式中。分解是解决数据冗余的主要方法，系模式中。分解是解决数据冗余的主要方法，也是规范化的一条原则：也是规范化的一条原则：“关系模式有冗余关系模式有冗余问题就分解它问题就分解它”。书中未讲到的还有：书中未讲到的还有：嵌入多值依赖嵌