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

第二部分设计篇 Ch 4数据依赖与关系模式规范Ch 5数据库设计 Ch 4数据依赖与关系模式规范化 1 问题的提出2 数据依赖3 关系模式分解4 关系模式规范化 一个具体的例子 SCT S C Grade Teacher Dept SCT至少在两个方面存在着比较严重的问题 1 数据冗余 Teacher和Dept属性上存在着大量的重复取值 不仅消耗了更多的存储空间 而且还容易引起数据的不一致 2 更新异常 例如 CS 01 课程的任课教师为刘朝 因某种原因此课改由张明华担任任课教师 更新时如果不注意就可能仅将一部分选修了 CS 01 的元组更新了 从而造成了 CS 01 课程有两名任课教师的情况 这时就出现了修改时的异常 1 问题的提出 我们认为关系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一个 如何从关系数据理论的层面上来解决关系模式的分解及规范化这一类问题 将是本章后面各节的主要内容 数据依赖是指关系模式的属性间存在的一些制约关系 常见的数据依赖包括两种类型 即函数依赖 FunctionalDependency FD 和多值依赖 MultivaluedDependency MD 数据依赖是一个语义问题 是根据该关系模式及其属性所表达的具体含义而定的 数据依赖是我们评价一个关系的重要依据 根据关系模式上的数据依赖 我们可以判断这个关系是否是合理的 2 数据依赖 1 函数依赖定义4 1 设R为关系模式 r是R上的任意一个关系实例 X Y是R的两个属性子集 若对于r上的任意两个元组t1 t2 r都有如果t1 X t2 X 则必有t1 Y t2 Y 则称在R上X函数决定Y或者Y函数依赖于X 记为X Y X称为决定子 Determinant 定义4 2 设R为关系模式 X Y是R的不同属性集 如果X Y成立 且不存在X中的子集使得X Y也成立 则称Y完全函数依赖于X 记为X f Y 否则称Y部分依赖于X 记为X p Y 定义4 3 设X Y Z是R上的不同属性集合 如果有X Y Y Z成立且Y X 则称Z传递函数依赖于X Armstrong公理系统 该公理系统中与函数依赖有关的规则主要有以下三条 A1 自反率 如果Y X U 则X Y成立 A2 增广率 如果X Y成立 且Z U 则XZ YZ成立 A3 传递率 如果X Y Y Z成立 则X Z成立 引理4 1 Armstrong公理是正确的 定义4 4 设F是函数依赖集合 X Y是一个函数依赖 如果F在某个R上成立时必然有X Y也成立 则称F逻辑蕴涵X Y 记为F X Y 定义4 5 由函数依赖集合F所逻辑蕴涵的全部函数依赖所构成的集合称之为F的闭包 记作F F X Y F X Y 定义4 6 属性集X关于R U F 上的函数依赖集合F的闭包XF定义为XF A A U X A可由Armstrong公理推出 引理4 2 X Y可由Armstrong公理推出的充分必要条件是Y X F 定理4 1 Armstrong公理系统是有效而且完备的 算法4 1 计算X F输入 U X F且X U输出 X F步骤 1 令X 0 X i 0 2 计算Z A v w V W F vX i A w 3 X i 1 X i Z 4 判断X i 1 是否与X i 相等或X i 1 等于属性全集U 5 如果X i 1 X i 且X i 1 U 则i i 1 转至 2 6 如果X i 1 X i 或X i 1 U 则X i 1 即为X F 输出X i 1 计算结束 定义4 7 设F G是两个函数依赖集合 如果F G 则称F等价于G 或者F与G互相覆盖 引理4 3 F G 的充分必要条件是F G 且G F 定义4 8 若F满足下列条件 1 F中所有函数依赖的右部均为单属性 2 F中不存在这样的函数依赖X A及ZX 使得F F X A Z A 3 F中不存在这样的函数依赖X A 使F F X A 则称F为最小函数依赖集或最小覆盖 定理4 2 任一函数依赖集合必等价于某一最小函数依赖集合Fmin 2 多值依赖SchoolDeanDept每名领导均可对各系进行管理电信学院何海潮计算机系电信学院何海潮电子系电信学院何海潮通信工程系电信学院李萌计算机系电信学院李萌电子系电信学院李萌通信工程系电信学院王国栋计算机系电信学院王国栋电子系电信学院王国栋通信工程系外国语学院苏勤英语系外国语学院苏勤日语系外国语学院姚远英语系外国语学院姚远日语系这个关系的元组具有这样一个特点 即对于School属性上的每一个取值 如 电信学院 Dean School 电信学院 Man 与 Dept School 电信学院 Man 集合中任意两个元素的组合一定在关系Man中出现 定义4 9 设R为关系模式 X Y Z是R的属性子集 且Z U X Y 如果对于R的任何实例r都有 如果r中存在两个元组s t使得s X t X 则R中必然存在两个元组u v使得 u X v X s X t X u Y t Y u Z s Z v Y s Y v Z t Z 即交换元组s t在Y属性集上的取值后所得新元组仍然在r中出现 则称在R上Y多值依赖于X 记为X Y Armstrong公理系统也在仅与函数依赖有关的A1 A3基础上进行了扩充 增加了以下五条与多值依赖有关的规则 当然 A4 A8也是完备的 A4 互补率 如果X Y 则X U X Y A5 增广率 如果X Y 且V W 则WX VY A6 传递率 如果X Y Y Z 则X Z Y A7如果X Y 则X Y A8如果X Y Z Y 且对某一W当Y W 时有W Z 则X Z成立 对于不太恰当的关系模式 通常的处理办法是将其分解为若干小的子关系模式 当然这样的分解并不是随意进行的 分解时需要保证无损连接和保持函数依赖两个特性 1 无损连接分解 2 保持函数依赖分解 1 无损连接分解定义4 10 关系模式R U F 的分解是一个关系模式的集合 R1 U1 F1 Rk Uk Fk 其中U 且对于任意的1 i j k有Ui Uj Fi是F在Ui上的投影 定义4 11 函数依赖集合F在Ui上的投影定义为 Ui F X Y X Y F XY Ui 3 关系模式分解 引理4 4 设 R1 R2 Rk 是R的一个分解 r是满足R的一个关系 令ri Ui r 1 i k 则有 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的任一个关系 令ri Ui r 1 i k 如果该分解 满足条件r r1 r2 rk 则称分解 是无损连接分解 算法4 2 判别无损连接的模式分解输入 关系模式R U F U A1 An F是最小函数依赖集 R的一个分解 R1 Rm 输出 YES NO步骤 1 根据R及 构造一个m n的符号表T 符号表每行对应一个子关系模式 每列对应R上的一个属性 符号表取值规则为 T i j ajAj RibijAj Ri 2 根据F对T进行变换 逐个扫描F中的函数依赖Xi Ai 根据Xi Ai对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 定理4 3 关系模式R的一个分解 R1 U1 R2 U2 无损连接的充分必要条件是 U1 U2 U1 U2 F 或者 U1 U2 U2 U1 F 2 保持函数依赖分解定义4 13 设 R1 R2 Rk 是R U F 的一个分解 如果F 则称分解 保持函数依赖 无损连接和保持函数依赖是模式分解时的两个重要性质 如果一个分解既是无损连接的 同时又保持函数依赖 那么这样的分解将是一个非常理想的分解 既保证了关系的等价 又保证了函数依赖的等价 1 范式范式 NormalForm NF 就是满足了一定限制条件的关系模式 这个概念首先由关系数据模型的奠基人E F Codd提出 后来又有Boyce Fagin等学者对其进行了扩充 目前常用的范式包括1NF 2NF 3NF BCNF 4NF等 范式所要求的限制条件通常都会与关系模式上的数据依赖和候选键有关 因此在介绍范式的概念前 我们需要给出一个计算关系模式上所有候选键的算法 4 关系模式规范化 算法4 3 计算关系模式上的全部候选键输入 关系模式R U F 其中F是最小覆盖输出 R上的所有候选键步骤 1 首先将R的全部属性分为四类 分别是C1 不在任何函数依赖中出现的属性 C2 仅在函数依赖决定子中出现的属性 C3 仅在函数依赖右部出现的属性 C4 在函数依赖左部右部均有出现的属性 任何候选键中必然会包括C1 C2中的属性 2 若 C1 C2 U或者C4 则C1 C2即为惟一的候选键 否则 逐一将C4中的属性加入C1 C2并计算其闭包 若其闭包为U 则C1 C2与该属性构成关系上的一个候选键 重复该过程直至找出所有的候选键 定义4 14 如果R的每个属性均是原子属性 且元组在每个属性上的取值也是不可再分的 则称R满足1NF 可以表示为R 1NF 定义4 15 如果关系模式R中的所有非主属性都完全函数依赖于所有CK 则称R满足2NF 表示为R 2NF 定义4 16 如果关系模式R中的非主属性既不部分函数依赖也不传递函数依赖于R上的所有候选键 则称R满足3NF 表示为R 3NF 定义4 17 若对于R上的任何非平凡函数依赖X Y都有X必包含R的某个候选键 则称R满足BCNF 表示为R BCNF 定义4 18 如果对于R中的非平凡多值依赖X Y X必包含R的某个候选键 则称R满足4NF 表示为R 4NF 由于满足上述各种范式的要求条件是逐渐增强的 所以可以得到如下的范式间包含关系 4NFBCNF3NF2NF1NF 满足更高级别范式的关系模式一定满足低级别范式的要求 但反之不成立 给出一个各类范式间的转换方法 规范化示例 1 非规范化关系 1NF非规范化关系订货单 订单号 供应商 订货日期 发货日期 零件号 价格 数量 总计这是含有重复组的表 是非规范化关系 分解为两个符合1NF的表 订货单 订单号 供应商 订货日期 发货日期 总计订货项目 订单号 零件号 价格 数量 2 1NF 2NF去除部分函数依赖 非PK不完全依赖PK 完全依赖是指 关系R的一个属性或一组属性B函数依赖于关系R的另一组属性A的整体 但不是A的任何子集 则称B完全依赖于A 例子 配件 供应商 库存 关系1配件编号2配件名称3规格4供应商名称5供应商地址6厂价7库存量8库存占用资金A001发动机解放CA10长春一汽长春解放路43502295700A002发动机北京212北京汽车厂北京双井24501639200A002发动机北京212萍乡内燃机厂江西萍乡2400819200 配件编号和供应商名称是PK 表中配件名称 规格函数依赖于配件编号 供应商地址函数依赖于供应商名称 表需转换为符合2NF的三个关系 配件库存 配件编号 供应商名称厂价库存量库存占有资金配件 配件编号配件名称规格供应商 供应商名称供应商地址为什么要这样做 不做会出现什么问题 3 2NF 3NF再看表 配件库存 配件编号 供应商名称厂价库存量库存占有资金其中的非PK之间存在传递依赖 厂价 库存量 库存占有资金 虽然范式的级别越高 关系模式越不会出现冗余和更新异常等不合理情况 但是关系模式的数目在不断的分解过程中将会不可避免的逐渐增加 于是就引出了另外一个需要重视的问题 即关系数目的增加必然会导致连接操作的增多 而连接操作是一个开销非常大的运算 过多的关系连接必然加重数据库系统的负担 影响系统效率 所以说模式的分解切不可一味追求其规范化程度而忽略了实际的使用方便性 在应用当中我们需要结合实际情况酌情考虑 尽可能使二者达到一个比较均衡的状态 2 规范化算法算法4 4 既无损连接又保持函数依赖的3NF分解算法输入 关系模式RR UR FR 输出 R0 R1 Rk Rck 步骤 1 首先将FR转换为等价的最小覆盖 记为F 2 将不在F中出现的属性单独构成关系模式R0 U0 其余属性记为U UR U0 于是得到第一个分解 R0 R 其中R U F 3 如果R中有某一个函数依赖包含U中的全部属性 则算法终止 输出即为 4 否则 将F中的函数依赖按照决定