第4章关系数据库规范化理论.

Page1第4章关系数据库规范化理论关系数据理论是关系数据库的理论基础，也是设计关系数据库的指南。本章计论关系数据理论的基本概念、方法和题解。如何设计数据库模式1)设计一个好的关系数据库模式（概念模式）——逻辑设计2)凭经验设计？3)什么是好的关系数据库模式？4)好的关系数据库模式应该包括多少关系模式？5)每个关系模式应该包含哪些属性？6)借助数学工具规定设计的理论和方法——规范化Page24.1为什么要规范化假设有如下关系STUDENT：STUDENT（NO,NAME,SEX,COUR,DEGE)表示学号,姓名,性别,课程,成绩其中NO,COUR是主关键字这个关系模式存在如下问题:数据冗余一个学生选修多门课程,导致NAME和SEX多次重复存储.不一致性由于数据存储冗余,当更新某些数据项时,就有可能一部分修改了,而另一部分未修改,造成数据不一致性插入异常如果某个学生未选课,他的信息(NO,NAME.SEX)就无法插入删除异常当要删除所有学生成绩时,将所有(NO,NAME,SEX)也都删除了,这便是删除异常Page3为了克服上述这些异常,将STUDENT分解为如下两个关系STUDENT(NO,NAME,SEX)SC(NO,COUR,DEGR)这是因为STUDENT关系中的某些属性间存在数据依赖,数据依赖是现实世界事物之间的相互关联性的一种表达,是属性固有语义的体现.人们只有对一个数据库所要表达的现实世界进行认真的调查与分析,才能归纳与客观事实相符合的数据依赖Page44.2函数依赖4.2.1函数依赖(FD)的定义函数依赖定义4-1设R(U)是一个关系模式,X,Y是R的两个属性集合,X,YR,R[X,Y]是关系R在属性X∪Y上的投影,当任何时刻R[X,Y]中的任意两个元组中的X属性值相同时,则它的Y属性值也相同,则称X函数决定Y,或称为Y函数依赖于X,记作X→Y例子(1)S(SNO,SN,AGE,SEX,DEPT)(2)SNO决定函数(SN,AGE,SEX,DEPT)(3)函数(SN,AGE,SEX,DEPT)依赖于SNO(4)SNO→(SN,AGE,SEX,DEPT)Page54.2.2函数依赖公理函数依赖的推导公理-Armstrong公理（阿姆斯特朗公理）设有关系模式R（U），X，Y，Z，WU，则：A1（自反性）：若YX，则X→YA2（增广性）：若X→Y，则XZ→YZA3（传递性）：若X→Y，Y→Z，则X→Z由Armstrong公理可以得到以下推论合成规则：若X→Y，X→Z，则X→YZ；分解规则：若X→YZ，则X→Y，X→Z；伪传递规则：若X→Y，YW→Z，则XW→ZPage64.2.3函数依赖的分类1)平凡函数依赖与非平凡函数依赖定义2在关系R(U)中,对于U的子集X和Y,如果X→Y,但Y不是X的了集,则X→Y是非平凡函数依赖.若Y是X的子集,则称X→Y为平凡函数依赖Page72)完全函数依赖与部分函数依赖设X→Y是一个FD,并且对于任何一个X’X,X’→Y不成立,则称X→Y是一个完全函数依赖,记作XY设X→Y是一个FD,并且存在一个X’X,使X’→Y成立,则称X→Y是一个部分函数依赖,记作XY示例1)SC(SNO,CNO,G)(SNO,CNO)→G是完全函数依赖(2)SC(SNO,CNO,SNAME,CNAME,G)SNO,CNO是主键(SNO,CNO)→GSNO→SNAMECNO→CNAME所以存在部分函数依赖Page83)传递函数依赖设X,Y,Z是R互不相同的属性集合X→Y，Y→X,且Y→Z则称属性集合Z传递(transfer)函数依赖于X,记作X→Z(1)UN(SNO,CN,G,DN,DM)(学号,课程名,成绩,系名,系主任)(2)SNO→DN(3)DN→SNO(4)DN→DM则DM传递函数依敕于SNOPage9引理：X→A1A2…AN成立的充分必要条件是X→AI成立(I=1,2,3….N)4.2.4函数依赖与属性关系如果X和Y之间是‘1-1’关系，则存在X→Y，Y→X如果X和Y之间是“多对1”关系，则存在X→Y如果X和Y之间是“多对多”，则X和Y不存在函数依赖Page10小结1)函数依赖是完整性约束的一种特殊形式2)函数依赖分为(1)完全函数依赖(2)部分函数依赖(3)传递函数依赖3)函数依赖是规范化理论的依据4)函数依赖是规范化程度的准则Page114.2.5函数依赖的闭包F+属性闭包及其计算函数依赖的闭包F+定义4-5关系模式R(U,F)中为F所逻辑蕴含的函数依赖的全体称为F的闭包,记为:F+例:关系模式S(U,F),其中U={SNO,SNAME,SEX,AGE}F={SNO→SNAME,SNO→SEX,SNO→AGE}Page12定义4-6设关系模式R(U),F为其函数依赖集,则称所有用Armstrong公理从F推出的函数依赖X→Ai中的Ai的属性集合为X的属性闭包,记作X+例:有关系模式S(SNO,SN,SEX,AGE)有SNO→SN,SNO→SEX,SNO→AGE则有SNO+=SNO,SN,SEX,AGE定理设关系模式R(U),F为其函数依赖集,X,YU,则从F推出X→Y的充分必要条件是Y∈X+Page13算法4-1求属性集X关于函数依赖F的属性闭包X+算法求属性的闭包X+输入X,F输出X+步骤(1)令X(0)=X,I=0(2)求B,B={A|(E)(W)(V→W∈F∧VX(I)∧A∈W}(A是这样的属性:在F中寻找尚未用过的左边是X(I)的子集的函数依赖)(3)X(I+1)=B∪X(I)(4)判断X(I+1)=X(I)吗?(5)若相等,或X(I)=U,则X(I)为属性集X的属性闭包.且算法终止(6)若不相等,则I=I+1,返回第2步.Page14属性闭包计算示例例1已知关系模式R(U,F),U={A,B,C,D,E};F={A→B,D→C,BC→E,AC→B}求(AE)+,(AD)+解求(AE)+设X(0)=AE计算X(1):逐一扫描F中的各个函数依赖,找出左部为A,E或AE的函数依赖,得到一个:A→B.故有X(1)=AE∪B=ABE计算X(2):逐一扫描F中的各个函数依赖,找到左部为A,B,E或AB,AE,BE,ABE的函数依赖,示发现有新的函数依赖X(2)=X(1)∪Ø=ABE有X(1)=X(2),算法终止,(AE)+=ABE(注:因为找不到新的函数依赖,即F中未用过的函数依赖的左边属性已没有X(1)的子集,所以,不必再计算下去,算法终止)练习求(AD)+Page15解求(AD)+X(0)=AD求X(1):逐一扫描F中的各个函数依赖,找出左部为A,D或AD的函数依赖,得到:A→B,D→C,故有X(1)=ABCD求X(2):逐一扫描F中的各个函数依赖,找出左部为ABCD或其子集的函数依赖,得到:BC→E,AC→B,故有X(2)=ABCDE因为X(2)=U,故算法终止,(AD)+=ABCDEPage16例2设有关系模式R(U,F),其中U={A,B,C,D,E,I};F={A→D,AB→E,BI→E,CD→I,E→C}计算(AE)+解:设X(0)=AE求X(1)在F的左部找出AE及其子集的函数依赖,有A→D,E→C所以X(1)=ACDE求X(2)在F的左部找出ACDE及其子集的函数依赖,新的依赖有CD→I所以X(2)=ACDEI求X(3)因为在F中未用过的函数依赖左边属性已没有X(2)的子集,所以不必再计算,即X(3)=X(2),算法终止(AE)+=ACDEIPage17练习设有函数依赖集F={D→G,C→A,CD→E,A→B}计算闭包D+,C+,A+,(CD)+,(AD)+,(AC)+,(ACD)+Page184.2.6最小函数依赖集及其算法1.等价与覆盖定义:一个关系模式R(U)上的两个依赖集F和G,如果F+=G+,则称F和G是等价的,记作FG.如果函数依赖集FG.则称G是F的一个覆盖,反之亦然两个等价的依赖集在表示能力上是完全相同的.Page194.2.6最小函数依赖集及其算法2.最小函数依赖集定义:对于给定的函数依赖F,当满足下列条件时,称为F的最小集,记作F′:1)F′的每个依赖的右部都是单个属性2)对于F′中的任何一个函数依赖X→A,F′-{X→A}与F′都不等价3)对于F′中的任何一个X→A和X的真子集Z,(F′-{X→A})∪{Z→A}与F′都不等价说明:条件(2)保证了在F中不存在多余的函数依赖;条件(3)保证了F中每个函数依赖的左边没有多余的属性Page204.2.6最小函数依赖集及其算法算法4-2计算最小依赖集输入:一个函数依赖集F输出:F的一个等价最小依赖集F′方法:(1)应用分解规则,使F中每一个依赖的右部属性单一化(2)去掉各依赖左部多余的属性.具体做法是:一个一个地检查F中左边是非单属性的依赖,例如XY→A,现在要判断Y是否为多余的,则以X→A代替XY→A是否等价?只要在F中求X+,若X+包含A,则Y是多余的属性;否则Y不是多余的属性.依次判断其他属性即可消除各依赖左边的多余属性.(3)去掉多余的依赖.具体做法是:从第一个依赖开始,从F中去掉它(假设该依赖为X→Y),然后在剩下的依赖中求X+,看X+是否包含Y,若是,则去掉X→Y;若不包含Y,则不能去掉X→Y.(4)这样依次做下去.Page21例设有依赖集:F={AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD,CE→AG}计算其等价的最小依赖集.解:(1)将依赖右边属性单一化,结果为F1=AB→CBE→CC→ACG→BBC→DCG→DACD→BCE→AD→ECE→GD→GPage22(2)在F1中去掉依赖左部多余的属性,因为有C→A,则对CE→A,E是多余的,对于ACD→B,若去掉A,由于(CD)+=ABCDEG,则A是多余的,删除依赖左部多余的依赖后:F2=AB→CBE→CC→ACG→BBC→DCG→DCD→BC→AD→ECE→GD→GPage23(3)在F2中去掉多余的依赖.对于CG→B,去掉他,仍有(CG)+=ABCDEG,则是多余的,删除多余的依赖后:F3=AB→CD→GC→ABE→CBC→DCG→DCD→BCE→GD→EAB→CBE→CC→ACG→BBC→DCG→DCD→BC→AD→ECE→GD→G注意：F的最小依赖集不一定是惟一的，它与对各函数依赖FD及X→A中X各属性的处理顺序有关。F3即是求得的最小函数依赖集F′Page244.2.7候选关键字的求解理论与算法候选关键字:属性或属性的最小组合,其值能够惟一地标识一个元组.对于给定的关系R(A1,A2,…An)和函数依赖集F,可将其属性分为四类:L类:仅出现在F的函数依赖左部的属性R类:仅出现在F的函数依赖右部的属性N类:在F的函数依赖左右两边均未出现的属性LR类:在F的函数依赖左右两边均出现的属性例:有关系模式R(A,B,C,D,E,F,P)R的函数依赖集为F={A→D,E→D,D→B,BC→D,DC→A,D→F}则L类属性有:CER类属性有:FLR类属性有:ABDN类属性:PPage251.快速求解候选关键字的充分条件定理对于给定的关系模式R及其函数依赖F,若X(X∈R)是L类属性,则X必为R的任一候选关键字的成员,若Y(Y∈R)是R类属性,则Y不在任何候选关键字中,若Z(Z∈R)是N类属性,则Z必包含在R的任一候选关键字中.推论1对于给定的关系模式R及其函数依赖集F，如果X是L类属性，且X包含了R的全部属性；则X必为R的惟一候选关键字推论2对于给定的关系模式及其函数依赖集F，如果X是R的N类和L类组成的属性集，且X+包含了R的全部属性，则X是R的惟一候选关键字Page26例1设有关系模式R（A,B,C,D),其函数依赖集F={D→B,B→D,A