第5章关系模式的规范化设计.ppt

第5章关系模式的规范化设计 主要内容 问题提出函数依赖关系模式的分解关系模式的范式 本章重要概念 1 关系模式的冗余和异常问题 2 fd的定义 逻辑蕴涵 闭包 推理规则 与关键码的联系 平凡的fd 属性集的闭包 推理规则的正确性和完备性 fd集的等价 最小依赖集 3 无损分解的定义 性质 测试 保持依赖集的分解 4 关系模式的范式 1nf 2nf 3nf bcnf 分解成2nf 3nf模式集的算法 前言 关系数据库的规范化设计是指面对一个现实问题 如何选择一个比较好的关系模式集合 即应该构造几个关系模式 每个关系由哪些属性组成 规范化设计理论主要包括三个方面的内容 数据依赖 核心的作用 范式模式设计方法数据依赖研究数据之间的联系 范式是关系模式的标准 模式设计方法是自动化设计的基础 规范化设计理论对关系数据库结构的设计起着重要的作用 例4 1设有一个关系模式r tname address cno cname 其属性分别表示教师姓名 教师地址 任教课程的编号和课程名 关系模式r的实例 在数据库设计中 如果一个关系模式设计得不好 就会出现像文件系统一样的数据冗余 异常 不一致等问题 关系模式的冗余和异常问题 1 关系模式的冗余和异常问题 2 该模式出现的问题有 1 数据冗余 如果一个教师教几门课程 那么这个教师的地址就要重复几次存储 2 操作异常 由于数据的冗余 在对数据操作时会引起各种异常 修改异常 例如教师t1教三门课程 在关系中就会有三个元组 如果他的地址变了 这三个元组中的地址都要改变 若有一个元组中的地址未更改 就会造成这个教师的地址不惟一 产生不一致现象 插入异常 如果一个教师刚调来 尚未分派教学任务 那么要将教师的姓名和地址存储到关系中去时 在属性cno和cname上就没有值 空值 在数据库技术中空值的语义是非常复杂的 对带空值元组的检索和操作也十分麻烦 删除异常 如果在图4 1中要取消教师t3的教学任务 那么就要把这个教师的元组删去 同时也把t3的地址信息从表中删去了 这是一种不合适的现象 关系模式的冗余和异常问题 3 可以说 关系模式r不是一个好的模式 一个 好 的模式应当不会发生插入异常 删除异常 更新异常 数据冗余应尽量少 规范化原则 关系模式有操作异常或冗余问题 就分解它 本章的符号约定 一般地 我们设计关系数据库模式时 要注意三方面的问题 必须从语义上摸清这些数据联系 实体联系和属性联系 尽可能的将互相依赖密切的属性构成单独模式 切忌把依赖关系不密切 特别是具有 排它 性的属性硬凑到一起 英文字母表首部的大写字母 a b c d 表示单个属性 英文字母表尾部的大写字母 u v w x y z 表示属性集 大写字母r表示关系模式 小写字母r表示其关系 属性集 a1 a2 an 简记为a1a2 an 属性集x和y的并集x y简记为xy x a 简写为xa或ax 5 2函数依赖 主要内容 函数依赖的定义fd的逻辑蕴含fd的推理规则fd和关键码的联系属性集的闭包fd集的最小依赖集 函数依赖的定义 1 函数依赖是属性间基本的一种依赖 它是关键码概念的推广 定义5 1设有关系模式r u x和y是属性集u的子集 若对于r u 的任意一个可能的关系r r中不可能存在两个元组在x上的属性值相等 而在y上的属性值不等 则称x函数确定y或y函数依赖 functionaldependency 简记为fd 于x 记作x y 函数依赖的定义 fd是对关系模式r的一切可能的关系r定义的 对于r的任意两个元组 如果x值相同 则要求y值也相同 即对一个x值有唯一个y值与之对应 该定义类似于数学中的单值函数定义 在图中 左边图有 a b右边图没有 a b 函数依赖只能根据语义来确定 如姓名 年龄只有在该部门没有同名人的条件下是函数依赖 函数依赖的定义 2 注意 函数依赖不是指关系r的某个或某些关系满足的约束条件 而是指r的一切关系均要满足的约束条件 例5 2有一个关于学生选课 教师任课的关系模式 r sno sname cno grade cname tname tage 属性分别表示学生学号 姓名 选修课程的课程号 成绩 课程名 任课教师姓名和年龄等意义 如果规定 每个学号只能有一个学生姓名 每个课程号只能决定一门课程 那么可写成下列fd形式 sno snamecno cname每个学生每学一门课程 有一个成绩 那么可写出下列fd sno cno grade还可以写出其他一些fd cno cname tname tage tname tage 函数依赖的定义 3 对于函数依赖的定义注意以下三点 函数依赖是一个基于关系模式 不是一个关系模式的特定实例 的函数概念 即如果一个关系模式r中存在函数依赖x y 则要求该模式的所有具体关系都满足x y 函数依赖不取决于属性构成关系的方式 即关系结构 而是关系所表达的信息本身的语义特性 我们只能根据这种语义信息确定函数依赖 没有其他途径 函数依赖是数据库设计者对于关系模式的一种断言或决策 即在设计关系型数据库时不仅要设计关系结构 而且要定义数据依赖的条件 限制进入关系的所有元组都必须符合所定义的条件 否则拒绝接受输入 fd的逻辑蕴涵 定义5 2设f是在关系模式r上成立的函数依赖的集合 x y是一个函数依赖 如果对于r的每个满足f的关系r也满足x y 那么称f逻辑蕴涵x y 记为f x y 定义5 3设f是函数依赖集 被f逻辑蕴涵的函数依赖全体构成的集合 称为函数依赖集f的闭包 closure 记为f 即f x y 记为f x y 说明 即使一个小的函数依赖集f 其闭包f 也是很大的 一般情况下总有 研究逻辑蕴涵的目的是利用推理的方法 从一组已知的函数依赖推导出另一组函数依赖 从而找出所有函数依赖f 从已知的一些fd 可以推导出另外一些fd 这就需要一系列的推理规则 设u是关系模式r的属性集 f是r上成立的只涉及到u中属性的函数依赖集 fd的推理规则有以下三条 a1 自反性 reflexivity 若y x u 则x y在r上成立 a2 增广性 augmentation 若x y在r上成立 且z u 则xz yz在r上成立 a3 传递性 transitivity 若x y和y z在r上成立 则x z在r上成立 fd的推理规则 1 目的 是由f再通过这些fd推理规则找到f fd的推理规则 结论fd推理规则a1 a2和a3是正确的 也就是 如果x y是从f用推理规则导出 那么x y在f 中 fd的其他五条推理规则 1 a4 合并性 union x y x z x yz 2 a5 分解性 decomposition x y z y x z 3 a6 伪传递性 x y wy z wx z 4 a7 复合性 composition x y w z xw yz 5 a8 通用一致性 x y w z x w y yz 例5 3设有关系模式r a b c d e f是它的属性集的子集 r满足下列函数依赖 f a bc cd ef 证明 函数依赖ad f成立 证明 a bc 已知 a c 分解性 ad cd 增广性 cd ef 已知 ad ef 传递性 ad f 分解性 fd的推理规则 2 fd和关键码的联系 定义5 4设关系模式r的属性集是u x是u的一个子集 如果x u在r上成立 那么称x是r的一个超键 如果x u在r上成立 但对于x的任一真子集w 都有w u不成立 那么称x是r上的一个候选键 候选键举例 例5 4在学生选课 教师任课的关系模式中 r sno sname cno cname grade tname tage 如果规定 每个学生每学一门课只有一个成绩 每个学生只有一个姓名 每个课程号只有一个课程名 每门课程只有一个任课教师 根据这些规则 可以知道 sno cno 能函数决定r的全部属性 并且是一个候选键 虽然 sno sname cno tname 也能函数决定r的全部属性 但相比之下 只能说是一个超键 而不能说是候选键 因为其中含有多余属性 定义5 5设有关系模式r u u a1 a2 an x是u的子集 f是u上的一个函数依赖集 则称所有用armstrong公理从f推出的函数依赖x ai i 1 2 n 中ai的集合为x的属性集闭包 记为 即 ai ai u 且x ai可用armstrong公理从f推出 属性集的闭包 属性集的闭包举例 例5 5设关系模式r abc 的函数依赖集为f a b b c 分别求a b c的闭包 解 若x aa b b c 已知 a c 传递性 a a 自反性 a b c 据定义 若x bb b 自反性 b c 已知 b c 据定义 若x c c c 自反性 c 据定义 fd集的最小依赖集 1 如果关系模式r u 上的两个函数依赖集f和g 有f g 则称f和g是等价的函数依赖集 函数依赖集f中的fd很多 应该从f中去掉平凡的fd 无关的fd 以求得f的最小依赖集fmin 形式定义如下 定义5 6设f是属性集u上的fd集 如果满足 f中每一个函数依赖的右部都是单个属性 对f中任一个函数依赖x a f x a 都不与f等价 对于f中的任一个函数依赖x a和x的任一子集z f x a z a 都不与f等价 则称f是一个最小函数依赖集 记为fmin 上述三个条件的作用分别是 条件 保证了每个函数依赖的右部都不会有多个属性 条件 保证了f中没有多余的函数依赖 条件 保证了函数依赖的左部没有重复属性 fd集的最小依赖集 2 算法4 2计算函数依赖集f的最小依赖集g的步骤 第一步 根据分解性推理规则 得到一个与f等价的fd集g g中每个fd的右边均为单属性 第二步 在g的每个fd中消去左边冗余的属性 第三步 在g中消除冗余的fd fd集的最小依赖集 3 例5 6设f是关系模式r abc 的fd集 f a bc b c a b ab c 试求fmin 解 先把f中的fd写成右边是单属性形式 f a b a c b c a b ab c 显然多多了一个a b 可删去 得f a b a c b c ab c 在f中 由a b和b c可以推出a c 所以a c是冗余的 可删去 得f a b b c ab c f中ab c可从b c推出 因此ab c也可删去 最后得f a b b c 即为所求的fmin 5 3关系模式的分解 主要内容 模式分解问题无损分解保持函数依赖分解 对于存在数据冗余 插入异常 删除异常问题的关系模式 应采取将一个关系模式分解为多个关系模式的方法进行处理 但是这种分解过程必须是 可逆 的 即模式分解的结果应该能重新映像到分解前的关系模式 模式分解问题 模式分解定义 定义5 7f是关系模式r u 的一个函数依赖集 记为r f u 如果若干个关系模式的集合 r1 u1 f1 r2 u2 f2 rk uk fk 其中 关系模式r的属性全集u是分解后所有小关系模式的属性集ui的并集 对于每个i j 1 i j k 有uiuj 分解的小属性集间不会相互为子集 fi x y x y f xy ui fi i 1 2 k 是f在ui上的投影 则称 是关系模式r f u 的一个分解 定义5 7实际上仅给出了模式分解必须满足的基本条件 有时也会出现将原模式存储信息丢失的现象 无损分解 1 例5 7设关系模式r abc 分解成 ab ac 上图分解后的关系可以通过自然连接还原 而下图分解后的关系通过自然连接后不能还原 称比r多出来的元组为 噪音 无损分解 2 定义4 10设r是一个关系模式 f是r上的一个fd集 r分解成数据库模式 r1 rk 如果对r中满足f的每一个关系r 都有r r1 r r2 r rk r 那么称分解 相对于f是 无损联接分解 losslessjoindecomposition 简称为 无损分解 否则称为 损失分解 lossydecomposition 例5 7给出了 无损分解 和 损失分解 的例子 无损分解 3 例设关系模式r abc 分解成 ab bc a 和 b 分别是模式ab和bc上的值r1和r2 c 是r1 r2的值 显然 bc r1 r2 r2 这里r2中元组 b2c2 就是一个悬挂元组 由于它的存在 使得r1和r2不存在泛关系r 模式分解的目的就是为了消除冗余和操作异常现象 但有时会产生存储泛关系中无法存储的信息 悬挂元组 无损分解 4 算法5 1无损分解的测试 构造一张k行n列的表格 每列对应一个属性aj 1 j n 每行对应一个模式ri 1 i k 如果aj在ri中 那么在表格的第i行第j列处填上符号aj 否则填上bij 把表格看成模式r的一个关系 反复检查f中每个fd在表格中是否成立 若不成立 则修改表格中的值 修改方法为 对于f中一个fdx y 如果表格中有两行在x值上相等 在y值上不相等 那么把这两行在y值上也改成相等的值 如果y值中有一个是aj 那么另一个也改成aj 如果没有aj 那么用其中一个bij替换另一个值 尽量把下标ij改成较小的数 一直到表格不能修改为止 这个过程称为chase过程 若修改的最后一张表格中有一行是全a 即a1a2 an 那么称 相对于f是无损分解 否则称损失分解 无损分解 5 a 初始表格 a 修改后的表格 b 初始表格 b 修改后的表格 例5 8设关系r abcd r分解成 ab bc cd 如果r上成立的函数依赖集f1 b a c d 则 对f1是否为无损分解 如果f1换为f2 a b c d 呢 本行全是a 是无损连接 无a行 是有损连接 无损分解 6 对于分解为两个模式的情况 可根据下列定理分解 定理5 1设 r1 r2 是关系模式r的一个分解 f是r上成立的fd集 那么分解 相对于f是无损分解的充分必要条件是 r1 r2 r1 r2 或 r1 r2 r2 r1 说明 该定理中的两个函数依赖不一定属于f 只要属于f 即可 例 设有关系模式r sno sname cno grade sno sname snocno grade 的一个分解为 r1 sno sname sno sname r2 sno cno grade snocno grade 因为r1 r2 sno r1 r2 sname 所以r1 r2 r1 r2 即sno sname 它属于f 由定理4 7可知 分解具有无损性连接 如果两个关系模式间的公共属性集至少包含其中一个关系模式的主健 则此分解是无损分解 保持函数依赖分解 1 定义5 9设f是属性集u上的fd集 z是u的子集 f在z上的投影用 z f 表示 定义为 z f x y x y f 且xy z 定义5 10设 r1 rk 是r的一个分解 f是r上的fd集 如果有 ri f f 那么称分解 保持函数依赖集f 定理5 2 保持函数依赖分解的充要条件是 保持函数依赖分解的意义 在作任何数据输入和修改时 只要每个关系模式本身的函数依赖约束可满足 就可以确保整个数据库中数据的语义完整性不受破坏 保持函数依赖分解 2 例设关系模式r wno ws wg 的属性分别表示职工的工号 工资级别和工资数目 如果规定每个职工只有一个工资级别 并且一个工资级别只有一个工资数目 那么r上的fd有wno ws和ws wg r1上fd是f1 wno ws r2上的fd是f2 wno wg 但从这两个fd推导不出在r上成立的fdws wg 因此分解 把ws wg丢失了 即 不保持f 如果r分解成 r1 r2 其中r1 wno ws r2 wno wg 可以验证这个分解是无损分解 保持函数依赖分解 3 一个无损连接不一定具有函数依赖保持性 反之一个具有函数依赖保持性的分解也不一定是无损连接 例5 9设r abcd f a b c d r1 a b a b r2 c d c d 因为f a b c d f1 f2 a b c d 所以f f1 f2 即分解 具有依赖保持性 易验证 不具有无损性 保持函数依赖分解 4 例5 10设r abc f a b c b r1 a b f1 r2 a c f2 其中f1 a b f2 a c 因为r1 r2 a r1 r2 b r2 r1 c所以r1 r2 r1 r2为a b f 但f f1 f2 可见 具有无损分解 但不具有保持函数依赖分解 5 4关系模式的范式 主要内容 第一范式第二范式第三范式bcnf范式数据库设计的原则 关系模式的范式 关系模式的好与坏 用什么标准衡量 这个标准就是模式的范式 normalforms 简记为nf 范式的种类与数据依赖有着直接的联系 基于fd的范式有1nf 2nf 3nf bcnf等多种 在不提及fd时 关系中是不可能有冗余的问题 但是当存在fd时 关系中就有可能存在数据冗余问题 1nf是关系模式的基础 2nf已成为历史 一般不再提及 在数据库设计中最常用的是3nf和bcnf 关系模式的范式 对于各种范式之间的联系有 第一范式 非规范模式变为1nf 1 把不含单纯值的属性分解为多个原子值 2 把关系模式分解 定义5 11如果关系模式r的每个关系r的属性值都是不可分的原子值 那么称r是第一范式 firstnormalform 简记为1nf 的模式 满足1nf的关系称为规范化的关系 否则称为非规范化的关系 关系数据库研究的关系都是规范化的关系 例如关系模式r name address phone 如果一个人有两个电话号码 phone 那么在关系中至少要出现两个元组 以便存储这两个号码 1nf是关系模式应具备的最起码的条件 第二范式 1 定义5 12对于fdw a 如果存在x w有x a成立 那么称w a是局部依赖 a局部依赖于w 否则称w a是完全依赖 完全依赖也称为 左部不可约依赖 定义5 13如果a是关系模式r的候选键中属性 那么称a是r的主属性 否则称a是r的非主属性 定义5 14如果关系模式r是1nf 且每个非主属性完全函数依赖于候选键 那么称r是第二范式 2nf 的模式 如果数据库模式中每个关系模式都是2nf 则称数据库模式为2nf的数据库模式 第二范式 2 例5 11设关系模式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模式 第二范式 3 算法5 2分解成2nf模式集的算法设关系模式r u 主键是w r上还存在fdx z 并且z是非主属性和x w 那么w z就是一个局部依赖 此时应把r分解成两个模式r1 xz 主键是x r2 y 其中y u z 主键仍是w 外键是x referencesr1 利用外键和主键的联接可以从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 第三范式 定义5 15如果x y y a 且y x和a y 那么称x a是传递依赖 a传递依赖于x 定义5 16如果关系模式r是1nf 且每个非主属性都不传递依赖于r的候选键 那么称r是第三范式 3nf 的模式 如果数据库模式中每个关系模式都是3nf 则称其为3nf的数据库模式 第三范式 1 例在例5 9中 r2是2nf模式 而且也已是3nf模式 但r1 cno tname taddr 是2nf模式 却不一定是3nf模式 如果r1中存在函数依赖cno tname和tname taddr 那么cno taddr就是一个传递依赖 即r1不是3nf模式 此时r1的关系中也会出现冗余和异常操作 譬如一个教师开设五门课程 那么关系中就会出现五个元组 教师的地址就会重复五次 如果把r2分解成r21 tname taddr 和r22 cno tname 后 cno taddr就不会出现在r21和r22中 这样r21和r22都是3nf模式 算法5 3分解成3nf模式集的算法设关系模式r u 主键是w r上还存在fdx z 并且z是非主属性 z x 且x不是候选键 这样w z就是一个传递依赖 此时应把r分解成两个模式 r1 xz 主键是x r2 y 其中y u z 主键仍是w 外键是x referencesr1 利用外键和主键相匹配机制 r1和r2通过联接可以重新得到r 如果r1和r2还不是3nf 则重复上述过程 一直到数据库模式中每一个关系模式都是3nf为止 如果r是3nf模式 那么r也是2nf模式 第三范式 2 第三范式 3 定理设关系模式r 当r上每一个fdx a满足下列三个条件之一时 a x 即x a是一个平凡的fd x是r的超键 a是主属性 则关系模式r就是3nf模式 第三范式 4 违反3nf的传递依赖的三种情况 部分依赖 键是超键 传递依赖 第三范式 5 局部依赖和传递依赖是模式产生数据冗余和操作异常的两个重要原因 由于3nf模式中不存在非主属性对候选键的局部依赖和传递依赖 因此消除了很大一部分存储异常 具有较好的性能 定义5 16设f是关系模式r的fd集 如果对f中每个非平凡的函数依赖x y 都有x是r的超键 或者y的每个属性都是主属性 那么称r是3nf的模式 这个定义表明 如果非平凡的函数依赖x y x不包含超键 并且y不是主属性 那么y必传递依赖于候选键 因此r不是3nf模式 bcnf范式 1 定义5 17如果关系模式r是1nf 且每个属性都不传递依赖于r的候选键 那么称r是bcnf的模式 如果数据库模式中每个关系模式都是bcnf 则称为bcnf的数据库模式 如果r是bcnf模式 那么r也是3nf模式 设f是关系模式r的fd集 如果对f中每个非平凡的fdx y 都有x是r的超键 那么称r是bcnf的模式 一个满足bcnf的关系模式有 所有非主属性对每一个码都是完全函数依赖 所有的主属性对每一个不包含它的码 也是完全函数依赖 没有任何属性完全函数依赖于非码的任何一组属性 bcnf范式 2 例5 13关系模式s sno sname sdept age 假定sname也具有唯一性 那么s就有两个键 这两个键都由单个属性组成 彼此不相交 其他属性不存在对键的传递依赖与部分依赖 所以s是3nf 同时s中除sno sname外没有其他决定因素 所以s也是bcnf 例5 14关系模式stj s t j 中 s表示学生 t表示教师 j表示课程 每一教师只教一门课 每门课有若干教师 某一学生选定某门课 就对应一个固定的教师 由语义可得到如下的函数依赖 s j t s t j t j 这里 s j s t 都是候诜键 stj是3nf 因为没有任何非主属性对键函数传递依赖或部分函数依赖 但stj不是bcnf模式 是因为t是决定因素 而t不包含键 3nf和bcnf是在函数依赖的条件下对模式分解所能达到的分离程度的测度 一个数据库中的关系模式如果都是