04 关系数据库的规范化设计.ppt

第第4章章 RDB的规范化设计的规范化设计王传栋王传栋南京邮电大学计算机学院软件工程系南京邮电大学计算机学院软件工程系内容提纲内容提纲n1）关系模式的设计问题）关系模式的设计问题q内涵与外延内涵与外延q冗余和异常冗余和异常n2）函数依赖）函数依赖qFD定义、逻辑蕴涵、闭包、推理规则定义、逻辑蕴涵、闭包、推理规则qFD与关键码的联系与关键码的联系q平凡的平凡的FD，属性集闭包，推理规则的正确性和完备性属性集闭包，推理规则的正确性和完备性qFD集的等价，最小集的等价，最小FD集集n3）关系模式的分解特性）关系模式的分解特性q无损分解无损分解q保持依赖集保持依赖集2Chd.Wang，E-Mail：C内容提纲内容提纲n4）关系模式的范式）关系模式的范式q1NF，2NF，3NF，BCNFq算法算法n分解成分解成2NF、3NF模式集模式集n5）关系模式的进一步规范化处理）关系模式的进一步规范化处理qMVD、4NF、JD和和5NF的定义的定义3Chd.Wang，E-Mail：C引言引言n关系关系DB的规范化设计的规范化设计q是指面对一个现实问题（是指面对一个现实问题（问题域问题域），如何选择一个比较好的关），如何选择一个比较好的关系模式集合（系模式集合（求解域求解域：DB的实现方案，也称数据库模式）的实现方案，也称数据库模式）q规范化设计理论，对关系数据库结构的设计起着重要的作用，规范化设计理论，对关系数据库结构的设计起着重要的作用，涉及涉及3个方面的内容：个方面的内容：n数据依赖数据依赖q起着核心作用，研究数据之间的联系起着核心作用，研究数据之间的联系n范式（范式（NF）q关系模式的标准关系模式的标准n模式设计方法模式设计方法q自动化设计的基础自动化设计的基础4Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n外延和内涵外延和内涵q外延，外延，与时间有关，随时间推移不断变化与时间有关，随时间推移不断变化n通常指关系、表或当前值通常指关系、表或当前值q内涵，内涵，与时间是独立的，与时间是独立的，通常指关系模式，包括通常指关系模式，包括2个方面个方面n数据的定义：数据的定义：关系、属性、域的定义和说明关系、属性、域的定义和说明n数据完整性约束的定义数据完整性约束的定义q静态约束，涉及到数据之间联系（称为数据依赖，静态约束，涉及到数据之间联系（称为数据依赖，data dependences）、）、主键和值域的设计主键和值域的设计q动态约束，定义各种操作（插入、删除、修改）对关系值动态约束，定义各种操作（插入、删除、修改）对关系值的影响的影响5Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n冗余和异常冗余和异常q问题域：学生选修课程问题域：学生选修课程q泛关系模式泛关系模式nR（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit,CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）q泛关系泛关系6Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n冗余和异常冗余和异常q数据冗余是指同一个数据在系统中多次重复出现数据冗余是指同一个数据在系统中多次重复出现q数据冗余引起操作异常数据冗余引起操作异常n修改异常修改异常n插入异常插入异常n删除异常删除异常q消除冗余的主要方式：消除冗余的主要方式：分解分解q问题问题n什么是最优关系模式？什么是最优关系模式？n标准是什么？标准是什么？n如何实现？如何实现？7Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n冗余和异常冗余和异常q求解域求解域n数据库模式数据库模式n数据库实例：关系集合数据库实例：关系集合8Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n非形式化设计准则非形式化设计准则q准则准则1：一事一地的设计原则一事一地的设计原则n关系模式设计应尽可能只包含有直接联系的属性，不要包含关系模式设计应尽可能只包含有直接联系的属性，不要包含有间接联系的属性有间接联系的属性n也就是：每个关系模式应只对应于一个实体类型或一个联系也就是：每个关系模式应只对应于一个实体类型或一个联系类型类型q准则准则2n关系模式设计应尽可能使相应关系中不出现插入、删除和修关系模式设计应尽可能使相应关系中不出现插入、删除和修改等操作异常现象改等操作异常现象n如果出现任何异常，则要清楚地加以说明，并确保更新数据如果出现任何异常，则要清楚地加以说明，并确保更新数据库的程序正确操作库的程序正确操作9Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n非形式化设计准则非形式化设计准则q准则准则3n关系模式设计应尽可能使相应关系中避免放置经常为空值的关系模式设计应尽可能使相应关系中避免放置经常为空值的属性属性（允许为（允许为NULL的属性尽量少）的属性尽量少）q准则准则4n关系模式设计应尽可能使关系的关系模式设计应尽可能使关系的等值连接在主键和外键的属等值连接在主键和外键的属性上进行性上进行，并且保证连接后不会生成额外的元组，并且保证连接后不会生成额外的元组10Chd.Wang，E-Mail：C关系模式的设计问题关系模式的设计问题n符号规定符号规定q大写字母大写字母“A，B，C，”n表示单个属性表示单个属性q大写字母大写字母“，U，V，W，X，Y，Z”n表示属性集表示属性集q大写字母大写字母R表示关系模式，小写字母表示关系模式，小写字母r表示其关系表示其关系n有时也用属性名的组合写法表示关系模式有时也用属性名的组合写法表示关系模式n若模式有若模式有A、B、C有三个属性，就用有三个属性，就用ABC表示关系模式表示关系模式q属性集属性集A1，An简写为简写为A1AnnX Y 简写为简写为XYnX A简写为简写为XA或或AX11Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n定义定义q关系模式关系模式R(U)，X U，Y U，r是是R的当前关系，函数依赖的当前关系，函数依赖FD是形为是形为XY的一个命题：的一个命题：nr中任意两个元组中任意两个元组t和和s，都有都有tXsX蕴涵蕴涵tYsY，则称则称FD XY在关系模式在关系模式R(U)中成立中成立q若若XY，且且YX，记作记作X Y，X与与Y一一对应一一对应（一对一）（一对一）n理解理解q函数依赖是指：函数依赖是指：一个或一组属性的值可以决定其它属性的值一个或一组属性的值可以决定其它属性的值n属性值之间的联系（本质：实体完整性）属性值之间的联系（本质：实体完整性）n是基于整个关系模式的，而不是关系模式的特定实例是基于整个关系模式的，而不是关系模式的特定实例(或值或值)qXY，读读“X函数决定函数决定Y”或或“Y函数依赖于函数依赖于X”，称称X为为决定子决定子qY不依赖于不依赖于X，记作记作XY/12Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n示例示例q1）n关系关系R中中qFD ABn关系关系S中中qFD ABq2）关系模式关系模式R（ABCD），），属性值间具有联系：属性值间具有联系：nA值与值与B值有一对多联系值有一对多联系qFD BA；AB nC值与值与D值有一对一联系值有一对一联系qFD CD，DC；D C/13Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n示例示例q3）R（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit,CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）nSNOSNAME，SNO(AGE,SEX)nCNOCNAMEn(SNO,CNO)GRADE，(SNO,CNO)UnCNOTNO，TNOCNOnAGESNO，SEXAGE等等/14Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的逻辑蕴涵的逻辑蕴涵q定义定义n设设F是在关系模式是在关系模式R上成立的函数依赖的集合，上成立的函数依赖的集合，XY 是一个是一个函数依赖。如果对于函数依赖。如果对于R的每个满足的每个满足F的关系的关系r也满足也满足XY，那那么称么称F逻辑蕴涵逻辑蕴涵 XY，记为记为F XYn示例示例qF=AB，BC ACq定义定义n设设F是函数依赖集，被是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集称为函数依赖集F的闭包（的闭包（closure），），记为记为F+q即即 F+=XY记为记为F XY 15Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则qArmstrong公理，关系模式公理，关系模式R（U，F），），X、Y、Z、W U FD的推理规则有以下三条：的推理规则有以下三条：nA1（自反性，自反性，reflexivity）q若若Y X U，则则 XY 在在R上成立上成立nA2（增广性，增广性，augmentation）q若若 XY在在R上成立，且上成立，且Z U，则则 XZYZ 在在R上成立上成立nA3（传递性，传递性，transitivity）q若若 XY 和和YZ 在在R上成立，则上成立，则 XZ 在在R上成立上成立q定理：定理：FD推理规则推理规则A1、A2和和A3是正确的是正确的（证明（证明P121）n即，如果即，如果XY是从是从F用推理规则导出的，则用推理规则导出的，则XY在在F+中中16Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q其他五条推理规则其他五条推理规则n1）A4（合并性，合并性，union）q XY，XZ XYZn2）A5（分解性，分解性，decomposition）q XY，Z Y XZn3）A6（伪传递性）伪传递性）q XY，WYZ WXZn4）A7（复合性，复合性，composition）q XY，WZ XWYZn5）A8q XY，WZ X（WY）YZ17Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q其他五条推理规则的证明其他五条推理规则的证明n1）A4（合并性，合并性，union）：）：XY，XZ XYZq证明证明 XY，X XX Y，即即XXY XZ，X YY Z，即即XYYZ XXY，XYYZ；XYZn2）A5（分解性，分解性，decomposition）：）：XY，Z Y XZq证明证明 Z Y，YZ ；XY，YZ，XZ18Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q其他五条推理规则的证明其他五条推理规则的证明n3）A6（伪传递性）：伪传递性）：XY，WYZ WXZq证明证明 XY，W XW Y，即即 WXWY WXWY，WYZ；WXZn4）A7（复合性，复合性，composition）：）：XY，WZ XWYZq证明证明 XY，W XW Y，即即XWWY WZ，W YY Z，即即WYYZ，XWYZ19Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q其他五条推理规则的证明其他五条推理规则的证明n5）A8：XY，WZ X（WY）YZq证明证明 XY X(WY)(WY)Y 即：即：X(WY)WY WZ WYYZ X(WY)WY，WYYZ X(WY)YZ20Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q定义定义n对于对于FD XY，如果如果Y X，那么称那么称XY是一个是一个“平凡的平凡的FD”，否则称为否则称为“非平凡的非平凡的FD”q定理定理n如果如果A1，An是关系模式是关系模式R的属性集，那么的属性集，那么XA1An成成立的充分必要条件是立的充分必要条件是XAi（i=1，n）成立成立q备注备注n依据推理规则，求解依据推理规则，求解F的闭包的闭包F+问题的规模是指数级的问题的规模是指数级的n那么如何降低问题的复杂度？那么如何降低问题的复杂度？21Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q示例示例n设有关系模式设有关系模式R（A，B，C，D，E）,其上的函数依赖集其上的函数依赖集F=ABCD，AB，DE。求证求证F必蕴涵必蕴涵AEn证明证明 AB（已知）已知）AAB（扩展律）扩展律）ABCD（已知）已知）ACD（传递律）传递律）AC，AD（分解规则）分解规则）DE（已知）已知）AE（传递律传递律)22Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD的推理规则的推理规则q示例示例n已知关系模式已知关系模式R（ABC），），F=AB，BC，求求F+n求解求解q据已知条件和推理规则，可知据已知条件和推理规则，可知F+有有43个个FDq3个属性，个属性，F+=43个个FD；问题规模指数级问题规模指数级23Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD和关键码的联系和关键码的联系q定义定义n关系模式关系模式R（U），），假设假设X1 X，X Uq若若XU在在R上成立上成立，则称则称X是是R的一个的一个超键超键q若若XU在在R上成立上成立，但对于但对于 X1U 不成立（不成立（X1U），则称则称X是是R上的一个上的一个候选键候选键/24Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD和关键码的联系和关键码的联系q示例示例nR（SNO,SNAME,AGE,SEX,NativePlace,CNO,CNAME,Credit,CreditHours,CPNO,TNO,TNAME,TITLE,SEX,DNO,DNAME,Grade）n(SNO,CNO)是唯一的候选键，因为是唯一的候选键，因为q(SNO,CNO)Uq如何确定关系的候选键？如何确定关系的候选键？n包含包含(SNO,CNO)的属性组合就是的属性组合就是超键，但不是候选键，超键，但不是候选键，如如q(SNO,CNO,AGE)q(SNO,SNAME,CNO,CNAME)q能能U，但但 25Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n属性集的闭包属性集的闭包q引言引言n通过求属性集闭包，通过求属性集闭包，把把“求解求解F+问题的规模问题的规模”从指数级降从指数级降低到多项式级；低到多项式级；可以可以判断关系模式的候选键判断关系模式的候选键q定义定义n设设R（U，F），X U，则属性集，则属性集X相对于相对于F的闭包：的闭包：qX =属性属性AF+XAq是一个使用推理规则从是一个使用推理规则从F推出的，所有形如满足推出的，所有形如满足XA的属的属性性A的集合的集合q定理定理nXY能用能用FD推理规则推出的充分必要条件是推理规则推出的充分必要条件是Y X+F F26Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n属性集的闭包属性集的闭包q算法，算法，R（U，F），X U，求，求X+F F27Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n属性集的闭包属性集的闭包q示例示例nR(A,B,C,D,E),F=ABC,BD,CE,ECB,ACB 求求(AB)n1）X(0)=X=AB;搜索搜索F,得到得到ABC,BD；X(1)=AB C D=ABCDn2）X(1)X(0);搜索搜索F,得到得到CE,ACB；X(2)=ABCD E B=ABCDEn3）X(2)X(1);搜索搜索F,得到得到ECB；X(3)=ABCDE B=ABCDEn4）X(3)=X(2);结束，结束，(AB)=ABCDE+F F+F F28Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n属性集的闭包属性集的闭包q应用应用nABE能否从能否从F中推出？中推出？(AB)=ABCDE，YESnR(A,B,C,D,E)，(AB)是候选键吗？是候选键吗？(AB)=ABCDE，YESnR（U,F），），求候选键的方法：求候选键的方法：q若属性若属性A仅在仅在FD右部，则它一定不包含在任何候选键中右部，则它一定不包含在任何候选键中q若属性若属性A仅在仅在FD左部，则它一定包含在某个候选键中左部，则它一定包含在某个候选键中q若属性若属性A既在既在FD右部又在右部又在FD左部，则它可能包含在某个左部，则它可能包含在某个候选键中候选键中q在上述基础上求属性闭包在上述基础上求属性闭包+F F+F F29Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n属性集的闭包属性集的闭包q应用应用nR（C,T,H,R,S,G）F=CT,HRC,HTR,CSG,HSR 求其候选键求其候选键n求解求解q+CTR q(HS)=CTHRSG，HS是候选键是候选键qH，S不是候选键不是候选键qHSC，HSR，HST，HSCT，HSCR，HSTR，HSCTR不不是候选键是候选键+F F30Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）nFD推理规则的完备性推理规则的完备性q定理定理nFD推理规则推理规则A1，A2，A3是完备的是完备的（证明（证明P123）q理解理解n正确性正确性q从从FD集集F使用推理规则集推出的使用推理规则集推出的FD必定在必定在F+中中q保证了推出的所有保证了推出的所有FD是正确的是正确的n完备性完备性qF+中的中的FD都能从都能从F集使用推理规则集导出集使用推理规则集导出q保证了可以推出所有被蕴涵的保证了可以推出所有被蕴涵的FDn两个方面保证了推导的有效性和可靠性两个方面保证了推导的有效性和可靠性31Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n最小最小FD集集q定义定义n若关系模式若关系模式R（U）上的两个上的两个FD集集F和和G，有有F+=G+，则称则称F和和G是等价的是等价的FD集集n如果如果FD集集G满足下列三个条件，则称满足下列三个条件，则称G是最小是最小FD集：集：q G中每个中每个FD的的右边都是单属性右边都是单属性q G中中没有冗余的没有冗余的FD即，即，G中不存在中不存在FD XY，使得使得GXY与与G等价等价q G中每个中每个FD的的左边没有冗余的属性左边没有冗余的属性即，即，G中不存在中不存在FD XY，X有真子集有真子集W使得使得 G XY WY与与G等价等价q注：最小注：最小FD集，不一定唯一集，不一定唯一32Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n最小最小FD集集q算法算法计算函数依赖集计算函数依赖集F的最小依赖集的最小依赖集Gn 据推理规则的分解性（据推理规则的分解性（A5），），得到一个与得到一个与F等价的等价的FD集集G，G中每个中每个FD的右边均为单属性的右边均为单属性n 在在G的每个的每个FD中消除左边冗余的属性中消除左边冗余的属性n 在在G中消除冗余的中消除冗余的FDq注注n算法操作步骤的顺序不能颠倒，否则可能无法消除算法操作步骤的顺序不能颠倒，否则可能无法消除FD左边的左边的冗余属性冗余属性33Chd.Wang，E-Mail：C函数依赖（函数依赖（functional dependency，简记为简记为FD）n最小最小FD集集q示例：示例：R(ABC)，F=ABC,BC,AB,ABC，求求Fminn求解求解q1）用分解规则将）用分解规则将F中所有依赖的右部变成单个属性中所有依赖的右部变成单个属性 F=AF=AB,B,A AC,BC,AB,ABCC,BC,AB,ABC =A=AB,B,A AC,BC,ABCC,BC,ABC q2 2）用所含属性较少的依赖代替所含属性较多的依赖）用所含属性较少的依赖代替所含属性较多的依赖 AB ABB AB ABB BC BC ABCABCF=AF=AB,B,A ACC,BC,BCq3 3）根据阿氏公理去掉）根据阿氏公理去掉F F 中的多余依赖中的多余依赖Fmin=A AB,BCB,BC34Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q理解理解n问题域问题域q学生学生选修选修课程课程？35Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q定义定义n设有关系模式设有关系模式R(U)，属性集为属性集为U，R1、Rk都是都是U的子集，的子集，并且有并且有R1 R2 RkU；关系模式关系模式R1、Rk的集合用的集合用表示，表示，=R1，Rk。用用代替代替R的过程称为关系模式的过程称为关系模式的分解，这里的分解，这里称为称为R的一个分解，也称的一个分解，也称数据库模式数据库模式q问题问题n1）和和r是否等价，是否表示了同样的数据是否等价，是否表示了同样的数据?q用用“无损分解无损分解”表示表示n2）F与与F1,Fk与是否等价与是否等价?q用用“保持依赖保持依赖”表示表示36Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q示例示例n问题描述问题描述qCTND（C#，TN，D），），F=C#TN，TNDn分解方案分解方案q1）CN（C#），），TN（TN），），DN（D）q2）CD（C#，D），），TND（TN，D）q3）CTN（C#，TN），），CD（C#，D）q4）CTN（C#，TN），），TND（TN，D）n问，那种分解方案是好的？问，那种分解方案是好的？q好的标准：好的标准：既做到了无损分解，又保持了函数依赖既做到了无损分解，又保持了函数依赖37Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q示例示例n问题描述问题描述qCTND（C#，TN，D），），F=C#TN，TNDn分解方案分解方案q1）CN（C#），），TN（TN），），DN（D）q问题问题无法还原出原实例无法还原出原实例依赖依赖F=C#TN，TND丢失丢失38Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q示例示例n问题描述问题描述qCTND（C#，TN，D），），F=C#TN，TNDn分解方案分解方案q2）CD（C#，D），），TND（TN，D）q问题问题CD TND!=CTNDFCD=C#D，FTND=TND39Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q示例示例n问题描述问题描述qCTND（C#，TN，D），），F=C#TN，TNDn分解方案分解方案q3）CTN（C#，TN），），CD（C#，D）q问题问题CTN CD=CTNDFCTN=C#TN，FCD=C#D40Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n分解问题分解问题q示例示例n问题描述问题描述qCTND（C#，TN，D），），F=C#TN，TNDn分解方案分解方案q4）CTN（C#，TN），），TND（TN，D）q问题问题CTN CD=CTNDFCTN=C#TN，FTND=TND41Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解无损分解q定义：定义：寄生元组寄生元组n在泛关系模式在泛关系模式R分解成数据库模式分解成数据库模式=R1，Rk时，泛时，泛关系关系r在在的每一模式的每一模式Ri（1ik）上投影后再连接起来，比原上投影后再连接起来，比原来来r中多出来的元组，称为中多出来的元组，称为“寄生元组寄生元组”（spurious tuple）q泛关系假设论泛关系假设论n假设关系模式假设关系模式R存在泛关系存在泛关系r，在此基础上探讨模式分解，这在此基础上探讨模式分解，这就是关系数据库理论的就是关系数据库理论的“泛关系假设论泛关系假设论”n实际应用中，不存在实际应用中，不存在“泛关系泛关系”，可能是，可能是某个数据库模式方某个数据库模式方案不合理案不合理，其中两个关系自然连接时，可能丢失元组。丢失，其中两个关系自然连接时，可能丢失元组。丢失的元组，称为的元组，称为“悬挂元组悬挂元组”42Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解无损分解q定义定义n设设R是一个关系模式，是一个关系模式，F是是R上的一个上的一个FD集，集，R分解成数据库分解成数据库模式模式=R1，Rkn如果对如果对R中满足中满足F的每一个关系的每一个关系r，都有都有qr=R1（r）R2（r）Rk（r）n那么称分解那么称分解相对于相对于F是是“无损连接分解无损连接分解”（lossless join decomposition），），简称为简称为“无损分解无损分解”n否则，称为否则，称为“损失分解损失分解”（lossy decomposition）43Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解无损分解q性质性质n设设=R1，Rk是关系模式是关系模式R的一个分解，的一个分解，r是是R的任一的任一关系，关系，ri=Ri（r）（）（1ik），），那么有下列性质：那么有下列性质：q r m（r）q若若s=m（r），），则则Ri（s）=riq幂等性（幂等性（idempotent）m（m（r）=m（r）n注：注：qm（r）=Ri（r）（）（1ik）=R1（r）R2（r）Rk（r）44Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解无损分解q定义定义n在无泛关系假设时，对两个关系进行自然连接中被丢失的元在无泛关系假设时，对两个关系进行自然连接中被丢失的元组称为悬挂元组组称为悬挂元组q悬挂元组是造成两个关系不存在泛关系的原因悬挂元组是造成两个关系不存在泛关系的原因q示例示例 关系关系r1 关系关系r2 关系关系r1r245Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n模式分解的优缺点模式分解的优缺点q优点优点n模式分解能模式分解能消除数据冗余和操作异常消除数据冗余和操作异常现象现象n在分解了的数据库中可以存储悬挂元组，存储泛关系中无法在分解了的数据库中可以存储悬挂元组，存储泛关系中无法存储的信息存储的信息q缺点缺点n分解以后，分解以后，检索操作需要做笛卡儿积或连接操作检索操作需要做笛卡儿积或连接操作，这将付出，这将付出时间代价时间代价n在有泛关系假设时，对数据库中关系进行自然连接时，可能在有泛关系假设时，对数据库中关系进行自然连接时，可能产生寄生元组，即损失了信息产生寄生元组，即损失了信息n在无泛关系假设时，由于数据库中可能存在悬挂元组，就有在无泛关系假设时，由于数据库中可能存在悬挂元组，就有可能不存在泛关系可能不存在泛关系46Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解的测试方法无损分解的测试方法q输入输入n一个关系模式一个关系模式R（A1，A2，An）nR上函数依赖集上函数依赖集FRnR的一个分解的一个分解=R1，Rkq输出输出n确定确定相对于相对于F是否具有无损分解特性是否具有无损分解特性47Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解的测试方法无损分解的测试方法q算法算法n1）初始化初始化：一个：一个k行行n列表格列表格q第第i行对应于模式行对应于模式Ri，第第j列对应于属性列对应于属性Ajq填表：若填表：若Aj Ri，则第则第i行第行第j列上填入列上填入aj，否则填入否则填入bij n2）修改表修改表：逐一检查：逐一检查F中的每个中的每个FD XY在表格上是否成立，在表格上是否成立，若不成立则修改表格中的值若不成立则修改表格中的值q把把X列上符号相同的行，对应的列上符号相同的行，对应的Y列的符号改为相同列的符号改为相同Y列有列有aj，则将则将bij改为改为aj；Y列无列无aj，则将它们全改为则将它们全改为bij，i一般取其中最小行号一般取其中最小行号n3）结论结论：若某一行变成全：若某一行变成全a，即即a1，a2，an，则此分解则此分解是无损分解，否则是损失分解是无损分解，否则是损失分解48Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解的测试方法无损分解的测试方法q示例示例n设有设有R（U,F），），求证分解是否无损？求证分解是否无损？n验证验证q1）q2）q3）修改表依据修改表依据 F=AC,BC,CD,DEC,CEA初始化表格，并填写初表：初始化表格，并填写初表：aj或或bij AC/b13/b13BC/b13CD/a4/a4/a4DEC/a3/a3CEA/a1/a1R3 所在行全是所在行全是a，为为a1,a2,a3,a4,a5，因此，是无损分解因此，是无损分解结论结论49Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解的测试方法无损分解的测试方法q定理定理n设设=R1，R2是关系模式是关系模式R的一个分解，的一个分解，F是是R上成立的上成立的FD集，那么分解集，那么分解相对于相对于F是无损分解的是无损分解的充分必要条件是充分必要条件是q（R1R2）（R1R2）或或q（R1R2）（R2R1）q定理定理n如果如果FD XY在模式在模式R上成立，且上成立，且XY=，那么那么R分解成分解成=RY，XY是无损分解是无损分解50Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n无损分解的测试方法无损分解的测试方法q示例示例n关系模式关系模式R（U,F），），其中其中qU=SNO，SNAME，CNO，GRADE qF=SNOSNAME，(SNO,CNO)GRADE 其一个分解为：其一个分解为：=R1(U1,F1)，R2(U2,F2)，其中其中qU1=SNO,SNAME，F1=SNOSNAME qU2=SNO,CNO,GRADE，F2 =(SNO,CNO)GRADE 问：问：是否无损分解？是否无损分解？q解：解：R1R2=SNO，R1-R2=SNAME，SNOSNAME F R1R2R1-R2，分解分解是无损分解是无损分解51Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n保持函数依赖的分解保持函数依赖的分解q若分解不能保持依赖，则数据的语义会出现混乱若分解不能保持依赖，则数据的语义会出现混乱q定义定义n设设F是属性集是属性集U上的上的FD集，集，Z是是U的子集，的子集，F在在Z上的投影用上的投影用Z（F）表示，定义为：表示，定义为：qZ（F）=XYXY F+，且且XY Zq定义定义n设设=R1，Rk是是R的一个分解，的一个分解，F是是R上的上的FD集，如集，如果有果有Ri（F）F，那么称分解那么称分解保持函数依赖集保持函数依赖集Fki=152Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n保持函数依赖的分解保持函数依赖的分解q示例示例1n设有设有R（A,B,C,D），），F=AB，CD，=R1(A,B,AB ),R2(C,D,CD )n问问是否具有依赖保持性是否具有依赖保持性n解：解：F=AB,CD，F+=AB,CD F1UF2=AB,CD =(F1UF2)+F+=(F1UF2)+具有依赖保持性具有依赖保持性53Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n保持函数依赖的分解保持函数依赖的分解q示例示例2n设有设有R（SNO,BClass,Monitor），），其其FD集集F=SNOBClass，BClassMonitor ，分解方案：分解方案：=R1,R2，其中其中 R1=SNO,Bclass,FR1=SNOBclass R2=SNO,Monitor,FR2=SNOMonitor n问问是否具有依赖保持性是否具有依赖保持性n解：解：分解是无损分解，但不保持依赖分解是无损分解，但不保持依赖(FR1UFR2)BClassMonitor，即即F+=(F1UF2)+/54Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n模式分解与模式等价问题模式分解与模式等价问题q数据库模式等价，包括数据库模式等价，包括数据等价数据等价和和依赖等价依赖等价两个方面两个方面q违反数据等价或依赖等价的分解违反数据等价或依赖等价的分解，很难说是好的模式设计很难说是好的模式设计q数据等价数据等价n是指是指两个数据库实例两个数据库实例应表示同样的信息内容应表示同样的信息内容n用用“无损分解无损分解”衡量衡量n若是无损分解，对泛关系反复的投影和连接不会丢失信息若是无损分解，对泛关系反复的投影和连接不会丢失信息q依赖等价依赖等价n是指是指两个数据库模式两个数据库模式应有相同的依赖集闭包应有相同的依赖集闭包n用用“保持依赖保持依赖”衡量衡量n在依赖集闭包相等情况下，数据语义是不会出现混乱的在依赖集闭包相等情况下，数据语义是不会出现混乱的q保持依赖保持依赖无损分解无损分解55Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n模式分解与模式等价问题模式分解与模式等价问题q示例示例n设关系模式设关系模式R(ABC)，=AB,AC 是是R的一个分解。试分的一个分解。试分析分别在各种析分别在各种FD的情况下，的情况下，是否具有无损分解和保持是否具有无损分解和保持FD的的分解特性分解特性相对于相对于F1=AB，分解分解是无损分解且保持是无损分解且保持FD相对于相对于F2=AC,BC q分解分解是无损分解，但不保持是无损分解，但不保持FD（丢失了丢失了BC）相对于相对于F3=BA q分解分解是损失分解，但保持是损失分解，但保持FD相对于相对于F4=CB,BA q分解分解是损失分解，且不保持是损失分解，且不保持FD（丢失了丢失了CB）56Chd.Wang，E-Mail：C关系模式的分解特性关系模式的分解特性n模式分解与模式等价问题模式分解与模式等价问题q示例示例n示意图示意图注：注：为为无无非非平平凡凡的的FD57Chd.Wang，E-Mail：C关系模式的范式关系模式的范式n引子引子q1）规范化）规范化 使关系模式满足某种条件的处理过程使关系模式满足某种条件的处理过程q2）范式）范式NF（Normal Form）关系模式满足的条件关系模式满足的条件q3）有）有6级范式，级别越高，条件越严格级范式，级别越高，条件越严格n1NFn2NFn3NFBCNFn4NFn5NF在在模式设计模式设计中，解决数中，解决数据之间的函数依赖问题据之间的函数依赖问题多值依赖多值依赖连接依赖连接依赖，理论研究理论研究58Chd.Wang，E-Mail：C关系模式的范式关系模式的范式n第一范式（第一范式（1NF）q定义定