关系系统及查询优化与范式定理

1、第四章 范式定理关系数据库的设计中，一个非常重要的被视为理论问题的内容是如何构造合理的关系，使之能准确地反应现实世界，有利于应用和具体的操作。这一问题就是关系规范化要研究的问题。通过本章的学习，应重点掌握：函数依赖及 Armstrong 公理系统为什么要对模式进行分解，如何分解如何判断关系模式达到几范式如何求属性的闭包及如何求最小函数依赖集判断分解后的关系模式是不是无损连接或保持函数依赖判断分解后的关系模式既无损连接又保持函数依赖(一 )函数依赖及相关概念定义设 R(U) 是属性集U 上的关系模式，X ，Y 是 U 的子集。 若对 R(U) 的任何一个可能的关系 r ， r 中不可能存在两个元

2、组在X 上的属性值相等，而在Y 上的属性值不等，则称X 函数决定 Y 或 Y 函数依赖于X，记作： XY。f(1)完全函数依赖：在R(U) 中，如果XY，并且对于X 的任何一个真子集X ，都有 X不能决定Y，则称Y 对 X 完全函数依赖，记作：XY例给定一个学生选课关系SC(Sno，Cno，G)，我们可以得到F=(Sno ，Cno)G ，对 (Sno，Cno) 中的任何一个真子集Sno 或 Cno 都不能决定G ，所以， G 完全依赖于Sno， Cno。p(2)平凡的函数依赖：如果XY，但 Y 不完全函数依赖于X，则称Y 对 X 部分函数依赖，记作：XY(3) 传递依赖：在R(U) 中，如果X

3、Y ， (YX) ， YX ， YZf则称 Z 对 X 传递依赖。(4) 码：设K 为 R(U ， F) 中的属性的组合，若KU，则 K 为 R 的候选码，若有多个候选码，选一个作为主码。注 : 候选码也称候选关键字。主属性和非主属性： 包含在任何一个候选码中的属性叫做主属性，否则叫做非主属性。(6) 外码：若R(U) 中的属性或属性组X 非 R 的码，但是另一关系的码，则称X 为外码。范式在关系数据库中的一个非常重要的问题就是如何评价分解后的各个关系模式的好坏。通常可以通过判断分解后的模式达到几范式来评价模式的好坏。范式有：1NF 、2NF 、3NF 、BCNF 、4NF 和 5NF 。这几

4、种范式之间的关系如下：1NF2NF 3NFBCNF4NF 5NF通过模式分解，将低一级范式的关系模式分解成了若干个高一级范式的关系模式的集合，这种过程叫做 规范化 。下面将给出各个范式的定义。1 1NF( 第一范式 )定义 若关系模式 R 的每一个分量是不可再分的数据项，则关系模式R 属于第一范式 (1NF) 。例 供应者和它所提供的零件信息，关系模式如下：FIRST (Sno ，Sname，Status，City ，Pno，Qty) 并且有 F SnoSname， SnoStatus，StatusCity ， (Sno， Pno)Qty 。具体的关系如图 5 l 所示。SnoSnameSta

5、tusCityPnoQtyS1精益20天津P1200S1精益20天津P2300S1精益20天津P3480S2盛锡10北京P2168S2盛锡10北京P3500S3东方红30北京P1300S3东方红30北京P2280S4泰达20上海P2460从图 5 1 中可以看出，每一个分量都是不可再分的数据项，所以是1NF 。但是， 1NF 带来四个问题：冗余度大：例如每个供应者的Sno， Sname， Status， City 要与零件的种类一样多；(2) 引起修改操作的不一致性：例如供应者S1 从“天津”搬到“上海”，若稍不注意，就会使一些数据被修改，另一些数据没有被修改，导致数据修改的不一致性；插入异常

6、：若某个供应者的其它信息未提供时，如“零件号”，则不能进行插入操作；(4) 更新异常：若供应商S4 的 P2 零件销售完了，删除后，在基本关系FIRST找不到 S4，可S4 又是客观存在的。正因为上述原因引入了2NF 。2 2NF( 第二范式 )定义若关系模式R1NF ，且每一个非主属性完全依赖 于码，则关系模式R2NF 。即当 1NF 消除了非主属性对码的部分函数依赖，则成为2NF 。例FIRST 关系中的码是Sno、Pno，而 SnoStatus，因此非主属性Status 部分函数依赖于码，故非2NF 的。若此时，将FIRST 关系分解为：FIRSTl(Sno ， Sname， Statu

7、s， City)2NFFIRST2(Sno ， Pno， Qty)2NF因为 FIRSTl 和 FIRST2中的码分别为Sno 和 Sno， Pno 每一个非主属性完全依赖于码。3 3NF( 第三范式 )定义若关系模式R(U ， F) 中不存在这样的码X ，属性组Y 及非主属性Z(ZY) 使得XY ， (YX)YZ 成立，则关系模式R3NF 。即当 2NF 消除了 非主属性对码的传递函数依赖，则成为3NF 。例 FIRSTl 3NF ，因为在分解后的关系模式FIRSTl 中有：SnoStatus， StatusCity ，存在着非主属性City 传递依赖于码Sno。4 BCNF( 巴克斯范式

8、)；定义若关系模式R1NF ，若 XY 且 YX 时， X 必含有码，则关系模式RBCNF 。即当 3NF 消除了主属性对码的部分和传递函数依赖，则成为BCNF 。结论一个满足BCNF 的关系模式，应有如下性质：所有非主属性对每一个码都是完全函数依赖；所有非主属性对每一个不包含它的码，也是完全函数依赖；没有任何属性完全函数依赖于非码的任何一组属性。(三 )多值依赖1多值依赖定义若关系模式R(U) 中， X、Y、Z是U 的子集，并且Z U X Y。当且仅当对R(U)的任何一个关系r ，给定一对(x ， z)值，有一组Y 的值，这组值仅仅决定于x 值而与z 值无关，则称“Y多值依赖于X ”或“X

9、多值决定Y ”成立。记为：XY。2多值依赖的性质多值依赖具有如下六条性质：(1) 多值依赖具有对称性。即若XY ，则XZ ，其中Z U XY(2) 多值依赖的传递性。即若XY ， YZ，则XZ Y函数依赖可以看成是多值依赖的特殊情况(4)若 XY ， XZ，则 XYZ(5)若 XY ， XZ，贝， XY Z；(6)若 XY ， XZ，则 XZ Y。3 4NF( 第四范式 )定义(4NF) 若关系模式R1NF ，若对于R 的每个非平凡多值依赖XY 且 YX 时，X必含有码，则关系模式R(U ， F)4NF 。(四 )函数依赖的公理系统Armstrong 公理系统： 设关系模式R(U ，F) ，其

10、中U 为属性集，F 是U 上的一组函数依赖，那么有如下推理规则：(1)A1 自反律：若Y(2)A2 增广律：若X(3)A3 传递律：若XU，则 XY为F所蕴涵；Y 为 F 所蕴涵，且ZU，则 XZXY，YZ 为 F 所蕴涵，则XYZZ 为为 F 所蕴涵；F 所蕴涵。根据上述三条推理规则又可推出下述三条推理规则：(1)合并规则：若XY， XZ ，则XYZ为F所蕴涵(2)伪传递率：若XY， WYZ，则XWZ 为F 所蕴涵(3)分解规则：若XY， ZY ，则XZ 为F 所蕴涵。引理：XA： A1 A2 A1成立的充分必要的条件是XAi成立I=1 ， 2， 3， k）F( 五 ) 函数依赖的闭包F+及

11、属性的闭包X +：1 函数依赖的闭包定义关系模式 R(U ， F) 中为 F 所逻辑蕴含的函数依赖的全体称为F 的闭包，记为： F+ 。2 属性的闭包X+F定义设 F 为属性集 U 上的一组函数依赖， XU ， A | X X + A 能由 F 根据 ArmstrongF公理导出 ，则称为属性集 X 关于数依赖集F 的闭包。X+3 求属性 X 的闭包 X 吉的算法X +FF算法求属性的闭包X +F输入X ， F输出X +F步骤令 X (0) =X ， i 0(2)求 B， B A |( v)( w)(VWF V X (i)A W)(3)X (i+1) BX (i)判断 X (i+1) = X

12、(i) 吗(5)若相等，或X (i)=U ，则 X (i) 为属性集 X 关于函数依赖集F 的闭包。且算法终止(6) 若不相等，则i i+1 ，返回第二步例 1已知关系模式R(U ，F)，UA，B，C，D，E)；FAB， DC， BCE， ACB求(AE) +F (AD) +F解求(AE)+X(0)=AEF计算 X (1) : 逐一扫描 F 中的各个函数依赖，找到左部为A、 E 或 AE 的函数依赖，得到一个：AB。故有 X (1) =AEB。计算 X (2) ：逐一扫描F 中的各个函数依赖，找到左部为ABE 或 ABE 子集的函数依赖，因为找不到这样的函数依赖，所以，X (1) X (2)

13、。算法终止，(AE) +ABE 。F求 (AD) ；，由上述算法，设 XtO AD计算 X ”：逐一扫描F 中的各个函数依赖，找到左部为A、 D 或 AD 的函数依赖，得到两个： A+B ， D-C 函数依赖。故有XCl ： ADUBC 。计算 X n：逐一扫描F 中的各个函数依赖，找到左部为ADBC 或 ADBC 子集的函数依赖，得到两个：BC E ， AC B 函数依赖。故有X 2，： ABCDUE 。所以， X(2 ： ABCDE ： U ，算法终止，(AD) 吉： ABCDE 。(六 )最小函数依赖集1等价和覆盖定义一个关系模式R(U ， F) 上的两个依赖集F 和 G，如果F G ，

14、则称F 和 G 是等价的，记做F 三 G 。若 F 三 G ，则称 G 是 F 的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。2最小函数依赖集定义如果函数依赖集F 满足下列条件，则称F 为最小函数依赖集或最小覆盖。；(1)F 中的任何一个函数依赖的右部仅含有一个属性；”(2)F 中不存在这样一个函数依赖X A ，使得F 与 F 一 X A等价；扩(3)F 中不存在这样一个函数依赖X A，X 有真子集Z 使得F 一 X AUZ+A 与 F 等价。； 3计算最小函数依赖集的算法。算法计算最小函数依赖集。输入一个函数依赖集输出F 的一个等价的最小函数依赖集G。步骤(1) 用分解

15、的规则，使F 中的任何一个函数依赖的右部仅含有一个属性；，：(2) 去掉多余的函数依赖： 从第一个函数依赖X+Y 开始将其从F 中去掉， 然在剩下的函数依赖中求X 的闭包X ，看X是否包含Y ，若是，则去掉X Y ；否则不能去掉，依次做下去。直到拽不到冗余的函数依赖；去掉各依赖左部多余的属性。一个一个地检查函数依赖宏部非单个属性的依赖。例如XY+A ，若要判Y 为多余的，则以醑+A 代替 XY+A 是否等价 ?若 AE(X) ，则 Y 是多余属性，可以去掉。例 2已知关系模式R(U ，F) ， UA，B， C，D，E，G ；江FAB+C ，DEG ， CA，BE+C 扩BC D，CG BD ，

16、ACD-B ，CE AG ； 请将 F 化为最小函数依赖集。； 解此题可以有两种求解方法，求解过程如下： 辈方法 1(利用算法求解， 使得其满足三个条件)； (1)利用分解规则，将所有的函数依赖变成右边都是单个属：性的函数依赖，得F 为：FABC，D+E ，D+G ，CA，BECBCD，CG B，CGD，ACD B，CE+A ， CE G(2) 去掉 F 中多余的函数依赖，具体做法如下：从第一个函数依赖开始从F 中去掉它 (假定它为 X Y) ，剩下的函数依赖F求X 的闭包，看X 是否含Y ，若包含Y ，则 X+Y 为冗余函数依赖，则去掉它，否则不去。依次下去，直到能满足定义最小依赖的第二个条

17、件。故有：设 AB C 为冗余的函数依赖，则去掉AB+C 得F1D+E ，D G，C+A ，BE CBC+D ，CGB，CG D，ACD+B ，CE A ， CE+G因为从 Fl 中找不到找到左部为AB 或 AB 子集的函数依赖，则(AB) 击。所以 AB+C 非冗余的函数依赖，不能去掉。设 CG B 为冗余的函数依赖，则去掉CG B 得F2AB+C ，DE，D+G ，C+A ，BECBC+D ， CG+D ， ACD+B ，CE A ， CE+G求 (CG) 左设 X*) ：CG计算 X ”：逐一扫描 F2中的各个函数依赖，找到左部为C 、 (；或 CG 的函数依赖，得到一个： C A 函数

18、依赖。故有X“ CGA 。计算 X “：逐一扫描 F2 中的各个函数依赖，找到左部为CGA 或 CGA 子集的函数依赖，得到一个： CG+D 函数依赖。故有X 9 ACDG 。：计算 X “：逐一扫描F2 中的各个函数依赖，找到左部为AC 拓或 ACDG 子集的函数依赖，得到两个： ACD B， D ， E 函数依瓤故有XCa)2ABCDEG。；：扭因为 X ABCDEG ； U ，算法终止， (CG) 占 ABCDE 。所以 CG B 为冗余的函数依赖，从F2中去掉。：设 CG+D 为冗余的函数依赖，则去掉CG D 得；捍F3 AB+C ， D-*E ，D+G ， C-,-A ， BE CB

19、C+D ， ACD-B ， CE A ， CE+G ：求 (CG) 占； 设 XCO) ： CG ：计算 Xm ：逐一扫描 F3 中的各个函数依赖，找到左部为C、 G 城 CG 的函数依赖，得到一个：C+A 函数依赖。故有 Xu ：； ACG 。熟 计算 X ”：逐一扫描F3 中的各个函数依赖，找到左部为ACG诚ACG 子集的函数依赖，周为找不到这样的函数依赖。故有谨X ”，算法终止。(CG)占 ACG 。：因为 ACG 芒 D ，所以 CG+D 非冗余的函数依赖，不能从F3 冲去掉。 ；设 CE+A 为冗余的函数依赖，则去掉CE A 得瞰F4 AB-*C， D-E ， D-*G ， C+A

20、， BE C；BC-*-D ， CG D ， ACD-B ， CE+G) ：求 (CZ) 击； 设 X(O ： CE 芝计算 X-) ：逐一扫描 F4 中的各个函数依赖，找到左部为C 、 E 藏 CE 的函数依赖，得到一个：CA 函数依赖。故有： X(1 5ACE 。 计算XC2) ：逐一扫描 F4中的各个函数依赖，找到左部为ACE ；藏 ACE 子集的函数依赖，得到一个：CE G 函数依赖。故有：骚X 2)ACEG 。计算 X ”：逐一扫描F4 中的各个函数依赖，找到左部为ACEG 或 ACEG 子集的函数依赖，得到一个：CG D 函数依赖。故有：X ACDEG 。计算 X “：逐一扫描F4

21、 中的各个函数依赖，找到左部为AC DEG 或 ACDEG子集的函数依赖，得到一个：ACD B 函数依赖。故有：X ABCDEG 。因为 X “ ABCDEG U ，算法终止，(CE) 占： ABCDEG 。所以 CE+A 为冗余的函数依赖，从F4中去掉。又因为 F4 中无多余函数依赖所以转(3)。去掉 F4 中各函数依赖左边多余的属性。函数依赖ACD+B ，属性A 是多余的，去掉A 得 CD B，因为 C A，所以可推导出 ACD B。故最小函数依赖集为：FMIN AB+C ，DE，D+G ， C A，BE CBC+D ，CGD，CD+B ，CE G方法 2(利用 Armstrong 公理系

22、统的推理规则求解 )假设 CG B 为冗余的函数依赖，那么，从F 中去掉它后能根据 Armstrong 公理系统的推理规则导出。因为CG+D CA (已知 )所以CGA ACD (增广律 )因为ACD B(已知 )所以CGA B(传递律 )因为CA (已知 )所以CG B(蕴涵 )同理可证：CE A 是冗余的。又因C A ， CD B 可知， ACD-B L故去掉左边多余的属性得CD-B 。需要注意的是，F 的最小依赖集FMIN不一定是惟一的，它与对各函数依赖FDi 及 X A 中X 各属性的处理顺序有关。例 3已知关系模式R(U ，F)，UA ，B，C ；FA+B ，BA，B+C，A+C ，

23、 CA求最小函数依赖集。分析此题可以有两种不同的答案，下面分别叙述如下。答案 1设 B A 是冗余的，将其从F 中去掉，看能否根据，Armstrong 公理系统的推理规则导出。因B-C ，CA(已知 )故B A(传递律 )故 B-,-A 是冗余的，将其从F 中去掉，得n 为F1 ： A+B ， B-C ， A+C ， C+A 。又设 A C 为冗余，将其从F1 中去掉因AB，B-C(已知 )故AC(传递律 )故 A+C 是冗余的，将其从n 中去掉，得Fm 为：FM ， A B，B+C ，G+A 。因为在 FM ，中的其它函数依赖是非冗余的，所以，FMl 为最小函数依赖集。答案 2设 B C 是

24、冗余的，将其从F 中去掉，看能否根据、Armstrong 公理系统的推理规则导出。：因B A， A+C(已知 )故B C(传递律 )故 B+C 是冗余的，将其从F 中去掉，得FM2 为FM2 A B，B+C ，A C ，C A。：i因为在Fm 中的其它函数依赖是非冗余的，所以，FM2 为最小函数依赖集。从上分析我们可以得到两个最小函数依赖集Fh4 ，和 Fht 。，因此， F 的最小函数依赖集不是惟一的。(七 )模式分解1分解定义(分解 )关系模式R(U ， F) 的一个分解是指，P Rl(Ul ， P1)， R2(U2 ， F2) ， R 。 (U 。， F。 ) ，其中：nU UU ，并且

25、没有U(U ， 1 i， j n， E 是 F 在 U 上的投影。其中 Fi X YX YEF 八 XY 三 Ui对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有三种情况：分解具有无损连接性；分解要保持函数依赖；分解既要无损连接性；又要保持函数依赖。2无损连接定义 (无损连接 )P R ， (U1 ， F： )， R ： (U：， F2) ， Rh(Uk ， Fk) 是关系模式 R(U ， F) 的一个分解， 若对 R(U ，F) 的任何一个关系 r 均有 r mP(r) 成立，则成分解 P 具有无损连接性 (简称无损分解)。k其中， mP(r) ：冈丌 R ： (r) 。定理

26、关系模式R(U ， F) 的一个分解，P R1(U ：， F1) ， R：(U2 ， F ： )具有无损连接的充分必要的条件是：Ul 门 U2 一 Ul U2EF 或Ul 门 U2+U2 一 UlEF 3保持函数依赖定义：设关系模式R(U ， F) 的一个分解，P 民 (U ：， F1) ， R：咖 2，F2) ，Rk(Uk ，Pk) ，如果：F (U 丌 Ki(F1-) ，则称分解P 保持函数依赖。 十4判别一个分解的无损连4i-1 和保持函数依赖的算法；算法1判别一个分解的无损连接性。广pRl(U ：， F1)， R。 (U2 ，F：)，凡 (UL ，Fb) 是关系模式R： (U ，F)

27、的一个分解，U ：A1 ， A ：， A 。 ， F FDl ， FD2 ，： FDp ，并设 F 是一个最小依赖集，记FDi 为戈一 Au ，其步骤如下：(1) 建立一张n 列 k 行的表，每一列对应一个属性，每一行对：应分解中的一个关系模式。若属性八仨U ，则在j 列 i 行上填上钙，否则填上、b芝(2) 对于每一个 FDi 做如下操作：找到Xi 所对应的列中具有：；相同符号的那些行。考察这些行中1i 列的元素，若其中有，则全；都改为，否则全部改为bmli ，m 是这些行的行号最小值。i，如果在某次更改后，有一行成为：a1， a2， an，则算法终止。：且分解p 具有无损连接性，否则不具有

28、无损连接性。：，对 F 中 p 个 FD 逐一进行一次这样的处理，称为对F 的一次；扫描。：；：(3)比较扫描前后，表有无变化，如有变化，则返回第(2) 步，：否则算法终止。斗 如果发生循环，那么前次扫描至少应使该表减少一个符号，表：中符号有限，因此，循环必然终止。：算法 2转换成3NF 的保持函数依赖的分解。孓p R1(U ：， F1) ， R ： (U ：，F： )， Rk(Uk ， Fk) 是关系模式R：囊 U， F) 的一个分解，U： A ：， A ：， An ， FFDl ，FD2 ，： FD ， ，并设 F 是一个最小依赖集，记FDi 为咒一，其步骤如下：；(1)对 R(U ， F

29、) 的函数依赖集F 进行极小化处理(处理后的：结果仍记为F) ； i找出不在 F 中出现的属性，将这样的属性构成一个关系模式。把这些属性从U 中去掉，剩余的属性仍记为U ；若有 X A 正 F，且 XA U，则 P R ，算法终止；(4) 否则，对F 按具有相同左部的原则分组(假定分为k 组 )，每一组函数依赖Fi 所涉及的全部属性形成一个属性集U 。若 U三 U(ire 就去掉U。由于经过了步骤(2) ，故U U9 ，于是 P R ， (Ul， F1) ， R2(U2 ， F2) ， Rk(Uk ，Fk) 构成 R(U ， F) 的一个保持函数依赖的分解。并且，每个Ri(Ui ， E) 均属

30、于 3NF 且保持函数依赖。例 4 关系模式 R(U ，F)，其中 UC， T， H，I，S， G)，FCSG， C+T ，TH I ，HI C，HS I ，将其分解成3NF 并保持函数依赖。解 根据算法 2 求解如下：(1)F 已为最小函数依赖集；(2)R 中的所有属性均在F 中都出现，所以转(3) ；对 F 按具有相同左部的原则分为：R1 CSG ， R2 ； CT ， R3： THI ， R4 ： HIC ，R5 ： HSR 。所以 P R1(CSG) ， R2(CT) ， R3(THl) ， R4(HIC) ， R5 (HSR)算法 3将一个关系模式转换成3NF ，使它既具有无损连接又

31、保持函数依赖的分解。输入关系模式R 和 R 的最小函数依赖集F。输出R(U ，F) 的一个分解P R1(U ，F1) ，R：(U ：，F：)， Rk(Uk ，Fk) ，民为 3NF ，且 P 具有无损连接又保持函数依赖的分解。操作步骤如下：(1) 根据算法2 求出保持依赖的分解P R1 ， R 。， R 。 ii(2) 判分解P 是否具有无损连接性，若有，转(4) ；惑；、(3) 令 ppUX) ，其中 X 是 R 的候选关键字； 牡知(4)输出 P 孙。 例 5对例 4 的关系模式R(U ，F) 将其分解成3NF ，使 P 具有嘎损连接又保持函数依赖的分解。弘，解根据算法3 求解如下：扒(1

32、) 据例 4 得3NF 保持函数依赖的分解如下：杠。二 RI(CSG) ，R2(CT) ，R3(THl) ，R4(HIC) ，R5(HSR) (2)根据算法1 构造一个二维矩阵如图5 2 所示。；：根据 F 中的 C T，对上表进行处理，由于属性列C 上第一；行、第二行及第四行相同a，所以将属性列T 上 b12、 b 2 改为同一：符号a：。又根据HI C 将属性列C 上 b“、bsl 改为同一符号a1；修改后如图5 3 所示。根据 F 中的 CS G，对上表进行处理，由于属性列CS 上第一行、第五行相同al、 a5，所以将属性列G 上 b，。改为同一符号a6。又根据C T 将属性列T上 b。

33、：改为同一符号a2，修改后如图5 4 所示。从上可见，找到一行(第 5 行 )为全 a，所以分解是无损的。算法 4将关系模式转换成BCNF ，使它具有无损连接的分解。输入关系模式R 和函数依赖集F。输出R(U ，F) 的一个分解PR，(U ，F1) ，R。(U2 ，F：)，Rk(Uk ，Fk) ，民为 BCNF ，且 P 具有无损连接的分解。操作步骤如下：(1) 令 P R(2)若 P 中的所有模式都是BCNF ，则转 (4)；(3)若 P 中有一个关系模式民不是BCNF ，则民中必能找到一个函数依赖X A，且 X 不是民的候选键，且A 不属于X ，设Rn(XA) ， Ri2( 民一 A) ，

34、用分解 民， Rn 代替民，转(2)；输出 F；例 6 关系模式 R(U ，F)其中： U： C，T，H ，I，S，G，F 二 CSC，CT，TH I ，HI+C ， HS I ，将其无损连接地分解成BCNF 。解 R 上只有一个候选关键字HS(1)令 P R(U ， F)l： (2)p中不是所有的模式都是BCNF ，转 (3) ； R 扭；(3) 考虑 CS G，这个函数依赖不满足BCNF条件 (CS不包蒙禽候选键HS) ，所以将其分解成Ri(CSG) 、R2(CTHIS) 。计算法 1 和 R2 的最小函数依赖集分别为：Fl CS G ，F2 C 一黔 T ，TH I ，HI C， HS

35、I 。 R2 的候选关键字为HS 。默因R1 已是 BCNF ，而 R2 的 F2 中存在不为码的决定因睽素HIC驻 故R2 不属于 BCNF ，进一步分解R2 即可。爱：分解R2：考虑 C T，将其分解成R21(CT)、R22(CHIS)。计6 薯 R21 和 R22 的最小函数依赖集分别为：F21 C T ， F22 ： CH+I， HI+C ， HS+I ， C T ， TH 一 1，在F22 中，有 CH 一心。 R22 的候选关键字为HS 。整因R21 已是 BCNF ，R22不是 BCNF 熙故进一步分解 R22 即可。默分解 R22 ：考虑 CH 一 1，将其分解成 R221(C

36、Hl) 、R222 扭 CHS) 。计算 R221 和 R222 的最小函数依赖集分别为：盼酝F221 CH I，HI C鞯 R：F222：HS+C 。 ir 戴因R221 ，R222 已是 BCNF 磬故将 R 分解后为：芝p R1(CSG) ，R21(CT) ，R221(CHl) ，R222(CHS) 醛算法 5将关系模式分解成4NF ，使它具有无损连接性。酝输入 关系模式 R 和函数依赖集F。黔输出R(U ，F) 的一个分解P Rl(U ，F1) ，R2(U ：，F2) ， F? ”，Rk(U ，Fk) ，民为 4NF ，且 P 具有无损连接的分解。卧操作步骤如下： 芝(1)令 P R(

37、2) 若 P 中的所有模式都是4NF ，则转 (4) ；若 P 中有一个关系模式民不是 4NF ，则 Ri 中必能找到一个函数依赖含民的候选键，且 A X 乒中， XA ；i 民令 Z A X ，由分解规则得出X一一A，且X不包 X 一一 Z。令 R。(XZ) ，Ri2( 民一 Z) ，用分解 ， F A B)，如下的两个分解：(1)F1 AB ， BC(2)p ： AB ， AC 判这两个分解是否无损。解 (1)根据定理判断本题因 AB 门 BCB ABBCABCABC故 BA茫FB+C 争 F故 P，为有损连接。(2) 根据定理判断本题因 AB门AC二A ABAC BACABC故 AB正F

38、B+C F芝故 p：为无损连接。豁例 5 2对给定的关系模式R(U ， F) ， U A ， B， C ， D， E ，F 山 A C， B C ， C D， DE C，CE A ，如下的分解：；p R： (AD) ，R2(AB) ，R ：(BE) ， R： (CDE) ， Rs(AE) 捌分解P 是否无损。豪解(1) 构造一个初始的二维表如图5 5所示。拦臻(2) 根据 A+C ，对上表进行处理，由于属性列A 上第一行、汝二行及第三行相同a，所以将属性列C 上 b，、 b：，、 b53 改为同一瓢细号b13，取行号最小值。又根据B C 将属性列C 上 b、 b 北改为粗阑一符号b13，修改后

39、的表如图5 6 所示。牡(3) 根据 C+D ，对上表进行处理， 由于属性列C 上第一行第野仁行、第三行及第五行相同b，且属性列D 上第一行为a，所以将R洄性列D 上 b：，、 b，：、 b：，改为同一符号a：，修改后的表如图5 7 渤示。苣团O(4) 根据 DE+C ，将属性列C 上第三行及第五行改为同一符号a，修改后的表如图5 8 所示。田 OO根据 CE+A ，将属性列 A 上第三行及第四行改为同一符号 al，修改后的表如图 5 9 所示。通过上述更改，使第三行成为：a1， a：， a， a4， a。，则算法终止。且分解P 具有无损连接性。例 53对给定的关系模式R(U ，F)，UA，B

40、， C，D，E，尸通过上述更改，使第三行成为：a1， a：， a， a4， a。，则算法终止。且分解P 具有无损连接性。例 53对给定的关系模式R(U ，F)，UA，B，C，D，E，尸轧 F；AB，CP，EA， CE D ，如下的分解：感p R1(ABE) ， R2(CDEP)甄。： (1)求 R 的候选关键字，并判分解 p 是否无损；扫； (2)R1 、 R ：属于几范式。瓤解(1) 候选关键字为CE筻因(CE) U 6；十故有 CE+U ，并且在 CE 中不存在一个真子集能决定R 抽全体属性U，故 CE为R的候选关键字。萨：根据定理判断本题分解P 是否无损举因ABE 门 CDEP E 2

41、：；蔑“ABE CDEP AB 醛 磬CDEP ABE ： CDP良因E+A ， A+B(已知 )莨故有 E+B(传递律 )寥“因E+A ，EB 豪故有 E+AB(合并律 )封： 因E+ABEF 卧：故故 P 为无损连接。甄(2)R1 、 R ：属于几范式 ?踩： R1E2NF骚；因 E A， A+B 良故E B，存在传递依赖野故 R1任 3NF 萨 R：仨 1NF 皂因CE+D ，C+P 瑟故CE 能惟一地确定R：中的每一个元组，故为候选关漠字。醛因CE 是候选关键字，而C P，所以 P 部分函数依赖良与 CE故 R2手2NF例 54对给定的关系模式R(U ，F)，UA，B，C，D，E，P

42、，FAB，CP，EA， CE+D ，如下的分解：p R1(CP) ， R ：(BE) ，R3(ECD) ，R： (AB) ，判分解P 是否无损。解(1)构造一个初始的二维表如图5 10 所示。(2) 根据 A B，对上表进行处理，由于属性列A 上无相同元素，所以不能修改表。又根据C P 将属性列P 上 b：，改为a，修改后的表如图5 11 所示。(3) 根据 E A，对上表进行处理，由于属性列E 上第二行、第三行相同a5，所以将属性列A上 b：，、 L 改为同一符号b：，修改后的表如图5 12 所示。；(4) 根据 CE D ，对上表进行处理，无法修改上表。因此，在辗后的表格，找不到一行全为a

43、l， a：， an，所以P 是有损的。：例 5 5试证明由Armstrong 公理系统推导出下面三条推理规则是正确的：l(1) 合并规则：若X Z， X Y ，则有 X YZ伪传递规则：若 X Y ， WY Z，则有 XW Z(3) 分解规则：若XY，Z 任 Y，则有 X 一 2证明(1)合并规则：因X Y(已知 )器故XXY (增广律 )因X Z(已知 )故XY YZ(增广律 )：因XXY ，XY YZ(从上面得知 )故XYZ(传递律 ) (2) 伪传递规则：，因X+Y(已知 )故WX WY(增广律 )因 WYZ (已知)故XW 一 2(传递律 )(3)分解规则：因 Z(Y(已知 )故Y Z

44、(自反律 )因X Y(已知 )故X Z(传递律 )例 3-6关系 R(A ，B，C， D，E，F，G ，H ，I ，J)满足下列函数依赖：ABD+E ， AB G， B F， C 一工， CJ I ， G+H该函数依赖集是最小函数依赖集吗?给出该关系的候选码。解 该函数依赖集不是最小函数依赖集。因 CJ，CJI (已知 )故 CJ (逻辑蕴涵 )显然， ABCDGJ 是一个超码，即所有出现在函数依赖左边的属性的集合是超码。但是因CJ(已知 )故 可将 J 从超码中去掉。因ABG(已知 )故 可将 G 从超码中去掉。此时，超码中只剩下ABCD ，由于它们都没有在函数依赖集的任何一个函数依赖的右边

45、出现，所以它们都不能从超码中去掉。故候选码为：ABCD 。所谓超码是指能惟一标识关系中的每一个元组，不含多余属性的才是候选关键字(或候选码 )。例 3 7设 P R1(U1 ， F1) ， R2(U2 ， F2) 是 R(U ， F) 上的一个分解，试证明P 具有无损连接的充分必要的条件是：U1 门 U ：一 Ul U2 仨 F或 Ul 门 Uz U2 一 Ul 仨 F。证明(1)充分性：设U、门 Uz-U ：一 U ：，则可构造表如图5 13 所示。该图省略了a、b 的下标。如果 U ，门 U2+U ，一 U2 在 F 中，则可将表的第二行U ，一 U ：瀚韵所有符号全改为aaa a，使得该

46、表的第二行全为a，则 P 具有海损连接性。同理可证U 、门 U： +U ：一 U：的情况。如果Ul 门 U2 知：一U ：不在 F 中，但在F中，那么，它可以从Armstrong 公理纂统的推理规则导出，从而也能推出Ul 门 U2 一九，且Ai 三 U1 一巍中，所以可以将九列的b 改为 a，同样，可将Ul U2 的其它属醛对应的第二行也全改为a，这样，第二行就变成全a，所以分解是凛有无损连接性。卧(2)必要性：设构造的表中有一行全为a，例如第一行全为a湘由函数依赖的定义可知U：门 U ：一 U ：一Ul ；如第二行全为a，则油函数依赖的定义可知U ，门 U2+Ul U2 。黔例 5 8试证明

47、由关系模式中全部属性组成的集合为候选拱键字的关系是3NF ，同 时 也 是BCNF 。证明由于关系模式中的全部属性组成的集合为候选关键障，该关系中没有非主属性，满足R 属于 3NF 的条件，即每个非主幽性即不函数依赖候选关键字，也不传递依赖于候选关键字。醛又因为它没有非候选关键字的属性，也满足BCNF 的三个降件：F(1) 所有非主属性对每个候选关键字都完全函数依赖；苣(2)没有任何属性都完全函数依赖于非候选关键字的任一组61 性；因为它只是一个候选关键字，所以又满足BCNF 的另一个陋伍(3)所有的主属性对每一个不包含它的候选关键字也是完全函数依赖。例 5 9试证明一个关系模式R 是 BCN

48、F ，那么它一定是3NF 。证明采用反证法。设关系模式R 是 BCNF ，不是3NF 的，则必存在非主属性A 和候选关键字X 以及属性组Y ，使得：X ， Y ， Y+A ，其中A+X ， A Y ， Y+X不属于F，这就是说Y 不可能包含R 的候选关键字，但 Y A 却成立。 根据 BCNF 定义， R 不是 BCNF ，与题设矛盾， 所以一个BCNF 必是 3NF的。例 5 10关系 R(A ， B， C ， D， E) 满足下列函数依赖：FA C，C D，BC，DE C，CE A给出关系 R 的候选关键字；判 P AD ， AB ， BC， CDE ， AE 是否无损连接分解；将 R 分

49、解为 BCNF ，并具有无损连接性。解(1)从函数依赖集F 中看，候选关键字至少包含BE ，因为BE 不依赖于谁，而(BE) ABCDE ，所以， BE 是 R 的候选关键字。(2) 构造一个二维表，如图5 14 所示。根据A+C ，对上表进行处理，由于属性列A 上第 1， 2， 5 行相同，但属性列C 上对应的1， 2， 5 行上无ai 元素，所以，只能将b13b： bs，改为行号最小值b130 又根据C D 将属性列 D 上 b改为 a：，修改后的表如图5 15 所示。臣b lb 扩根据B C，对上表进行处理，由于属性列B 上第 2， 3 行相湘，但属性列C 上对应的3 行为 a：元素，所

50、以，只能将第2 行 b13 改洳 a3。又根据DE C ，CE A 不能修改此表所以修改后的表如卜 i 声 5 16 所示。摹”。”：根据A C，对上表进行处理，由于属性列A 上第 1， 2， 5 府相同，但属性列C 上对应的1， 2， 5 行上有a3 元素，所以，只能将藻1， 5 行 b13 改为 a3。又根据C+D 将属性列D 上 b2 bs：改为a4，：修改后的表如图5 17 所示。根据 CE+A ，对上表进行处理，由于属性列CE 上第 4，5 行相伺，但属性列A 上对应的5行为 al 元素，所以，将第4 行 b41 改为 a，。修改后的表如图5 18 所示。继续扫描F 不能修改此表，由

51、于找不到一行全为a，所以该分解是有损的。(3) 考虑 A C ，因为AC 不包含候选关键字，所以AC 不是BCNF ，故将ABCDE 分解为两个子模式R1(AC)R2(ABDE)。此时， R1 正 BCNF 。，继续分解R2 ，考虑 B D ，将 ABDE 分解为两个子模式R21 (BD)R22(ABE)，此时， R21 和R22 均属于BCNF 。所以R 分解为 BCNF ，并具有无损连接性的分解如下：P AC ， BD， ABE三、习题一、选择题L 设学生关系模式为：学生(学号，姓名，年龄，性别，成绩，专业)，则该关系模式的主键是()。A姓名B学号，姓名C 学号 D 学号，姓名年龄搬2设关

52、系模式R(U ， F) ， U 为 R 的属性集合， F 为 U 上的一种函数依甑，则对R(U ， F)而言，如果 X Y 为 F 所蕴涵，且 Z 巨 U，则 XZ YZ 为 F 所酶硒。这是函数依赖的()。笋 A传递律U合并规则巴自反律D增广律瓤3X 一九成立是X A1A2 Ah 成立的 ( )。终久充分条件D必要条件随C 充要条件D 既不充分也不必要蒺4设一关系模式为：运货路径 (顾客姓名，顾客地址，商品名，供应商姓辐，供应商地址)，则该关系模式的主键是 ()。女儿顾客姓名，供应商姓名-幂B B 顾客姓名，商品名轧巴顾客姓名，商品名，供应商姓名乏D顾客姓名，顾客地址，商品名醛5设有关系模式

53、R(U ，F)， U 是 R 的属性集合， X， Y 是 U 的子集，则多灌函数依赖的传递律为()。萨 A 如果 X+Y ，且 Y Z ，则 X Z 小 h：，萨B如果 X一 +Y ， Y+ 一 Z，则 X+(Z Y) 粒豪C如果 X 一+Y ，则 X一+(U YX)铲D 如果 X+一 Y，VOW ，则 WX一 +VY严 6下列有关范式的叙述中正确的是( )。瓤A 如果关系模式 RElNF ，且 R 中主属性完全函数依赖于主键，则R遵2NF蜂B如果关系模式RE3NF ，X，YOU ，若 X+Y ，则 R 是 BCNF C 如果关系模式REBCNF ，若 X+ 一 Y(Y篡 X) 是平凡的多值依

54、赖，簿斓R是4NF芝D 一个关系模式如果属于4NF ，则一定属于BCNF ；反之不成立酾7关系模式学生(学号，课程号，名次)，若每一名学生每门课程有一定辆名次，每门课程每一名次只有一名学生，则以下叙述中错误的是()。牲A (学号，课程号 )和 (课程号，名次 )都可以作为候选键驻D只有 (学号，课程号)能作为候选键弹巴关系模式属于第三范式D 关系模式属于BCNF8下列叙述中正确的是()。A若 X+ 一 Y ，其中Z 二 U X+Y ：中，则称X 一一 Y 为非平凡的多疽依赖且若 X ，一 Y ，其中Z： U X Y：中，则称X 一一 Y 为平凡的多值依赖巴对于函数依赖A1， A2， An B

55、来说，如果B 是 A 中的某一个，则称为非平凡函数依赖D对于函数依赖A1 ， A2 ， An B 来说，如果B 是 A 中的某一个，则称为平凡函数依赖9能消除多值依赖引起的冗余的是()。A 2NFa 3NFC 4NFa BCNF10下列叙述中正确的是()。丸第三范式不能保持多值依赖D第四范式肯定能保持多值依赖C BC 范式可能保持函数依赖D第四范式不能保持函数依赖11下列关于第四范式的叙述中错误的是()。丸第四范式条件实质上是BC 范式条件第四范式应用与多值依赖如果一个关系属于第四范式，则每个非平凡多值依赖实际上就是一个左边为超键码的函数依赖D属于BC 范式的每个关系都属于第四范式12以下叙述

56、中正确的是()。久函数依赖X Y 的有效性仅决定于两属性集的值；而多值依赖X 一一 Y 的有效性与属性集的范围有关D函数依赖X Y与多值依赖X+Y的有效性都决定于两属性集的值C 多值依赖X 一一Y 若在R(U)上成立，则对任何Y 三Y都有X 一一Y 成立D对于函数依赖X Y在R 上成立，不能断言对任何ycY均有X隘 r 成立醛：13关系数据库设计理论中，起核心作用的是()。蘸 A 范式D模式设计巳数据依赖D数据完整性醛爵二、填空题跹酽1关系数据库是以为基础的数据库，利用细述现实世界。一个关系既可以描述，也可以描述攥l+ 扛2在关系数据库中，二维表称为一个表的每一行称为卜：二，表的每一列称为。芝

57、3数据完整性约束分为和两类。黔4关系数据库设计理论，主要包括三个方面内容：、：二和。其中起着核心的作用。隘5X-,-Y 是模式 R 的一个函数依赖，在当前值，的两个不同元组中，如海X 值相同，就一定要求。也就是说，对于x 的每一个具体涕，都有与之对应。隘；6设 F 是关系模式R 的一个函数依赖集， X ，Y 是 R 的属性子集，如果熬，则称 F 逻辑蕴涵X Y ，记为。被F 逻辑蕴涵 g麴函数依赖的全体构成的集合，称为，记作。；：7设 U 是关系模式R 的属性集， X ， Y ， Z 是 U 的子集，则： FD 的自反律泌；增广律是；传递律是。函数依阳推理规则系统(自反律、增广律和传递律)是的

58、。 芝8关系模式 R(U) 上的两个函数依赖集 F 和予，如果满足酝，则称F 和 G 是等价的。芝9每个函数依赖集F 都可以被的函数依赖集G 所覆盖。酿lo将一个关系模式分解成多个关系模式时，为了保持原模式所满足的豪特性要求分解处理具有和11设 R 是一关系模式，分解成关系模式P R1 ， R2 ， Rk ， P 是 R 上的一个函数依赖集，如果对R 中满足F 的每一个关系，都有胆，N， j 称该分解P 相 Z F&“ xN 969”。臣12如果R 的分解为P Rl ， R2 ， F 为 R 所满足的函数依赖集合，分解P 具有无损联接性的充分必要条件是或。13，多值依赖的合并律是；伪传递律是；

59、分解律是。14对于函数依赖X Y，如果Y 巨 X，则称X Y 是一个。15对属性集U 上的一个多值依赖X+ 一 Y(X ， Y 是 U 的子集 )，如果，则称是一个平凡的多值依赖。16好的模式设计应符合、三条原则。三、问答题1关系规范化一般应遵循的原则是什么?2多值依赖与函数依赖有哪些主要的区别?3低级范式的关系模式对数据存储和数据操作产生的不利影响是什么?4 3NF 与 BCNF 的区别和联系各是什么?5设一关系为：学生(学号，姓名，年龄，所在系，出生日期)，判断此关系属性组属于第几范式。为什么?6下面的结论哪些是正确的?哪些是错误的?对于错误的请给出一个反例说明之。(1)任何一个二目关系是

60、属于3NF 。(2)任何一个二目关系是属于BCNF 。(3)任何一个二目关系是属于4NF 。(4)当且仅当函数依赖A+B 在 R 上成立，关系R(A ， B， C) 等与其投影Rl(A ， B)和凡 (A ， C)的连接。若 RARB， RB-R C，则民 A-*R C若 RARB， RA+兄 C，则 R A 一民 (B，C)若 RBRA RC+R A，则 R(B， C)一 RA若 R(B，C)一 RA，则 RB-R A，RCRA四、综合题1对给定的关系模式 R(U ， F)， U A ， B， C， D) ， F： A B， C D ， BC卧灿球 P、。胆： 2已知学生关系模式S(Sno，