《关系数据理论》PPT课件.ppt

第5章关系数据理论,5.1基本概念,5.2范式,5.3Armstrong公理系统,5.4模式分解,第5章关系数据理论,以学生成绩管理应用为例说明数据库模式的“好”与“坏”。设数据库模式schema_1：学生（学号，姓名，性别，出生日期，专业，课程号，课程名，学分，成绩）。表5.1为该数据库模式在某时刻的一个数据实例。,表5.1学生表,程序设计,思想道德,修养与法,第5章关系数据理论,若将数据库模式分解为如下的数据库模式schema_2：学生（学号，姓名，性别，专业，出生日期）课程（课程号，课程名，学分）选课（学号，课程号，成绩）则解决了插入异常、修改异常、删除异常的问题，数据冗余也得到了控制。什么样的数据库模式算一个好的数据库模式呢？一个好的数据库模式应有如下特点：能客观地描述应用领域的信息；无插入异常；无删除异常；无过度的数据冗余。,5.1基本概念,数据依赖：是客观世界实体集内部或实体集之间属性相互联系的抽象，为了描述这些联系，人们提出多种类型的数据依赖，如函数依赖、多值依赖、连接依赖，但最重要的是函数依赖（FunctionalDependency，FD）和多值依赖（MultivaluedDependency，MD）。数据依赖实际上反映了属性之间的相互约束关系。函数依赖：若X，Y为单一属性或属性组，当给定X的值时，就可唯一地确定Y的值，则称X函数决定Y，或Y函数依赖于X，记为XY；若Y不函数依赖于X，记为XY。若XY，则称X为决定因素。若XY，YX，则记为：YX。若XA1，XA2，XAn，则可写成：XA1A2An。平凡函数依赖：如果对于函数依赖XY，YX，则称该函数依赖为平凡函数依赖。非平凡函数依赖：如果XY，YX，则称该函数依赖为非平凡函数依赖。完全非平凡函数依赖：如果XY，且对于X的任一真子集X，都有XY，则称Y对X完全非平凡函数依赖，记为：；否则称为部分函数依赖，记为：。传递函数依赖：若XY，YZ，YX，且YX，则称Z对X传递函数依赖。关系模式：一个关系模式R可描述为一个四元组：R（U，D，dom，F），其中，U为属性的集合；D为属性组U的值域；dom为属性到域的映射；F为定义在属性组U上的一组函数依赖集，F取决于与应用有关的语义。,5.1基本概念,在具体关系模式的表示中，往往将一个关系模式表达为R（U，F）的形式，若在上下文环境中，F不是讨论的重点，则可将关系模式表达为R（U）的形式，例如，我们在前面涉及关系模式时，都是以R（U）的形式表达。如果用图表示一个关系模式中属性之间的函数依赖关系，则称该图为函数依赖图，图5.1为完全函数依赖、部分函数依赖和传递函数依赖的图。,图5.1完全函数依赖、部分函数依赖和传递函数依赖图,5.1基本概念,有了函数依赖的概念，可从函数依赖的角度定义码（候选码）：码：如果关系模式R（U，F）的一个或多个属性的组合A1A2An满足如下条件，则该组合为关系模式R的码：这些属性函数决定该关系模式的所有属性，即A1A2AnUA1A2An的任何真子集都不能函数决定R的所有属性。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码。包含在任何一个码中的属性，称为主属性，反之，不包含在任何码中的属性称为非主属性或非码属性。下面通过具体实例说明对上述概念的理解。将数据库模式schema_2用符号表示如下：student（sno，sname，ssex，specility，birthday）course（cno，cname，credit）selector（sno，cno，grade）对于student关系模式有如下事实。每个学生有唯一的学号，允许有同名学生，则存在如下函数依赖：snosnamessexspecilitybirtyday,5.1基本概念,snosnamessexspecilitybirtyday从分析可知，sno为码，主属性有sno，非主属性有sname，specility，birthday。对于course关系模式有如下事实。每门课有唯一的课程号，不同班级可能上相同课程，因此，课程名也可同名，则存在如下函数依赖：cnocnamecredit从分析可知，cno为码，主属性有cno，非主属性有cname，credit。对于selector关系模式有如下事实。每个同学可选修多门课程，每门课程可被多个同学选修，当一个同学选修一门课程后，有相应的成绩，则存在如下函数依赖：snocnograde从分析可知，sno，cno两个属性组合构成码，主属性有sno，cno，非主属性有grade。思考：如果在student关系模式中，不允许同学同名，请确定函数依赖集、码、主属性和非主属性。,5.2范式,如果要求关系模式属性之间的数据依赖关系满足一定的约束条件，则可减少操作异常，减少冗余数据的存储。E.F.Codd等人将范式分为：第1范式第3范式（3NF）、BCNF范式及第4范式（4NF），后来，又有学者在此基础上提出了第5范式（5NF）。图5.2为范式的类别及各类范式之间的关系，从图中可看出：5NF4NFBCNF3NF2NF1NF。,图5.2范式的类别及各类范式之间的关系,5.2范式,1第1范式（1NF）如果关系模式R（U，F）中的每个属性都是不可再分的，则该关系模式属于第1范式。第1范式即要求关系模式的每个属性是原子的。根据定义可知：数据库模式schema_1的关系模式属于1NF，而图5.3描述学生基本信息的结构不属于第1范式，因为“主要社会关系”属性是非原子项。一般来说，关系型数据库管理系统要求数据库模式的每一个关系模式必须属于1NF。,图5.3描述学生基本信息的非第1范式结构,5.2范式,2第2范式（2NF）对于关系模式R（U，F），若R1NF，且每个非主属性都完全函数依赖于码，则R2NF，即2NF要求非主属性不能部分依赖于码。例如，对于本章开始给出的数据库模式schema_1用符号表示为：sudent（sno，sname，specility，birthday，cno，cname，credit，grade），码为（sno，cno），因此，主属性为sno，cno，其他属性为非主属性。根据语义，确定各属性之间的函数依赖关系如下：snosnamessexspecilitybirthdaycnocnamecreditsnocnograde图5.4为对应的函数依赖图。从上述函数依赖关系可看出：非主属性sname，specility，birthday是部分依赖于码，非主属性cname，credit也是部分依赖于码，因此，student关系模式不属于2NF。一个关系R不属于2NF，会产生插入异常、删除异常、修改异常等问题，产生这些问题的原因：非主属性对码不是完全函数依赖。如何解决这些问题呢？,5.2范式,图5.4sudent关系模式的函数依赖图,解决的办法：对原有模式进行分解，用新的一组关系模式代替原来的关系模式，在新的关系模式中，每一非主属性对码都是完全函数依赖的。例如，前面我们对数据库模式schema_1进行分解，构成数据库模式schema_2，则解决了上述问题。3第3范式（3NF）在关系模式R（U，F）中，对任一非平凡函数依赖XY如果满足如下条件之一：X是超码，Y是主属性，则称R3NF。,5.2范式,分析：从3NF的定义可知：XY不满足3NF的约束条件分为两种情况：Y是非主属性，而X是码的真子集，在此情况下，非主属性Y部分函数依赖于码；Y非主属性，X既不是码，也不是码的真子集，在此情况下，设K为一个码，因为XK，YK，有非平凡依赖：KX，XY所以Y传递依赖于码。由上述定义，得出如下推论：若R（U，F）3NF，则每个非主属性既不部分依赖于码也不传递依赖于码；对于关系模式R（U，F），若R（U，F）R2NF，且每个非主属性都不传递依赖于码，则R（U，F）3NF；若R3NF，则主属性可以传递依赖于码。对于数据库模式schema_2中的student关系模式，考虑增加两个属性：学生所在的院系及院系主任，此时，schema_2对应的student关系模式如下：student（sno，sname，ssex，specility，birthday，sdept，dept_manager）sno为码，根据语义确定函数依赖集F为：snosnamessexspecilitysdeptbirthdaysdeptdept_manager由此，存在非主属性对码的传递依赖：snodept_manager所以student不属于3NF。,5.2范式,一个关系模式不属于3NF，有可能存在插入异常、删除异常，解决的办法：对关系模式进行分解。我们可将schema_2中的student关系模式分解为如下两个关系模式：student（sno，sname，ssex，sdept，specility，birthday）dept（sdept，dept_manager）4Boyce/Codd范式（BCNF）设关系模式R1NF，若XY，YX，X必含有码，则RBCNF。即在关系模式R中，若每个决定因素都包含码，则RBCNF。BCNF范式因由Boyce和Codd共同提出而得名，BCNF范式又称为修正的第3范式或扩充的第3范式。从BCNF范式的定义知：如果RBCNF，则在R中不存在决定因素不含码的非平凡函数依赖。3NF与BCNF的关系：如果关系模式RBCNF，必有R3NF；如果R3NF，R不一定属于BCNF。【例5.1】根据如下语义，设计一个关系模式，用于描述学生、课程及教师三实体集之间的联系，指出该关系模式的码，并说明其是否属于BCNF范式。学生、教师可重名；一个学生属于某个班级，一门课程可给多个班级开设；一个学生可选多门课程，一门课程可被多个学生选修，如果某个学生选修了某一课程，则应有相应的成绩；,5.2范式,一门课程只能被一位教师讲授，一位教师只讲授一门课程。答：根据语义（1），（2），（3），（4）定义如下属性符号，sno：学号，sname：学生姓名，tno：教师编号，tname：教师姓名，cno：课程号，cname：课程名，class：班级，grade：成绩；构造关系模式：student_teacher_course（U，F）其中，U=sno，sname，tno，tname，cno，cname，class，grade；根据语义（1），（2），（3），（4），定义函数依赖集F如下：snosnametnotnamesnoclasscnocnamesnocnogradecnotnotnocno,5.2范式,F表达的函数依赖关系如图5.5所示。分析图5.5得出：关系模式student_teacher_course的码为（sno，cno）和（sno，tno），根据范式的定义及F包括的函数依赖得知，F中存在非主属性对码的部分依赖，所以它满足的最高范式为1NF。因此该关系模式不满足BCNF的条件（因为BCNF要求F中每个函数依赖的决定因素必须含有码），它不属于BCNF范式。,图5.5F表达的函数依赖关系,5.2范式,【例5.2】设数据库模式schema_2的各关系模式如下：student（sno，sname，ssex，sdept，specility，birthday，F1）F1：snosnamessexspecilitysdeptbirthdaydept（sdept，dept_manager，F2）F2：sdeptdept_managercourse（cno，cname，credit，F3）F3：cnocnamecreditselector（sno，cno，grade，F4）F4：snocnograde请指出各关系模式是否属于BCNF范式。答：对上述关系模式分析得知，关系模式student的码为sno，从F1可看出，函数依赖的决定因素为码，所以student属于BCNF。同理得：关系模式dept，course，selector都属于BCNF范式。,5.2范式,5第4范式（4NF）设关系模式teacher_school_course（teacher，school，course，）有如下语义：一位教师可在多个学校教多门课程，而且在每个学校都是教同样的几门课程，表5.2是该关系模式下某一时刻的数据实例，这一例子体现了关系模式属性间的多值依赖关系。BCNF是基于函数依赖的最高范式，但不是数据库模式设计的最高范式，如果一个数据库模式中的每个关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，消除了插入和删除异常，但属性之间可能还存在多值依赖，多值依赖会导致不必要的数据冗余。下面介绍多值依赖的概念及消除多值依赖的方法。,表5.2teacher_school_course表,5.2范式,多值依赖:设R（U）是属性集U上的一个关系模式，X，Y，Z是U的子集，且Z=UXY，对于R的任何关系r，如果存在两个元组s，t，则必然存在两个元组u，v，使得：uX=vX，sX=tX，uY=tY且uZ=sZ，vY=sY，且vZ=tZ，即交换元组s，t在属性组Y上的值，得到两个新元组u，v必在关系r中，则称Y多值依赖于X，记为：XY。对于关系模式teacher_school_course（U），U=teacher，school，course，我们讨论几种情况：如果限制一位教师只能在一个学校教一门课程，则前面的多值依赖蜕化为函数依赖，所以函数依赖可看成多值依赖的特例。如果一位教师可在多个学校教多门课程，但在不同学校可教不完全一样的课程，这种情况与多值依赖很相似，但并不是多值依赖。平凡多值依赖：设R（U）是属性集U上的一个关系模式，X，Y，Z是U的子集，如果XY=U，则称XY为平凡多值依赖。,5.2范式,多值依赖的性质多值依赖的传递性如果XY且YZ，则XZY。多值依赖的对称性如果XY且Z=UXY，则XZ。扩展律如果XY且VW，则WXVY。如果XY，则XY即函数依赖是多值依赖的特例。4NF设FD，MVD分别为定义在关系模式R上的函数依赖集和多值依赖集，若R1NF，且MVD中所有非平凡多值依赖XY的决定因素X都含有码，则称R4NF。4NF实际上是要求关系模式的属性之间不存在非平凡且非函数依赖的多值依赖。根据4NF的定义，对于每个非平凡的多值依赖XY，X都含有码，则有XY，所以4NF所允许的非平凡多值依赖实际上是函数依赖，显然，如果一个关系模式为4NF，则必为BCNF。,5.2范式,【例5.3】将表5.2对应的关系模式teacher_school_course（teacher，school，course）分解为4NF。从表5.2对应的语义可知：关系模式teacher_school_course的码为全码，属于BCNF范式，因其中存在多值依赖teacherschool，teachercourse，所以teacher_school_course不属于4NF。将teacher_school_course分解为如下的4NF：teacher_school（teacher，school，）teacher_course（teacher，course，）将teacher_school_course分解为两个关系模式后，每个关系模式都没有多值依赖，因此，分解后的每个关系模式都属于4NF。模式分解的过程实际上是将非平凡多值依赖转化为平凡多值依赖或函数依赖的过程。,5.3Armstrong公理系统,将低级范式转化为高一级范式的基本方法是对低级范式进行模式分解，而模式分解算法的理论基础是Armstrong公理系统，下面介绍相关内容。逻辑蕴涵：设有满足函数依赖集F的关系模式R，对于R的任一关系r，若函数依赖XY都成立（即对于r中任意两元组t，s，若tX=sX，则tY=sY），则称F逻辑蕴涵XY，记为：FXY。对于关系模式R有以下推理规则：（1）自反律若YXU，则FXY。（2）增广律若FXY，且ZU，则FZXZY。（3）传递律若FXY及FYZ，则FXZ。由于上述推理规则由Armstrong于1974年首先提出，因此将这些规则称为Armstrong公理系统。根据Armstrong公理系统可得到如下推理规则：合并规则。若XY，XZ，则XYZ。伪传递规则。若XY，WYZ，则有WXZ。分解规则。若XY，且ZY，则有XZ,5.3Armstrong公理系统,若XA1A2AK，则据分解规则可将其分解为XAi（i=1，2，k）；若XAi（i=1，2，k），则据合并规则可得XA1A2Ak，所以，XA1A2Ak与XAi（i=1，2，k）等价。F的闭包。设有关系模式R（U，F），F逻辑蕴涵的函数依赖的全体称为F的闭包，记为F+。即从F出发，根据Armstrong公理系统可导出的函数依赖的全体。F+的计算是一个NP完全问题，例如，设S=B1，B2，Bn，F=AB1，ABn，式中，A，B1，Bn均为单属性，则F+=AY|Y(s)，（s）是S的幂集，因|(s)|=2n，所以，当F较复杂时，很难全部列出F+的每个元素，由此，引出了属性集X关于函数依赖集F的闭包XF+的定义。XF+的定义：设F为属性集U上的一组函数依赖，XU，YU，XF+=Y|XY能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。求属性集X关于函数依赖集F的闭包。XF+的算法流程如图5.6所示。,5.3Armstrong公理系统,图5.6求XF+的算法流程,5.3Armstrong公理系统,【例5.4】设有关系模式R（U，F），U=A，B，C，D，W，V，F=ABC，BCAD，DW，CVB，求（AB）F+。解：根据求XF+的算法流程：初始X（0）:=A，B据ABC，X（1）:=X（0）C/X（1）:=A，B，CX（0）:=X（1）据BCAD，X（1）:=X（0）D/X（1）:=A，B，C，DX（0）:=X（1）据DW，X（1）:=X（0）W/X（1）:=A，B，C，D，W因为不可能使X（1）增加新的元素，所以X（1）即为（AB）F+。对于给定关系模式R（U，F）的属性子集X，要判断F是否逻辑蕴涵XY，可通过判断Y是否属于XF+来实现。【例5.5】设有关系模式R（U，F），U=A，B，C，D，E，F=AB，BC，CDE，请判断F是否逻辑蕴涵AE。解：要判断F是否逻辑蕴涵AE，只需判断E是否属于（A）F+即可。根据求XF+的算法流程可求得（A）F+=A，B，C，因为E（A）F+，所以AE不被F所逻辑蕴涵。,5.3Armstrong公理系统,【例5.6】设有关系模式R（U，F），U=A，B，C，D，E，G，F=ED，CB，CEG，BA，求该关系模式的码。解：对属性进行分组：仅出现在函数依赖左部的属性L=E，C。既出现在函数依赖左部又出现在右部的属性LR=B。求关系模式R（U，F）的码KEY：设X=LLR，因为KEYFU，设M为X中单个属性或X中属性的最小组合，若（M）F+=U，则M为码。据此，因为（EC）F+=E，D，C，B，A，G=U，所以EC即为码。注：若一个关系模式有多个码，可采用类似的方法求出。两个函数依赖集等价：设有函数依赖集F，G，如果G+=F+，则说函数依赖集F与G互为覆盖，或称F与G等价。最小依赖集（最小覆盖、正则覆盖）：如果函数依赖集F满足如下条件。F中任一函数依赖的右部仅含有单一属性；F中不存在这样的函数依赖XA，使得F与FXA等价；F中不存在这样的函数依赖XA，X有真子集Z使得F与FXAZA等价，则称F为最小依赖集或最小覆盖。,5.3Armstrong公理系统,说明：条件是要求最小覆盖F中不存在多余的函数依赖；条件是要求最小覆盖F中的每个函数依赖都是完全函数依赖。定理：每个函数依赖集F均等价于一个极小函数依赖集Fm，Fm称为F的最小依赖集。证明：采用构造法证明，步骤如下：对F中的每个函数依赖右部进行单一化处理：逐一检查F中的每个函数依赖XY，若Y=A1A2Ak，则用XAj取代（j=1，k）XY；去掉F中多余的函数依赖：逐一检查F中各函数依赖XA，令G=FXA，若AXG+，则XA多余，从F中去掉此函数依赖；去掉F中每个函数依赖左部的多余属性：逐一取出F中各函数依赖XA，设X=B1B2Bm，逐一考查Bi（i=1，m），若F与FXAXBiA等价，则以XBi取代X。重复步骤，直至F中的函数依赖不再发生变化。经上述处理后的F即为所求的最小函数依赖集（正则覆盖）Fm。说明：对F进行最小化时，处理函数依赖的顺序不同，得到的结果可能不同，所以一个函数依赖集F可能存在多个等价的最小函数依赖集。,5.3Armstrong公理系统,【例5.7】设有关系模式R（U，F1），U=A，B，C，D，E，F，G，H，F1=ABHC，AD，CE，BCHF，FAD，EF，BHE求F1的正则覆盖Fm。解：对函数依赖的右部进行单一化处理后F1如下：ABHC，AD，CE，BCHFFA，FD，EF，BHE去掉F1中多余的函数依赖，考察F1中的函数依赖，对于ABHC，设G1=F1ABHC，因为（ABH）G1+=A，B，H，E，F，D，C（ABH）G1+，所以ABHC不多余。采用同样的方法知：AD，CE也不多余。对于F1中的BCHF，设G1=F1BCHF，因为（BGH）G1+=B，G，H，E，F，D，A，C，F（BGH）G1+，所以BCHF多余，令F1=F1BCHF。采用同样的方法可知：FD也是多余的函数依赖，删除多余函数依赖后得F1如下：ABHC，AD，CE，FA，EF，BHE删除F1中函数依赖左部多余的属性：考察ABHC，令:G1=F1ABHCBHC，因为（BH）G1+=B，H，C，E，F，A，所以ABHC与BHC等价，由此得F1如下：BHC，AD，CE，FA，EF，BHE，采用同样的方法知：F1中的各函数依赖的左部无多余属性。再次根据算法可求得F1中BHE是多余的函数依赖，删除之，得：F1=BHC，AD，CE，FA，EF，此即为最小函数依赖集Fm。,5.4模式分解,前面我们介绍了各种范式，通过例子说明采用模式分解的方法可将一个属于较低级范式的关系模式分解为一组满足高一级范式要求的关系模式，现在的问题是应依据什么原则来进行模式分解呢？下面介绍有关的概念及算法。定义1关系模式R的一个分解是指=R1，R2，Rn，其中U=，UiUj，ij，i，j=1，n；Fi是F在Ui上的投影。定义2数据依赖集XY|XYF+XYUi的一个覆盖Fi叫做F在属性子集Ui上的投影。对于一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价，根据不同应用的需要，等价的含义一般基于如下分解准则之一：分解具有“无损连接性”；分解要“保持函数依赖”；分解既要“保持函数依赖”，又具有“无损连接性”。定义3m（r）设=R1，R2，Rn是R的一个分解，r是R的任一关系，定义m（r）为关系r在中各关系模式上投影的连接，即：m（r）=Ri（r）。,5.4模式分解,算法1判别一个分解的无损连接性。输入：R的一个分解=R1，RkU=A1，An设F为正则覆盖，F=FD1，FD2，FDp，记FDi为XiAli。输出：输出判别结果。步骤：建立初始表。建立一张n列k行的表，每列对应一个属性，每行对应分解中的一个关系模式，若属性Aj属于关系模式Ri对应的属性集Ui，则在第j列第i行交叉处填上aj，否则填上bij；对初始表进行处理。对F中的每个FDi：XiAli做如下操作：找到X所对应的列中具有相同符号的那些行，考查这些行中第li列的元素，若其中有ali，则全部改为ali；否则全部改为bmli，m是这些行的行号最小值。注意：若某个btli被更改为ali，则该表li列中所有的btli均应做相应修改。根据处理后的表进行判断。经第2步处理后，检查表中是否有一行为a1，a2，an，若有，则具有无损连接性，算法终止，否则，检查表中数据是否有变化，若有变化，则转第2步，否则，不具有无损连接性，算法终止。,5.4模式分解,【例5.8】设有关系模式R（U，F），U=A，B，C，D，E，F=AC，CD，BC，DEC，CEA，求R的所有码；判断=R1（AD），R2（AB），R3（BC），R4（CDE），R5（AE）是否为无损连接分解。解：（1）求码对属性进行分组仅出现在函数依赖左部的属性L=B，E既出现在函数依赖左部又出现在右部的属性LR=A，C，D求关系模式R（U，F）的码KEY因为KEYU，设X=LLR，M为X中单个属性或X中属性的最小组合，若（M）F+=U，则M为码，因为（BE）F+=B，C，D，E，A