[工学]数据库系统原理 第11章.ppt

1,关系数据库的规范化设计是指面对一个现实问题,如何选择一个比较好的关系模式集合，即应该构造几个关系模式，每个关系由哪些属性组成。 规范化设计理论主要包括三个方面的内容：数据依赖、范式和模式设计方法。其中数据依赖起着核心的作用。数据依赖研究数据之间的联系，范式是关系模式的标准，模式设计方法是自动化设计的基础。规范化设计理论对关系数据库结构的设计起着重要的作用。,第11章 关系数据规范化理论P250,2,例11-1 设有一个关系模式R（TNAME，ADDRESS，CNO，CNAME），其属性分别表示教师姓名、教师地址、任教课程的编号和课程名。,在数据库设计中，如果一个关系模式设计得不好，就会出现像文件系统一样的数据冗余、异常、不一致等问题。,图11.1,3,该模式出现的问题有： (1) 数据冗余: 如果一个教师教几门课程，那么这个教师的地址就要重复几次存储。 (2) 操作异常: 由于数据的冗余，在对数据操作时会引起各种异常： 修改异常。例如教师t1教三门课程，在关系中就会有三个元组。如果他的地址变了，这三个元组中的地址都要改变。若有一个元组中的地址未更改，就会造成这个教师的地址不惟一，产生不一致现象。,4, 插入异常。如果一个教师刚调来，尚未分派教学任务，那么要将教师的姓名和地址存储到关系中去时，在属性CNO和CNAME上就没有值（空值）。在数据库技术中空值的语义是非常复杂的，对带空值元组的检索和操作也十分麻烦。 删除异常。如果在是上图11.1中要取消教师t3的教学任务，那么就要把这个教师的元组删去，同时也把t3的地址信息从表中删去了。这是一种不合适的现象。,5,可以说，关系模式R不是一个好的模式。一个“好”的模式应当不会发生插入异常、删除异常、更新异常，数据冗余应尽量少。 规范化原则：“关系模式有操作异常或冗余问题，就分解它。”,是否算最佳分解？ 那末，什么样的关系模式是最优的？标准是什么？如何实现？,6,如何构造合适的关系模式? 应构造几个关模式? 每个关系模式由哪些属性组成? 这就关系到数据库的逻辑设计问题,7,X函数决定Y，或Y函数依赖于X可表示为： XY 如果有一个关系模式R(A1，A2，,An),X和Y为A1，A2，,An的子集，那么对于关系R中的任意一个x值，都只有一个y值与之对应，则称X函数决定Y，或Y函数依赖于X,11.1.1函数依赖的基本概念,11.1 函数依赖 P248,8,函数依赖是属性间基本的一种依赖，它是关键码概念的推广。 定义1 设有关系模式R(U)，X和Y是属性集U的子集，若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖（Functional Dependency，简记为FD）于X，记作XY。 FD是对关系模式R的一切可能的关系r定义的。对于r的任意两个元组，如果X值相同，则要求Y值也相同，即对一个X值有唯一个Y值与之对应。该定义类似于数学中的单值函数定义。,9,例11-2： 有一个关于学生选课、教师任课的关系模式： R（SNO，SNAME，CNO，GRADE，CNAME，TNAME，TAGE） 属性分别表示学生学号、姓名、选修课程的课程号、成绩、课程名、任课教师姓名和年龄等意义。 如果规定，每个学号只能有一个学生姓名，每个课程号只能决定一门课程，那么可写成下列FD形式： SNOSNAME CNOCNAME 每个学生每学一门课程，有一个成绩，那么可写出下列FD： （SNO，CNO）GRADE 还可以写出其他一些FD： CNOCNAME，TNAME，TAGE） TNAMETAGE,注意：函数依赖不是指关系R的某个或某些关系满足的约束条件， 而是指R的一切关系均要满足的约束条件。,10,对于函数依赖的定义注意以下三点： 函数依赖是一个基于关系模式（不是一个关系模式的特定实例）的函数概念，即如果一个关系模式R中存在函数依赖XY，则要求该模式的所有具体关系都满足XY。 函数依赖不取决于属性构成关系的方式（即关系结构），而是关系所表达的信息本身的语义特性，我们只能根据这种语义信息确定函数依赖，没有其他途径。 函数依赖是数据库设计者对于关系模式的一种断言或决策，即在设计关系型数据库时不仅要设计关系结构，而且要定义数据依赖的条件，限制进入关系的所有元组都必须符合所定义的条件，否则拒绝接受输入。,11,11.1.2 一些术语和符号 P249,设有关系模式R（A1，A2，An）,X和Y为（A1，A2，An）的子集，则有以下结论： （1）如果XY，但Y不包含于X，则称XY是非平凡的函数依赖。 （2）如果Y函数不依赖于X，则记为X Y。 （3）如果XY ，则称X为决定因子。 （4）如果XY ，并且，则Y X，记X Y （5）如果XY ，并且对于X的任意一个真子集X都有 X Y，则称Y完全函数依赖于X，记为X f Y。如果 X Y成立，则称Y部分依赖于X，记为X p Y,12,(6)如果XY （非平凡的函数依赖，并且Y X）、Y Z，则称Z传递函数依赖于X。 例11-3：P249例11.1 11.2,13,11.2 关系规范化 P251,设用U表示关系模式R的属性全集，即U=A1，A2，An，用F表示关系模式R上的函数依赖集，则关系模式R可表示为R（U，F）。 1、候选码 设K为R（U，F）中的属性，若K f U，则K为R的候选码（K为决定R全部属性值的最小属性组）。,11.2 .1 关系模式中的码,14,主码:关系R(U,F)中可能有多个候选码,则选其中一个作为主码 全码:候选码为整个属性组 主属性:在R(U,F)中,包含在任一候选码中的属性 非主属性:在R(U,F)中,不包含在任一候选码中的属性 例11-4: P251例11.3和11.4,15,2、外码 用于在关系表之间建立关联的属性（组）称为外码。,16,关系模式的好与坏，用什么标准衡量？这个标准就模式的范式（Normal Forms，简记为NF）。范式的种类与数据依赖有着直接的联系，基于FD的范式有1NF、2NF、3NF、BCNF等多种。 在不提及FD时，关系中是不可能有冗余的问题，但是当存在FD时，关系中就有可能存在数据冗余问题。 1NF是关系模式的基础；2NF已成为历史，一般不再提及；在数据库设计中最常用的是3NF和BCNF。,11.2 .2 范式 P251,17,对于各种范式之间的联系有：,5NF,4NF,2NF,BCNF,3NF,1NF,范式越高、规范化的程度越高，关系模式就越好。,18,1、第一范式,定义： 如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式（first normal form，简记为1NF）的模式。 满足1NF的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。例如关系模式R（NAME， ADDRESS，PHONE），如果一个人有两个电话号码（PHONE），那么在关系中至少要出现两个元组，以便存储这两个号码。 1NF是关系模式应具备的最起码的条件。,非规范模式变为1NF： (1) 把不含单纯值的属性分解为多个原子值。 (2) 把关系模式分解。,19,2、第二范式,定义 如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键（主码），那么称R是第二范式（2NF）的模式。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。,20,例11-5： 设关系模式R（SNO，CNO，GRADE，TNAME，TADDR）的属性分别表示学生学号、选修课程的编号、成绩、任课教师姓名和教师地址等意义。（SNO，CNO）是R的候选键。 R上有两个FD：（SNO，CNO）（TNAME，TADDR）和CNO（TNAME，TADDR），因此前一个FD是局部依赖，R不是2NF模式。此时R的关系就会出现冗余和异常现象。譬如某一门课程有100个学生选修，那么在关系中就会存在100个元组，因而教师的姓名和地址就会重复100次。 如果把R分解成R1（CNO，TNAME，TADDR）和R2（SNO，CNO，GRADE）后，局部依赖（SNO，CNO）（TNAME，TADDR）就消失了。 R1和R2都是2NF模式。,21,算法： 分解成2NF模式集的算法 设关系模式R（U），主键是W，R上还存在FD XZ，并且Z是非主属性和XW，那么WZ就是一个局部依赖。此时应把R分解成两个模式R1（XZ），主键是X； R2（Y），其中Y=U-Z，主键仍是W，外键是X（REFERENCES R1）。 利用外键和主键的联接可以从R1和R2重新得到R。 如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。 如:在关系模式R（SNO，CNO，GRADE，TNAME，TADDR）中，W=SNO，CNO Z=TNAME，TADDR，X=CNO，Y=SNO，CNO，GRADE,22,3、第三范式,定义 如果XY，YA，且YX和 AY，那么称XA是传递依赖（A传递依赖于X）。 定义 如果关系模式R是2NF，且每个非主属性都不传递依赖于R的主码，那么称R是第三范式（3NF）的模式。如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式 。,23,例11-6： 在上例中，R2是2NF模式，而且也已是3NF模式。但R1（CNO，TNAME，TADDR）是2NF模式，却不一定是3NF模式。如果R1中存在函数依赖CNOTNAME和TNAMETADDR，那么CNOTADDR就是一个传递依赖，即R1不是3NF模式。此时R1的关系中也会出现冗余和异常操作。譬如一个教师开设五门课程，那么关系中就会出现五个元组，教师的地址就会重复五次。 如果把R2分解成R21（TNAME，TADDR）和R22（CNO，TNAME）后，CNOTADDR就不会出现在R21和R22中。这样R21和R22都是3NF模式。,24,算法 分解成3NF模式集的算法 设关系模式R（U），主键是W，R上还存在FD XZ。并且Z是非主属性，ZX，且X不是候选键，这样WZ就是一个传递依赖。此时应把R分解成两个模式： R1（XZ），主键是X； R2（Y），其中Y=U-Z，主键仍是W，外键是X（REFERENCES R1）。 利用外键和主键相匹配机制，R1和R2通过联接可以重新得到R。 如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。,25,违反3NF的传递依赖的三种情况,部分依赖,键是超键,传递依赖,26,4、BCNF,定义 如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。如果数据库模式中每个关系模式都是BCNF，则称为BCNF的数据库模式。 如果R是BCNF模式，那么R也是3NF模式。 设F是关系模式R的FD集，如果对F中每个非平凡的FD XY，都有X是R的超键，那么称R是BCNF的模式。,一个满足BCNF的关系模式有： 所有非主属性对每一个码都是完全函数依赖； 所有的主属性对每一个不包含它的码,也是完全函数依赖； 没有任何属性完全函数依赖于非码的任何一组属性。,27,Boyce-Codd范式（BCNF）是根据Ray Boyce（SQL的创建者之一）以及Edgar Codd（关系数据库之父）的名字来命名的。它是第二范式和第三范式的替代品，并且构建得更好，它包含了第二范式和第三范式的内在意义，但使用了一种更普通的方式进行重新表述。要注意的是，满足BCNF时，不会提到第二范式或第三范式。BCNF覆盖了这两个范式 实体满足第一范式。 所有属性完全依赖于某个键。 如果所有的判定都是一个键，则实体满足BCNF。 让我们逐个看看后两条规则。,28,例11-7： 关系模式S(SNO，SNAME，SDEPT，AGE)，假定SNAME也具有唯一性，那么S就有两个键，这两个键都由单个属性组成，彼此不相交。其他属性不存在对键的传递依赖与部分依赖，所以S是3NF。同时S中除SNO，SNAME外没有其他决定因素，所以S也是BCNF。,29,例11-8： 关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数依赖。 (S，J)T；(S，T)J；TJ。 这里(S，J)、(S，T)都是候选键。 STJ是3NF，因为没有任何非主属性对键函数传递依赖或部分函数依赖。但STJ不是BCNF模式，是因为T是决定因素，而T不包含键。 3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。一个数据库中的关系模式如果都是BCNF，那么在函数依赖范畴内，它已经实现彻底的分离，已消除了插入和删除异常。,30,对于存在数据冗余、插入异常、删除异常问题的关系模式，应采取将一个关系模式分解为多个关系模式的方法进行处理，但是这种分解过程必须是“可逆”的，即模式分解的结果应该能重新映像到分解前的关系模式。 模式分解的准则： （）模式分解必须具有无损连接性。 （）模式分解能够保持函数依赖,11. 关系模式分解的准则 P254,31,定义 设F是在关系模式R上成立的函数依赖的集合，XY是一个函数依赖。如果对于R的每个满足F的关系r也满足XY，那么称F逻辑蕴涵XY，记为F XY。 定义 设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包（closure），记为F+。即 F+= XY |记为 FXY。 说明：即使一个小的函数依赖集F，其闭包F+也是很大的，一般情况下总有 。,研究逻辑蕴涵的目的是利用推理的方法，从一组已知的函数依赖推导出另一 组函数依赖，从而找出所有函数依赖F+。,32,定义 F是关系模式R(U)的一个函数依赖集，记为R(F，U)。如果若干个关系模式的集合 =R1(U1,F1)，R2(U2,F2)，Rk(Uk,Fk) 其中： / * 关系模式R的属性全集U是分解后所有小关系模式的属性集Ui的并集 */ 对于每个i，j(1i,jk)，有Ui Uj /* 分解的小属性集间不会相互为子集 */ Fi=XY| XYF+XYUi /* Fi(i=1，2，k)是F在Ui上的投影 */ 则称是关系模式R(F，U)的一个分解。 定义实际上仅给出了模式分解必须满足的基本条件，有时也会出现将原模式存储信息丢失的现象。,33,无损分解,例11-8： 设关系模式R（ABC），分解成=AB，AC。 见下页图,34,上 图分解后的关系可以通过自然连接还原。而下图分解后的关系通过自然连接后不能还原。,称比r多出来的元组为”噪音”,35,定义 设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式= R1，Rk 。如果对R中满足F的每一个关系r，都有 r=R1（r）R2（r） Rk（r） 那么称分解相对于F是“无损联接分解”(lossless join decomposition ),简称为“无损分解”，否则称为“损失分解”（lossy decomposition）。 上例中给出了“无损分解”和“损失分解”的例子。,36,例11-9： 设关系模式R（ABC）分解成= AB，BC 。（a）和（b）分别是模式AB和BC上的值r1和r2，（c）是r1 r2的值。显然BC（r1 r2）r2。这里r2中元组（b2c2）就是一个悬挂元组，由于它的存在，使得r1和r2不存在泛关系r。,模式分解的目的就是为了消除冗余和操作异常现象，但有时会 产生存储泛关系中无法存储的信息（悬挂元组）。,37,算法 无损分解的测试 构造一张k行n列的表格，每列对应一个属性Aj（1jn），每行对应一个模式Ri（1ik）。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下： 对于F中一个FD XY，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj，那么另一个也改成aj；如果没有aj，那么用其中一个bij替换另一个值（尽量把下标ij改成较小的数）。一直到表格不能修改为止。（这个过程称为chase过程） 若修改的最后一张表格中有一行是全a，即a1a2an，那么称相对于F是无损分解，否则称损失分解。,38,（F1） 初始表格,（F1） 修改后的表格,例11-10： 设关系R(ABCD),R分解成=AB，BC，CD，如果R上成立的函数依赖集F1=BA，CD，则对F1是否为无损分解？如果F1换为F2=AB，CD呢？,本行全是a, 是无损连接,无a行, 是有损连接,（F2） 初始表格,（F2） 修改后的表格,39,对于分解为两个模式的情况，可根据下列定理分解： 定理 设= R1，R2 是关系模式R的一个分解，F是R上成立的 FD集，那么分解相对于F是无损分解的充分必要条件是： （R1R2）（R1R2）或（R1R2）（R2R1）。 说明：该定理中的两个函数依赖不一定属于F，只要属于F+即可。 例11-11：设有关系模式R（SNO，Sname,CNO,Grade, SNOSname,(SNO,CNO)Grade） 的一个分解为： =R1（SNO，Sname,SNOSname), R2(SNO,CNO,Grade ,(SNO,CNO)Grade) 因为R1R2=SNO,R1-R2=Sname,所以R1 R2R1-R2,即SNOSname,它属于F，由定理可知，分解具有无损性连接。,如果两个关系模式间的公共属性集至少包含其中一个关系模式的主健， 则此分解是无损分解。,40,保持函数依赖分解,保持函数依赖分解的意义：在作任何数据输入和修改时，只要每个关系模式本身的函数依赖约束可满足，就可以确保整个数据库中数据的语义完整性不受破坏。,41,定义 设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用Z（F）表示，定义为Z（F）= XY | XYF+，且XYZ 定义 设= R1，RK 是R的一个分解，F是R上的FD集， 如果有 Ri（F）=F，那么称分解保持函数依赖集F。 定理 保持函数依赖分解的充要条件是,42,例11-12: 设关系模式R（WNO，WS，WG）的属性分别表示职工的工号、工资级别和工资数目。如果规定每个职工只有一个工资级别，并且一个工资级别只有一个工资数目，那么R上的FD有WNOWS和WSWG。,R1上FD是F1=WNOWS，R2上的FD是F2=WNOWG。但从这两个FD推导不出在R上成立的FD WSWG，因此分解把WSWG丢失了，即不保持F。,如果R分解成=R1，R2，其中R1=WNO，WS，R2=WNO，WG，可以验证这个分解是无损分解。,43,一个无损连接不一定具有函数依赖保持性，反之一个具有函数依赖保持性的分解也不一定是无损连接。 例11-13: 设R（ABCD），F=AB，CD，=R1（A，B，AB），R2（C，D，CD）。 因为 F=AB，CD F1F2=AB，CD 所以 F+=(F1F2)+ 即分解具有依赖保持性，易验证不具有无损性。,44,例11-14: 设R(ABC)，F=AB，CB，=R1(A，B，F1)，R2(A，C，F2)，其中F1=AB，F2=AC。 因为 R1R2=A，R1-R2=B，R2-R1=C 所以 R1R2R1-R2 因为 ABF，但F+(F1F2)+ 可见具有无损分解，但不具有保持函数依赖分解。,45,数据库设计者在进行关系数据库设计时，一般尽可能设计成BCNF模式集。如果设计成BCNF模式集时达不到保持函数依赖和无损分解的特点，那么只能降低要求，设计成3NF模式集，以求达到保持函数依赖和无损分解的特点。,46,一个好的数据库模式设计方法应符合三条原则： 表达性涉及到数据库模式的等价问题，即数据等价和语义等价，分别用无损分解和保持函数依赖分解来衡量。 分离性是指在关系中只存储有直接联系的属性值，而不要把有间接联系的属性值放在一张表中。应该把有间接联系的属性值放在不同的表中。实际上“分离”就是清除冗余和异常现象。如能达到这个目的，就分离。分离的基准是一系列范式。在分解成BCNF模式集时，分离与依赖等价有时是不兼容的。 最小冗余性要求分解后的模式个数和模式中属性总数应最少。目的是节省存储空间，提高操作效率，消除不必要的冗余。但要注意，实际使用时并不一定要达到最小冗余，因为有时带点冗余对提高查询速度是有好处的。,47,本章小结,本章讨论如何设计关系模式问题。关系模式设计得好与坏，直接影响到数据冗余度、数据一致性等问题。要设计好的数据库模式，必须有一定的理论为基础。这就是模式规范化理论。,在数据库中，数据冗余是指同一个数据存储了多次，由数据冗余将会引起各种操作异常。通过把模式分解成若干比较小的关系模式可以消除冗余。,函数依赖XY是数据之间最基本的一种联系，在关系中有两个元组，如果X值相等那么要求Y值也相等。FD有