1、关系数据库规范化理论第4章 关系数据库规范化理论数据库设计的一个最基本的问题是怎样建立一个合理的数据库模式，使数据库系统无论是在数据存储方面，还是在数据操作方面都具有较好的性能。什么样的模型是合理的模型，什么样的模型是不合理的模型，应该通过什么标准去鉴别和采取什么方法来改进，这是在进行数据库设计之前必须明确的问题。为使数据库设计合理可靠、简单实用，长期以来，形成了关系数据库设计理论，即规范化理论。它是根据现实世界存在的数据依赖而进行的关系模式的规范化处理，从而得到一个合理的数据库设计效果。本章首先说明关系规范化的作用，接着引入函数依赖和范式等基本概念，然后介绍关系模式等价性判定和模式分解的方法
2、，最后简要介绍两种数据依赖的概念。4.1 关系规范化的作用4.1.1问题的提出从前面的有关章节可知，关系是一张二维表，它是涉及属性的笛卡尔积的一个子集。从笛卡尔积中选取哪些元组构成该关系，通常是由现实世界赋予该关系的元组语义来确定的。元组语义实质上是一个n目谓词（n是属性集中属性的个数）。使该n目谓词为真的笛卡尔积中的元素（或者说凡符合元组语义的元素）的全体就构成了该关系。但由上述关系所组成的数据库还存在某些问题。为了说明的方便，我们先看一个实例。【例4.1】设有一个关于教学管理的关系模式R(U)，其中U由属性Sno、Sname、Ssex、Dname、Cname、Tname、Grade组成的属
3、性集合，其中Sno的含义为学生学号，Sname为学生姓名，Ssex为学生性别，Dname为学生所在系别，Cname为学生所选的课程名称，Tname为任课教师姓名，Grade为学生选修该门课程的成绩。若将这些信息设计成一个关系，则关系模式为：教学（Sno，Sname，Ssex，Dname，Cname，Tname，Grade）选定此关系的主键为（Sno,Cname）。由该关系的部分数据（如表4-1所示），我们不难看出，该关系存在着如下问题：1. 数据冗余（Data Redundancy）每一个系名对该系的学生人数乘以每个学生选修的课程门数重复存储。每一个课程名均对选修该门课程的学生重复存储。每一个
4、教师都对其所教的学生重复存储。2. 更新异常（Update Anomalies）由于存在数据冗余，就可能导致数据更新异常，这主要表现在以下几个方面： 插入异常（Insert Anomalies）：由于主键中元素的属性值不能取空值，如果新分配来一位教师或新成立一个系，则这位教师及新系名就无法插入；如果一位教师所开的课程无人选修或一门课程列入计划但目前不开课，也无法插入。 修改异常（Modification Anomalies）：如果更改一门课程的任课教师，则需要修改多个元组。如果仅部分修改，部分不修改，就会造成数据的不一致性。同样的情形，如果一个学生转系，则对应此学生的所有元组都必须修改，否则，
5、也出现数据的不一致性。 删除异常（Deletion Anomalies）：如果某系的所有学生全部毕业，又没有在读及新生，当从表中删除毕业学生的选课信息时，则连同此系的信息将全部丢失。同样地，如果所有学生都退选一门课程，则该课程的相关信息也同样丢失了。由此可知，上述的教学管理关系尽管看起来能满足一定的需求，但存在的问题太多，从而它并不是一个合理的关系模式。表4-1 教学关系部分数据SnoSnameSsexDnameCnameTnameGrade0450301张三恺男计算机系高等数学李刚830450301张三恺男计算机系英语林弗然710450301张三恺男计算机系数字电路周斌920450301张三
6、恺男计算机系数据结构陈长树860450302王薇薇女计算机系高等数学李刚790450302王薇薇女计算机系英语林弗然940450302王薇薇女计算机系数字电路周斌740450302王薇薇女计算机系数据结构陈长树680420131陈杰西男园林系高等数学吴相舆970420131陈杰西男园林系英语林弗然790420131陈杰西男园林系植物分类学花裴基930420131陈杰西男园林系素描丰茹884.1.2 解决的方法不合理的关系模式最突出的问题是数据冗余。而数据冗余的产生有着较为复杂的原因。虽然关系模式充分地考虑到文件之间的相互关联而有效地处理了多个文件间的联系所产生的冗余问题。但在关系本身内部数据之
7、间的联系还没有得到充分的解决，正如例4.1所示，同一关系模式中各个属性之间存在着某种联系，如学生与系、课程与教师之间存在依赖关系的事实，才使得数据出现大量冗余，引发各种操作异常。这种依赖关系称之为数据依赖（Data Independence）。关系系统当中数据冗余产生的重要原因就在于对数据依赖的处理，从而影响到关系模式本身的结构设计。解决数据间的依赖关系常常采用对关系的分解来消除不合理的部分，以减少数据冗余。在例4.1中，我们将教学关系分解为三个关系模式来表达：学生基本信息（Sno，Sname，Ssex，Dname），课程信息（Cno，Cname，Tname，）及学生成绩（Sno，Cno，Gr
8、ade），其中Cno为学生选修的课程编号；分解后的部分数据如表4-2、表4-3与表4-4所示。表4-2 学生信息SnoSnameSsexDname0450301张三恺男计算机系0450302王薇薇女计算机系0420131陈杰西男园林系表4-3 课程信息CnoCnameTnameGS01101高等数学李刚YY01305英语林弗然SD05103数字电路周斌SJ05306数据结构陈长树GS01102高等数学吴相舆ZF02101植物分类学花裴基SM02204素描丰茹表4-4 学生成绩SnoCnoGrade0450301GS01101830450301YY01305710450301SD05103920
9、450301SJ05306860450302GS01101790450302YY01305940450302SD05103740450302SJ05306680420131GS01102970420131YY01305790420131ZF02101930420131SM0220488对教学关系进行分解后，我们再来考察一下： 数据存储量减少。设有n个学生，每个学生平均选修m门课程，则表4-1中学生信息就有4nm之多。经过改进后学生信息及成绩表中，学生的信息仅为3nmn。学生信息的存储量减少了3(m-1)n。显然，学生选课数绝不会是1，因而，经过分解后数据量要少得多。 更新方便。 插入问题部分解
10、决：对一位教师所开的无人选修的课程可方便地在课程信息表中插入。但是，新分配来的教师、新成立的系或列入计划但目前不开课的课程，还是无法插入。要解决无法插入的问题，还可继续将系名与课程作分解来解决。 修改方便：原关系中对数据修改所造成的数据不一致性，在分解后得到了很好的解决，改进后，只需要修改一处。 删除问题也部分解决：当所有学生都退选一门课程时，删除退选的课程不会丢失该门课程的信息。值得注意的是，系的信息丢失问题依然存在，解决的方法还需继续进行分解。虽然改进后的模式部分地解决了不合理的关系模式所带来的问题，但同时，改进后的关系模式也会带来新的问题，如当查询某个系的学生成绩时，就需要将两个关系连接
11、后进行查询，增加了查询时关系的连接开销，而关系的连接代价却又是很大的。此外，必须说明的是，不是任何分解都是有效的。若将表4-1分解为（Sno，Sname，Ssex，Dname，）、（Sno，Cno，Cname，Tname）及（Sname，Cno，Grade），不但解决不了实际问题，反而会带来更多的问题。那么，什么样的关系模式需要分解？分解关系模式的理论依据又是什么？分解后能完全消除上述的问题吗？回答这些问题需要理论的指导。下面几节将加以讨论。4.1.3 关系模式规范化由上面的讨论可知，在关系数据库的设计中，不是随便一种关系模式设计方案都“合适”，更不是任何一种关系模式都可以投入应用的。由于数据
12、库中的每一个关系模式的属性之间需要满足某种内在的必然联系，设计一个好的数据库的根本方法是先要分析和掌握属性间的语义关联，然后再依据这些关联得到相应的设计方案。在理论研究和实际应用中，人们发现，属性间的关联表现为一个属性子集对另一个属性子集的“依赖”关系。按照属性间的对应情况可以将这种依赖关系分为两类，一类是“多对一”的依赖，一类是“一对多”的。“多对一”的依赖最为常见，研究结果也最为齐整，这就是本章着重讨论的“函数依赖”。“一对多”依赖相当复杂，就目前而言，人们认识到属性之间存在两种有用的“一对多”情形，一种是多值依赖关系，一种是连接依赖关系。基于对这三种依赖关系在不同层面上的具体要求，人们又
13、将属性之间的这些关联分为若干等级，这就形成了所谓的关系的规范化（Relation Normalixation）。由此看来，解决关系数据库冗余问题的基本方案就是分析研究属性之间的联系，按照每个关系中属性间满足某种内在语义条件，以及相应运算当中表现出来某些特定要求，也就是按照属性间联系所处的规范等级来构造关系。由此产生的一整套有关理论称之为关系数据库的规范化理论。4.2 函数依赖函数依赖是数据依赖的一种，函数依赖反映了同一关系中属性间一一对应的约束。函数依赖是关系规范化的理论基础。4.2.1 关系模式的简化表示关系模式的完整表示是一个五元组：R（U，D，Dom，F）其中：R为关系名；U为关系的属性
14、集合；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(
15、U)是一个关系模式，U是R的属性集合，X和Y是U的子集。对于R(U)的任意一个可能的关系r，如果r中不存在两个元组，它们在X上的属性值相同，而在Y上的属性值不同，则称“X函数确定Y”或“Y函数依赖于X”，记作XY。函数依赖和其他数据依赖一样，是语义范畴的概念。我们只能根据数据的语义来确定函数依赖。例如，知道了学生的学号，可以惟一地查询到其对应的姓名、性别等，因而，可以说“学号函数确定了姓名或性别”，记作“学号姓名”、“性别”等。这里的惟一性并非只有一个元组，而是指任何元组，只要它在X（学号）上相同，则在Y（姓名或性别）上的值也相同。如果满足不了这个条件，就不能说它们是函数依赖了。例如，学生姓名
16、与年龄的关系，当只有在没有同名人的情况下可以说函数依赖“姓名年龄”成立，如果允许有相同的名字，则“年龄”就不再依赖于“姓名”了。当XY成立时，则称X为决定因素（Determinant），称Y为依赖因素（Dependent）。当Y不函数依赖于X时，记为XY。如果XY，且YX，则记其为XY。特别需要注意的是，函数依赖不是指关系模式R中某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。函数依赖概念实际是是候选键概念的推广，事实上，每个关系模式R都存在候选键，每个候选键K都是一个属性子集，由候选键定义，对于R的任何一个属性子集Y，在R上都有函数依赖KY成立。一般而言，给定R的一个属性
17、子集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）。对于任一关系模式，平凡函数依赖都是必然成立的。它不反映新的语义，因此，若不特别声明，本书总是讨论非平
18、凡函数依赖。 完全函数依赖与部分函数依赖定义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 Depe
19、ndency）于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为关系模式
20、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并非
21、R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreign Key），也称为外码。码是关系模式中的一个重要概念。候选码能够惟一地标识关系的元组，是关系模式中一组最重要的属性。另一方面，主码又和外部码一起提供了一个表示关系间联系的手段。4.2.4 函数依赖和码的惟一性码是由一个或多个属性组成的可惟一标识元组的最小属性组。码在关系中总是惟一的，即码函数决定关系中的其他属性。因此，一个关系，码值总是惟一的（如果码的值重复，则整个元组都会重复）。否则，违反实体完整性规则。与码的惟一性不同，在关系中，一个函数依赖的决定因素可能是惟一的，也可能不是惟一的。如果我们知道A决定B，且A和B在同一关系
22、中，但我们仍无法知道A是否能决定除B以外的其他所有属性，所以无法知道A在关系中是否是惟一的。【例4.2】有关系模式：学生成绩（学生号，课程号，成绩，教师，教师办公室）此关系中包含的四种函数依赖为：（学生号，课程号）成绩课程号教师课程号教师办公室教师教师办公室其中，课程号是决定因素，但它不是惟一的。因为它能决定教师和教师办公室，但不能决定属性成绩。但决定因素（学生号，课程号）除了能决定成绩外，当然也能决定教师和教师办公室，所以它是惟一的。关系的码应取（学生号，课程号）。函数依赖性是一个与数据有关的事物规则的概念。如果属性B函数依赖于属性A，那么，若知道了A的值，则完全可以找到B的值。这并不是说可
23、以导算出B的值，而是逻辑上只能存在一个B的值。例如，在人这个实体中，如果知道某人的惟一标识符，如身份证号，则可以得到此人的性别、身高、职业等信息，所有这些信息都依赖于确认此人的惟一的标识符。通过非主属性如年龄，无法确定此人的身高，从关系数据库的角度来看，身高不依赖于年龄。事实上，这也就意味着码是实体实例的惟一标识符。因此，在以人为实体来讨论依赖性时，如果已经知道是哪个人，则身高、体重等等就都知道了。码指示了实体中的某个具体实例。4.3 函数依赖的公理系统研究函数依赖是解决数据冗余的重要课题，其中首要的问题是在一个给定的关系模式中，找出其上的各种函数依赖。对于一个关系模式来说，在理论上总有函数依
24、赖存在，例如平凡函数依赖和候选键确定的函数依赖；在实际应用中，人们通常也会制定一些语义明显的函数依赖。这样，一般总有一个作为问题展开的初始基础的函数依赖集F。本节主要讨论如何通过已知的F得到其他大量的未知函数依赖。4.3.1 函数依赖集的完备性1. 问题的引入我们先考察下面的例子。考察关系模式R上已知的函数依赖XA，B时，按照函数依赖概念，就有函数依赖X A和XB；而已知成立非平凡函数依赖XY和YZ，且有YX时，按照传递依赖概念，可以得到新的函数依赖XZ。若函数依赖X A、XB和XZ并不直接显现在问题当中，而是按照一定规则（函数依赖和传递函数依赖概念）由已知“推导”出来的。将这个问题一般化，就
25、是如何由已知的函数依赖集合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逻辑
26、蕴含XY，记为FXY。如果考虑到F所蕴含（所推导）的所有函数依赖，就有函数依赖集合闭包的概念。3. 函数依赖集合的闭包设F是函数依赖集合，被F逻辑蕴含的函数依赖的全体构成的集合，称为函数依赖集F的闭包（Closure），记为F，即FXYFXY由以上定义可知，由已知函数依赖集F求得新函数依赖可以归结为求F的闭包F。为了用一套系统的方法求得F，还必须遵守一组函数依赖的推理规则。4.3.2 函数依赖的推理规则为了从关系模式R上已知的函数依赖F得到其闭包F，W. W. Armstrong于1974年提出了一套推理规则。使用这套规则，可以由已有的函数依赖推导出新的函数依赖。后来又经过不断完善，形成了著名
27、的“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上成立呢？或者说，这个公理系统是否正确呢？这个问题并不明显，需要进行必要的讨论。 由于公理是不能证明的，其“正确性”只能按照某种途径进
28、行间接的说明。人们通常是按照这样的思路考虑正确性问题的：即如果XY是基于F而由Armstrong公理系统推出，则XY一定属于F，则就可认为Armstrong公理系统是正确的。由此可知： 自反律是正确的：因为在一个关系中不可能存在两个元组在属性X上的值相等，而在X的某个子集Y上的值不等。 增广律是正确的：因为可以使用反证法，如果关系模式R(U)中的某个具体关系r中存在两个元组t和s违反了XZYZ，即tXZsXZ，而tYZsYZ，则可以知道tYsY或tZsZ。此时可以分为两种情形：如果tYsY，就与XY成立矛盾。如果tZsZ，则与假设tXZsXZ矛盾。这样假设就不成立，所以增广性公理正确。 传递律
29、是正确的，还是使用反证法。假设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
30、）：若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公
