关系数据理论 (2)优秀课件.ppt

《关系数据理论 (2)优秀课件.ppt》由会员分享，可在线阅读，更多相关《关系数据理论 (2)优秀课件.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系数据理论(2)第1页，本讲稿共92页第五章第五章规范化设计规范化设计 （8学时）学时）第七章第七章数据库设计数据库设计 （4学时）学时）第八章第八章 数据库的管理数据库的管理 （8 8学时）学时）第第九九章章分布式数据库系统分布式数据库系统 （4学时）学时）第十章第十章 对象关系对象关系数据库数据库（4学时）学时）习题分析、总复习习题分析、总复习（2学时）学时）数据库原理二数据库原理二数据库原理二数据库原理二课堂教学（课堂教学（课堂教学（课堂教学（3030学时学时学时学时)内容及安排：内容及安排：内容及安排：内容及安排：第2页，本讲稿共92页实验五实验五:编程实施学分制教务管理信息系统（编

2、程实施学分制教务管理信息系统（12学时）学时）(教材教材P.373)实验实验六：六：SQL Server 2000 高级技术使用高级技术使用（6学时）学时）(教材教材P.303)验验收：收：（2学时）学时）数据库原理二数据库原理二数据库原理二数据库原理二实验内容和安排（实验内容和安排（实验内容和安排（实验内容和安排（20202020学时）学时）学时）学时）第3页，本讲稿共92页 第五章第五章 规范化设计规范化设计本章讨论如何设计关系数据库的模式问题。本章讨论如何设计关系数据库的模式问题。关系数据库关系数据库规范化设计理论规范化设计理论即即“模式设计理论模式设计理论”数据依赖数据依赖研究数据之间

3、的联系研究数据之间的联系范范式式关系模式的标准关系模式的标准模式设计方法模式设计方法规范化的方法规范化的方法第4页，本讲稿共92页 本章重要概念本章重要概念:关系模式的一般形式和关系模式的冗余和异常问题。关系模式的一般形式和关系模式的冗余和异常问题。数据依赖的定义、数据依赖与关键码的联系；平凡的数据依赖的定义、数据依赖与关键码的联系；平凡的FD。关系模式的范式：关系模式的范式：1NF，2NF，3NF，BCNF。逻辑蕴涵、闭包、数据依赖的公理系统和推理规则；属性集的逻辑蕴涵、闭包、数据依赖的公理系统和推理规则；属性集的闭包；闭包；FD集的等价；最小依赖集。集的等价；最小依赖集。无损分解的定义、性

4、质、测试；保持依赖的分解定义。无损分解的定义、性质、测试；保持依赖的分解定义。分解算法：分解成分解算法：分解成3NF、BCNF模式集的算法。模式集的算法。MVD、4NF和和5NF的定义。的定义。第5页，本讲稿共92页1概述概述一、关系模式的一般形式一、关系模式的一般形式:R第6页，本讲稿共92页R其中：其中：U：为组成关系为组成关系R的全部属性的集合，即的全部属性的集合，即UA1,A2,An。D：为域的集合，即属性的取值范围的集合。为域的集合，即属性的取值范围的集合。Dom：为为U与与D之间的映象，即之间的映象，即Dom：UD|Dom安全约束集。安全约束集。F：为属性为属性U上的上的一组约束，

5、即数据依赖集。一组约束，即数据依赖集。例如：学习关系例如：学习关系SC中存在如下数据依赖：中存在如下数据依赖：（SNO,CNO）GRADE学生关系学生关系S中存在如下数据依赖：中存在如下数据依赖：SNOSNAME（SNO,SNAME）AGE第7页，本讲稿共92页关系模式一般形式可简化为：关系模式一般形式可简化为：R 泛关系模式泛关系模式满足上述满足上述制约条件制约条件F的关系用符号的关系用符号r 表示表示r 表示的关系称为表示的关系称为：泛关系泛关系例如例如:学习关系模式学习关系模式SC 其其中中:U=SNO,CNO,GRADE F=(SNO,CNO)GRADE 第8页，本讲稿共92页设计关系

6、数据库的核心问题是关系模式的设计。设计关系数据库的核心问题是关系模式的设计。对于一个数据库设计，可以有多个关系模式的选择。对于一个数据库设计，可以有多个关系模式的选择。按照什么原则来选择关系模式？按照什么原则来选择关系模式？标准是什么？标准是什么？如何实现？如何实现？第9页，本讲稿共92页二关系模式的存储异常问题二关系模式的存储异常问题在数据管理中在数据管理中,数据冗余一直是影响系统性能的大问题。数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在系统中多次重复出现。数据冗余是指同一个数据在系统中多次重复出现。例：例：SPJ_A(SNOSPJ_A(SNO，PNOPNO，JNOJNO，J

7、NAMEJNAME，JCITYJCITY，PRICEPRICE，QTY)QTY)属性分别表示属性分别表示:供应商号、供应商号、零件号、工程项目号、工程项目名称、零件号、工程项目号、工程项目名称、工程项目所在城市、零件单价、供应数量。工程项目所在城市、零件单价、供应数量。SPJ_ASPJ_A的一个实例：的一个实例：第10页，本讲稿共92页存在的存在的问题：问题：数据冗余数据冗余修改异常修改异常 插入异常插入异常 删除异常删除异常关系模式关系模式 SPJ_A SPJ_A 的一个实例：的一个实例：SPJ_A1SPJ_A1关系关系SNOSNOPNOPNOJNOJNOJNAMEJNAMEJCITYJCI

8、TYPRICEPRICEQTYQTYS1S1P1P1J1J1东方明珠东方明珠上海上海22.6022.608080S1S1P1P1J4J4明珠线明珠线上海上海22.6022.606060S1S1P3P3J1J1东方明珠东方明珠上海上海22.8022.80100100S1S1P3P3J4J4明珠线明珠线上海上海22.8022.806060S1S1P3P3J6J6南浦大桥南浦大桥上海上海22.8022.806 6S3S3P3P3J5J5炼钢工地炼钢工地天津天津22.1022.10100100S3S3P4P4J1J1东方明珠东方明珠上海上海11.9011.903030S3S3P4P4J4J4明珠线明珠

9、线上海上海11.9011.906060S3S3P4P4J6J6南浦大桥南浦大桥上海上海11.9011.906 6S4S4P2P2J4J4明珠线明珠线上海上海33.8033.806060S4S4P2P2J6J6南浦大桥南浦大桥上海上海33.8033.808 8S5S5P5P5J1J1东方明珠东方明珠上海上海22.8022.802020S5S5P5P5J4J4明珠线明珠线上海上海22.8022.806060S5S5P5P5J6J6南浦大桥南浦大桥上海上海22.8022.808 8S8S8P3P3J1J1东方明珠东方明珠上海上海13.0013.002020第11页，本讲稿共92页关系可定义为笛卡儿积

10、的一个子集，并不是每个子集都是有意义的。关系可定义为笛卡儿积的一个子集，并不是每个子集都是有意义的。对关系的值要作各种限制，这种限制称为数据完整性约束条件。对关系的值要作各种限制，这种限制称为数据完整性约束条件。数据完整性约束主要有两种：数据完整性约束主要有两种：1.依赖于值域的限制依赖于值域的限制-由由DBMS完整性子系统实现；完整性子系统实现；2.只依赖于属性间取值的相等与否的只依赖于属性间取值的相等与否的限制限制-仅取决于仅取决于两个元组的某些分量是否相等两个元组的某些分量是否相等-统称为数据依赖统称为数据依赖数据依赖描述的是属性与属性之间的对应关系。数据依赖描述的是属性与属性之间的对应

11、关系。2 2 函数依赖函数依赖第12页，本讲稿共92页一、一、函数依赖定义函数依赖定义定定 义义：设设 有有 关关 系系 模模 式式 R（A1,A2,An），X和和 Y是是 属属 性性 集集（A1,A2,An）的的子子集集，如如果果对对于于R的的任任何何一一个个关关系系r中中的的任任两两个个元元组组u和和v，对对应应于于X的的属属性性分分量量的的值值相相等等，而而对对应应于于Y的的属属性性分分量量的值也相等，即：只要有的值也相等，即：只要有uX=vX，就有，就有uY=vY，称，称“X函数确定函数确定Y”或称或称“Y函数依赖于函数依赖于X”,其符号表示为：其符号表示为：XYFD的确切语义的确切语

12、义：表示了关系模式集：表示了关系模式集X值与值与Y值的多对一联系。值的多对一联系。(SNO,PNO,JNO)(JNAME,JCITY).JNO(JNAME,JCITY)更明确地说：更明确地说：对于对于r r中属性或属性组中属性或属性组X X的每一个值，的每一个值，r r中中Y Y只有一个值与之对应。只有一个值与之对应。第13页，本讲稿共92页二、二、完全完全函数依赖函数依赖定义：定义：在关系模式在关系模式R（A1,A2,An）中，已知）中，已知XY,对于对于X中任中任何真子集何真子集X(X X)都不能函数确定都不能函数确定Y，称称 X X Y Y是完全函数依赖是完全函数依赖,用符号用符号XY表

13、示表示。完全依赖也称为完全依赖也称为“左部不可约依赖左部不可约依赖”。f三、部分函数依赖三、部分函数依赖定义：定义：在关系模式在关系模式R（A1,A2,An）中，已知）中，已知XY,如果存在一如果存在一个真子集个真子集X(X X)，满足，满足XY Y，则称，则称Y对对X是部分函数依赖，是部分函数依赖，用符号用符号XY表示。表示。p四、传递函数依赖四、传递函数依赖定义：定义：在关系模式在关系模式R（A1,A2,An）中，已知）中，已知XY，Y Y Z Z(Y X，Z Y不存在不存在YX X），），则则称称 X Z X Z 是传递函数依赖是传递函数依赖。t第14页，本讲稿共92页 定义定义:如果如

14、果A是关系模式是关系模式R的候选键的候选键K中属性，那么称中属性，那么称A是是R的的主属性主属性；否则称；否则称A是是R的非主属性。的非主属性。五、函数依赖和关键码的联系五、函数依赖和关键码的联系定义定义:设有关系模式设有关系模式R(A1,A2,An),K是属性集是属性集(A1,A2,An)的一个子集。如果的一个子集。如果KU（U完全函数依完全函数依赖于赖于K）在在R上成立，那么称上成立，那么称K K是是R R的一个的一个候选键候选键。f如果如果X U(K X)在在R R上成立上成立,那么称那么称X X是是R R的一个的一个超键超键。p第15页，本讲稿共92页3关系模式的范式关系模式的范式用什

15、么标准来衡量关系模式设计的好与坏用什么标准来衡量关系模式设计的好与坏？-关系模式的范式关系模式的范式(NormalForms,简记为简记为NF)。一、一、第一范式（第一范式（1NF）定义定义：如果关系模式如果关系模式R的每个关系的每个关系r的属性值都是不可分的属性值都是不可分 的原子值的原子值,那么称那么称R是是第一范式第一范式(firstnormalform)的模式。的模式。满足满足1NF的关系称为规范化的关系，否则称为非规范化的关系。的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。关系数据库研究的关系都是规范化的关系。第16页，本讲稿共92页既使关系模

16、式是既使关系模式是1NF，但很可能具有不受欢迎的冗余和异常现象。，但很可能具有不受欢迎的冗余和异常现象。因此需把关系模式作进一步的规范化。因此需把关系模式作进一步的规范化。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。二、二、第二范式（第二范式（2NF）定义定义:如果关系模式如果关系模式R 1NF,并且并且R中中每个非主属性都每个非主属性都完全函数依赖于完全函数依赖于R的候选键，的候选键，称称R是第二范式是第二范式（2NF）的模式。）的模式。第17页，本讲稿共92页三、第三范式（三、第三范式（3NF3NF）定义定义:如果关系模式如果关系模式R 1NF,并且并且R中

17、中每个非主属性每个非主属性都不传递依赖于都不传递依赖于R的候选键的候选键,那么称那么称R是第三是第三范式（范式（3NF）的模式。）的模式。如果数据库模式中每个关系模式都是如果数据库模式中每个关系模式都是3NF，则称，则称其为其为3NF的数据库模式。的数据库模式。在在3NF模式中，并未排除主属性对候选键的传递依赖，模式中，并未排除主属性对候选键的传递依赖，仍有可能有冗余和异常现象。仍有可能有冗余和异常现象。3NF分解第18页，本讲稿共92页四、四、BCNF模式模式定义：定义：如果关系模式如果关系模式R 1NF，并且，并且R中每个属性都中每个属性都不传递依赖于不传递依赖于R的候选键的候选键,那么称

18、那么称R是是BCNF的模式。的模式。由由BCNFBCNF的定义得出如下结论：的定义得出如下结论：1.非主属性对码完全函数依赖；非主属性对码完全函数依赖；2.主属性对不包含它的码也是完全函数依赖；主属性对不包含它的码也是完全函数依赖；3.没有属性完全依赖非码的任何属性组。没有属性完全依赖非码的任何属性组。如果数据库模式中每个关系模式都是BCNF，称其为BCNF的数据库模式。第19页，本讲稿共92页例如：关系模式例如：关系模式R(C,S,Z)其中其中C：城市名称：城市名称S：街道名称：街道名称Z：邮政编码邮政编码假定：假定：F=CSZ,ZCCSZ:表示地址表示地址(城市和街道城市和街道)决定决定邮

19、政编码邮政编码;Z Z C:C:表示表示邮政编码邮政编码决定决定城市名称城市名称。R的候选码为：的候选码为：CS和和SZ。第20页，本讲稿共92页R(C,S,Z)的候选码为：的候选码为：CS 和和SZ。由于由于F中存在中存在Z C:主属性主属性C对不包含它的码对不包含它的码SZ不是完全函数依赖，不是完全函数依赖，所以所以R(C,S,Z)不是不是BCNF模式，但模式，但R(C,S,Z)是是3NF，因为没有任何非主属性对码传递函数依赖或部分函数依赖。因为没有任何非主属性对码传递函数依赖或部分函数依赖。如果把如果把R(C,S,Z)分解为分解为:R1（S，Z）R2（Z,C）能解决冗余问题，而且能解决冗

20、余问题，而且R1，R2都是都是BCNF模式集。模式集。但丢失了但丢失了CSZ，数据语义将会引起新的矛盾。，数据语义将会引起新的矛盾。第21页，本讲稿共92页 4 4 数据依赖的公理系统数据依赖的公理系统 一、函数依赖一、函数依赖 FD FD 的逻辑蕴涵的逻辑蕴涵 F F 逻辑蕴涵逻辑蕴涵 XYXY，记为：记为：F F XYXY 。定义一：设定义一：设F是关系模式是关系模式R(A1,A2,An)上成立的函数依赖集，上成立的函数依赖集，X和和Y是属性集（是属性集（A1,A2,An）的子集）的子集，XY是一个其他的是一个其他的函数依赖。函数依赖。如果如果对于对于R的每个满足的每个满足F的关系的关系r

21、也满足也满足XY（或从（或从F推导出推导出XY也在也在R（U）上成立），）上成立），那么称那么称第22页，本讲稿共92页定义二：定义二：设设F F是关系模式是关系模式R R（A1,A2,An）上成立的函上成立的函数依赖集，数依赖集，X X和和Y Y是属性集是属性集（A1,A2,An）的子集，的子集，F的所有逻辑蕴涵组成的集合称为函数依赖集的所有逻辑蕴涵组成的集合称为函数依赖集F的闭包的闭包,记为记为F+。F+=XY|F XY 即：从给定的函数依赖集合即：从给定的函数依赖集合F推出的所有函数依赖组成推出的所有函数依赖组成 的集合，称为的集合，称为F的闭包。的闭包。第23页，本讲稿共92页二、二、

22、FD推理规则（推理规则（Armstrong公理）公理）设设U是关系模式是关系模式R的属性集，的属性集，F是是R上成立的一组函数依赖集上成立的一组函数依赖集X、Y分别是分别是U上的子集，存在上的子集，存在如下规则如下规则：1、FD公理（函数依赖公理）：公理（函数依赖公理）：自反性：自反性：若若Y X U，则，则XY在在R上成立。上成立。增广性：增广性：若若XY在在R上成立，且上成立，且Z U，则，则XZYZ在在R上成立。上成立。传递性：传递性：若若XY和和YZ在在R上成立，则上成立，则XZ在在R上成立。上成立。第24页，本讲稿共92页2、FD推理规则推理规则并规则：并规则：若若XY，XZ，则，则

23、XYZ。伪传递伪传递规则规则：若若XY，YWZ，则，则XWZ。分解规则：分解规则：若若XY，Z Y，则，则XZ。复合规则复合规则：若XY，WZ，则XWYZ。通用一致性定理通用一致性定理：若XY，WZ，则X（WY）YZ。从并规则和分解规则可得到下面的定理。从并规则和分解规则可得到下面的定理。定理:如果A1An是关系模式R的属性集，那么那么XA1An成立成立的充分必要条件是的充分必要条件是XAi（i=1，n）成立。）成立。第25页，本讲稿共92页例例:已知关系模式已知关系模式R(ABC),F=AB，BC,求求F+。答：根据函数依赖公理系统，可推出答：根据函数依赖公理系统，可推出F的的F+有有43个

24、个FD。其中：。其中：据自反性据自反性可得出可得出27个个FD：ABCABBCCAABCAABBCCABABCBCAAABCAABBBCCCACABCBABABBCBCCACAABCCABCABABCBCABCCAABCABC第26页，本讲稿共92页据增广性据增广性可得出可得出7个个FD：ABBCABC(AB，ABB,BC)AABBBCABABCCABC(CAA,AB,BBC)据传递性据传递性可得出可得出9个个FD：AC(AB，BC)CAB(CAA,AB)ACAABC(ACA,CABC)ABBC(ABA,ABC）CAAB(CAA,AAB)CAAB(CAA,AAB)ABCA(ABA,ACA)AA

25、BC(ACA,CAABC)第27页，本讲稿共92页在在实实际际使使用用中中，经经常常要要判判断断能能否否从从已已知知的的函函数数依依赖赖集集F推推导导出出函函数数依依赖赖XY，那么可先求出F的闭包F+，然后再看XY是否在F+中。但是从F求F+是一个复杂且困难的问题（NP完全问题，指数级问题）。下面引入属性集闭包概念，将使判断问题化为多项式问题。使判断问题化为多项式问题。定义三：定义三：对于函数依赖对于函数依赖XY，如果如果Y X，那么称，那么称XY是一个是一个“平凡的平凡的FD”；否则称为否则称为“非平凡的非平凡的FD”。平凡的FD并没有实际意义，根据自反性就可推出。我们感兴趣的是非平凡的FD

26、。只有非平凡的非平凡的FD与完整性约束条件相关。与完整性约束条件相关。第28页，本讲稿共92页三、属性集的闭包三、属性集的闭包定义：设F是属性集U上的FD集,X是U的子集，那么（相对于F）属性集X的闭包用XF+表示，它是一个从F集使用FD推理规则推出的所有满足XA的属性A的集合：X XF F+=A|A U，XA F+从属性集闭包的定义可得出下面的定理。从属性集闭包的定义可得出下面的定理。定理：定理：XY能用能用FD推理规则推出的充分推理规则推出的充分必要条件是必要条件是:Y X XF F+第29页，本讲稿共92页四、属性集四、属性集X的闭包的计算方法的闭包的计算方法输入：一个有限的属性集合输入

27、：一个有限的属性集合U；U上满足的函数依赖集合上满足的函数依赖集合F；U的一个子集的一个子集X。输出：输出：X关于关于F的闭包的闭包X XF F+。方法：根据下列规则计算属性集序列方法：根据下列规则计算属性集序列X（0），），X（1），），。、置初值置初值X（0）:=X,i=0；、X(i+1):=X(i)A|YZFA ZY X(i)、判断、判断X（i）=X（i+1）否？）否？若不等，若不等，置置X（i）=X（i+1）,i:=i+1转转若相等，若相等，计算终止，此时计算终止，此时X（i+1）就是所要求的属性集）就是所要求的属性集X关于关于F的闭包的闭包X XF F+。第30页，本讲稿共92页四、

28、属性集四、属性集X的闭包的计算方法的闭包的计算方法输入：一个有限的属性集合输入：一个有限的属性集合U；U上满足的函数依赖集合上满足的函数依赖集合F；U的一个子集的一个子集X。输出：输出：X 关于关于F 的闭包的闭包X XF F+。第31页，本讲稿共92页方法：根据下列规则计算属性集序列X（0），X（1），。、置初值、置初值X（0）:=X,i=0；、X(i+1):=X(i)A|YZFA ZY X(i)、判断、判断X（i）=X（i+1）否？）否？若不等，若不等，置置X（i）=X（i+1）,i:=i+1转转若相等，若相等，计算终止，此时计算终止，此时X（i+1）就是所要求的属）就是所要求的属性集性集

29、X关于关于F的闭包的闭包X XF F+。第32页，本讲稿共92页例例：设设U A,B,C,D,E,G，F=ABC，CA，BCBCD,ACDB,DEG,BEC,CGBD,CEAG 求求(BD)BD)F F+解：解：设设X=BD令：令：X(0)=BD 计算 X(1):=BDEG=BDEG;(DEG)计算 X(2):=BDEGC=BCDEG;(BEC)计算 X(2):=BCDEGA=ABCDEG;(CA,BCBCD,CGBD,CEAG)X(3)已包括所有属性，算法终止。(BD)BD)F F+=ABCDEG第33页，本讲稿共92页五、函数依赖集的等价和最小依赖集五、函数依赖集的等价和最小依赖集定义一定

30、义一:关系模式关系模式R(U)上的两个函数依赖集上的两个函数依赖集F和和G，如果如果F+=G+，称，称F和和G是等价的；是等价的；如果如果F和和G等价，称等价，称F覆盖覆盖G，或，或G覆盖覆盖F。定理：定理：F+=G+的充分必要条件是：的充分必要条件是：F G+且且G F+第34页，本讲稿共92页定义二：如果函数依赖集定义二：如果函数依赖集F满足下列三个条件满足下列三个条件,称称F为最小依赖集：为最小依赖集：F中每一个函数依赖的右边都是单属性中每一个函数依赖的右边都是单属性;-右端无冗余属性右端无冗余属性对于对于F中任一函数依赖中任一函数依赖XA，其，其FXA与与F不等价；不等价；-F中没有冗

31、余的函数依赖中没有冗余的函数依赖对于对于F中任一函数依赖中任一函数依赖XA，其，其FXAZA与与F不等不等价，其中价，其中Z X。-左端无冗余属性。左端无冗余属性。定理：任何一个函数依赖集定理：任何一个函数依赖集F至少存在一个最小函数依赖集至少存在一个最小函数依赖集Fmin。第35页，本讲稿共92页例：例：分析下列函数依赖集分析下列函数依赖集F1，F2，F3是否为最小函数依赖集。是否为最小函数依赖集。ADBCADACF1=BECF2=BAF3=ADBCHACCDBDDADC解析：解析：F1不是最小集，因为不是最小集，因为ADBC不满足条件不满足条件。F2不是最小集不是最小集,因为因为F2AC等

32、价于等价于F2，不满足条件，不满足条件。F3不是最小集，因为F3ADBDB等价于F3，不满足条件。(F3中：DA，ADB 由伪传递得DB)第36页，本讲稿共92页函数依赖集最小化处理的一般步骤：函数依赖集最小化处理的一般步骤：1、用分解规则消去函数依赖右端的冗余属性。、用分解规则消去函数依赖右端的冗余属性。(使使F中每一个函数依赖的右边都是单属性中每一个函数依赖的右边都是单属性).2、应用传递性应用传递性消去函数依赖集消去函数依赖集F中冗余的函数依赖。中冗余的函数依赖。(对于对于F中每一个函数依赖中每一个函数依赖XA,分别检验分别检验F与与FXA不等价不等价)3、应用伪传递应用伪传递规则消去函

33、数依赖左端的冗余属性。规则消去函数依赖左端的冗余属性。（对于（对于F中任一函数依赖中任一函数依赖XA，其，其FXAZA与与F不等价，不等价，Z X）。）。第37页，本讲稿共92页例例:设函数依赖集设函数依赖集F=AC,CA,AB,BA,BC，试求，试求Fmin。解：第一步：解：第一步：F已满足最小函数依赖集的第已满足最小函数依赖集的第个条件中。个条件中。第二步：对于第二步：对于F中每一个函数依赖中每一个函数依赖XA,分别检验分别检验F与与FXA是否等价是否等价;F中的中的AC（AB，BC，据传递性）是多余的，所以，据传递性）是多余的，所以AC可删去。得可删去。得F=AB，BA，BC，CA同样同

34、样F中中BA也是多余的（也是多余的（BC,CA）,BA可删去。可删去。得得F=AB，BC，CA第三步：消去函数依赖左端的多余属性：在本例中，第三步：消去函数依赖左端的多余属性：在本例中，F中每一中每一个函数依赖左端的都是单属性，不可再分。个函数依赖左端的都是单属性，不可再分。Fmin=AB，BC，CA第38页，本讲稿共92页例例:已知已知F=ADF=AD，BDBD，BDCABDCA，CDB CDB，求，求 F Fmin min 。第二步：消去函数依赖左端的冗余属性第二步：消去函数依赖左端的冗余属性(应用伪传递应用伪传递)由由BD,BDC,BD,BDC,可推出可推出BC,BC,所以所以BDCBD

35、C的左端的的左端的D D是多余的是多余的;由由BDBD，BDA,BDA,可可推推出出BA,BA,所所以以BDABDA的的左左端端的的D D是是多多余余的的;F2=F2=AD AD，BDBD，BCBC，BA,CDB BA,CDB 第三步：去除第三步：去除F中冗余的中冗余的FD(应用传递性应用传递性);由由 BABA，ADAD，可推出，可推出 BDBD，所以，所以 BD BD 是多余的。是多余的。F Fminmin=AD=AD，BCBC，BA,CDB BA,CDB 解解:第一步：第一步：应用分解规则得：应用分解规则得：F1=ADF1=AD，BDBD，BDCBDC，BDA,CDB BDA,CDB 第

36、39页，本讲稿共92页 解决的办法是：解决的办法是：对关系模式进行分解对关系模式进行分解 即：即：将一个模式分解为多个关系模式。将一个模式分解为多个关系模式。但在分解后又会出现新新的的问问题题，原原模模式式所所满满足足的的特特征征（如如属属性性之间的约束）在新模式中是否被保持；之间的约束）在新模式中是否被保持；即 模式的等价性问题模式的等价性问题。关系模式存在多余的函数依赖或者说模式不够规范，关系模式存在多余的函数依赖或者说模式不够规范，就有可能出现存储异常现象。就有可能出现存储异常现象。5 5 关系模式的分解关系模式的分解第40页，本讲稿共92页 等价性问题包括等价性问题包括:数据等价数据等

37、价和和依赖等价依赖等价两个方面两个方面:数数据据等等价价是是指指两两个个数数据据库库实实例例应应表表示示同同样样的的信信息息内内容容,用用“无无损损联联接接”来来衡衡量量。如果是无损联接分解，那么反复投影和自然联接都不会丢失信息。依依赖赖等等价价是是指指两两个个数数据据库库模模式式应应有有相相同同的的依依赖赖集集闭闭包包。在依赖集闭包相同的情况下，数据的语义是不会出差错的。一个违反数据等价或依赖等价的分解很难说是一个好的模式设计。第41页，本讲稿共92页一、模式分解问题一、模式分解问题定义：设有关系模式定义：设有关系模式R（U），），R1、Rk都是都是R的子集，的子集，U=R1Rk,关系模式关

38、系模式R1、Rk的集合用的集合用表示，表示，=R1，Rk,用用代替代替R的过程称为关系模式的过程称为关系模式R的分解。的分解。称为称为R的一个分解的一个分解,也称为数据库模式。也称为数据库模式。泛关系模式泛关系模式数据库模式数据库模式R=R1，Rkr=r1，rk泛关系泛关系(元组的集合）元组的集合）数据库实例（数据库）数据库实例（数据库）第42页，本讲稿共92页把把R分解成分解成的目的的目的:是为了消除数据冗余和操作异常现象。是为了消除数据冗余和操作异常现象。问题是：问题是：和和r是否表示同一个数据库。是否表示同一个数据库。如果两者表示不同的内容，那么这个分解就没有什么意义了。如果两者表示不同

39、的内容，那么这个分解就没有什么意义了。第43页，本讲稿共92页可以从两个角度来考虑分解：可以从两个角度来考虑分解：和和r是否等价是否等价:即是否表示同样的数据即是否表示同样的数据?用用“无损分解无损分解”特性表示。特性表示。在模式在模式R上有一个函数依赖集上有一个函数依赖集F，在，在的每一个模式的每一个模式Ri上上也有一个也有一个FD集集Fi，那么，那么F1，Fn与与F是否等价是否等价?用用“保持依赖保持依赖”特性表示。特性表示。第44页，本讲稿共92页 二、二、无损无损联接联接分解分解定定义义：如如果果R R是是一一个个关关系系模模式式,数数据据库库模模式式=R=R1 1，R Rk k 是是

40、R R的的一一个个分分解解,F,F是是R R上上成成立立的的一一个个函函数数依依赖赖集集。如如果果在在R R中中满满足足F F的的每每一一个关系个关系r r，都有下式成立：，都有下式成立：r=r=R1R1（r r）R2R2（r r）RkRk（r r）称分解称分解相对于相对于F F是是“无损联接分解无损联接分解”，否则称为，否则称为“损失分解损失分解”。其中：符号其中：符号 RiRi（r r）表示：表示：关系关系r r在模式在模式R Ri i属性上的投影。属性上的投影。r r的投影联接表达式的投影联接表达式R1R1(r r)Rk Rk(r r)用用符号符号m m(r r)表示：表示：Km m（r

41、 r）=RiRi（r r）i=1第45页，本讲稿共92页如如果果R是是一一个个关关系系模模式式，=R1,R2,，Rk是是关关系系模模式式R上上的的一一个个分分解解，r是是R上上的的任任一一关关系系，ri=Ri(r)（1ik）,则则有有下下列列性性质：质：r m(r);(r);若若s=ms=m(r),(r),则则RiRi(s)=r(s)=ri i;m(m(m(r)=m(r)=m (r);(r);幂等性。幂等性。第46页，本讲稿共92页三、无损联接的测试三、无损联接的测试算法算法1：输入：输入：关系模式关系模式R（A1,A2,An）,R上成立的函数依赖集上成立的函数依赖集F，R的一个分解的一个分解

42、=R1，R2，Rk。输出：输出：判断判断相对于相对于F是否具有无损联接特性。是否具有无损联接特性。具体步骤具体步骤:构造一张构造一张k行行n列列的表格的表格,每列对应一个属性每列对应一个属性Aj(1jn)，每行对应一个模式每行对应一个模式Ri(1ik)：如果如果Aj在在Ri中中，那么在表格的，那么在表格的第第i行第行第j列处填上符号列处填上符号aj，否则填上否则填上符号符号bij。第47页，本讲稿共92页反复检查反复检查F中的每一个函数依赖中的每一个函数依赖,并修改表格中的元素并修改表格中的元素,方法是：方法是：取取F中的一个函数依赖中的一个函数依赖XY，如果表格中有两行在如果表格中有两行在X

43、分量上相等分量上相等,在在Y分量上不相等，那么修改分量上不相等，那么修改Y，使这两行在使这两行在Y分量上也相等。分量上也相等。原则：原则：a.如果如果Y的分量中的分量中有一个是有一个是aj，那么另一个也修改成那么另一个也修改成aj；b.如果如果没有没有aj，那么那么用其中一个用其中一个bij替换另一个符号替换另一个符号（尽（尽量把下标量把下标ij改成较小的数）。改成较小的数）。一直到表格不能修改为止一直到表格不能修改为止（这个过程称为（这个过程称为Chase过程）。过程）。、若修改到最后、若修改到最后,一张表格中一张表格中有一行是全有一行是全a，即，即a1a2an,那么那么相对于相对于F是无损

44、联接分解是无损联接分解。第48页，本讲稿共92页例：设有例：设有R R（ABCDEABCDE），），F=ACF=AC，BCBC，CDCD，CEACEA，DECDEC，R R 的一个分解的一个分解 =AD=AD，ABAB，BEBE，CDECDE，AEAE，求求的分解无损性。的分解无损性。答：根据已知条件构造一张根据已知条件构造一张5行行5列的表格如下列的表格如下：jiABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5第49页，本讲稿共92页根据根据AC C，对表一进行处理，将，对表一进行

45、处理，将b23，b53改为改为b13，jiABCDEADa1b12b13a4b15ABa1a2b23 b13b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53 b13b54a5 再考虑再考虑BC，将，将b33改为改为b13;第50页，本讲稿共92页根据根据AC C，对表一进行处理，将，对表一进行处理，将b23，b53改为改为b13，再考虑再考虑BC，将，将b33改为改为b13;jiABCDEADa1b12b13a4b15ABa1a2b23 b13b24 b25BEb31a2b33 b13b34 a5CDEb41b42a3a4a5AEa1b52b53 b

46、13b54 a5第51页，本讲稿共92页根据根据AC C，对表一进行处理，将，对表一进行处理，将b23，b53改为改为b13，再考虑再考虑BC，将，将b33改为改为b13;然后考虑然后考虑C CD，将，将b24，b34，b54改为改为a4。修改后的表格如下：。修改后的表格如下：jiABCDEADa1b12b13a4b15ABa1a2b23 b13b24 a4b25BEb31a2b33 b13b34 a4a5CDEb41b42a3a4a5AEa1b52b53 b13b54 a4a5第52页，本讲稿共92页 在上表的基础上，考虑在上表的基础上，考虑DECDEC，将，将b b1313改为改为 a a

47、3 3;考虑考虑CEACEA，将，将b b3131,b b4141改为改为 a a1 1。由于由于 第三行为全第三行为全a,a,所以所以是无损联接。是无损联接。ABCDEADa1b12b13 a4b15ABa1a2b13a4b25BEb31 a a1 1a2b13 a a3 3a4a5CDEb41 a a1 1b42a3a4a5AEa1b52b13 a a3 3a4a5第53页，本讲稿共92页2、无损联接的测试、无损联接的测试算法算法2：如如果果R的的一一个个分分解解为为=R1,R2R1,R2，F为为R所所满满足足的的函函数依赖集合，分解数依赖集合，分解相对于相对于F F是无损分解的是无损分解

48、的充要条件是：充要条件是：R1R2 R1-R2R1R2 R1-R2 或或 R1R2 R2-R1R1R2 R2-R1第54页，本讲稿共92页例：试分析下列分解是否具有无损联接性：例：试分析下列分解是否具有无损联接性：设设R（ABC），），F=AB在在R上成立，上成立，1=AB，AC。52页页答：答：1相对于相对于F具有无损联接性。具有无损联接性。R1R2=ABAC=A；R1-R2=AB-AC=B；满足满足AB；模式模式1=AB，AC具有无损联接性。具有无损联接性。第55页，本讲稿共92页设设R(ABC),F=AB在在R上成立，上成立，2=AB，BC。答：答：22相对于相对于F3F3是有损分解：是

49、有损分解：R1R2=ABBC=B；R1-R2=AB-BC=A；不满足不满足AB；模式模式2=AB，BC是有损分解。是有损分解。第56页，本讲稿共92页四、保持函数依赖的分解四、保持函数依赖的分解如果关系模式在分解后不能保持函数依赖，如果关系模式在分解后不能保持函数依赖，那么在数据库中就会出现异常现象。那么在数据库中就会出现异常现象。所以，所以，关系模式关系模式R到到=R1，R2，Rk的分解，的分解，应使函数依赖集应使函数依赖集F被被F在这些在这些Ri上的投影所逻辑蕴涵。上的投影所逻辑蕴涵。这就是这就是保持函数依赖保持函数依赖问题。问题。第57页，本讲稿共92页定义一定义一:设设F是属性集是属性

50、集U上的函数依赖集上的函数依赖集,Z是是U上的一个子上的一个子集集,F在在Z上的一个投影用上的一个投影用Z（F）表示：表示：Z（F）=XY|XY F+X,Y X,Y Z定义二定义二:设设=R=R1 1,R,R2 2,，R Rk k 是关系模式是关系模式R R的一个的一个分解分解，F F是是R上的函数依赖集，如果上的函数依赖集，如果k k RiRi（F F）F Fi=1称称分解分解保持函数集保持函数集F。第58页，本讲稿共92页 k k k k从从定义一定义一可知可知F Ri（F），），从从定义二定义二可知可知Ri（F）F F，i=1k ki=1因此，在分解因此，在分解保持函数依赖情况下有保持函