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

第6章 关系数据库规范化理论 第第6章章 关系数据库规范化理论关系数据库规范化理论 6.1 关系规范化的作用关系规范化的作用 6.2 函数依赖函数依赖 6.3 关系模式的规范化关系模式的规范化 6.4 多值依赖和第四范式多值依赖和第四范式 6.5 关系的规范化程度关系的规范化程度 6.6 函数依赖公理与模式分解函数依赖公理与模式分解 6.7 小结小结 第6章 关系数据库规范化理论 6.1 关系规范化的作用关系规范化的作用 所谓规范化,就是用形式更为简洁、结构更加规范的关系模式取代原有关系的过程。例 有三个属性的工资表（姓名,级别,工资）关系模式。对应此模式建立的表如表 6 1 所示。第6章 关系数据库规范化理论 表 6 1 工 资 表第6章 关系数据库规范化理论 6.1.1 表 6 1 存在的问题 1.数据冗余度大 表 6 1 中,工资是从级别推导出的,但却重复存放。数据在数据库中的重复存放称为数据冗余。冗余度大,不仅浪费存储空间,重要的是在对数据进行修改时,又易造成数据的不一致性。如10级的工资变化时,如果表中有K个职工的工资为10级,就需要修改K次,一旦遗漏就使数据不一致。第6章 关系数据库规范化理论 2.插入与删除异常 无法插入某部分信息或删除掉不应删除的信息称为插入或删除异常。例如,9级工资为660元的信息无法插入表。因为该表的码是姓名,而目前无职工工资级别为9级,表中不能插入码为空值的记录。即在插入一行时,此关系模式强迫同时增加关于两个实体的数据。又如,要删除姓名为C的职工记录时,又将7级工资的信息一起删去了。即在删除一行时,删除了关于两个实体的数据。第6章 关系数据库规范化理论 6.1.2 解决方法 上述现象的产生,是由于关系模式不合理。如果一个关系中,存储了两个或两个以上实体的数据,一般应将它分解为多个关系,使每个关系只有一个实体。将表 6 1 分解为两个模式表达：职工级别（姓名,级别）,级别工资（级别,工资）,如表 6 2、表 6 3 所示。第6章 关系数据库规范化理论 表 6 2 职工级别 第6章 关系数据库规范化理论 表 6 3 级别工资 第6章 关系数据库规范化理论 改进后,有如下好处：(1)数据量减少。设有n个职工,m个工资级别,nm,则表 6 1 有3n个数据,表 6 2和表 6 3 共有2n+2m个数据,显然后者的数据量要少得多。(2)表达能力强。表 6 1 中无法进入的信息（如9级工资）,而在采用改进后的两个模式表达时则可加入；当删除职工C时,也不会丢失7级工资信息。(3)修改方便。改进后,修改某一级别工资时只要修改一处。第6章 关系数据库规范化理论 当然,改进后的关系模式也存在另外一个问题,当查询某个职工的工资时,需要将两个关系连接后进行查询,而关系的连接代价是很大的。那么,什么样的关系模式需要分解？分解关系模式的理论依据又是什么？分解后能完全消除上述三种问题吗？回答这些问题需要理论的指导。下面将加以讨论。第6章 关系数据库规范化理论 6.2 函数依赖函数依赖 6.2.1 属性间的关系 前面章节讲到客观世界的事务间有着错综复杂的联系。实体间的联系有两类,一类是实体与实体之间的联系；另一类是实体内部各属性间的联系。在数据库建模一章中主要讨论了前一类联系,现在讨论第二类联系。第6章 关系数据库规范化理论 属性间的联系可分为以下三类：1.一对一关系（1 1）以职工模式为例：职工（职工号,姓名,职称,部门）,如果该企业（或单位）中职工无重名,则属性职工号与姓名之间是1 1关系。一个职工号唯一地决定一个姓名,一个姓名也可决定唯一的职工号。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中至多有一个值与之对应,且反之亦然,则称X、Y两属性间是一对一关系。第6章 关系数据库规范化理论 2.一对多关系（1 m）职工模式中,职工号和职称间是一对多关系。一个职工号只对应一种职称（如胡一民只能对应工程师）,但一种职称却可对应多个职工号（如工程师可对应多名职工）。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中至多有一个值与之对应,而Y中的一个值却可以和X中的n个值（n0）相对应,则称Y对X是一对多关系。第6章 关系数据库规范化理论 3.多对多关系（m m）在职工模式中,职称和部门之间是多对多关系。一种职称可分布在多个部门中（如每一个部门中均可有工程师）,而一个部门中也可有多个职称。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中有m（m0）个值与之对应,而Y中的一个值也可以和X中的n个值（n0）相对应,则称Y对X是多对多关系。第6章 关系数据库规范化理论 上述属性间的三种关系实际上是属性值之间相互依赖又相互制约的反映,称为属性间的数据依赖。数据依赖是现实世界属性间相互联系的抽象,是世界内在的性质,是语义的体现。数据依赖共有三种：函数依赖（Functional Dependency,简称FD）、多值依赖（Multivalued Dependency,简称MVD）和连接依赖（Join Dependency,简称JD）,其中最重要的是函数依赖和多值依赖。第6章 关系数据库规范化理论 6.2.2 函数依赖 函数依赖是属性之间的一种联系。假设给定一个属性的值,就可以唯一确定（查到）另一个属性的值。例如,知道职工号的值,可以得出其对应的职称的值。如果这种情况成立，就可以说职称函数依赖于职工号。定义 1 所谓函数依赖是指在关系R中,X、Y为R的两个属性或属性组,如果对于R的所有关系r都存在：对于X的每一个具体值,Y都只有一个具体值与之对应,则称属性Y函数依赖于属性X。第6章 关系数据库规范化理论 或者说,属性X函数决定属性Y,记作XY。其中X叫决定因素,Y叫被决定因素。此定义可简单表述为：如果属性X的值决定属性Y的值,那么属性Y函数依赖于属性X。换一种说法是,如果知道X的值,就可以获得Y的值。(1)若Y函数不依赖于X,记作XY。(2)若XY,YX,记作XY。前面讨论的属性间的三种关系,并不是每一种关系中都存在函数依赖。第6章 关系数据库规范化理论 (1)如果两属性集X、Y间是1 1关系,则存在函数依赖：XY。如职工关系模式中，如果不允许同名职工存在,则有：职工号姓名。(2)如果两属性集X、Y间是1 m关系,则存在函数依赖：XY。如：职工号职称,职工号部门。(3)如果两属性集X、Y间是m n关系,则不存在函数依赖。如职称与部门之间即如此。第6章 关系数据库规范化理论 我们再以关系模式学生课程为例,来说明属性间的函数依赖。设关系模式为：学生课程（学生号,课程号,成绩,教师,教师办公室）,在该关系中,成绩要由学生号和课程号共同确定,但教师和教师办公室由课程号决定,所以此关系中包含了以下四种函数依赖关系：（学生号,课程号）成绩；课程号教师；课程号教师办公室；教师教师办公室注意,属性间的函数依赖不是指R的某个或某些关系满足上述限定条件,而是指R的一切关系都要满足定义中的限定。只要有一个具体关系r不满足定义中的条件,就破坏了函数依赖,使函数依赖不成立。第6章 关系数据库规范化理论 6.2.3 码的定义 在前面章节中我们已对码进行了直观的定义,下面用函数依赖的概念对码作出较为精确的形式化的定义。定义 2 设K是关系模式R（U,F）中的属性或属性组,K是K的任一真子集。若KU,而不存在KU,则K为R的候选码（Candidate Key）。若候选码多于一个,则选定其中的一个为主码（Primary Key）；包含在任一候选码中的属性,叫做主属性（Prime Attribute）；第6章 关系数据库规范化理论 不包含在任何码中的属性称为非主属性（Nonprime Attribute）或非码属性（Nonkey Attribute）；关系模式中,最简单的情况,单个属性是码,称为单码（Single Key）；最极端的情况,整个属性组是码,称为全码（AllKey）。前面我们已经多次遇到单码的情况,下面举一全码的例子。在第 5 章有关演员、制片公司、电影的一关系模式如下：签约（演员名,制片公司名,电影名）第6章 关系数据库规范化理论 该关系模式反映了某个演员为某部电影与某制片公司的签约情况。由于一个制片公司可以为一部电影和多个演员签约,一个演员可以和多个制片公司签约饰演多部电影中的角色,一部电影可由不同的制片公司制作。所以此关系模式的码为（演员名,制片公司名,电影名）,即全码。第6章 关系数据库规范化理论 定义 3 设有两个关系模式R和S,X是R的属性或属性组,并且X不是R的码,但X是S的码（或与S的码意义相同）,则称X是R的外部码（Foreign Key）,简称外码。设有如下两个关系模式：职工（职工号,姓名,性别,职称,部门号）部门（部门号,部门名,电话,负责人）其中部门号不是职工表的码,但是部门表的码,所以部门号在职工表中称为外码。第6章 关系数据库规范化理论 关系间的联系可通过同时存在于两个或多个关系中的主码和外码的取值来建立。例如要查询某个职工所在部门的详细情况,只需查询部门表中的部门号与该职工部门号相等的记录。所以主码和外部码提供了一个表示关系间联系的途经。第6章 关系数据库规范化理论 6.2.4 函数依赖和码的唯一性 码是由一个或多个属性组成的可唯一标识元组的最小属性组。码在关系中总是唯一的,即一个码函数唯一地决定一行。如果码的值重复,则整个元组都会重复。否则,违反实体完整性规则。与码的唯一性不同,函数依赖的决定因素可能是唯一的,也可能不是唯一的。如果我们知道A决定B,且A和B在同一关系中,但我们仍无法知道A是否能决定除B以外的其他所有属性，所以无法知道A在关系中是否是唯一的。第6章 关系数据库规范化理论 看关系模式：学生课程（学生号,课程号,成绩,教师,教师办公室）,此关系中包含的四种函数依赖为：（学生号,课程号）成绩；课程号教师；课程号教师办公室教师教师办公室其中,课程号是决定因素,但它不是唯一的。因为它能决定教师和教师办公室,但不能决定属性成绩。但决定因素（学生号,课程号）除了能决定成绩外,当然也能决定教师和教师办公室,所以它是唯一的。关系的码应取（学生号,课程号）。第6章 关系数据库规范化理论 函数依赖性是一个与数据有关的事物规则的概念。如果属性B函数依赖于属性A,那么,若知道了A的值,则完全可以找到B的值。这并不是说可以导算出B 的值,而是逻辑上只能存在一个B 的值。例如,在人这个实体中,如果知道某人的唯一标识符,如身份证号,则可以得到此人的性别、身高、职业等信息,所有这些信息都依赖于确认此人的唯一标识符。第6章 关系数据库规范化理论 通过非主属性如年龄,无法确定此人的身高,从关系数据库的角度来看,身高不依赖于年龄。事实上,这也就意味着码是实体实例的唯一标识符。因此,在以人为实体来讨论依赖性时,如果已经知道是哪个人,则身高、体重等等就都知道了。码指示了实体中的某个具体实例。第6章 关系数据库规范化理论 6.3 关系模式的规范化关系模式的规范化 6.3.1 非规范化的关系 当一个关系中的所有分量都是不可分的数据项时,该关系是规范化的。表 6 4 具有组合数据项,表 6 5 具有多值数据项,因此都不是规范化的表。第6章 关系数据库规范化理论 表 6 4 具有组合数据项的非规范化的表第6章 关系数据库规范化理论 表 6 5 具有多值数据项非规范化表 第6章 关系数据库规范化理论 6.3.2 第一范式（1NF）定义 4 如果关系模式R中不包含多值属性,则R满足第一范式,简称1NF（First Normal Form）,记作R1NF。1NF是对关系的最低要求,不满足1NF的关系是非规范化关系,如表 6 4、表 6 5 所示。非规范化关系转化为1NF的方法很简单,当然也不是唯一的。对表 6 4、表 6 5分别进行横向和纵向展开,可分别转化为如表 6 6、表 6 7 所示的符合1NF的关系。第6章 关系数据库规范化理论 表 6 6 消除组合数据项后的表 第6章 关系数据库规范化理论 表 6 7 消除多值数据项后的表 第6章 关系数据库规范化理论 6.3.3 第二范式（2NF）表 6 7 虽然已符合1NF的要求,但表中存在大量的数据冗余和潜在的数据更新异常。原因是该关系的码是（职工号,学历）,但姓名、职称、系名、系办公地址却与学历无关,即它们只与码的一部分有关。定义5 设X、Y是关系R的两个不同的属性或属性组,且XY。如果存在X的某一个真子集X,使XY成立,则称Y部分函数依赖于X,记作X Y。反之,则称Y完全函数依赖于X,记作X Y。F F 第6章 关系数据库规范化理论 定义6 如果一个关系R属于1NF,且它的所有非主属性都完全函数依赖于R的任一候选码,则R属于第二范式,记作R2NF。例如,对于关系模式：职工信息（职工号,姓名,职称,项目号,项目名称,项目排名）该模式存储了职工的信息和职工所参加的项目信息,码为（职工号,项目号）。函数依赖有：第6章 关系数据库规范化理论 因为：职工号姓名,所以：（职工号,项目号）姓名；同样有：（职工号,项目号 职称,（职工号,项目号）项目名称；（职工号,项目号）项目排名 因此非主属性姓名、职称、项目名称并不完全依赖于码,它不符合2NF的定义。P P P F 第6章 关系数据库规范化理论 因此非主属性姓名、职称、项目名称并不完全依赖于码,它不符合2NF的定义。不符合2NF定义的关系模式,会产生以下几个问题：(1)插入异常。假如要插入一职工,但该职工还未参加任何项目,即项目号为空。根据实体完整性约束规则,关系中元组的主码属性不能为空,项目号是主属性,因此,该职工信息无法插入。第6章 关系数据库规范化理论 (2)删除异常。假设有一职工,只参加了一个项目,现在,又从这个项目中退出来了，该职工的此项目记录将被删除,由于项目号是主属性,该记录只能被全部删除,该职工的其他信息也随着被删除。这样就删除了不该删除的信息,即出现了删除异常。第6章 关系数据库规范化理论 (3)修改异常。当某个项目的项目名称发生变化时,必须修改多个元组,造成了修改的复杂化,一旦有遗漏,将破坏数据库中数据的一致性。可把它分解如下,使其符合2NF：职工项目（职工号,姓名,职称）排名（职工号,项目号,项目排名）项目(项目号,项目名称)第6章 关系数据库规范化理论 同样,对于表 6 7 所示的关系模式：职工信息（职工号,姓名,职称,系名,系办公地址,学历,毕业年份）由于也包含了部分函数依赖,不符合2NF的定义,可将其分解为下面两个关系模式：职工信息（职工号,姓名,职称,系名,系办公地址）学历（职工号,学历,毕业年份）推论：如果关系模式R1NF,且它的每一个候选码都是单码,则R2NF。第6章 关系数据库规范化理论 6.3.4 第三范式（3NF）符合第二范式的关系模式仍可能存在数据冗余、更新异常等问题。如前面从表 6 7 分解出的职工信息关系模式：职工信息（职工号,姓名,职称,系名,系办公地址）。如果一个系有100位职工,那么系办公地址就要重复存储100次,存在着较高的数据冗余。原因是此关系模式的码是职工号,而系办公地址通过系名函数依赖于职工号,即职工号系名,系名系办公地址,是一个传递依赖的过程。第6章 关系数据库规范化理论 定义7 在关系R中,X、Y、Z是R的三个不同的属性或属性组,如果XY,YZ，但YX且Y不是X的子集,则称Z传递依赖于X。再看表 6 1 的关系模式,它之所以存在着数据冗余、插入或删除异常,就是因为其中存在着传递函数依赖：姓名级别,级别工资 定义8 如果关系模式R属于2NF,且它的每一个非主属性都不传递依赖于任何候选码,则称R是第三范式,记作R3NF。第6章 关系数据库规范化理论 推论1 如果关系模式R1NF,且它的每一个非主属性既不部分依赖、也不传递依赖于任何候选码,则R3NF。推论2 不存在非主属性的关系模式一定为3NF。上述职工关系不属于3NF,可把它分解如下,使其符合3NF：职工（职工号,姓名,职称,系名）系（系名,系办公地址）第6章 关系数据库规范化理论 6.3.5 改进的3NFBCNF 第三范式的修正形式是BoyeeCodd范式（简称BCNF）,是由Boyee与Codd提出的。定义9 设关系模式R（U,F）1NF,若F的任一函数依赖XY（YX）中X都包含了R的一个码,则称RBCNF。换言之,在关系模式R中,如果每一个决定因素都包含码,则RBCNF。第6章 关系数据库规范化理论 由BCNF的定义可以得到以下推论：如果RBCNF,则 R中所有非主属性对每一个码都是完全函数依赖;R中所有主属性对每一个不包含它的码,都是完全函数依赖;R中没有任何属性完全函数依赖于非码的任何一组属性。第6章 关系数据库规范化理论 定理：如果RBCNF,则R3NF一定成立。证明：用反证法。如果RBCNF,但不是3NF,则R中一定存在传递函数依赖。即R中必定存在候选码X,非主属性A,属性组Y,其中AX,AY,YX,使得XYA成立。Y不是R的码,但Y是R的决定因素,根据BCNF的定义,R不是BCNF,与假设相矛盾。所以假设不成立。下面是一个BCNF的例子：职工（职工号,姓名,职称,系名）第6章 关系数据库规范化理论 在该关系中,假定职工无重名,则候选码为职工号或姓名,除了职工号和姓名以外没有其他决定因素,即符合BCNF的定义,故该关系是BCNF的。当然,该关系中的非主属性（职称或系名）对这两个码不存在部分函数依赖和传递函数依赖,因此是3NF的。但是如果R3NF,R未必属于BCNF。3NF比BCNF放宽了一个限制,即允许决定因素不包含码。请看下面两个例子：第6章 关系数据库规范化理论 例 6.1 通讯（城市名,街道名,邮政编码）该关系的码是（城市名,街道名）,根据语义其函数依赖集为：F=（城市名,街道名）邮政编码,邮政编码城市名 所以非主属性邮政编码完全函数依赖于码,且无传递依赖,属于3NF。但邮政编码也是一个决定因素,它没有包含码,所以该关系不属于BCNF。第6章 关系数据库规范化理论 例 6.2 授课（学生,教师,课程）假设该校规定：一个教师只能教一门课,每门课可由多个教师讲授。学生一旦选定某门课,教师就相应地固定。根据语义关系的函数依赖集为：F=教师课程,（学生,课程）教师,（学生,教师）课程 该关系的候选码为（学生,课程）或（学生,教师）,因此三个属性都是主属性,由于不存在非主属性,该关系一定是3NF的。但由于决定因素教师没包含码,该关系不属于BCNF。第6章 关系数据库规范化理论 不属于BCNF的关系模式,仍然存在数据冗余问题。如例 6.2 中如果有100个学生选定了某一门课,则教师与该课程的关系就要重复存储100次。可分解为如下两个BCNF的关系模式,消除此种冗余：教师（教师,课程）学生（学生,教师）一个关系模式如果达到了BCNF,那么在函数依赖范围内,它已实现了彻底的分离,消除了数据冗余、插入和删除异常。规范化程度还可有更高的范式：4NF、5NF,将在后面介绍。第6章 关系数据库规范化理论 6.4 多值依赖和第四范式多值依赖和第四范式 6.4.1 多值依赖（Multivalued Dependency）在属性之间的数据依赖中,除了函数依赖,还有多值依赖。在讨论多值依赖之前,请先看一个例子,见表 6 8。第6章 关系数据库规范化理论 表 6 8 教师开课一览表 第6章 关系数据库规范化理论 从表中可以得到如下信息：哪门课由哪些教师开,由哪些班级开设了这门课。因此,我们可以从已知的元组推出表中一定存在的其他元组。例如,如果已知表中存在元组：（网络技术,王宝钢,98级本科）（网络技术,张丽萍,99级大专）那么表中应该有元组：（网络技术,王宝钢,99级大专）（网络技术,张丽萍,98级本科）将表 6 8 转化为规范化的表 6 9：教师开课表。第6章 关系数据库规范化理论 表 6 9 教师开课表：CTC第6章 关系数据库规范化理论 第6章 关系数据库规范化理论 这种依赖关系称为多值依赖。与函数依赖不同,函数依赖是属性值之间的约束关系,而多值依赖是元组值之间的约束关系。定义10 设R（U）是属性集U上的一个关系模式,X、Y、Z是U的子集,且Z=U-X-Y。如果对R（U）的任一关系r,给定一对（x,z）值,都有一组Y值与之对应,这组Y值仅仅决定于x值而与z值无关。称Y多值依赖于X,或X多值决定Y,记作XY。第6章 关系数据库规范化理论 在表 6 9 中,对于一对（x,z）值（数据结构,00级本科）有一组Y值王晓萍,陈保乐,刘彤彤与之对应,这组值仅决定于课程“数据结构”。对于另一个（x,z）值（数据结构，00级辅修）,对应的仍是这组Y值王晓萍,陈保乐,刘彤彤。因此,课程教师。第6章 关系数据库规范化理论 多值依赖的另一个等价的形式化定义为：设关系模式R（U）,X、Y、Z是U的子集,Z=U-X-Y,r是R的任意一个关系,t1、t2是r的任意两个元组。如果t1X=t2X,在r中存在元组t3,使得 t3X=t1X,t3Y=t1Y,t3Z=t2Z 成立,则XY。上述定义中,由于t1、t2的对称性,实际隐含着关系r中还存在着另一个元组t4,t4满足：t4X=t1X,t4Y=t1Y,t4Z=t2Z第6章 关系数据库规范化理论 换句话说,如果r有两个元组在X属性上的值相等,则交换这两个元组在Y上的属性值,得到的两个新元组也必是r中的元组。定义中如果Z=（即Z为空集）,则称XY为平凡的多值依赖,否则为非平凡多值依赖。下面再举一多值依赖的例子。例：关系模式：供应（项目,供应商,零件）,假设一个项目可由不同的供应商供应该项目所需要的多种零件,一个供应商可为多个项目供应多种零件,如表 6 10 所示。第6章 关系数据库规范化理论 表 6 10 供 应第6章 关系数据库规范化理论 对于项目中的每一个Ii,都有一完整的供应商集合与之对应,同时交换供应商和零件的值所得的新元组必在原关系中。因此有,项目供应商,项目零件。多值依赖具有以下性质：(1)多值依赖具有对称性。若XY,则XZ,其中Z=U-X-Y。如上例中,对于项目中的每一个Ii,都有一完整的零件集合与之对应。因此,项目零件。第6章 关系数据库规范化理论 (2)多值依赖具有传递性。若XY,YZ,则XZ-Y。(3)若XY,XZ,则XYZ。(4)若XY,XZ,则XYZ。(5)若XY,XZ,则XY-Z,XZ-Y。第6章 关系数据库规范化理论 一般来讲,当关系至少有三个属性,其中的两个是多值,且它们的值只依赖于第三个属性时,才会有多值依赖。即对于关系R（A,B,C）,如果A决定B的多个值,A决定C的多个值,B和C相互独立,这时才存在多值依赖。第6章 关系数据库规范化理论 在具有多值依赖的关系中,如果随便删去一个元组而破坏了其对称性,那么,为了保持多值依赖关系中数据的“多值依赖”性,必须删去另外的元组以维持其对称性。这个规则称为“多值依赖的约束规则”,这种规则只能由设计者在软件设计中加以体现,目前的RDBMS不具有维护此规则的能力。函数依赖可看成是多值依赖的特例,即函数依赖的一定是多值依赖；多值依赖是函数依赖的概括,即存在多值依赖的关系,不一定存在函数依赖。第6章 关系数据库规范化理论 6.4.2 第四范式（4NF）定义11 如果关系模式R1NF,对于R的每个非平凡的多值依赖XY（YX）,X含有码,则称R是第四范式,即R4NF。一个关系模式如果属于4NF,则一定属于BCNF,但一个BCNF的关系模式不一定是4NF的,R中所有的非平凡多值依赖实际上是函数依赖。在前面的供应关系中,项目供应商,项目零件,且都是非平凡的多值依赖。第6章 关系数据库规范化理论 但该关系的码是全码（项目,供应商,零件）,而项目没有包含码（只是码的一部分）,所以该关系模式属于BCNF而不属于4NF。如将其分解为两个关系,可达到4NF：需求（项目,零件）供应（项目,供应商）这两个关系中,项目零件,项目供应商,它们均是平凡多值依赖。即关系中已不存在非平凡、非函数依赖的多值依赖,所以它们均是4NF。第6章 关系数据库规范化理论 一般地,如果关系模式R（X,Y,Z）满足XY,XZ,那么可将它们分解为关系模式R1（X,Y）和R2（X,Z）。在一般应用中,即使作数据存储操作,也只要达到BCNF就可以了。因为应用中具有多值依赖的关系较少,因此需要达到4NF的情况也就比较少。在理论上,还有与数据依赖中的连接依赖（JD）有关的第五范式（5NF）,这里就不再介绍了。第6章 关系数据库规范化理论 6.5 关系的规范化程度关系的规范化程度 各种规范化之间的关系为：5NF4NFBCNF3NF2NF1NF。关系规范化的目的是解决关系模式中存在的数据冗余、插入和删除异常、更新繁琐等问题。其基本思想是消除数据依赖中的不合适部分,使各关系模式达到某种程度的分离,使一个关系描述一个概念、一个实体或实体间的一种联系。因此,规范化的实质是概念的单一化。第6章 关系数据库规范化理论 关系规范化的递进过程如图 6 1 所示。一般来说,规范化程度越高,分解就越细,所得数据库的数据冗余就越小,且更新错误也可相对减少。但是,如果某一关系经过数据大量加载后,主要用于检索,那么,即使它是一个低范式的关系,也不要去追求高范式而将其不断进行分解。因为在检索时,又会通过多个关系的自然连接才能获得全部信息,从而降低了数据的检索效率。即,数据库设计满足的范式越高,其数据处理的开销也越大。第6章 关系数据库规范化理论 图 6 1 范式递进过程示意图 1NF消除非主属性对码的部分函数依赖BCNF2NF消除非主属性对码的传递函数依赖3NF消除主属性对码的部分和传递依赖4NF消除非平凡且非函数依赖的多值依赖5NF消除不为候选码所隐含的连接依赖第6章 关系数据库规范化理论 所以,规范化的基本原则是：由低到高,逐步规范,权衡利弊,适可而止。通常,以满足第三范式为基本要求。把一个非规范化的数据结构转换成第三范式,一般经过以下几步：(1)把该结构分解成若干个属于第一范式的关系。(2)对那些存在组合码,且有非主属性部分函数依赖的关系必须继续分解,使所得关系都是属于第二范式。第6章 关系数据库规范化理论 (3)若关系中有非主属性传递依赖于码,则继续分解之,使得关系都属于第三范式。关系模式的规范化过程是通过投影分解实现的,即用投影运算把一个模式分解成若干个高一级的关系模式。这种投影分解不是唯一的。在分解时应注意满足以下三个条件：(1)分解是无损连接分解,分解后既不丢失又不增加信息。(2)分解所得的所有关系都是高一级范式的。(3)分解所得关系的个数最少。第6章 关系数据库规范化理论 事实上,规范化理论是在与SQL编程语言结合时产生的。关系理论的基本原则指出,数据库被规范化后,其中的任何数据子集都可以用基本的SQL操作符获取。这就是规范化的重要性所在。数据库不进行规范化,就必须通过编写大量复杂代码来查询数据。规范化规则在关系建模和关系对象建模中同等重要。第6章 关系数据库规范化理论 6.6*函数依赖公理与模式分解函数依赖公理与模式分解 在前面的规范化过程中,在进行模式分解时,并没有给出分解的算法。实际上,在规范化理论中,模式分解以及判断分解是否等价是有一定算法的。函数依赖的公理系统是模式分解算法的基础,它可以从已知的函数依赖,推导出其他函数依赖。下面首先讨论函数依赖的一套推论规则,这套规则是1974年由Armstrong提出来的,常被称为Armstrong公理系统。第6章 关系数据库规范化理论 6.6.1 函数依赖公理 Armstrong公理系统 设有关系模式R（U,F）,X,Y,Z,WU,则对R（U,F）有：A1（自反律）：若YX,则XY；A2（增广律）：若XY,则XZYZ；A3（传递律）：若XY,YZ,则XZ。这些规则是保真的,它们不会产生错误的函数依赖。说明：XZ表示XZ。第6章 关系数据库规范化理论 引理 6.1 Armstrong公理是正确的。即如果函数依赖F成立,则由F根据Armstrong公理所推导的函数依赖总是成立的。证明：设t1、t2是关系R中的任意两个元组。A1：如果t1X=t2X,则因为YX,所以有t1Y=t2Y,故XY成立。A2：如果t1XZ=t2XZ,则有t1X=t2X、t1Z=t2Z。第6章 关系数据库规范化理论 又已知XY,因此得t1Y=t2Y。可知t1YZ=t2YZ,故XZYZ成立。A3：如果t1X=t2X,则t1Y=t2Y；如果t1Y=t2Y,则t1Z=t2Z。因此可得：如果t1X=t2X,则t1Z=t2Z,即XZ成立。第6章 关系数据库规范化理论 定理 6.1 Armstrong公理是正确的、完备的。由Armstrong公理系统,可以得到以下三个推论：合成规则：若XY,XZ,则XYZ；分解规则：若XYZ,则XY,XZ；伪传递规则：若XY,WYZ,则XWZ。第6章 关系数据库规范化理论 引理 6.2 XA1A2Ak成立的充分必要条件是XAi成立（i=1,2,k）。例 6.3 设关系模式R（A,B,C,G,H,I）,函数依赖集为 F=AB,AC,CGH,CGI,BH,利用规则,可以得到关系中存在以下几个函数依赖：(1)AH。由于AB,BH,使用传递律可得到AH。(2)CGHI。由于CGH,CGI,由合成律可得CGHI。(3)AGI。由于AC,CGI,由伪传递律可推出AGI。第6章 关系数据库规范化理论 6.6.2 闭包及其计算 定义 12 设关系模式R（U,F）,U为R的属性集合,F为其函数依赖集,则称所有用Armstrong公理从F推出的函数依赖XAi中Ai的属性集合,为X的属性闭包,记作X+,读作X关于函数依赖集F的闭包。由引理6.2可以推出：引理6.3 设关系模式R（U,F）,U为R的属性集合,F为其函数依赖集,X,YU,则从F推出XY的充要条件是YX+。第6章 关系数据库规范化理论 如果要判断XY是否能由F根据Armstrong公理导出,只需求出X+,判断Y是否为X+的子集。这可由算法6.1完成。算法 6.1 求属性集X关于函数依赖F的属性闭包X+。输入：关系模式R的全部属性集U,U的子集X,U上的函数依赖集F。输出：X关于F的属性闭包X+。第6章 关系数据库规范化理论 步骤：设i=0,1,2,。(1)初始化：i=0,X(i）=X(0)=X。(2)求属性集A。A是这样的属性：在F中寻找尚未用过的左边是X(i）子集的函数依赖：Y(i)X(i),并且在F中有Y(i)Z(i),则A=Z(1)Z(2)Z(i)；(3)X(i+1)=X(i）A。(4)判断以下条件之一是否成立,若有条件成立,则转向(5)；否则,i=i+1,转向(2)。第6章 关系数据库规范化理论 X(i+1)=X(i）；X(i）中已包含了R的全部属性；在F中的每个函数依赖的右边属性中已没有X(i）中未出现过的属性；在F中未用过的函数依赖的左边属性已没有X(i）的子集。(5)输出X(i+1）,即为X+。算法 6 1 实际是系统化寻找满足条件AX+的属性的方法。第6章 关系数据库规范化理论 例 6.4 设关系模式R（U,F）,其中,U=A,B,C,D,E,I,F=AD,ABC,BIC,EDI,CE,求（AC）+。解：(1)令X=AC,则X(0)=AC。(2)在F中找出左边是AC子集的函数依赖：AD,CE。(3)X(1)=X(0)DE=ACDE。第6章 关系数据库规范化理论 (4)很明显X(1)X(0),所以X(i)=X(1),并转向算法中的步骤(2)。(5)在F中找出左边是ACDE子集的函数依赖：EDI。(6)X(2)=X(1)I=ACDEI。(7)虽然X(2)X(1),但是F中未用过的函数依赖的左边属性已没有X(2)的子集,所以,可停止计算,输出（AC）+=X(2)=ACDEI。第6章 关系数据库规范化理论 算法6.1可用伪Pascal代码书写如下：（输出结果存储在变量result中）result =X;WHILE(result发生变化)DO FOR EACH 函数依赖YZ IN F DO BEGIN IF Yresult THEN result =resultZ;END 读者可自行验证此算法描述的正确性。第6章 关系数据库规范化理论 6.6.3 函数依赖的覆盖 定义13 设F和G是关系模式R（U）上的两个函数依赖集,如果F+=G+，则称F和G是等价的,记作FG。也可称为F覆盖G,或G覆盖F,或F、G相互覆盖。引理6.4 FG的充分必要条件是FG+、GF+。引理6.5 任一函数依赖集总可以为一右边都为单属性的函数依赖集所覆盖。第6章 关系数据库规范化理论 证明：构造G=XA|XYF且AY根据分解规则：GF+；根据合并规则：FG+。可得：F+=G+,即F为G所覆盖。证毕。第6章 关系数据库规范化理论 定义14 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集,也称为最小依赖集或最小覆盖。(1)F中任一函数依赖的右部都是单属性。(2)F中任一函数依赖XA,都不会使F与F-XA等价。(3)F中任一函数依赖XA,X的任一真子集Z,不会使F-XAZA与F等价。条件(2)保证了F中不存在多余的函数依赖,条件(3)保证了F中每个函数依赖的左边没有多余的属性。第6章 关系数据库规范化理论 定理6.2 任一函数依赖集F均等价于一个极小函数依赖集Fm。最小依赖集可由算法6.2计算出来。算法6.2 计算最小依赖集。输入：一个函数依赖集F 输出：F的一个等价最小依赖集G。第6章 关系数据库规范化理论 步骤：(1)应用分解规则,使F的每个函数依赖的右部属性都为单属性。(2)依次去除F的每个函数依赖左部多余的属性。设XYA是F的任一函数依赖,在F中求出X的闭包X+。如果X+包含了Y,则Y为多余属性,该函数依赖变为XA。(3)依次去除多余的函数依赖。设XA是F的任一函数依赖,在F-XA中求出X的闭包X+。如果X+包含了A,则XA为多余的函数依赖,应该去除；否则,不能去除。第6章 关系数据库规范化理论 例 6.5 设有函数依赖集F=AC,CA,BAC,DAC,BDA,计算它等价的最小依赖集。解：(1)化单依赖右边的属性,结果为 F1=AC,CA,BA,BC,DA,DC,BDA (2)去除F1的依赖中左边多余的属性。对于BDA,由于有BA,所以是多余的。结果为 F2=AC,CA,BA,BC,DA,DC第6章 关系数据库规范化理论(3)去除F2中多余的依赖。因为：AC,CA,所以AC。故：BA、BC以及DA、DC中之一为多余的。取F3=AC,CA,BA,DA。在F3中：对于AC,F3-AC中A+=A；对于CA,F3-CA中C+=C；对于BA,F3-BA中B+=B；对于DA,F3-DA中D+=D；所以,F3中已没有多余的函数依赖。即F的等价最小依赖集为：AC,CA,BA,DA。第6章 关系数据库规范化理论 注意：函数依赖集的最小集并不是唯一的,本例中还可以有以下几个答案：AC,CA,BA,DA 或 AC,CA,BC,DA 或 AC,CA,BC,DC 第6章 关系数据库规范化理论 6.6.4 关系模式的分解 关系模式经分解后,应与原来的关系模式等价。所谓“等价”是指两者对数据的使用者来说应是等价的。即对分解前后的关系,做相同内容的查询,应产生同样的结果。这是对模式分解的基本要求。历年来,人们对等价的概念形成了三种不同的定义：分解具有“无损连接性”（Lossless join）；分解具有“函数依赖保持性”（Preserve dependency）；分解既要具有“无损连接性”,又要具有“函数依赖保持性”。第6章 关系数据库规范化理论 一、无损连接性 所谓无损连接性是指,对关系模式分解时,原关系模式下的任一合法关系实例,在分解之后,应能通过自然连接运算恢复起来。无损连接性有时也称为无损分解。定义 15 设=R1,R2,Rk是关系模式R（U,F）的一个分解,如果对于R的任一满足F的关系r,都有 则称分解满足函数依赖集F的无损连接。根据算法6.3可以测试一个分解具有无损连接性（是否为无损分解）。第6章 关系数据库规范化理论 算法 6.3 检验分解的无损连接性。输入：关系模式R（A1,A2,An）；R上的函数依赖集F；R上的分解=R1,R2,Rk。输出：是否具有无损连接性。步骤：(1)构造一k行n列的表（或矩阵）,第i行对应于分解后的关系模式Ri,第j列对应于属性Aj,如表 6 11 所示。第6章 关系数据库规范化理论 表 6 11 构造判断矩阵 第6章 关系数据库规范化理论 (2)对F中的每一个函数依赖进行反复的检查和处理。具体处理为：取F中一个函数依赖XY,在X的分量中寻找相同的行,然后将这些行中的Y分量改为相同的符号。即如果其中之一为aj,则将bij改为aj；若其中无aj,则改为bij,如：两个符号分别为b23和b13,则将它们统一改为b23或b13。表中各分量的值由下面的规则确定：jjiijijjiaARMbAR第6章 关系数据库规范化理论 (3)如此反复进行,直至M无可改变为止。如果发现某一行变成了a1,a2,an,则具有无损连接性；否则,不具有无损连接性。例 6.6 设关系模式R（U,F）中,U=A,B,C,D,E,F=ABC,CD,DE,R的一个分解=R1（A,B,C）,R2（C,D）,R3（D,E）。试判断具有无损连接性。第6章 关系数据库规范化理论 表 6 12 分解的无损连接判断表第6章 关系数据库规范化理论 解：(1)首先构造初始表,如表 6 12(a)所示。(2)按下列次序反复检查函数依赖和修改M：ABC,属性A、B（第1、2列）中都没有相同的分量值,故M值不变；CD,属性C中有相同值,故应改变D属性中的M值,b14改为a4；DE,属性D中有相同值,b15、b25均改为a5。结果如表 6 12（b）所示。第6章 关系数据库规范化理论 (3)此时第一行已为a1,a2,a3,a4,a5,所以具有无损连接性。说明：在上例步骤后,如果没有出现a1,a2,a3,a4,a5,并不能马上判断不具有无损连接性。而应该进行第二次的函数依赖检查和修改M。直至M值不能改变,才能判断是否具有无损连接性。第6章 关系数据库规范化理论 二、函数依赖保持性 定义16 设有关系模式R,F是R的函数依赖集,Z是R的一个属性集合,则Z所涉及到的F中所有函数依赖为F在Z上的投影,记为Z(F),有 Z(F)=XY|XYF+且XYZ 定义 17 设关系模式R的一个分解=R1,R2,Rk,F是R的依赖集,如果F等价于 ,则称分解具有依赖保持性。12()()()KRRRFFF第6章 关系数据库规范化理论 一个无损连接的分解不一定具有依赖保持性；同样地,一个依赖保持的分解也不一定具有无损连接性。检验分解是否具有依赖保持性,实际上是检验 是否覆盖F。12()()()KRRRFFF第6章 关系数据库规范化理论 算法 6.4 检验一个分解是否具有依赖保持性。输入：关系模式R上的函数依赖集F；R的一个分解=R1,R2,Rk。输出：是否具有依赖保持性。步骤：(1)计算F到每一个Ri上的投影 ,i=1,2,k；1()RF第6章 关系数据库规范化理论(2)FOR 每一个XYF DO Z1=X；Z0=；DO WHILE Z1Z0 Z0=Z1；FOR i=1 TO k DO Z1=Z1（Z1Ri）+Ri）ENDFOR ENDDO IF Y-Z1=RETURN(true)RETURN(false)ENDFOR第6章 关系数据库规范化理论 例 6.7 试判断例 6.6 中的分解是否具有依赖保持性。解：因为123123(),(),()()()(),RRRRRRFABCFCDFDEFFFABC CD DE所以 第6章 关系数据库规范化理论 等价于F,因此具有依赖保持性。在实际数据库设计中,关系模式的分解主要有两种准则：只满足无损连接性；既满足无损连接性,又满足函数依赖保持性。准则比准则理想,但分解时受到的限制更多。如果一个分解,只满足函数依赖保持性,但不满足无损连接性,是没有实用价值的。第6章 关系数据库规范化理论 6.7 小小 结结 在关系模式中,并非所有关系的存储质量都是一样的。规范化是把存储质量不太“好”的关系,转化为质量较“好”的关系的过程。函数依赖是属性间的联系。在同一关系中,如果X的值决定Y的值,则Y函数依赖于X,决定因素是位于函数依赖左边的由一个或多个元素组成的属性组。码是能唯一标识一个元组的包含一个或多个属性的属性组,每个关系至少有一个码。第6章 关系数据库规范化理论 在极端情况下,码是关系中的所有属性构成的集合。码总是唯一的,但函数依赖中的决定因素则不一定。属性是否是码以及属性间的依赖关系是没有规则可言的,而是决定于用户环境的需要和数据库设计人员的理解。为了减少数据冗余和消除更新异常,可以把一个关系分解成两个或多个关系。使它们达到一定的范式。根据定义,每一个规范化的关系都在第一范式中。第6章 关系数据库规范化理论 如果一个关系的所有非主属性都依赖于整个码,则该关系在第二范式中。如果一个关系在第二范式中,且没有非主属性对码的传递依赖,则该关系在第三范式中。如果一个关系的所有决定因素都是候选码,则该关系在BC范式中。在函数依赖讨论范围内,BC范式是最高范式。如果一个关系在BC范式中,且没有非平凡的多值依赖,则该关系在第四范式中。第五范式的定义我们没有讨论。第6章 关系数据库规范化理论 关系的规范化程度并非是越高越好。当一个表分解为两个或多个表时,就产生了表间的关联约束（通过外部码实现）。如果处理两个表及其关联约束的额外费用超过了避免更新异常所带来的好处,则不推荐使用规范化技术。规范化技术的出发点,是假设已存在一个单一的关系模式,这就是泛关系假设。因此,对于错综复杂的现实世界作第一次抽象（概念模型）时,并未完全把握本质内容的话,规范化技术的收效也是不大的。