第5章关系数据库设计理论重点

1第5章关系数据库设计理论25.1关系模式的非形式化设计规则一个关系数据库模式包括一组关系模式，各关系之间既存在一定的独立性（分别反映事物某一方面的特性），又存在必然的关联，从而构成一个关系数据库模式整体。下面将详细讨论关系模式的设计质量方面的相互关联的四个非形式化的衡量标准。35.1.1关系属性的语义规则5.1：设计一个关系模式要能够更容易解释它的语义。不要将多个实体类型和联系类型的属性组合成一个单一的关系。如果一个关系模式对应于一个实体类型或一个联系类型，那么它的语义就很清晰。否则，若一个关系对应于多个实体和联系的混合体，就会变得语义不清，也就不容易对该关系进行解释。4SnumSnameSsexDnumDirectorCnumCnameScore0903330002李波涛男D003张小龙C004自动控制原理750903330001张山男D002方维伟C002C语言程序设计530903330001张山男D002方维伟C004自动控制原理890903330001张山男D002方维伟C005数据结构65...学生关系模式S(Snum，Sname，Ssex，Dnum，Dname，Director，Cnum，Cname，Score)其属性分别表示学号、姓名、性别、所在的系编号、系主任、课程号、课程名、成绩。55.1.2元组中的冗余信息和更新异常(1)存储冗余一个学生肯定要学几十门课，那么该学生的姓名、系编号、系主任等信息就要重复存储，其存储冗余问题是相当严重的。(2)插入异常对于刚成立的系，如果还没有学生，由于Snum是主属性，不能为空值，因此该系主任等信息就无法加入到该关系中，这是极不合理的。即存在插入异常问题。6(3)删除异常若某学生因病下学期未选课程，则需删除该学生所对应所有元组，结果该学生的学号、姓名、性别等信息也同时删去了，即删去了一些不该删除的信息。这样在该关系中就找不到该学生的姓名、性别等信息了。这也是极不合理的。(4)修改异常如果更换了某个系的主任，那么该系学生所有对应的元组的系主任等信息都要修改，修改量很大，潜在着严重的数据不一致问题，有可能会出现同一个系有不同主任的情况。这种不一致性是由于数据的存储冗余产生的。7规则5.2：设计的关系模式不要出现插入异常、删除异常和修改异常。如果有任何异常出现，要明确注释，确保数据库进行插入、删除和修改时能正确操作。规则5.2和规则5.1是一致的，并且某种程度上是对规则5.1的重新陈述。所以我们需要一种更形式化的方法，来评估一个设计是否满足这些规则。85.1.3元组中的空值规则5.3：设计一个关系模式要尽可能避免在其中放置经常为空值的属性。如果空值不可避免，则应确保空值在特殊情况下出现而不是在大部分元组中出现。95.1.4伪元组的生成规则5.4：设计关系模式要使它们在主键或外键的属性上进行等值连接，并且保证不会生成伪元组。如果一定要有不满足上述条件的关系，则不要将它们在这类非主键-外键的属性上进行连接，以避免产生伪元组。105.2函数依赖11函数依赖(functionaldependency，简记为FD)是关系模式设计理论中的一个基本概念，是一种分析工具。函数依赖这一概念是键概念的推广，是合法关系集上的一种特殊约束。函数依赖在数据库设计中具有重要作用。12函数依赖是数据库中两个属性集之间的约束。定义5.1：设R(U)是属性集U上的关系模式，X、Y是U的子集，r是R的任一具体关系。设t1、t2是关系r中的任意两个元组，如果t1[X]=t2[X]，有t1[Y]=t2[Y]，则称X函数决定Y，或Y函数依赖于X，记作X→Y，属性集X称为函数依赖的左边(left-handside)，而Y则称为右边（right-handside）。如果R上的一个约束说明在R的任一具体关系r中都没有两个或两个以上的具有给定的X值的元组，即X是R的候选键，那么对于R的任一属性子集Y均有X→Y。5.2.1函数依赖的定义13函数依赖不是指关系模式R的某个或某些关系满足定义中的约束条件，而是指R的一切关系都要满足定义中的约束条件。关系模式中属性或属性组之间的函数依赖取决于属性的语义的理解，即这些属性如何相互关联。所以，函数依赖的主要作用是通过在其属性上指定总是必须保持的约束，来进一步来描述关系模式R。14定义5.2:在关系模式R(U)中，X,Y是U的子集，若X→Y，且不存在X'X，使X'→Y，则称X→Y是完全函数依赖（fullfunctionaldependency），记作XY否则称X→Y是部分函数依赖（partialfunctionaldependency），记作XY→F→P15定义5.3:在关系模式R(U)中，X,Y是U的子集，若X→Y，Y→Z，并且X不函数依赖于Y，则称Z传递函数依赖于X。这里加上条件X不函数依赖于Y很重要，如果Y→X则X↔Y，X与Y一一对应，实际上处于等价地位，Z就直接函数依赖于X，而不是传递函数依赖于X。165.2.2函数依赖的逻辑蕴涵在2.3节中，关系模式形式化地表示为:R(U,D,dom,F),其中R是关系名，是符号化的元组语义；U为组成关系的属性名的集合；D为属性组U中属性所来自的域；dom为属性和域之间的映像集合；F为关系中属性间的依赖关系集合。这个关系模式可以简化为一个三元组：R（U,F）。设计者典型地确定语义明显的函数依赖。通常只考虑给定的函数依赖集是不够的，还要考虑模式上成立的其它所有函数依赖。即从一些已知的函数依赖，去推导其它一些函数依赖也成立。17定义5.4：设F是关系模式R(U,F)的一个函数依赖集，X、Y是U的子集，若对R的每个满足F的关系r，X→Y都成立，则称F逻辑蕴涵X→Y。记作F╞X→Y。定义5.4表示函数依赖X→Y可由函数依赖集F推导出。定义5.5：被F逻辑蕴涵的函数依赖的全体构成的集合，称为函数依赖集F的闭包(closure)，记作F+。即F+={X→Y|F╞X→Y}一般FF+，若F=F+，则称F为函数依赖的完备集。在现实的例子中，实际上不可能指定函数依赖的完备集。185.2.3键定义5.6：设有关系模式R(U,F)，F是R的函数依赖集，X是U的一个子集。若(1)X→UF+；(2)不存在X的真子集Y，使得Y→U成立，且Y→UF+。则称X是R的一个候选键(candidatekey)。若候选键多于一个，则选定其中的一个为主键(primarykey)，其他的候选键则称为辅键。这里条件(1)表示键X可以决定R中的所有属性，条件(2)表示键X是具有这种性质的最小化的集合。19包含在任一候选键中的属性叫主属性(primeattribute)，不包含在任一候选键中的属性叫非主属性(nonprimeattribute)。最简单的情况是单个属性是键，这种情况是最普遍的，如学生关系S(Snum,Sname,Ssex,Dept)中的学号Snum。也可以是整个属性组是键，称为全键(All-key)，这种情况比较少见。包含候选键的属性或属性组称为超键(Superkey)，如学生选修关系SC(Snum,Cnum,Score)中的(Snum,Cnum)和(Snum,Cnum,Score)、学生关系S中的(Snum,Sname)都是超键。205.2.4函数依赖的推理规则为了从已知的函数依赖推导出其它的函数依赖，即确定函数依赖的逻辑蕴涵，需要一系列的推理规则。1974年由W.W.Armstrong总结了各种推理规则，并把其中最主要、最基本的作为公理，这就是著名的Armstrong公理。该公理说明怎样从一已知的一关系模式R所满足的一组函数依赖F中，求得其蕴含的函数依赖，即如何从已知的函数依赖F中导出其全部的函数依赖。A1自反律（reflexivity）：若YX，则X→Y。A2增广律（augmentation）：若X→Y，则XZ→YZ。A3传递律（transitivity）：若X→Y，Y→Z，则X→Z。21根据Armstrong公理的三条推理规则，可得到三个推论：(1)合并规则(union)：由X→Y，X→Z，则X→YZ。(2)分解规则(decomposition)：由X→YZ，则X→Y，X→Z。(3)伪传递规则(pseudotransitivity)：由X→Y，YW→Z，则XW→Z。22引理5.1：设Ai(i=1,2,…,n)为关系模式R的属性，X→A1A2…An成立的充分必要条件是X→Ai(i=1,2,…,n)均成立。Armstrong已经证明Armstrong公理是有效的、完备的。有效性的含义是，由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F的闭包F+中；完备性指的是，如果重复使用Armstrong公理来推导出其他函数依赖，直到不能推导出更多的函数依赖为止，则生成所有可以从F推导出的函数依赖的完备集。即F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。要证明完备性，首先要判断一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖集。如果能求出这个集合，问题就解决了。但不幸的是，这是一个NP完全问题。比如从F={X→A1,…,X→An}中至少可以推导出2n个不同的函数依赖。为此引入属性集的闭包的概念及相关的定理。23定义5.7：设由关系模式R(U,F)，U为属性全集即U=A1A2…An，X为U的子集，F是U上的一个函数依赖集，则所有基于F能推导出的由X函数决定的属性集合称为属性集X关于函数依赖集F的闭包，记作X+，即X+={Ai|X→Ai能由F根据Armstrong公理推导出}24引理5.2：设F是关系模式R(U,F)的函数依赖集，U为属性全集即U=A1A2…An，X、Y为U的子集，则X→Y能由F根据Armstrong公理导出的充分必要条件是YX+。于是，判断X→Y能否由F根据Armstrong公理导出的NP完全问题，就转化为求出X+，判定Y是否为X+的子集的问题。255.2.5函数依赖集的等价、覆盖和最小依赖集定义5.8：设F和G是关系模式R(U)上的两个函数依赖集，如果F+=G+，则称F和G等价，也可称F覆盖(Cover)G，或G覆盖F。定义5.9：如果函数依赖集F满足下列条件：(1)F中的每个函数依赖的右部只含有单个属性；(2)对于F中的任一函数依赖X→A，F－{X→A}与F不等价；(3)对于F中的任一函数依赖X→A，(F－{X→A})∪{Z→A}与F不等价，其中ZX。则称F为最小(minimal)依赖集或最小覆盖(minimalcover)。26定理5.3：任一函数依赖集F都等价于它的最小依赖集Fmin。证明：定理的证明过程实际上是构造最小依赖集的过程。根据最小依赖集的定义，构造满足定义中的三个条件的覆盖即可。(1)逐一检查函数依赖集F的各函数依赖X→A，如果A=A1A2…Ak,k=2，利用分解规则，用{X→Aj|j=1，2，…，k}来取代X→A。(2)检查F中的每一个函数依赖X→A，令G=F－{X→A}，若AXG+，即F与G等价，则从F中去掉X→A，即G，G中不存在多余的函数依赖，因此G满足定义5.6中的条件(2)，当然也满足条件(1)。(3)接下去使G中每一个函数依赖的左边没有多余的属性。检查G中的每一个函数依赖X→A，设X=B1B2…Bm，对Bi(i=1,2,…,m)逐一检查，若A（X-Bi）G+，即G与(G－{X→A})∪{(X－Bi)→A}等价，则令X'=X－Bi，用X'→A取代X→A，即Fmin=(G－{X→A})∪{X'→A}。显然Fmin满足定义5.6中三个条件，因此Fmin是可构造的。证毕。要注意的是，由于构造中选择函数依赖的次序可以不同，最小依赖集不是唯一的。275.3关系模式的规范化28E.F.Codd首先提出范式(NormalForms,记作NF)的概念及规范化的过程，他认为关系模式应满足的规范要求可分成n级，可以通过一系列的检验以证明一个关系模式是否满足某级范式。满足最低要求的叫第一范式(1NF)，在1NF中满足进一步要求的叫第2范式(2NF)，在