关系数据库规范化理论.doc

第4章 关系数据库规范化理论数据库设计的一个最基本的问题是怎样建立一个合理的数据库模式，使数据库系统无论是在数据存储方面，还是在数据操作方面都具有较好的性能。什么样的模型是合理的模型，什么样的模型是不合理的模型，应该通过什么标准去鉴别和采取什么方法来改进，这是在进行数据库设计之前必须明确的问题。为使数据库设计合理可靠、简单实用，长期以来，形成了关系数据库设计理论，即规范化理论。它是根据现实世界存在的数据依赖而进行的关系模式的规范化处理，从而得到一个合理的数据库设计效果。本章首先说明关系规范化的作用，接着引入函数依赖和范式等基本概念，然后介绍关系模式等价性判定和模式分解的方法，最后简要介绍两种数据依赖的概念。4.1 关系规范化的作用4.1.1问题的提出从前面的有关章节可知，关系是一张二维表，它是涉及属性的笛卡尔积的一个子集。从笛卡尔积中选取哪些元组构成该关系，通常是由现实世界赋予该关系的元组语义来确定的。元组语义实质上是一个n目谓词（n是属性集中属性的个数）。使该n目谓词为真的笛卡尔积中的元素（或者说凡符合元组语义的元素）的全体就构成了该关系。但由上述关系所组成的数据库还存在某些问题。为了说明的方便，我们先看一个实例。【例4.1】设有一个关于教学管理的关系模式R(U)，其中U由属性Sno、Sname、Ssex、Dname、Cname、Tname、Grade组成的属性集合，其中Sno的含义为学生学号，Sname为学生姓名，Ssex为学生性别，Dname为学生所在系别，Cname为学生所选的课程名称，Tname为任课教师姓名，Grade为学生选修该门课程的成绩。若将这些信息设计成一个关系，则关系模式为：教学（Sno，Sname，Ssex，Dname，Cname，Tname，Grade）选定此关系的主键为（Sno,Cname）。由该关系的部分数据（如表4-1所示），我们不难看出，该关系存在着如下问题：1. 数据冗余（Data Redundancy）l 每一个系名对该系的学生人数乘以每个学生选修的课程门数重复存储。l 每一个课程名均对选修该门课程的学生重复存储。l 每一个教师都对其所教的学生重复存储。2. 更新异常（Update Anomalies）由于存在数据冗余，就可能导致数据更新异常，这主要表现在以下几个方面： 插入异常（Insert Anomalies）：由于主键中元素的属性值不能取空值，如果新分配来一位教师或新成立一个系，则这位教师及新系名就无法插入；如果一位教师所开的课程无人选修或一门课程列入计划但目前不开课，也无法插入。 修改异常（Modification Anomalies）：如果更改一门课程的任课教师，则需要修改多个元组。如果仅部分修改，部分不修改，就会造成数据的不一致性。同样的情形，如果一个学生转系，则对应此学生的所有元组都必须修改，否则，也出现数据的不一致性。 删除异常（Deletion Anomalies）：如果某系的所有学生全部毕业，又没有在读及新生，当从表中删除毕业学生的选课信息时，则连同此系的信息将全部丢失。同样地，如果所有学生都退选一门课程，则该课程的相关信息也同样丢失了。由此可知，上述的教学管理关系尽管看起来能满足一定的需求，但存在的问题太多，从而它并不是一个合理的关系模式。表4-1 教学关系部分数据SnoSnameSsexDnameCnameTnameGrade0450301张三恺男计算机系高等数学李刚830450301张三恺男计算机系英语林弗然710450301张三恺男计算机系数字电路周斌920450301张三恺男计算机系数据结构陈长树860450302王薇薇女计算机系高等数学李刚790450302王薇薇女计算机系英语林弗然940450302王薇薇女计算机系数字电路周斌740450302王薇薇女计算机系数据结构陈长树680420131陈杰西男园林系高等数学吴相舆970420131陈杰西男园林系英语林弗然790420131陈杰西男园林系植物分类学花裴基930420131陈杰西男园林系素描丰茹884.1.2 解决的方法不合理的关系模式最突出的问题是数据冗余。而数据冗余的产生有着较为复杂的原因。虽然关系模式充分地考虑到文件之间的相互关联而有效地处理了多个文件间的联系所产生的冗余问题。但在关系本身内部数据之间的联系还没有得到充分的解决，正如例4.1所示，同一关系模式中各个属性之间存在着某种联系，如学生与系、课程与教师之间存在依赖关系的事实，才使得数据出现大量冗余，引发各种操作异常。这种依赖关系称之为数据依赖（Data Independence）。关系系统当中数据冗余产生的重要原因就在于对数据依赖的处理，从而影响到关系模式本身的结构设计。解决数据间的依赖关系常常采用对关系的分解来消除不合理的部分，以减少数据冗余。在例4.1中，我们将教学关系分解为三个关系模式来表达：学生基本信息（Sno，Sname，Ssex，Dname），课程信息（Cno，Cname，Tname，）及学生成绩（Sno，Cno，Grade），其中Cno为学生选修的课程编号；分解后的部分数据如表4-2、表4-3与表4-4所示。表4-2 学生信息SnoSnameSsexDname0450301张三恺男计算机系0450302王薇薇女计算机系0420131陈杰西男园林系表4-3 课程信息CnoCnameTnameGS01101高等数学李刚YY01305英语林弗然SD05103数字电路周斌SJ05306数据结构陈长树GS01102高等数学吴相舆ZF02101植物分类学花裴基SM02204素描丰茹表4-4 学生成绩SnoCnoGrade0450301GS01101830450301YY01305710450301SD05103920450301SJ05306860450302GS01101790450302YY01305940450302SD05103740450302SJ05306680420131GS01102970420131YY01305790420131ZF02101930420131SM0220488对教学关系进行分解后，我们再来考察一下： 数据存储量减少。设有n个学生，每个学生平均选修m门课程，则表4-1中学生信息就有4nm之多。经过改进后学生信息及成绩表中，学生的信息仅为3nmn。学生信息的存储量减少了3(m-1)n。显然，学生选课数绝不会是1，因而，经过分解后数据量要少得多。 更新方便。 插入问题部分解决：对一位教师所开的无人选修的课程可方便地在课程信息表中插入。但是，新分配来的教师、新成立的系或列入计划但目前不开课的课程，还是无法插入。要解决无法插入的问题，还可继续将系名与课程作分解来解决。 修改方便：原关系中对数据修改所造成的数据不一致性，在分解后得到了很好的解决，改进后，只需要修改一处。 删除问题也部分解决：当所有学生都退选一门课程时，删除退选的课程不会丢失该门课程的信息。值得注意的是，系的信息丢失问题依然存在，解决的方法还需继续进行分解。虽然改进后的模式部分地解决了不合理的关系模式所带来的问题，但同时，改进后的关系模式也会带来新的问题，如当查询某个系的学生成绩时，就需要将两个关系连接后进行查询，增加了查询时关系的连接开销，而关系的连接代价却又是很大的。此外，必须说明的是，不是任何分解都是有效的。若将表4-1分解为（Sno，Sname，Ssex，Dname，）、（Sno，Cno，Cname，Tname）及（Sname，Cno，Grade），不但解决不了实际问题，反而会带来更多的问题。那么，什么样的关系模式需要分解？分解关系模式的理论依据又是什么？分解后能完全消除上述的问题吗？回答这些问题需要理论的指导。下面几节将加以讨论。4.1.3 关系模式规范化由上面的讨论可知，在关系数据库的设计中，不是随便一种关系模式设计方案都“合适”，更不是任何一种关系模式都可以投入应用的。由于数据库中的每一个关系模式的属性之间需要满足某种内在的必然联系，设计一个好的数据库的根本方法是先要分析和掌握属性间的语义关联，然后再依据这些关联得到相应的设计方案。在理论研究和实际应用中，人们发现，属性间的关联表现为一个属性子集对另一个属性子集的“依赖”关系。按照属性间的对应情况可以将这种依赖关系分为两类，一类是“多对一”的依赖，一类是“一对多”的。“多对一”的依赖最为常见，研究结果也最为齐整，这就是本章着重讨论的“函数依赖”。“一对多”依赖相当复杂，就目前而言，人们认识到属性之间存在两种有用的“一对多”情形，一种是多值依赖关系，一种是连接依赖关系。基于对这三种依赖关系在不同层面上的具体要求，人们又将属性之间的这些关联分为若干等级，这就形成了所谓的关系的规范化（Relation Normalixation）。由此看来，解决关系数据库冗余问题的基本方案就是分析研究属性之间的联系，按照每个关系中属性间满足某种内在语义条件，以及相应运算当中表现出来某些特定要求，也就是按照属性间联系所处的规范等级来构造关系。由此产生的一整套有关理论称之为关系数据库的规范化理论。4.2 函数依赖函数依赖是数据依赖的一种，函数依赖反映了同一关系中属性间一一对应的约束。函数依赖是关系规范化的理论基础。4.2.1 关系模式的简化表示关系模式的完整表示是一个五元组：R（U，D，Dom，F）其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。由于D和Dom对设计关系模式的作用不大，在讨论关系规范化理论时可以把它们简化掉，从而关系模式可以用三元组来表示为：R（U，F）从上式可以看出，数据依赖是关系模式的重要要素。数据依赖（Data Dependency）是同一关系中属性间的相互依赖和相互制约。数据依赖包括函数依赖（Functional Dependency，简称FD）、多值依赖（Multivalued Dependency，简称MVD）和连接依赖（Join Dependency，简称JD）。4.2.2 函数依赖的基本概念1. 函数依赖定义4.1设R(U)是一个关系模式，U是R的属性集合，X和Y是U的子集。对于R(U)的任意一个可能的关系r，如果r中不存在两个元组，它们在X上的属性值相同，而在Y上的属性值不同，则称“X函数确定Y”或“Y函数依赖于X”，记作XY。函数依赖和其他数据依赖一样，是语义范畴的概念。我们只能根据数据的语义来确定函数依赖。例如，知道了学生的学号，可以惟一地查询到其对应的姓名、性别等，因而，可以说“学号函数确定了姓名或性别”，记作“学号姓名”、“性别”等。这里的惟一性并非只有一个元组，而是指任何元组，只要它在X（学号）上相同，则在Y（姓名或性别）上的值也相同。如果满足不了这个条件，就不能说它们是函数依赖了。例如，学生姓名与年龄的关系，当只有在没有同名人的情况下可以说函数依赖“姓名年龄”成立，如果允许有相同的名字，则“年龄”就不再依赖于“姓名”了。当XY成立时，则称X为决定因素（Determinant），称Y为依赖因素（Dependent）。当Y不函数依赖于X时，记为XY。如果XY，且YX，则记其为XY。特别需要注意的是，函数依赖不是指关系模式R中某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。函数依赖概念实际是是候选键概念的推广，事实上，每个关系模式R都存在候选键，每个候选键K都是一个属性子集，由候选键定义，对于R的任何一个属性子集Y，在R上都有函数依赖KY成立。一般而言，给定R的一个属性子集X，在R上另取一个属性子集Y，不一定有XY成立，但是对于R中候选键K，R的任何一个属性子集都与K有函数依赖关系，K是R中任意属性子集的决定因素。2函数依赖的三种基本情形函数依赖可以分为三种基本情形： 平凡函数依赖与非平凡函数依赖定义4.2在关系模式R(U)中，对于U的子集X和Y，如果XY，但Y不是X的子集，则称XY是非平凡函数依赖（Nontrivial Function Dependency）。若Y是X的子集，则称XY是平凡函数依赖（Trivial Function Dependency）。对于任一关系模式，平凡函数依赖都是必然成立的。它不反映新的语义，因此，若不特别声明，本书总是讨论非平凡函数依赖。 完全函数依赖与部分函数依赖定义4.3在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有X Y，则称Y完全函数依赖（Full Functional Dependency）于X，记作X F Y。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖（Partial Functional Dependency）于X，记作X P Y。如果Y对X部分函数依赖，X中的“部分”就可以确定对Y的关联，从数据依赖的观点来看，X中存在“冗余”属性。 传递函数依赖定义4.4在关系模式R(U)中，如果XY，YZ，且YX，则称Z传递函数依赖（Transitive Functional Dependency）于X，记作ZT X。传递函数依赖定义中之所以要加上条件YX，是因为如果YX，则XY，这实际上是Z直接依赖于X，而不是传递函数了。按照函数依赖的定义，可以知道，如果Z传递依赖于X，则Z必然函数依赖于X，如果Z传递依赖于X，说明Z是“间接”依赖于X，从而表明X和Z之间的关联较弱，表现出间接的弱数据依赖。因而亦是产生数据冗余的原因之一。4.2.3 码的函数依赖表示前面章节中给出了关系模式的码的非形式化定义，这里使用函数依赖的概念来严格定义关系模式的码。定义4.5 设K为关系模式R（U，F）中的属性或属性集合。若KU，则K称为R的一个超码（Super Key）。定义4.6 设K为关系模式R（U，F）中的属性或属性集合。若KF U，则K称为R的一个候选码（Candidate Key）。候选码一定是超码，而且是“最小”的超码，即K的任意一个真子集都不再是R的超码。候选码有时也称为“候选键”或“码”。若关系模式R有多个候选码，则选定其中一个作为主码（Primary Key）。组成候选码的属性称为主属性（Prime Attribute），不参加任何候选码的属性称为非主属性（Non-key Attribute）。在关系模式中，最简单的情况，单个属性是码，称为单码（Single Key）；最极端的情况，整个属性组都是码，称为全码（All Key）定义4.7 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreign Key），也称为外码。码是关系模式中的一个重要概念。候选码能够惟一地标识关系的元组，是关系模式中一组最重要的属性。另一方面，主码又和外部码一起提供了一个表示关系间联系的手段。4.2.4 函数依赖和码的惟一性码是由一个或多个属性组成的可惟一标识元组的最小属性组。码在关系中总是惟一的，即码函数决定关系中的其他属性。因此，一个关系，码值总是惟一的（如果码的值重复，则整个元组都会重复）。否则，违反实体完整性规则。与码的惟一性不同，在关系中，一个函数依赖的决定因素可能是惟一的，也可能不是惟一的。如果我们知道A决定B，且A和B在同一关系中，但我们仍无法知道A是否能决定除B以外的其他所有属性，所以无法知道A在关系中是否是惟一的。【例4.2】有关系模式：学生成绩（学生号，课程号，成绩，教师，教师办公室）此关系中包含的四种函数依赖为：（学生号，课程号）成绩课程号教师课程号教师办公室教师教师办公室其中，课程号是决定因素，但它不是惟一的。因为它能决定教师和教师办公室，但不能决定属性成绩。但决定因素（学生号，课程号）除了能决定成绩外，当然也能决定教师和教师办公室，所以它是惟一的。关系的码应取（学生号，课程号）。函数依赖性是一个与数据有关的事物规则的概念。如果属性B函数依赖于属性A，那么，若知道了A的值，则完全可以找到B的值。这并不是说可以导算出B的值，而是逻辑上只能存在一个B的值。例如，在人这个实体中，如果知道某人的惟一标识符，如身份证号，则可以得到此人的性别、身高、职业等信息，所有这些信息都依赖于确认此人的惟一的标识符。通过非主属性如年龄，无法确定此人的身高，从关系数据库的角度来看，身高不依赖于年龄。事实上，这也就意味着码是实体实例的惟一标识符。因此，在以人为实体来讨论依赖性时，如果已经知道是哪个人，则身高、体重等等就都知道了。码指示了实体中的某个具体实例。4.3 函数依赖的公理系统研究函数依赖是解决数据冗余的重要课题，其中首要的问题是在一个给定的关系模式中，找出其上的各种函数依赖。对于一个关系模式来说，在理论上总有函数依赖存在，例如平凡函数依赖和候选键确定的函数依赖；在实际应用中，人们通常也会制定一些语义明显的函数依赖。这样，一般总有一个作为问题展开的初始基础的函数依赖集F。本节主要讨论如何通过已知的F得到其他大量的未知函数依赖。4.3.1 函数依赖集的完备性1. 问题的引入我们先考察下面的例子。考察关系模式R上已知的函数依赖XA，B时，按照函数依赖概念，就有函数依赖X A和XB；而已知成立非平凡函数依赖XY和YZ，且有YX时，按照传递依赖概念，可以得到新的函数依赖XZ。若函数依赖X A、XB和XZ并不直接显现在问题当中，而是按照一定规则（函数依赖和传递函数依赖概念）由已知“推导”出来的。将这个问题一般化，就是如何由已知的函数依赖集合F，推导出新的函数依赖。为了表述简洁和推理方便，在本章的以下部分，对有关记号使用做如下约定： 如果声明X、Y等是属性子集，则将XY简记为XY。 如果声明A、B等是属性，则将集合A，B简记为AB。 如果X是属性集，A是属性，则将XA简记为XA或AX。以上是两个对象的情形，对于多个对象也做类似约定。 关系模式简讯为三元组R(U,F)，其中U为模式的属性集合，F为模式的函数依赖集合。2. 函数依赖集F的逻辑蕴涵我们先说明由函数依赖集F“推导”出函数依赖的确切含义。设有关系模式R(U,F)，又设X和Y是属性集合U的两个子集，如果对于R中每个满足F的关系r也满足XY，则称F逻辑蕴含XY，记为FXY。如果考虑到F所蕴含（所推导）的所有函数依赖，就有函数依赖集合闭包的概念。3. 函数依赖集合的闭包设F是函数依赖集合，被F逻辑蕴含的函数依赖的全体构成的集合，称为函数依赖集F的闭包（Closure），记为F，即FXYFXY由以上定义可知，由已知函数依赖集F求得新函数依赖可以归结为求F的闭包F。为了用一套系统的方法求得F，还必须遵守一组函数依赖的推理规则。4.3.2 函数依赖的推理规则为了从关系模式R上已知的函数依赖F得到其闭包F，W. W. Armstrong于1974年提出了一套推理规则。使用这套规则，可以由已有的函数依赖推导出新的函数依赖。后来又经过不断完善，形成了著名的“Armstrong公理系统”，为计算F提供了一个有效并且完备的理论基础。1. Armstrong公理系统 Armstrong公理系统有3条基本公理： A1（自反律，reflexivity）：如果YXU，则XY在R上成立。 A2（增广律，augmentation）：如果XY在R上成立，且ZU，则XZYZ。 A3（传递律，transitivity）：如果XY和YZ在R上成立，则XZ在R上也成立。基于函数依赖集F，由Armstrong公理系统推出的函数是否一定在R上成立呢？或者说，这个公理系统是否正确呢？这个问题并不明显，需要进行必要的讨论。 由于公理是不能证明的，其“正确性”只能按照某种途径进行间接的说明。人们通常是按照这样的思路考虑正确性问题的：即如果XY是基于F而由Armstrong公理系统推出，则XY一定属于F，则就可认为Armstrong公理系统是正确的。由此可知： 自反律是正确的：因为在一个关系中不可能存在两个元组在属性X上的值相等，而在X的某个子集Y上的值不等。 增广律是正确的：因为可以使用反证法，如果关系模式R(U)中的某个具体关系r中存在两个元组t和s违反了XZYZ，即tXZsXZ，而tYZsYZ，则可以知道tYsY或tZsZ。此时可以分为两种情形：如果tYsY，就与XY成立矛盾。如果tZsZ，则与假设tXZsXZ矛盾。这样假设就不成立，所以增广性公理正确。 传递律是正确的，还是使用反证法。假设R(U)的某个具体关系r中存在两个存在两个元组t和s违反了XZ，即tXsX，但tZsZ。此时分为两种情形讨论：如果tYsY，就与XY成立矛盾。如果tYsY，而tZsZ，就与YZ成立矛盾。由此可以知道传递性公理是正确的。 由Armstrong基本公理A1，A2和A3为初始点，可以导出下面4条有用的推理规则。 A4（合并性规则 union）：若XY，XZ，则XYZ。 A5（分解性规则 decomposition）：若XY，ZY，则XZ。 A6（伪传递性规则 pseudotransivity）：若XY，WYZ，则WXZ。 A7（复合性规则 compositon rule）：若XY，WZ，则WXYZ。 A8（通用一致性规则 general unification rule）：若XY，WZ，则X(WY)YZ。例：由合并性规则A4和分解性规则A5，立即可以得到如下结论：如果A1,A2,An是关系模式R的属性集，则XA1A2An的充分必要条件是XAi(I=1,2, ,n)成立。2. Armstrong公理系统的完备性如果由F出发根据Armstrong公理推导出的每一个函数依赖XY一定在F当中，人们就称Armstrong公理系统是有效的。由Armstrong公理系统正确性和有效性的一致性，不难得知Armstrong公理系统是具有有效性质的。另外，如果F中每个函数依赖都可以由F出发根据Armstrong公理系统导出，就称Armstrong公理系统是完备的。可以证明，Armstrong公理系统，即函数依赖推理规则系统（A1，A2，A3）具有完备性质。由Armstrong公理系统的完备性可以得到重要结论：F是由F根据Armstrong公理系统导出的函数依赖的集合。从而在理论上解决了由F计算F的问题。另外，由Armstrong公理系统的完备性和有效性还可以知道，“推导出”与“蕴含”是两个完全等价的概念，由此得到函数依赖集F的闭包的一个计算公式：FXYXY由F根据Armstrong公理系统导出【例4.3】设有关系模式R(U,F)，其中UABC，FAB，BC，则上述关于函数依赖集闭包计算公式，可以得到F由43个函数依赖组成。例如，由自反性公理A1可以知道，A，B，C，AA，BB，CC；由增广性公理A2可以推出ACB C，ABB ，AAB等；由传递性公理A3可以推出AC，。为了清楚起见，F的闭包F可以列举在表4-5中。表4-5F的闭包FAABACABCBCAAABAACAABCABBCCABABBACBABCBBCACABCACCABCCBBCAABABABACABABCABBCAACABACACACABCACBCBABCABBCACBCABCBCBCCAABCABABCACABCABCABCBCBC由此可见，一个小的具有两个元素函数依赖集F常常会有一个大的具有43个元素的闭包F，当然F中会有许多平凡函数依赖，例如A、ABB等，这些并非都是实际中所需要的。4.3.3 属性的闭包与F逻辑蕴含的充要条件从理论上讲，对于给定的函数依赖集合F，只要反复使用Armstrong公理系统给出的推理规则，直到不能再产生新的函数依赖为止，就可以算出F的闭包F。但在实际应用中，这种方法不仅效率较低，而且还会产生大量“无意义”或者意义不大的函数依赖。由于人们感兴趣可能只是F的某个子集。所以许多实际过程几乎没有必要计算F的闭包F自身。正是为了解决这样的问题，就引入了属性集闭包概念。1属性集闭包设F是属性集合U上的一个函数依赖集，XU，称XFAAU，XA能由F按照Armstrong公理系统导出为属性集X关于F的闭包。如果只涉及到一个函数依赖集F，即无需对函数依赖集进行区分，属性集X关于F的闭包就可简记为X。需要注意的是，上述定义中的A是U中单属性子集时，总有XXU。【例4.4】设有关系模式R(U,F)，其中UABC，FAB，BC，按照属性集闭包概念，则有：AABC，BBC，CC。2求属性集闭包算法设属性集X的闭包为closure，其计算算法如下：closure = x; do ifF中存在函数依赖UV满足Uclosure then closure = closure V; while (closure 有所改变)；3F逻辑蕴含的充要条件一般而言，给定一个关系模式R(U,F)，其中函数依赖集F的闭包F只是U上所有函数依赖集的一个子集，那么对于U上的一个函数依赖XY，如何判定它是属于F，即如何判定是否F逻辑蕴含XY呢？一个自然的思路就是将F计算出来，然后看XY是否在集合F之中，前面已经说过，由于种种原因，人们一般并不直接计算F。注意到计算一个属性集的闭包通常比计算一个函数依赖集的闭包来得简便，有必要讨论能否将“XY属于F”判断问题归结为其中决定因素X的闭包X的计算问题。下面的例题对此作出了回答。设F是属性集U上的函数依赖集，X和Y是U的子集，则XY能由F按照Armstrong公理系统推出即XY F的充分必要条件是YX。事实上，如果YA1A2An并且YX，则由X关于F闭包F的定义，对于每个AiY(i=1,2, ,n)能够关于F按照Armstrong公理推出，再由全并规则A4就可知道XY能由F按照Armstrong公理得到。充分性得证。如果XY能由F按照Armstrong公理导出，并且YA1A2An，按照分解规则A5可以得知XAi(i=1,2, ,n)，这样由X的定义就得到AiX(i=1,2, ,n)，所以YX，必要性得证。4.3.4 最小函数依赖集Fmin设有函数依赖集F，F中可能有些函数依赖是平凡的，有些是“多余的”。如果有两个函数依赖集，它们在某种意义上“等价”，而其中一个“较大”些，另一个“较小些”，人们自然会选用“较小”的一个。这个问题的确切提法是：给定一个函数依赖集F，怎样求得一个与F“等价”的“最小”的函数依赖集Fmin。显然，这是一个有意义的课题。1函数依赖集的覆盖与等价设F和G是关系模式R上的两个函数依赖集，如果所有为F所蕴含的函数依赖都为G所蕴含，即F是G的子集：FG，则称G是F的覆盖。当G是F的覆盖时，只要实现了G中的函数依赖，就自动实现了F中的函数依赖。如果G是F的函数覆盖，同时F又是G的函数覆盖，即FG，则称F和G是相互等价的函数依赖集。当F和G等价时，只要实现了其中一个的函数依赖，就自动实现了另一个的函数依赖。2最小函数依赖集对于一个函数依赖集F，称函数依赖集Fmin为F的最小函数依赖集，是指Fmin满足下述条件： Fmin与F等价：FminF。 Fmin中每个函数依赖XY的依赖因素Y为单元素集，即Y只含有一个属性。 Fmin中每个函数依赖XY的决定因素X没有冗余，即只要删除X中任何一个属性就会改变Fmin的闭包Fmin。顺便说一句，一个具有如此性质的函数依赖称为是左边不可约的。 Fmin中每个函数依赖都不是冗余的，即删除Fmin中任何一个函数依赖，Fmin就将变为了另一个不等价于Fmin的集合。最小函数依赖集Fmin实际上是函数依赖集F的一种没有“冗余”的标准或规范形式，定义中的“1”表明F和Fmin具有相同的“功能”；“2”表明Fmin中每一个函数依赖都是“标准”的，即其中依赖因素都是单属性子集；“3”表明Fmin中每一个函数依赖的决定因素都没有冗余的属性；“4”表明Fmin中没有可以从F的剩余函数依赖导出的冗余的函数依赖。3最小函数依赖集的算法任何一个函数依赖集F都存在着最小函数依赖集Fmin。事实上，对于函数依赖集F来说，由Armstrong公理系统中的分解性规则A5，如果其中的函数依赖中的依赖因素不是单属性集，就可以将其分解为单属性集，不失一般性，可以假定F中任意一个函数依赖的依赖因素Y都是单属性集合。对于任意函数依赖XY决定因素X中的每个属性A，如果将A去掉而不改变F的闭包，就将A从X中删除，否则将A保留；按照同样的方法逐一考察F中的其余函数依赖。最后，对所有如此处理过的函数依赖，再逐一讨论如果将其删除，函数依赖集是否改变，不改变就真正删除，否则保留，由此就得到函数依赖集F的最小函数依赖集Fmin。需要注意的是，虽然任何一个函数依赖集的最小依赖集都是存在的，但并不唯一。下面给出上述思路的实现算法： 由分解性规则A5得到一个与F等价的函数依赖集G，G中任意函数依赖的依赖因素都是单属性集合。 在G的每一个函数依赖中消除决定因素中的冗余属性。 在G中消除冗余的函数依赖。【例4.5】设有关系模式R(U,F)，其中UABC，FAB,C,BC, AB, A, BC，按照上述算法，可以求出Fmin。 将F中所有函数依赖的依赖因素写成单属性集形式：GAB, AC,BC, AB, A, BC这里多出一个AB，可以删掉，得到GAB, AC,BC, A, BC G中的AC可以从AB和BC推导出来，AC是冗余的，删掉AC可得：GAB, BC, A, BC G中的A, BC可以从BC推导出来，是冗余的，删掉A, BC最后得：GAB, BC。所以F的最小函数依赖集FminAB, BC。4.4 关系模式的规范化关系数据库中的关系必须满足一定的规范化要求，对于不同的规范化程度可用范式来衡量。范式是符合某一种级别的关系模式的集合，是衡量关系模式规范化程度的标准，达到的关系才是规范化的。目前主要有6种范式：第一范式、第二范式、第三范式、BC范式、第四范式和第五范式。满足最低要求的叫第一范式，简称为1NF。在第一范式基础上进一步满足一些要求的为第二范式，简称为2NF。其余以此类推。显然各种范式之间存在联系。1NF2NF3NFBCNF4NF5NF通常把某一关系模式R为第n范式简记为RnNF。范式的概念最早是由E.F.Codd 提出的。在1971到1972年期间，他先后提出了1NF、2NF、3NF的概念，1974年他又和Boyee共同提出了BCNF的概念，1976年Fagin提出了4NF的概念，后来又有人提出了5NF的概念。在这些范式中，最重要的是3NF和BCNF，它们是进行规范化的主要目标。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这个过程称为规范化。4.4.1 规范化的含义关系模式的规范化主要解决的问题是关系中数据冗余及由此产生的操作异常。而从函数依赖的观点来看，即是消除关系模式中产生数据冗余的函数依赖。定义4.8 当一个关系中的所有分量都是不可分的数据项时，就称该关系是规范化的。表4-6 具有组合数据项的非规范化关系下述例子（表4-6、表4-7）由于具有组合数据项或多值数据项，因而说，它们都不是规范化的关系。职工号姓名工资基本工资职务工资工龄工资表4-7 具有多值数据项的非规范化关系职工号姓名职称系名学历毕业年份05103周斌教授计算机大学研究生1983199205306陈长树讲师计算机大学19954.4.2 第一范式（1NF）定义4.9 如果关系模式R中每个属性值都是一个不可分解的数据项，则称该关系模式满足第一范式（First Normal Form），简称1NF，记为R1NF。第一范式规定了一个关系中的属性值必须是“原子”的，它排斥了属性值为元组、数组或某种复合数据的可能性，使得关系数据库中所有关系的属性值都是“最简形式”，这样要求的意义在于可能做到起始结构简单，为以后复杂情形讨论带来方便。一般而言，每一个关系模式都必须满足第一范式，1NF是对关系模式的起码要求。非规范化关系转化为1NF的方法很简单，当然也不是唯一的，对表4-5、表4-6分别进行横向和纵向展开，即可转化为如表4-8、表4-9所示的符合1NF的关系。表4-8 具有组合数据项的非规范化关系职工号姓名基本工资职务工资工龄工资表4-9 具有多值数据项的非规范化关系职工号姓名职称系名学历毕业年份01103周向前教授计算机大学197101103周向前教授计算机研究生197103307陈长根讲师计算机大学1993但是满足第一范式的关系模式并不一定是一个好的关系模式，例如，关系模式SLC（SNO，DEPT，SLOC，CNO，GRADE）其中SLOC为学生住处，假设每个学生住在同一地方，SLC的码为（SNO，CNO），函数依赖包括：（SNO，CNO）F GRADESNODEPT（SNO，CNO）P DEPTSNOSLOC（SNO，CNO）P SLOCDEPTSLOC（因为每个系只住一个地方）显然，SLC满足第一范式。这里（SNO，CNO）两个属性一起函数决定GRADE。（SNO，CNO）也函数决定DEPT和SLOC。但实际上仅SNO就函数决定DEPT和SLOC。因此非主属性DEPT和SLOC部分函数依赖于码（SNO，CNO）。SLC关系存在以下3个问题： 插入异常假若要插入一个SNO95102，DEPTIS，SLOCN，但还未选课的学生，即这个学生无CNO，这样的元组不能插入SLC中，因为插入时必须给定码值，而此时码值的一部分为空，因而该学生的信息无法插入。 删除异常假定某个学生只选修了一门课，如99022号学生只选修了3号课程，现在连3号课程他也选修不了，那么3号课程这个数据项就要删除。课程3是主属性，删除了课程号3，整个元组就不能存在了，也必须跟着删除，从而删除了99022号学生的其它信息，产生了删除异常，即不应删除的信息也删除了。 数据冗余度大如果一个学生选修了10门课程，那么他的DEPT和SLOC值就要重复存储10次。并且当某个学生从数学系转到信息系，这本是只是一件事，只需要修改此学生元组中的DEPT值。但因为关系模式SLC还含有系的住处SLOC属性，学生转系将同时改变住处，因而还必须修改元组中SLOC的值。另外如果这个学生选修了10门课，由于DEPT，SLOC重复存储了10次，当数据更新时必须无遗漏地修改10个元组中全部DEPT，SLOC信息，这就造成了修改的复杂化，存在破坏数据一致性的隐患。因此，SLC不是一个好的关系模式。4.4.3 第二范式定义4.10 如果一个关系模式R1NF，且它的所有非主属性都完全函数依赖于R的任一候选码，则R2NF。关系模式SLC出现上述问题的原因是DEPT，SLOC对码的部分函数依赖。为了消除这些部分函数依赖，可以采用投影分解法，把SLC分解为两个关系模式：SC（SNO，CNO，GRADE）SL（SNO，DEPT，SLOC）其中SC的码为（SNO，CNO），SL的码为SNO。显然，在分解后的关系模式中，非主属性都完全函数依赖于码了。从而使上述3个问题在一定程度上得到部分的解决。 在SL关系中可以插入尚未选课的学生。 删除学生选课情况涉及的是SC关系，如果一个学生所有的选课记录全部删除了，只是SC关系中没有关于该学生的记录了，不会牵涉到SL关系中关于该学生的记录。 由于学生选修课程的情况与学生的基本情况是分开存储在两个关系中的，因此不论该学生选多少门课程，他的DEPT和SLOC值都只存储了1次。这就大大降低了数据冗余程度。由于学生从数学系转到信息系，只需修改SL关系中该学生元组的DEPT值和SLOC值，由于DEPT，DLOC并未重复存储，因此简化了修改操作。2NF就是不允许关系模式的属性之间有这样的依赖XY，其中X是码的真子集,Y是非主属性。显然，码只包含一个属性的关系模式，如果属于1NF，那么它一定属于2NF，因为它不可能存在非主属性对码的部分函数依赖。上例中的SC关系和SL关系都属于2NF。可见，采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大等问题。但是将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。也就是说，属于2NF的关系模式并不一定是一个好的关系模式。例如，2NF关系模式SL（SNO，DEPT，SLOC）中有下列函数依赖。SNODEPTDEPTSLOCSNOSLOC由上可知，SLOC传递函数依赖于SNO，即SL中存在非主属性对码的传递函数依赖，SL关系中仍然存在插入异常、删除异常和数据冗余度大的问题。 删除异常：如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系的信息也丢掉了。 数据冗余度大：每一个系的学生都住在同一个地方，关于系的住处的信息却重复出现，重复次数与该系学生人数相同。 修改复杂：当学校调整学生住处时，比如信息系的学生全部迁到另一地方住宿，由于关于每个系的住处信息是重复存储的，修改时必须同时更新该系所有学生的SLOC属性值。 所以SL仍然存在操作异常问题。仍然不是一个好的关系模式。4.4.4 第三范式定义4.11 如果一个关系模式R2NF，且所有非主属性都不传递函数依赖于任何候选码，则R3NF。关系模式SL出现上述问题的原因是SLOC传递函数依赖于SNO。为了消除该传递函数依赖，可以采用投影分解法，把SL分解为两个关系模式：SD（SNO，DEPT）DL（DEPT，SLOC）其中SD的码为SNO，DL的码为DEPT。显然，在关系模式中既没有非主属性对码的部分函数依赖也没有非主属性对码的传递函数依赖，基本上解决了上述问题。 DL关系中可以插入无在校学生的信息。 某个系的学生全部毕业了，只是删除SD关系中的相应元组，DL关系中关于该系的信息仍然存在。 关于系的住处的信息只在DL关系中存储一次。 当学校调整某个系的学生住处时，只需修改DL关系中一个相应元组的SLOC属性值。3NF就是不允许关系模式的属性之间有这样的非平凡函数依赖XY，其中X不包含码，Y是非主属性。X不包含码有两种情况，一种情况X是码的真子集，这也是2NF不允许的，另一种情况X含有非主属性，这是3NF进一步限制的。上例中的SD关系和DL关系都属于3NF。可见，采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。但是将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。也就是说，属于3NF的关系模式虽然基本上消除大部分异常问题，但解决得并不彻底，仍然存在不足。例如：模型SC（SNO，SNAME，CNO，GRADE）如果姓名是惟一的，模型存在两个候选码：（SNO，CNO）和（SNAME，CNO）。模型SC只有一个非主属性GRADE，对两个候选码（SNO，CNO）和（SNAME，CNO）都是完全函数依赖，并且不存在对两个候选码的传递函数依赖。因此SC3NF。但是当学生如果退选了课程，元组被删除也失去学生学号与姓名的对应关系，因此仍然存在删除异常的问题；并且由于学生选课很多，姓名也将重复存储，造成数据冗余。因此3NF虽然已经是比较好的模型，但仍然存在改进的余地。4.4.5 BCNF范式定义4.12 关系模式R1NF，对任何非平凡的函数依赖XY（YX），X均包含码，则RBCNF。BCNF是从1NF直接定义而成的，可以证明，如果RBCNF，则R3NF。由BCNF的定义可以看到，每个BCNF的关系模式都具有如下3个性质。（1） 所有非主属性都完全函数依赖于每个候选码。（2） 所有主属性都完全函数依赖于每个不包含它的候选码。（3） 没有任何属性完全函数依赖于非码的任何一组属性。如果关系模式RBCNF，由定义可知，R中不存在任何属性传递函数依赖于或部分依赖于任何候选码，所以必定有R3NF。但是，如果R3NF，R未必属于BCNF。3NF和BCNF是以函数依赖为基础的关系模式规范化程度的测度。如果一个关系数据库中的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。BCNF是对3NF的改进，但是在具体实现时有时是有问题的，例如下面的模型SJT（U，F）中：USTJ，FSJT，STJ，TJ码是：ST和SJ，没有非主属性，所以STJ3NF。但是非平凡的函数依赖TJ中T不是码，因此SJT不属于BCNF。而当用分解的方法提高规范化程度时，将破坏原来模式的函数依赖关系，这对于系统设计来说是有问题的。这个问题涉及模式分解的一系列理论问题，在这里不再做进一步的探讨。在信息系统的设计中，普遍采用的是“基于3NF的系统设计”方法，就是由于3NF是无条件可以达到的，并且基本解决了“异常”的问题，因此这种方法目前在信息系统的设计中仍然被广泛地应用。如果仅考虑函数依赖这一种数据依赖，属于BCNF的关系模式已经很完美了。但如果考虑其他数据依赖，例如，多值依赖，属于BCNF的关系模式仍存在问题，不能算是一个完美的关系模式。4.5 多值依赖与4NF在关系模式中，数据之间是存在一定联系的，而对这种联系处理的适当与否直接关系到模式中数据冗余的情况。函数依赖是一种基本的数据依赖，通过对数据函数依赖的讨论和分解，可以有效地消除模式中的冗余现象。函数依赖实质上反映的是“多对一”联系，在实际应用中还会有“一对多”形式的数据联系，诸如此类的不同于函数依赖的数据联系也会产生数据冗余，从而引发各种数据异常现象。本节就讨论数据依赖中“多对一”现象及其产生的问题。4.5.1 问题的引入让我们先看下述例子：【例4.6】设有一个课程安排关系，如表4-10所示：表4-10 课程安排示意图课程名称任课教师选用教材名称高等数学T11T12T13B11B12数据结构T21T22T23B21B22B23在这里的课程安排具有如下语义：“高等数学”这门课程可以由3个教师担任，同时有两本教材可以选用。“数据结构”这门课程可以由3个教师担任，同时有3本教材可以选用。如果分别用Cn、Tn和Bn表示“课程名称”、“任课教师”和“教材名称”，上述情形可以表示如表4-11所示的关系CTB。表4-11 关系CTBCnTnBn高等数学T11B11高等数学T11B12高等数学T12B11高等数学T12B12高等数学T13B11高等数学T13B12数据结构T21B21数据结构T21B22数据结构T21B23数据结构T22B21数据结构T22B22数据结构T22B23数据结构T23B21数据结构T23B22数据结构T23B23很明显，这个关系表是数据高度冗余的。通过仔细分析关系CTB，可以发现它有如下特点： 属性集Cn与Tn之间存在着数据依赖关系，在属性集Cn与Bn之间也存在着数据依赖关系，而这两个数据依赖都不是“函数依赖”，当属性子集Cn的一个值确定之后，别一属性子集Tn就有一组值与之对应。例如当课程名称Cn的一个值“高等数学”确定之后，就有一组任课教师Tn的值“T11、T12和T13”与之对应。对于Cn与Bn的数据依赖也是如此，显然，这是一种“一对多”的情形。 属性集Tn和Bn也有关系，这种关系是通过Cn建立起来的间接关系，而且这种关系最值得注意的是，当Cn的一个值确定之后，其所对应的一组Tn值与U-Cn-Tn无关，取定Cn的一个值为“高等数学”，则对应Tn一组值“T11、T12和T13”与此“高等数学”课程选用的教材即U-Cn-Tn值无关。显然，这是“一对多”关系中的一种特殊情况。如果属性X与Y之间依赖关系具有上述特征，就不为函数依赖关系所包容，需要引入新的概念予以刻画与描述，这就是多值依赖的概念。4.5.2 多值