第4章-数据依赖与关系模式规范化

第4章数据依赖与关系模式规范化4.1关系模式设计中的问题4.2数据依赖4.3关系模式分解4.4关系模式规范化4.1关系模式设计中的问题针对一个具体的应用问题，应该如何构造一个适合于它的关系数据库模式？应该构造几个关系模式？每个关系由哪些属性组成？本章的任务:研究设计一个“好”的（即没有“毛病”的）关系模式的方法实例分析•前面章节中多次引用过的三个基本表：•Student(S#，Class，Sname，…)、•Course(C#，Cname，Teacher)、•SC(S#，C#，Grade)•对于这个应用而言，为什么仅设计了这三个表，如果将这三个表合并成一个或两个表，或者将其拆分为更多的表，这样是否更合适？S#C#GradeTeacherDept图4.1关系模式SCT属性间依赖关系实例分析•考虑下面的关系模式SCT:SCT(S#,C#,G,CN,T,D)S#C#GradeTeacherDept0205501902055019020550370205506602055066…CS－01CS－03CS－01CS－02CS－03…8986689273…刘朝张莹刘朝林琳张莹…计算机计算机计算机计算机计算机…图4.2关系模式SCT实例实例分析1.数据冗余(Redundancy)如果一个教师教多门课程，那么这个教师的地址就要重复多次存储。2.更新异常(UpdateAnomalies)如果教师t1教3门课程，在关系中就会有3个元组。如果他的地址变了，这3个元组中的地址都要改变。若有一个元组中的地址未更改，就会造成这个教师的地址不惟一，产生不一致现象。关系模式SCT存在的问题3.插入异常(InsertionAnomalies)如果一个教师刚调来，尚未分派教学任务，那么就无法将教师的姓名和地址存储到关系中去时，因为在属性C#和CNAME上就没有值（空值）。4.删除异常(DeletionAnomalies)如果要取消教师的教学任务，那么就要把这个教师的元组删去，同时也把该教师的地址信息从表中删去了。这是一种不合适的现象。关系模式SCT存在的问题实例分析•结论：SCT不是一个”好”的关系模式“好”的模式：数据冗余应尽可能少，不发生插入异常、删除异常、更新异常•原因：–存在于模式中的某些不合适的”数据依赖”•解决方法：–通过分解关系模式来消除其中不合适的数据依赖4.2数据依赖数据依赖(DataDependency)是通过一个关系中各属性值相等与否体现出来的一种数据间的相互制约关系，是现实世界中事物属性间相互联系的抽象，是数据内在的性质，是语义的体现已经提出了许多种类型的数据依赖，其中最重要的是函数依赖(FunctionalDependency简记为FD)和多值依赖(MultivaluedDependency简记为MVD)R表示一个抽象的关系模式，R上全部函数依赖的集合记为F；R的属性全集一般用U表示，U＝{A1，A2，…，An}，其中的每一个Ai（1≤i≤n）均表示R的一个属性，X、Y、Z等表示U的一个子集，也就是若干属性的集合；常用符号及其含义r是关系模式R上的一个实例，记为R(r)，即满足R的一些元组的集合，R可以有多个不同的实例r通常关系模式很少变化，经常发生变化的是关系的实例，因此将关系的模式称为关系的内涵，而将关系的实例r称为关系的外延，由于用户经常对关系进行插入、删除和修改操作，因此外延是与时间有关的，随着时间的推移在不断变化关系的内涵和外延关系的内涵和外延•关系的内涵是对数据的定义以及数据完整性约束的定义，一般是与时间独立的•对数据的定义包括对关系、属性、域的定义和说明。对数据完整性约束的定义涉及面较广，主要包括以下几个方面：•静态约束，涉及到数据之间联系（称为“数据依赖，datadependences）、主键和值域的设计•动态约束，定义各种操作（插入、删除、修改）对关系值的影响定义4.1：设R为关系模式，r是R上的任意一个关系实例，X，Y是R的两个属性子集，若对于r上的任意两个元组t1，t2∈r都有：如果t1[X]＝t2[X]，则必有t1[Y]=t2[Y]，则称在R上X函数决定Y或者Y函数依赖于X，记为X→Y，X称为决定子(Determinant)或左部函数依赖的定义•例4-1：ABCDABCDa1b1c1d1a1b1c1d1a1b1c2d2a1b2c2d2a2b2c3d3a2b2c3d3a3b1c4d4a3b2c4d4•分别检验：A→C？C→A？AB→D？•辨识：–满足依赖的关系：依赖在模式的某个关系实例上成立–模式上成立的依赖：依赖在模式的所有关系实例上都成立函数依赖的定义函数依赖的定义•函数依赖是语义范畴的概念，它反映了一种语义完整性约束，只能根据语义来确定一个函数依赖是否成立•例如，“姓名”“年龄”这个函数依赖只有在没有同名人的条件下成立，否则，此函数依赖不成立•函数依赖是指关系R模式的所有关系元组均应满足的约束条件,而不是关系模式中的某个或某些元组满足的约束条件定义4.2：设R为关系模式，X、Y是R的不同属性集，如果X→Y成立，且不存在X’X使得X’→Y也成立，则称Y完全函数依赖于X，记为XY，否则称Y部分依赖于X，记为XY完全函数依赖中的决定子不包含冗余属性，即只要将决定子中的任何一个属性去掉，这个函数依赖就不再成立了定义4.3：如果YX,则称X→Y为平凡的函数依赖Pf函数依赖的定义定义4.4：设X、Y、Z是R上的不同属性集合，如果有X→Y，Y→Z成立且YX，则称Z传递函数依赖于X条件YX非常重要，如果没有这个条件，那么X与Y就是一一对应关系，从而X→Z就是直接函数依赖函数依赖的定义函数依赖的逻辑蕴涵定义4.5：设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖，如果对于R的每个满足F的关系r也满足X→Y，那么称F逻辑蕴涵X→Y，记为F⊨X→Y例如：{X→Y，Y→Z}⊨X→Z定义4.6：由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包，记作F+，即F+＝{X→Y|FX→Y}据定义4.6易知，函数依赖集的闭包F+具有以下特点：(1)FF+，这是因为根据闭包的定义F中的每个函数依赖必定也在中F+；(2)(F+)+＝F+，该性质说明闭包运算是幂等的，即F经过任意多次的闭包运算后其结果仍然等于F+(3)如果F＝F+，则称F是完备的函数依赖集合的闭包函数依赖集合的闭包•例4-2:已知关系模式R（ABC），F=｛A→B，B→C｝，求F+解：据已知条件和推理规则，可知F+有43个FD：AфABфACфABCфBфCфAAABAACAABCABBCCABABBACBABCBBCффACABCACCABCCBBCAABABABACABABCABBCфAACABACACACABCACBCBABCABBCACBCABCBCBCCAABCABABCACABCABCABCBCBC•F+的计算是一个NP完全问题设U是关系模式R的属性集，F是R上的函数依赖集，则有：A1（自反率）：如果YXU，则X→Y成立；A2（增广率）：如果X→Y成立，且ZU，则XZ→YZ成立A3（传递率）：如果X→Y，Y→Z成立，则X→Z成立•人们又把自反律(A1),传递律(A2)和增广律(A3)称为Armstrong公理函数依赖的推理规则引理4.1：FD推理规则A1、A2和A3是正确的也就是，如果X→Y是从F用推理规则导出，那么X→Y在F+中由A1～A3易推出下面的三条推理规则也是正确的：(1)合并规则：若X→Y，X→Z成立，则X→YZ成立；(2)伪传递规则：若X→Y，WY→Z成立，则WX→Z成立；(3)分解规则：若X→Y，且ZY，则有X→Z；函数依赖的推理规则FD的逻辑导出•定义4.7：给定关系模式RU,F，如果能由F根据Armstrong公理导出X→Y，则称X→Y是F的逻辑导出，记为F=X→Y定义4.8：属性集X关于R(U，F)上的函数依赖集合F的闭包定义为＝{A|A∈U，F=X→A}•根据A1（自反率）可知对于任一属性集X一定有X，此外，计算的工作量应该远远小于计算F+的工作量，因为中的属性一定是可数的，最多就是属性全集U而已属性集合的闭包属性集合的闭包属性集的闭包•算法4.1：求属性集X(XU)关于U上的函数依赖集F的闭包X+F•输入：X，F•输出：X+F•步骤：1)令X(0)=X，i=02)求B，这里B={A|(存在V→W)(V→W∈F∧VX(i)∧A∈W)}；3)X(i+1)=X(i)∪B4)判断X(i+1)=x(i)吗?5)若相等或X(i)=U则X(i)就是X+F,算法终止。6)若否，则i=i+l，返回第2)步。FXFX属性集的闭包•例4-3:已知关系模式RU,F,其中:U={A,B,C,D,E}；F={AB→C，B→D，C→E，EC→B，AC→B}求(AB)+F•解：由算法，X(0)=AB；计算X(1)；逐一的扫描F集合中各个函数依赖,找左部为A,B,或AB的函数依赖。得到两个：AB→C，B→D。于是X(1)=AB∪CD=ABCD。因为X(0)≠X(1)，所以再找出左部为ABCD子集的那些函数依赖，又得到C→E，AC→B，于是X(2)=X(1)∪BE=ABCDE。因为X(2)已等于全部属性集合,所以(AB)+F=ABCDE•对于算法4.l，令ai=|X(i)|,{ai}形成一个步长大于1的严格递增的序列,序列的上界是|U|,因此该算法最多|U|-|X|次循环就会终止属性集的闭包•例4-4:属性集U为ABCD，FD集为｛A→B，B→C，D→B｝•则用上述算法，可求出:•A+=ABC，AD+=ABCDBD+=BCD等等Armstrong公理的正确性和完备性•Armstrong公理的正确性是指“使用推理规则从FD集F推出的FD必定在F+中”即，如果F=XY则F|=XY•Armstrong公理的完备性是指“F+中的FD都能从F集使用推理规则集导出”即，如果F|=XY则F=XY•Armstrong公理的正确性和完备性保证了FD推导过程的有效性和可靠性•定理4.1:Armstrong公理是正确的•证明：略Armstrong公理的正确性和完备性•定理4.2:Armstrong公理是完备的•证明：我们证明完备性的逆否命题，即若函数依赖X→Y不能由F从Armstrong公理导出，那么它必然不为F所蕴含，其证明分三步：1)若V→W成立，且VX+F，则WX+F因为VX+F,所以X→V成立；由A3规则有X→W成立，所以WX+FArmstrong公理的正确性和完备性Armstrong公理的正确性和完备性2)由下列两个元组构成的二维表，必是RU,F的一个关系r，即满足F中的全部函数依赖。若r不是RU,F的关系，则必由于F中有函数依赖V→W在r上不成立所致,由r的构成可知，V必定是X+F的子集，而W不是X+F的子集，但是由l)WX+F，矛盾!所以r必是RU,F的一个关系3)若X→Y不能由F从Armstrong公理导出，则Y不是X+F的子集，因此必有Y的子集Y‘满足Y’U-X+F，即X→Y在r上不成立，故X→Y必不为F蕴含。证毕•Armstrong公理的正确性和完备性说明“逻辑导出”与“逻辑蕴含”是两个等阶的概念•因此,F+也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合•从蕴含(或导出)的概念出发，又引出了两个函数依赖集等价和最小依赖集的概念Armstrong公理的正确性和完备性定义4.8：设F，G是两个函数依赖集合，如果F+＝G+，则称F等价于G，或者F与G互相覆盖引理4.3：F与G等价的充分必要条件是FG+并且GF+证：必要性显然,只需证充分性：1)若FG+,则XF+XG++2)任取X→Y∈F+则有YXF+XG++。所以X→Y∈(G+)+=G+，即F+G+3)同理可证G+