数据库原理与应用关系规范化理论.pptx

14.1 4.1 问题的提出问题的提出关系模式 R(UR(U，D D，domdom，I I，F)F)数据依赖：关系中属性间互相依存、互相制约的关系。函数依赖函数依赖、多值依赖、连接依赖、分层依赖和相互依赖第1页/共93页2例：例：U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任,(学号，课程名称)成绩系部系部系主任系主任成绩成绩 学号学号课程名称课程名称第2页/共93页3缺点1、冗余太大2、操作异常 1）插入异常 2）删除异常 3）修改异常 学号系部 系主任 课程 名称成绩02101CSXAAA02101CSXBBB02101CSXCCA02102MAMAAB02102MAMDDA02103MAMEEC02104ISJEEB02105ISJBBA第3页/共93页4一、一、函数依赖：函数依赖：属性或属性组之间可能存在的依赖性。属性或属性组之间可能存在的依赖性。1、定义 定义定义4.14.1：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，当且仅当r中任意一个给定的X的值，r中存在唯一的Y值与之对应。也就是说，如果X相等，Y也相等，则称Y函数依赖与X，或者X函数确定Y，记作XY。第4页/共93页5定义4.3：R（U）的属性子集X，Y之间的函数依赖用X Y表示，它在构成关系R的任意元组r上指定了一个约束。这个约束是：如果对于r中的任何两个元组t1和t2有t1Xt2X，则必须也有t1Yt2Y。定义定义4.2：设设R(U)是属性集是属性集U上的关系模式，上的关系模式，X，Y是是U的子集。若对于的子集。若对于R(U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值不等，则称上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作，记作XY。第5页/共93页6例：例：U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任,(学号，课程名称)成绩注意：函数依赖不是指关系模式R的某个或某些关系满足的条件，而是指R的一切关系均要满足的约束条件第6页/共93页7由定义可以导出下列基本概念：1.1.决定因素：决定因素：若X Y，则X叫做决定因素 2.2.互相依赖：互相依赖：若X Y，Y X，则记作X Y。3.3.若若Y Y不函数依赖于不函数依赖于X X，则记作X Y。第7页/共93页8 定义4.4：平凡（非平凡）函数依赖 在R(U)中，一个函数依赖如果满足Y X，则称此函数依赖是非平凡函数依赖，否则称为平凡函数依赖。第8页/共93页9 定义4.5：完全函数依赖 在R(U)中，如果X Y，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖。记作：FXY 定义4.6：部分函数依赖 在R(U)中，如果X Y，存在真子集X，有X Y成立，则称Y对X部分函数依赖。记作：PXY第9页/共93页10定义定义4.74.7：传递函数依赖传递函数依赖 在在R(U)中，如果中，如果X Y，(Y X)，Y X，Y Z，则称，则称Z对对X传递函数依赖。传递函数依赖。第10页/共93页11系部系部系主任系主任成绩成绩 学号学号课程名称课程名称第11页/共93页12定义4.8：设K为R(U，F)中的属性或属性组，若 ，则K为R的候选码。FKU主码：主码：若候选码多于一个，则选定其中的一个为主码。主属性：主属性：包含在任何一个侯选码中的属性。非主属性：非主属性：不包含在任何码中的属性。全码：全码：整个属性组是码。定义定义6.6:6.6:关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码外码。主码与外码提供了一个表示关系间联系的手段。主码与外码提供了一个表示关系间联系的手段。第12页/共93页13三、第一范三、第一范式式(1NF)(1NF)定义4.9：满足关系的每一个分量是不可分的数据项这一条件的关系模式就属于第一范式(1NF)。缺点：插入异常、删除异常、冗余太大、修改复杂 学号系部 系主任 课程 名称成绩99101CSXAAA99101CSXBBB99101CSXCCA99102MAMAAB99102MAMDDA99103MAMEEC99104ISJEEB99105ISJBBA第13页/共93页14第二范式第二范式(2NF)(2NF)定义4.10：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。系部系部系主任系主任成绩成绩 学号学号课程名称课程名称第14页/共93页15成绩成绩系部系部系主任系主任 学号，系部，系主任 学号学号 学号学号课程名称课程名称 学号，课程名称，成绩第15页/共93页16第三范式第三范式(3NF)(3NF)定义4.11：关系模式R(U，F)中若不存在这样的码X，属性组Y及非主属性组Z(Z Y)使得XY，(Y X)Y Z成立，则称R(U，F)3NF。即：若R 3NF，且每一个非主属性既不部分依赖于码也不传递依赖于码。系部系部系主任系主任 学号学号若若R 2NF，且每一个非主属性，且每一个非主属性不传递依赖于码，则不传递依赖于码，则R 3NF。第16页/共93页17例：项目(编号，项目名称，负责人，职务，成员，任务情况)(假设:负责人无重名情况）编号编号成员成员负责人负责人项目名称项目名称任务情况任务情况职务职务第17页/共93页18任务（编号，成员，任务情况）项目（编号，项目名称，负责人，职务）编号编号成员成员任务情况任务情况编号编号负责人负责人项目名称项目名称职务职务任务任务项目项目第18页/共93页19编号编号成成 员员任务情况任务情况任务任务编号编号负责人负责人项目名称项目名称项目项目负责人负责人职务职务负责人职务第19页/共93页20例：分析下列关系属于第几范式 学生学习情况：（学号，姓名，班级，年龄，宿舍，系部，系主任，课程号，课程名，先修课程，成绩）第20页/共93页21学号课程号学号课程号姓名成绩先修课程课程名系主任系部宿舍年龄班级分析函数依赖关系：判断：属于1NF第21页/共93页22成绩学号+课程号姓名系部宿舍年龄班级学号系主任系部先修课程课程名课程号第22页/共93页23设有关系模式设有关系模式R（A，B，C，D），其），其数据依赖集：数据依赖集：F（A，B）C，CD，则关系模式，则关系模式R的规范化程度最的规范化程度最高达到（高达到（）。）。第23页/共93页24BCNF(扩充的扩充的3NF)定义：定义：关系模式R(U，F)1NF。若 XY且Y X时X必含有码，则R(U，F)BCNF。即：关系模式R(U，F)中，若每一个决定因素都包含码，则R(U，F)BCNF。第24页/共93页25所有非主属性对每一个码都是完全所有非主属性对每一个码都是完全函数依赖。函数依赖。所有主属性对每一个不包含它的码所有主属性对每一个不包含它的码也是完全函数依赖。也是完全函数依赖。没有任何属性完全函数依赖于非码没有任何属性完全函数依赖于非码的任何一组属性。的任何一组属性。一个满足一个满足BCNF BCNF 的关系模式有的关系模式有:第25页/共93页26例：关系模式SJP（S，J，P）S：学生 学生选修课程有一定的名次 J：课程 每门课程中每一名次只有一个学生 P：名次 （名次没有并列）函数依赖：（S，J）P （J，P）S 分析得知：SJP 3NF SJP BCNF第26页/共93页27例：关系模式STJ（S，T，J）S：学生 某一学生选定某门课，就对应一个固定教师 T：教师 每个教师只教一门课 J：课程 每门课有若干教师 函数依赖：（S，J）T T J （S，T）J)分析得知：STJ 3NF 但是：STJ BCNF 因为：STJ可以分解为：ST（S，T）TJ（T，J）第27页/共93页28消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖1NF1NF2NF2NF3NF3NFBCNFBCNF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖第28页/共93页29指出下列关系模式属于第几范式，并说明理由指出下列关系模式属于第几范式，并说明理由。(1)R（X,Y,Z）FXY Z(2)R（X,Y,Z）FY Z,XZ Y(3)R（X,Y,Z）FY Z,Y X,X YZ第29页/共93页30假设某旅馆业务规定，每个账单对应一个顾客，账单的发票号是惟一的，账单中包含一个顾客姓名、到达日期和顾客每日的消费明细，账单的格式如图所示:试回答下列问题：(1)找出R的候选键。(2)判断R最高可达到第几范式，为什么?第30页/共93页31配件管理关系模式 WPE（WNO，PNO，ENO，QNT）分别表仓库号，配件号，职工号，数量。有以下条件 a.一个仓库有多个职工。b.一个职工仅在一个仓库工作。c.每个仓库里一种型号的配件由专人负责，但一个人可以管理几种配件。d.同一种型号的配件可以分放在几个仓库中,一个仓库可以存放多种型号的配件。请问：关系模式WPE最高可达几范式？1 ENO WNO2 WNO,PNO ENO3 WNO,PNO QNT候选码1(WNO，PNO)为候选码2 因为ENO，PNO WNO 所以（ENO，PNO）为候选码第31页/共93页32定义定义4.15 逻辑蕴含逻辑蕴含定义：对于R(U,F)，如果XY不在F中，但是对于其任何一个关系r，XY都成立，则称F逻辑蕴含XY。或者说：或者说：XYXY可以由可以由F F导出导出 例：关系模式R(U，F)其中U(A，B，C，D，E，F，G)F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE第32页/共93页33ArmstrongArmstrong公理系统公理系统 对于关系模式R(U，F)，有公理1：自反律自反律(Reflexivity)(Reflexivity)若Y X U，则XY为F所蕴含。公理2：增广律增广律(Augmenttation)(Augmenttation)若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。公理3：传递律传递律(Transitivity)(Transitivity)若XY，YZ为F所蕴含，则XZ为F所蕴含。自反律、增广律、传递律是最基本的Armstrong公理。第33页/共93页34公理4：合并规则 由XY，XZ，有XYZ。公理5：伪传递规则 由XY，WYZ，有XWZ公理6：分解规则 由XY及 Z Y，有XZ。由自反律、增广律、传递律可以导出下面三条推理规则。第34页/共93页35例：关系模式R(U，F)其中U(A，B，C，D，E，F，G)F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE解：解：AB （已知）AAB（增广率）ABE （已知）AE （传递率）第35页/共93页364.3.2函数依赖集闭包和属性集闭函数依赖集闭包和属性集闭包包定义 4.16 F的闭包定义：在关系模式R(U，F)中为F及F所逻辑蕴含的函数依赖的全体叫做F的闭包。记为F+。F+=X Y|F及能由F根据Armstrong公理导出第36页/共93页37X关于函数依赖集F的闭包定义：设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。定义定义 4.174.17 第37页/共93页38【例】设关系模式R（A、B、C）的函数依赖集为F=A B,B C，分别求A、B、C的闭包。若X=A，AB，BC（已知）AC （传递律）AA （自反律）XF+=A，B，C若X=B，BB BC XF+=B，C若X=C，CC XF+=C第38页/共93页39设F为属性集U上的一组函数依赖关系，X，Y U，X Y能 由 F根 据Armstrong公理导出的充分必要条件是Y XF。定理定理 4.2：第39页/共93页40求XF+的算法算法：输入：X，F 输出：XF+(1)令X(0)=X，i=0(2)求B,B=A|(V)(W)(VWFVX(i)AW)(3)X(i+1)=BX(i)(4)判断X(i+1)=X(i)吗？(5)若相等或X(i)=U则X(i)就是XF+，算法终止。(6)若否，则i=i+1，返回第(2)步。算法算法 4.1：第40页/共93页41例1：已知关系模式R(U，F)，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB求(AB)F+。解：1：X(0)=AB 2：计算X(1)=X(0)C D=ABCD 3：求X(2)=X(1)E B=ABCDE 4：由于X(2)已经等于全部属性集合所以 (AB)F+=ABCDE找出左部为A，B或AB的函数依赖第41页/共93页42例2：已知关系模式R(U，F)，其中U=A，B，C，D，E，F，G，H；F=AD，ABE，BHE，CDH，EC令X=AE，求X+。解：1：X(0)=AE 2：X(1)=X(0)D C=AECD 3：X(2)=X(1)H=ACDEH 4：X(3)=ACDEH不变，即X(3)=X(2)所以 X+=(AE)+=ACDEH第42页/共93页43定理：定理：Armstrong公理系统是有效的、完备的。有效性：有效性：指由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+。完备性：完备性：指F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。第43页/共93页444.3.3 4.3.3 函数依赖集的等价和函数依赖集的等价和最小函数依赖集最小函数依赖集定义定义4.184.18 如果G+=F+，则称F与G等价，记为F=G。F+=G+的充分必要条件是F G+且G F+第44页/共93页45例：R(U)U=ABC F=AB，BC，AC，ABC,A BC可以写成：G=AB，BC证明：1：AB，BC 传递规则 AC 2：AB，扩展ABBB 即 AB B 再由BC 所以 ABC3：AB，BC 扩展 BBC 所以 A BCF与G等价第45页/共93页46定义定义 4.194.19：最小依赖集定义：最小依赖集定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，也称最小依赖集或最小覆盖。1)F中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖XA，使得 F与F-X A等价。不存在冗余FD3)F中不存在这样的函数依赖XA，X有真子集Z使得F-X AZA与F等价。决定因素不存在冗余第46页/共93页47例：U=SNO，SDEPT，MN，CNAME，G F=SNO SDEPT，SDEPT MN，SNO，CNAME G 设F=SNO SDEPT，SNO MN，SDEPT MN，(SNO，CNAME)G，(SNO，SDEPT)SDEPT结论：结论：F与 F 等价 F是最小覆盖，F不是。第47页/共93页48算法 4.2求Fm（F的最小依赖集）的算法(1)将XA1A2Ak(k2)转换为XAi(i=1,2,k)将右部属性分解为单个属性(2)逐个检查函数依赖XA，令G=F-XA，若A(X)G+，则从F中去掉XA。逐个检查F中的每一项，看是否F-XA与F等价(3)逐个检查函数依赖XA，若X=B1B2Bm，逐个考查Bi(i=1,2,m)，若A(X-Bi)F+，则以X-Bi取代X。判每个函数依赖左部是否有冗余属性第48页/共93页49例：将下列函数依赖集F划为最小函数依赖集。F=AB，BA，BC，AC，CA解：1：分解为单个属性F1=F 2：消去F中冗余的函数依赖考察AB：令X=A 求X+=？X(0)=A X(1)=AC=X+因为B不属于X+所以AB不冗余。考察BA：令X=B 求X+=？X(0)=B X(1)=BC X(2)=ABC=X+因为A属于X+所以BA冗余。考察BC：令X=B 求X+=？X(0)=B X(1)=B=X+因为C不属于X+所以BC不冗余。第49页/共93页50考察AC：令X=A 求X+=？X(0)=A X(1)=AB X(2)=ABC=X+因为C属于X+所以AC冗余。考察CA：令X=C 求X+=？因为A不属于X+所以CA不冗余。因此 3：判每个函数依赖左部是否有冗余属性F=AB，BA，BC，AC，CAF m=AB，BA，AC，CA思思考考F2=AB，BC，CA第50页/共93页51 设有关系模式R（A，B，C，D），其上的函数依赖集为：FA C,C A，B AC，D AC，求F的最小覆盖。第51页/共93页52假定我们要够造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖集F如下：F=BCDA，BCE，AF，FG，CD，AG.找出这个函数依赖集的最小覆盖G第52页/共93页534.4 4.4 关系模式的分解关系模式的分解 n 模式分解等价性的三个判定准则模式分解等价性的三个判定准则 n分解的无损连接性和函数依赖保持性分解的无损连接性和函数依赖保持性 n模式分解的算法模式分解的算法第53页/共93页54T#TDDHT#TDDHT1T2T3T4D1D1D2D3AAAABBCC 设一关系模式R(T#，TD，DH)，其中T#表示教师编号，TD表示教师所属系部，DH表示系主任名。假定每位教师只能在一个系任教，每个系只有一位系主任。第54页/共93页55分解1：1=R1(T#)，R2(TD)，R3(DH)分解2：2=R1(T#，TD)，R2(T#，DH)分解3：3=R1(T#，TD)，R2(TD，DH)第55页/共93页56分解分解 1：T#T1T2T3T4R1R2TDD1D2D3R3DHAABBCC问题：T1是哪一个系的教师？无法回答。R1，R2，R3也无法恢复到原来的R。第56页/共93页57分解分解 2：T#T1T2T3T4R1TDD1D1D2D3T#T1T2T3T4R2DHAAAABBCC此时，R1，R2的分解是可恢复的，但仍然存在操作异常。原因：TDDH 在R1，R2中没有体现。第57页/共93页58分解分解 3：T#T1T2T3T4R1TDD1D1D2D3TDR2DHD1D2D3AABBCC此时，R1，R2的分解是可恢复的，并且消除了操作异常。第58页/共93页59 关系模式R被分解为两个投影R1和R2是独立的，当且仅当：1 R中的每个函数依赖都可由R1和R2的函数依赖导出。2 R1和R2中的公共属性至少是R1和R2 中某个关系的侯选码。第59页/共93页604.4.2 4.4.2 无损连接和函数依赖保持无损连接和函数依赖保持一、分解的无损连接性：一、分解的无损连接性：如果一个关系模式分解后，可以通过自然如果一个关系模式分解后，可以通过自然连接恢复原模式的信息，这一特性称为分解连接恢复原模式的信息，这一特性称为分解的无损连接性。的无损连接性。第60页/共93页61Tij=aj，如果如果AjRibij，如果如果AjRi1)构造一个n列k行的二维表T。=R1(U1,F1),Rk(Uk,Fk)是R(U,F)的一个分解，U=A1,An，F=FD1,FD2,FDp。算法算法 4.34.3 判定分解的无损连接性判定分解的无损连接性第61页/共93页622)根据F中函数依赖修改表T的内容。修改规则：修改规则：逐个考察F中的每个函数依赖XY，在属性X所在的那些列上找出具有相同符号的行，在这些行上使对应于Y的各属性列位置上的符号改为相同，如果其中有一个符号为a aj j，则把其它符号也改为 a aj j，否则改为b bmjmj，其中m是这些行的最小行号。直至在表中发现一行已变成a a1 1a a2 2a ak k，或表不能再进行修改为止。第62页/共93页633)如果发现表中有一行已变成a1a2ak，则表示该分解具有无损连接性，否则分解不是无损连接的。例：已知 R(U，F)U=A，B，C，D，E，F，F=ABC,CD，AF，DE，DF R的一个分解为：=R1(A，B，C)，R2(C，D)，R3(D，E，F)判断是否具有无损连接性。第63页/共93页64ABCDEFa1b21b31a2b22b32a3a3b33b14a4a4b15b25a5b16b26a6第一步：建第一步：建T=R1(A，B，C)R2(C，D)R3(D，E，F)Tij=aj，如果如果AjRibij，如果如果AjRi第64页/共93页65 第二步：逐个考察函数依赖，并修改表。(1)ABC,(2)CD,(3)AF,(4)DE,(5)DFa4a5a5ABCDEFa1b21b31a2b22b32a3a3b33a4a4a5a6b14b16b15b25b26a6a6由于没有相同的分量，所以表不改变第65页/共93页66 1=R1(T#)，R2(TD)，R3(DH)2=R1(T#，TD)，R2(T#，DH)3=R1(T#，TD)，R2(TD，DH)1 T#TD DH a1 b12 b13 b21 a2 b23 b31 b32 a3具有无损连接性具有无损连接性 2T#TD DH a1 a2 b13 a1 b22 a3 3 T#TD DH a1 a2 b13 b21 a2 a3具有无损连接性具有无损连接性第66页/共93页67练习 设有关系模式R(B,O,I,S,Q,D)，其函数依赖集为：F=SD,IB,ISQ,BO,如果将R分解为R1=SD,R2=IB,R3=ISQ,R4=BO,这样的分解是否具有无损连接性？第67页/共93页68BOISQDSDb11b12b13a4b15a6IBa1b22a3b24b25b26ISQb31b32a3a4a5b36BOa1a2b43b44b45b46第68页/共93页69BOISQDSDa4a6IBa1a3ISQa1a2a3a4a5a6BOa1a2F=SD,IB,ISQ,BO第69页/共93页70 设设=R1，R2是关系模式是关系模式R的一个分解，的一个分解，F是是R的一个函数依赖集，则对于的一个函数依赖集，则对于F，具有具有连接不失真性的充分必要条件是：连接不失真性的充分必要条件是：R1R2R1-R2F+或或 R1R2R2-R1F+。定理定理4.4:4.4:第70页/共93页71二、分解的函数依赖保持性：关系R(U,F)的一个分解表示为=R1(U1,F1),Rk(Uk,Fk)其中，Fi=定义：设关系模式R，F是R上的函数依赖集，Z是R上的一个属性集合，则称Z所涉及到得F+中的所有函数依赖为F在Z上的投影，记为第71页/共93页72二、分解的函数依赖保持性：若关系R(U,F)的一个分解=R1(U1,F1),Rk(Uk,Fk)的所有函数 依赖的并集 逻辑蕴涵了F中所有 函数依赖，即 =F+，则称分解具有函数依赖保持性。i=1k(Fi)i=1k(Fi)+第72页/共93页73例：关系模式R(U，F)U=A，B，C，DF=AB，BC，CD，DA分解=R1(A，B)，R2(B，C)，R3(C，D)是否具有函数依赖保持性？其中：F1U1(F)=(AB,BA)F2 U2(F)=(BC,CB)F3 U3(F)=(CD,DC)第73页/共93页74 F1F2 F3=AB,BA,BC,CB,CD,DC F=AB，BC，CD，DA因为(F1F2 F3)+=F+所以 分解具有函数依赖保持性。第74页/共93页75练习 设有R（U，F），其中，U=A，B，C，D，F，F=AC，BC，CD，DFC，CFA，R的一个分解为：R1=AB，R2=AD，R3=AF，R4=BF，R5=CDF，判断该分解是否具有函数依赖保持性。第75页/共93页76算法算法4.54.5：结果为结果为3 3NFNF的依赖保持分解算法的依赖保持分解算法 如果如果R R中有某些属性与中有某些属性与F F的最小覆盖中的每个依赖的左边和的最小覆盖中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从右边都无关，原则上可由这些属性构成一个关系模式，并从R R中将它们消除；否则，中将它们消除；否则，如果如果FF中有一个依赖涉及到中有一个依赖涉及到R R的所有属性，则输出的所有属性，则输出R R；否则，否则，输出一个分解输出一个分解，它由模式，它由模式XAXA组成，其中组成，其中XA XA F。但当。但当XA1XA1，XA2XA2，XAn XAn 均属于均属于FF时，则用模式时，则用模式XA1 XA1 A2AnA2An代替代替XAiXAi（i=1i=1，2 2，n n）。）。第76页/共93页77假定我们要够造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖集F如下：F=BCDA，BCE，AF，FG，CD，AG.求R R的一个满足3NF3NF的函数依赖保持分解举举 例例第77页/共93页78举举 例例 1 求求F的最小覆盖的最小覆盖FmBC AE,AF,FG，CD2 条件（条件（1）不满足）不满足 3 条件（条件（2）不满足）不满足 4 根据条件（根据条件（3）输出）输出 =BCAE,AF,FG,CD第78页/共93页79算法算法4.64.6：结果为结果为3 3NFNF的依赖保持和连接不失真分解的依赖保持和连接不失真分解 设设是是由由结结果果为为3NF3NF的的依依赖赖保保持持分分解解算算法法得得到到的的3NF3NF分分解解，X X为为R R的的一一个个候候选选关关键键字字，则则=X=X是是R R的的一一个个分分解解，且且中中的的所所有有关关系系模模式式均均满满足足3NF3NF，同同时时，既既具有连接不失真性，又具有依赖保持性。具有连接不失真性，又具有依赖保持性。第79页/共93页80 对对于于给给定定的的关关系系R R（A1A1，A2A2，AnAn）和和函函数数依依赖集赖集F F，可将其属性分为，可将其属性分为4 4类：类：n L L类类 仅出现在仅出现在F F的函数依赖左部的属性的函数依赖左部的属性n R R类类 仅出现在仅出现在F F的函数依赖右部的属性的函数依赖右部的属性n N N类类 在在F F的函数依赖左右两边均未出现的属性的函数依赖左右两边均未出现的属性n LRLR类类 在在F F的函数依赖左右两边均出现的属性的函数依赖左右两边均出现的属性第80页/共93页81定理定理1 对于给定的关系对于给定的关系模式模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是L L类类属性，则属性，则X X必是必是R R的候的候选码的成员。选码的成员。定理定理3 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是R R类属性，则类属性，则X X不在任何候选码中。不在任何候选码中。定理定理2 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是NN类属性，类属性，则则X X必是必是R R的候选码的成的候选码的成员。员。第81页/共93页82候选码求解推论候选码求解推论 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是R R的的L L类或类或N N类属性组成的属性类属性组成的属性集，且集，且X X包含了包含了R R的全部属性，则的全部属性，则X X是是R R的唯一的唯一候选码。候选码。第82页/共93页83设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：FAD,ED,DB,BC D,DC A,求R的候选码。举例举例：因因为为 CC，E E是是L L类类属属性性，P P是是N N类类属属性性，所所以以CEPCEP包含在所有候选码中；包含在所有候选码中；因为因为 （CEPCEP）ABCDEPABCDEP；所以所以 CEPCEP是是R R的唯一候选码。的唯一候选码。第83页/共93页84假定我们要够造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖集F如下：F=BCDA，BCE，AF，FG，CD，AG.求R R的一个满足3NF3NF的无损连接和函数依赖保持的分解举举 例例第84页/共93页85 1 求求F的最小覆盖的最小覆盖FmBC AE,AF,FG，CD2 R的满足的满足3NF且函数依赖保持的分且函数依赖保持的分解为：解为：=BCAE,AF,FG,CD 3 R的候选码为：的候选码为：BC 4 R的满足的满足3NF且函数依赖保持和无损且函数依赖保持和无损连接的分解为：连接的分解为：=BCAE,AF,FG,CD第85页/共93页86设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：FCB,ED,DB,B D,BC D,DC A,求R的一个满足3NF的无损连接和函数依赖保持的分解举举 例例第86页/共93页87第一步：求最小函数依赖集第一步：求最小函数依赖集FmFm=C B,E D,D B,B D,DC A第二步：求基于第二步：求基于3NF的函数依赖保持的分解的函数依赖保持的分解=CB,ED,DB,DCA第三步：求候选码第三步：求候选码XX=CEP第四步第四步:求基于求基于3NF的函数依赖保持和连接不失真的分解的函数依赖保持和连接不失真的分解=CB,ED,DB,DCA,CEP第87页/共93页881）若要求连接不失真，分解可达到BCNF；2）若要求依赖保持，则分解可达到3NF，但 不一定能达到BCNF。3）若同时要求连接不失真和依赖保持，则 分解可达到3NF，但不一定能达到BCNF。模式分解的几个重要事实模式分解的几个重要事实：第88页/共93页89为什么要规范化为什么要规范化非形式化判定准则非形式化判定准则 形式化判定（规范化理论）形式化判定（规范化理论）1NF1NF、2NF2NF、3NF3NF、BCNFBCNF 模式分解（等价性的判定：连接不失真性、依赖保持性）模式分解（等价性的判定：连接不失真性、依赖保持性）函数依赖集等价函数依赖集等价F F+=G=G+（=F=F+）连接不失真性连接不失真性的判定的判定 i=1k(Fi)+第89页/共93页90 分解算法分解算法 函数依赖保持的函数依赖保持的3NF3NF分解分解 连接不失真和函数依赖保持的连接不失真和函数依赖保持的3NF分解分解 求最小覆盖求最小覆盖Fm 求候选码求候选码 属性集闭包属性集闭包XF+第90页/共93页91模式规范化目的：模式规范化目的：1）消除异常现象。2）方便用户使用，简化检索操作。3）加强数据独立性，即当引入一个新数据项时，减少对原有数据结构的修改。4）使关系模式更灵活，更容易使用非过程化的高级查询语言。5）更容易进行各种查询统计工作。第91页/共93页921已知 U=A，B，C，D，E，I，F=AD，ABE，BIE，CDI，EC，计算（AE）+。2设有关系模式R（A，B，C，D），其上的函数依赖集为：FAC，CA，BAC，DAC 1）计算（AD）2）求R的码3设有依赖集：F=ABC，CA，BCD，ACDB，DEG，BEC，CGBD，CEAG 求：Fm4已知R（A1,A2,A3,A4,A5）为关系模式，其上函数依赖集为：F=A1A3,A3A4,A2A3,A4A5A3,A3A5A1=R1(A1,A4),R2(A1,A2),R3(A2,A3),R4(A3,A4,A5),R5(A1,A5)判断是否具有无损连接性。第92页/共93页93谢谢您的观看！第93页/共93页