ch.4数据依赖与关系模式规范化.ppt

2019年8月5日星期一1时46分28秒,数据库教程（沈-06.8）,1,第二部分 设计篇,Ch.4 数据依赖与关系模式规范化 Ch.5 数据库设计,2019年8月5日星期一1时46分28秒,数据库教程（沈-06.8）,2,Ch.4 数据依赖与关系模式规范化,1.问题的提出 2.数据依赖 3.关系模式分解 4.关系模式规范化,2019年8月5日星期一1时46分28秒,数据库教程（沈-06.8）,3,1。问题的提出,一个具体的例子 :SCT(S#，C#，Grade，Teacher，Dept) SCT至少在两个方面存在着比较严重的问题： (1)数据冗余:Teacher和Dept属性上存在着大量的重复取值，不仅消耗了更多的存储空间，而且还容易引起数据的不一致。 (2)更新异常:例如“CS01”课程的任课教师为刘朝，因某种原因此课改由张明华担任任课教师，更新时如果不注意就可能仅将一部分选修了“CS01”的元组更新了，从而造成了“CS01”课程有两名任课教师的情况，这时就出现了修改时的异常。,2019年8月5日星期一1时46分28秒,数据库教程（沈-06.8）,4,关系SCT不是一个“好”的关系，原因在于将S#、C#、Grade、Teacher、Dept等属性放在一个关系模式中是不合适的，怎么样对这个关系加以改进呢？ 将其分为两个关系SC(S#，C#，Grade)和CT(C#，Teacher，Dept)，这样一来关系中就不会存在数据的冗余了。然而观察关系CT(C#，Teacher，Dept)可以发现，该关系上的更新异常是仍然存在的。将关系CT (C#，Teacher，Dept)继续分解，将其拆分成C(C#，Teacher)和T(Teacher，Dept)。经过这两次调整之后，关系SCT(S#，C#，Grade，Teacher，Dept)被分解成了三个关系SC(S#，C#，Grade)、C(C#，Teacher)和T(Teacher，Dept)，此时的这三个关系都已经比较合理，分解也就到此为止了。 我们很好的解决了关系SCT存在的问题，但是实际当中可能存在数据冗余和更新异常等问题的关系并不仅仅只有SCT一个，如何从关系数据理论的层面上来解决关系模式的分解及规范化这一类问题，将是本章后面各节的主要内容。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,5,2。 数据依赖,数据依赖是指关系模式的属性间存在的一些制约关系，常见的数据依赖包括两种类型，即函数依赖(Functional Dependency，FD)和多值依赖(Multivalued Dependency，MD)。 数据依赖是一个语义问题，是根据该关系模式及其属性所表达的具体含义而定的。 数据依赖是我们评价一个关系的重要依据，根据关系模式上的数据依赖，我们可以判断这个关系是否是合理的 。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,6,2。 数据依赖,（1）函数依赖 （2）多值依赖 （1）函数依赖 定义4-1：设R为关系模式，r是R上的任意一个关系实例，X，YU是R的两 个属性子集，若对于r上的任意两个元组t1，t2r都有如果t1Xt2X，则必有t1Y=t2Y，则称在R上X函数决定Y或者Y函数依赖于X，记为XY，X称为决定子(Determinant)。 定义4-2：设R为关系模式，X、Y是R的不同属性集，如果XY成立，且不存在 X中的子集使得XY也成立，则称Y完全函数依赖于X，记为X(f) Y，否则称Y部分依赖于X，记为X(p) Y。 定义4-3：设X、Y、Z是R上的不同属性集合，如果有XY，YZ成立且 Y X，则称Z传递函数依赖于X。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,7,Armstrong公理系统，该公理系统中与函数依赖有关的规则主要有以下三条:A1（自反率）：如果YX U，则XY成立； A2（增广率）：如果XY成立，且Z U，则XZYZ成 立； A3（传递率）：如果XY，YZ成立，则XZ成立。 引理4-1：Armstrong公理是正确的。 定义4-4：设F是函数依赖集合，XY是一个函数依赖，如果F在某个R上成立 时必然有XY也成立，则称F逻辑蕴涵XY，记为FXY。 定义4-5：由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包，记作F，F XY | F XY。 定义4-6：属性集X关于R(U，F)上的函数依赖集合F的闭包XF定义为XFA|AU，XA可由Armstrong公理推出。 引理4-2：XY可由Armstrong公理推出的充分必要条件是Y XF。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,8,定理4-1：Armstrong公理系统是有效而且完备的。 算法4-1：计算X F 输入：U，X，F且X U 输出：X F 步骤：(1)令X(0)X，i:0； (2)计算ZA | (v) (w) (VWFvX(i)Aw)； (3) X(i1):X(i)Z； (4)判断X(i1)是否与X(i)相等或X(i1)等于属性全集U； (5)如果X(i1)X(i)且X(i1)U，则i:i1，转至(2)； (6)如果X(i1)X(i)或X(i1)U，则X(i1)即为X F ，输出X(i1)，计算结束。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,9,定义4-7：设F，G是两个函数依赖集合，如果FG，则称F等价于G，或者F与G互相覆盖。 引理4-3：FG的充分必要条件是F G且G F。 定义4-8：若F满足下列条件， (1)F中所有函数依赖的右部均为单属性； (2)F中不存在这样的函数依赖XA及ZX，使得F(F XAZA)； (3)F中不存在这样的函数依赖XA：使F(FXA)， 则称F为最小函数依赖集或最小覆盖。 定理4-2：任一函数依赖集合必等价于某一最小函数依赖集合Fmin。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,10,（2）多值依赖 School Dean Dept 每名领导均可对各系进行管理 电信学院 何海潮 计算机系 电信学院 何海潮 电子系 电信学院 何海潮 通信工程系 电信学院 李萌 计算机系 电信学院 李萌 电子系 电信学院 李萌 通信工程系 电信学院 王国栋 计算机系 电信学院 王国栋 电子系 电信学院 王国栋 通信工程系 外国语学院 苏勤 英语系 外国语学院 苏勤 日语系 外国语学院 姚远 英语系 外国语学院 姚远 日语系 这个关系的元组具有这样一个特点，就是对于School属性上的每一个取值，如“电信学院”，Dean(School电信学院(Man)与Dept(School电信学院(Man)集合中任意两个元素的组合一定在关系Man中出现,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,11,定义4-9：设R为关系模式，X、Y、Z是R的属性子集，且ZUXY，如果对于R的任何实例r都有：如果r中存在两个元组s，t使得sXtX，则R中必然存在两个元组u，v使得： uXvXsXtX uYtY，uZsZ vYsY，vZtZ 即交换元组s、t在Y属性集上的取值后所得新元组仍然在r中出现，则称在R上Y多值依赖于X，记为XY。 Armstrong公理系统也在仅与函数依赖有关的A1A3基础上进行了扩充，增加了以下五条与多值依赖有关的规则，当然，A1A8也是完备的。 A4（互补率）：如果XY，则X(UXY)； A5（增广率）：如果XY，且V W，则WXVY； A6（传递率）：如果XY，YZ，则X(ZY)； A7 如果XY，则XY； A8 如果XY，Z Y，且对某一W当YW时有WZ，则XZ成立；,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,12,3.关系模式分解,对于不太恰当的关系模式，通常的处理办法是将其分解为若干小的子关系模式，当然这样的分解并不是随意进行的，分解时需要保证无损连接和保持函数依赖两个特性. (1)无损连接分解 (2)保持函数依赖分解 (1)无损连接分解 定义4-10：关系模式R(U，F)的分解是一个关系模式的集合R1(U1，F1)，Rk(Uk，Fk)，其中U，且对于任意的1i，jk有UiUj，Fi是F在Ui上的投影。 定义4-11：函数依赖集合F在Ui上的投影定义为Ui(F) XY | XYFXY Ui。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,13,引理4-4：设R1，R2，Rk是R的一个分解，r是满足R的一个关系，令riUi (r)，1ik，则有 (1) r m (r)； (2) 设s= m (r)，则Ui (s)ri； (3) m m (r)= m (r) 其中m 是投影连接算子，m (r) ri。 定义4-12：设 R1，R2，Rk是R的一个分解，r是满足R的任一个关系，令riUi (r)，1ik，如果该分解满足条件rr1 r2 rk，则称分解是无损连接分解。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,14,算法4-2：判别无损连接的模式分解 输入：关系模式R(U，F)，UA1，An，F是最小函数依赖集，R的一个分解 R1，Rm； 输出：YES/NO 步骤： (1)根据R及构造一个mn的符号表T，符号表每行对应一个子关系模式，每列对应R上的一个属性，符号表取值规则为： Ti，jaj AjRi bij Aj Ri (2)根据F对T进行变换，逐个扫描F中的函数依赖XiAi，根据XiAi对T进行变换，如果T中存在不满足该函数依赖的行（即在Xi列上的取值相同，而在Ai列上的取值不同），则修改这些行在Ai属性列上的取值，具体修改方法为：如果这些行中存在某行在Ai列上的取值为a，则将其它行在Ai列上的取值也改为相同的a，否则改为i、j最小的bij； (3)扫描一遍后检验T是否发生变化，如果T中已有全a行或T较之于上一遍扫描结果未发生变化，则扫描终止，如T有变化且未出现全a行，则返回(2)； (4)算法终止时，若T中有全a行，则输出YES，否则输出NO。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,15,定理4-3：关系模式R的一个分解 R1(U1)，R2(U2)无损连接的充分必要条件是(U1U2)(U1U2)F或者(U1U2)(U2U1)F。 (2)保持函数依赖分解 定义4-13：设 R1，R2，Rk是R(U，F)的一个分解，如果F( ) +，则称分解保持函数依赖。 无损连接和保持函数依赖是模式分解时的两个重要性质，如果一个分解既是无损连接的，同时又保持函数依赖，那么这样的分解将是一个非常理想的分解，既保证了关系的等价，又保证了函数依赖的等价。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,16,4 .关系模式规范化,(1)范式 (2)规范化算法 (1)范式 范式(Normal Form，NF)就是满足了一定限制条件的关系模式，这个概念首先由关系数据模型的奠基人E.F.Codd提出，后来又有Boyce，Fagin等学者对其进行了扩充，目前常用的范式包括1NF，2NF，3NF，BCNF，4NF等 . 范式所要求的限制条件通常都会与关系模式上的数据依赖和候选键有关，因此在介绍范式的概念前，我们需要给出一个计算关系模式上所有候选键的算法。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,17,算法4-3：计算关系模式上的全部候选键 输入：关系模式R(U，F)，其中F是最小覆盖 输出：R上的所有候选键 步骤： (1)首先将R的全部属性分为四类，分别是C1：不在任何函数依赖中出现的属性；C2：仅在函数依赖决定子中出现的属性；C3：仅在函数依赖右部出现的属性；C4：在函数依赖左部右部均有出现的属性。任何候选键中必然会包括C1、C2中的属性。 (2)若(C1C2)U或者C4，则C1C2即为惟一的候选键；否则，逐一将C4中的属性加入C1C2并计算其闭包，若其闭包为U，则C1C2与该属性构成关系上的一个候选键，重复该过程直至找出所有的候选键。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,18,定义4-14：如果R的每个属性均是原子属性，且元组在每个属性上的取值也是不可再分的，则称R满足1NF，可以表示为R1NF。 定义4-15：如果关系模式R中的所有非主属性都完全函数依赖于所有CK，则称R满足2NF，表示为R2NF。 定义4-16：如果关系模式R中的非主属性既不部分函数依赖也不传递函数依赖于R上的所有候选键，则称R满足3NF，表示为R3NF。 定义4-17：若对于R上的任何非平凡函数依赖XY都有X必包含R的某个候选键，则称R满足BCNF，表示为RBCNF。 定义4-18：如果对于R中的非平凡多值依赖XY，X必包含R的某个候选键，则称R满足4NF，表示为R4NF。 由于满足上述各种范式的要求条件是逐渐增强的，所以可以得到如下的范式间包含关系：4NFBCNF3NF2NF1NF，满足更高级别范式的关系模式一定满足低级别范式的要求，但反之不成立。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,19,给出一个各类范式间的转换方法 :,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,20,规范化示例： 1）非规范化关系1NF 非规范化关系 订货单：订单号，供应商，订货日期，发货日期，（零件号、价格、数量），总计 这是含有重复组的表，是非规范化关系。 分解为两个符合1NF的表： 订货单：订单号，供应商，订货日期，发货日期， 总计 订货项目：订单号，零件号，价格，数量,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,21,2）1NF2NF 去除部分函数依赖（非PK不完全依赖PK，完全依赖是指：关系R的一个属性或一组属性B函数依赖于关系R的另一组属性A的整体，但不是A的任何子集，则称B完全依赖于A） 例子：“配件-供应商-库存”关系 1配件编号 2配件名称 3规格 4供应商名称 5供应商地址 6厂价 7库存量 8库存占用资金 A001 发动机 解放CA10 长春一汽 长春解放路 4350 22 95700 A002 发动机 北京212 北京汽车厂 北京双井 2450 16 39200 A002 发动机 北京212 萍乡内燃机厂 江西萍乡 2400 8 19200 - 配件编号和供应商名称是PK，表中配件名称、规格函数依赖于配件编号 ，供应商地址函数依赖于供应商名称 。,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,22,表需转换为符合2NF的三个关系： 配件库存：*配件编号 *供应商名称 厂价 库存量 库存占有资金 配 件： *配件编号 配件名称 规格 供 应 商： *供应商名称 供应商地址 为什么要这样做？不做会出现什么问题 ？,2019年8月5日星期一1时46分29秒,数据库教程（沈-06.8）,23,3）2NF3NF 再看表：配件库存：*配件编号 *供应商名称 厂价 库 存量 库存占有资金 其中的非PK之间存在传递依赖（厂价 库存量 库 存占有资金） 虽然范式的级别越高，关系模式越不会出现冗余和更新异常等不合理情况，但是关系模式的数目在不断的分解过程中将会不可避免的逐渐增加，于是就引出了另外一个需要重视的问题，即关系数目的增加必然会导致连接操作的增多，而连接