数据库系统原理及应用教程第四版课后答案 第7章.ppt

本章教学目标 重点和难点 教学目标 使学生了解关系模式规范化的必要性 理解函数依赖 多值依赖及其关系范式定义 掌握关系范式判断方法 教学重点 关系模式规范化 函数依赖 多值依赖 1 4NF的定义 关系范式判断方法 教学难点 1 4NF的定义 关系范式判断方法 关系模式的分解 第7章关系规范化理论和优化技术 7 1关系数据模式的规范化理论7 2关系模式的分解算法 7 1关系数据模式的规范化理论 范式 NormalForm 是指规范化的关系模式 由满足最基本规范化的关系模式叫第一范式 第一范式的关系模式再满足另外一些约束条件就产生了第二范式 第三范式 BC范式等等 一个低一级的关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合 这种过程叫关系模式的规范化 7 1 1关系模式规范化的必要性 1 关系模式应满足的基本要求1 元组的每个分量必须是不可分的数据项 2 数据冗余应尽可能少 3 不能因为数据更新操作而引起数据不一致问题 4 当执行数据插入操作时 数据不能产生插入异常现象 5 数据不能在执行删除操作时产生删除异常问题 6 数据库设计应考虑查询要求 数据组织应合理 2 关系规范化可能出现的问题 数据冗余大 插入异常 删除异常 更新异常 3 模式分解是关系规范化的主要方法 上述的关系模式 教学 学号 姓名 年龄 性别 系名 系主任 课程名 成绩 可以按 一事一地 的原则分解成 学生 教学系 和 选课 三个关系 其关系模式为 学生 学号 姓名 年龄 性别 系名称 教学系 系名 系主任 选课 学号 课程名 成绩 7 1 2函数依赖及其关系的范式 1 关系模式的简化表示法关系模式的完整表示是一个五元组 R U D Dom F 其中 R为关系名 U为关系的属性集合 D为属性集U中属性的数据域 Dom为属性到域的映射 F为属性集U的数据依赖集 关系模式可以用三元组来为 R U F 2 函数依赖的概念 1 设R U 是属性集U上的关系模式 X Y是U的子集 若对于R U 的任意一个可能的关系r r中不可能存在两个元组在X上的属性值相等 而Y上的属性值不等 则称X函数确定Y函数 或Y函数依赖于X函数 记作X Y 例如 对于教学关系模式 教学 U F U 学号 姓名 年龄 性别 系名 系主任 课程名 成绩 F 学号 姓名 学号 年龄 学号 性别 学号 系名 系名 系主任 学号 课程名 成绩 X Y 但YX 则称X Y是非平凡的函数依赖 若不特别声明 总是讨论非平凡的函数依赖 X Y 但Y X 则称X Y是平凡的函数依赖 若X Y 则X叫做决定因素 Determinant Y叫做依赖因素 Dependent 若X Y Y X 则记作X Y 若Y不函数依赖于X 则记作XY 完全函数依赖 传递函数依赖 2 在R U 中 如果X Y 并且对于X的任何一个真子集X 都有X Y 则称Y对X完全函数依赖 记作 X Y 若X Y 但Y不完全函数依赖于X 则称Y对X部分函数依赖 记作 X Y 例如 在教学关系模式 学号 课程名 成绩 学号 课程名 姓名3 在R U 中 如果X Y YX YX Y Z 则称Z对X传递函数依赖 传递函数依赖记作X Z 传递例如 在教学模式中 因为 学号 系名 系名 系主任 所以 学号 系主任 P F F P 传递 传递 3 1NF的定义 2NF的定义 如果关系模式R 其所有的属性均为简单属性 即每个属性都是不可再分的 则称R属于第一范式 记作R 1NF 若R 1NF 且每一个非主属性完全依赖于码 则R 2NF 在教学中 属性集 学号 姓名 年龄 系名 系主任 课程名 成绩 函数依赖集 学号 姓名 学号 年龄 学号 性别 学号 系名 系名 系主任 学号 课程名 成绩 主码 学号 课程名 非主属性 姓名 年龄 系名 系主任 成绩 非主属性对码的函数依赖 学号 课程名 姓名 学号 课程名 年龄 学号 课程号 性别 学号 课程名 系名 学号 课程名 系主任 学号 课程名 成绩 显然 教学模式不服从2NF 即 教学 2NF P P P P P 5 3NF的定义 关系模式R U F 中若不存在这样的码X 属性组Y及非主属性Z ZY 使得X Y YX Y Z成立 则称R U F 3NF 可以证明 若R 3NF 则每一个非主属性既不部分函数依赖于码 也不传递函数依赖于码 考查学生 系关系 由于存在 学号 系名 系名 系主任 则 学号 系主任 所以学生 系 3NF 如果分解为 学生 学号 姓名 年龄 性别 系名 教学系 系名 系主任 显然分解后的各子模式均属于3NF 传递 6 BCNF的定义 关系模式R U F 1NF 若X Y且YX时X必含有码 则R U F BCNF 也就是说 关系模式R U F 中 若每一个决定因素都包含码 则R U F BCNF 由BCNF的定义可以得到结论 一个满足BCNF的关系模式有 1 所有非主属性对每一个码都是完全函数依赖 2 所有的主属性对每一个不包含它的码 也是完全依赖 3 没有任何属性完全函数依赖于非码的任何一组属性 7 BCNF和3NF的比较 1 BCNF不仅强调其他属性对码的完全的直接的依赖 而且强调主属性对码的完全的直接的依赖 它包括3NF 即R BCNF 则R一定属于3NF 2 3NF只强调非主属性对码的完全直接依赖 这样就可能出现主属性对码的部分依赖和传递依赖 例如 关系模式STJ S T J 中 S表示学生 T表示教师 J表示课程 语义为 每一教师只能讲授一门课程 每门课程由若干教师讲授 每个学生选修某门课程就对应一个固定的教师 由语义可以得到STJ模式的函数依赖为 F S J T T J 显然 S J 和 T S 都是关系的码 关系的主属性集为 S T J 非主属性为 空集 由于STJ模式中无非主属性 所以它属于3NF 但因为存在T J 由于T不是码 故STJ BCNF 7 1 3多值依赖及关系的第4范式 1 研究多值依赖的必要性例如 给定一个关系模式JPW 产品 零件 工序 其中每种产品由多种零件构成 每个零件在装配时需要多道工序 设产品电视机需要的零件和工序如图所示 2 多值依赖的定义和性质 设有关系模式R U U是属性集 X Y是U的子集 如果R的任一关系 对于X的一个确定值 都存在Y的一组值与之对应 且Y的这组值又与Z U X Y中的属性值不相关 此时称Y多值依赖于X 或X多值决定Y 记为X Y 多值依赖具有以下性质 1 多值依赖具有对称性 即若X Y 则X Z 其中Z U X Y 2 函数依赖可以看作是多值依赖的特殊情况 即若X Y 则X Y 这是因为当X Y时 对X的每一个值x Y有一个确定的值y与之对应 所以X Y 3 在多值依赖中 若X Y且Z U X Y 则称X Y为非平凡的多值依赖 否则称为平凡的多值依赖 7 2关系模式的分解算法7 2 1关系模式分解的算法基础 1 函数依赖的逻辑蕴含设F是R U 函数依赖集 X和Y是属性集U的子集 如果从F中的函数依赖能推出X Y 则称F逻辑蕴含X Y 或称X Y是F的逻辑蕴含 1 Armstrong公理系统 设U为属性集 F是U上的函数依赖集 于是有关系模式R U F 1 自反律 若Y X U 则X Y为F所蕴含 2 增广律 若X Y为F所蕴含 且Z U 则XZ YZ为F所蕴含 3 传递律 若X Y及Y Z为F所蕴含 则X Z为F所蕴含 2 Armstrong公理的三个推理1 合并规则 由X Y X Z 有X YZ 2 伪传递规则 由X Y WY Z 有XW Z 3 分解规则 由X Y及Z Y 有X Z 2 Armstrong公理系统 3 函数依赖集闭包F 和属性集闭包XF 1 函数依赖集闭包F 和属性集闭包XF 的定义定义 在关系模式R U F 中 为F所逻辑蕴含的函数依赖的全体叫做F的闭包 记作F 定义 设有关系模式R U F X是U的子集 称所有从F推出的函数依赖集X Ai中Ai的属性集为X的属性闭包 记作XF 即 XF Ai Ai U X Ai F 2 属性集闭包XF 的求法 1 选X作为闭包XF 的初值XF 0 2 XF i 1 是由XF i 并上集合A所组成 其中A为F中存在的函数依赖Y Z 而A Z Y XF i 3 重复步骤2 一旦发现XF i XF i 1 则XF i 为所求XF 例子 例 已知关系R U F 其中U A B C D E F AB C B D C E EC B AC B 求 AB F 设X AB XF 0 ABXF 1 ABCDXF 2 ABCDEXF 3 XF 2 ABCDE AB F ABCDE A B C D E 4 函数依赖集的最小化 1 最小函数依赖集的定义1 F中任一函数依赖的右部仅含有一个属性 2 F中不存在这样的函数依赖X A 使得F与F X A 等价 3 F中不存在这样的函数依赖X A X有真子集Z使得F X A Z A 与F等价 2 最小函数依赖集的求法 1 逐一检查F中各函数依赖X Y 若Y A1A2 Ak k 2 则用 X Aj j 1 2 k 来取代X Y 2 逐一检查F中各函数依赖X A 令G F X A 若A XG 则从F中去掉此函数依赖 3 逐一取出F中各函数依赖X A 设X B1B2 Bm 逐一检查Bi i 1 2 m 如果A X Bi F 则以X Bi取代X 例 设F A BC B AC C A 对F进行极小化处理 解 1 把F中的函数依赖转换成右部都是单属性的函数依赖 分解后的函数依赖集仍用F表示 F A B A C B A B C C A 2 去掉F中冗余的函数依赖 判断A B 设 G1 A C B A B C C A 得 AG1 AC B AG1 A B不冗余判断A C 设 G2 A B B A B C C A 得 AG2 ABC C AG2 A C冗余判断B A 设 G3 A B B C C A 得 BG3 BCA A BG3 B A冗余判断B C 设 G4 A B C A 得 BG4 B C BG4 B C不冗余判断C A 设 G5 A B B C 得 CG5 C A CG5 C A不冗余Fm A B B C C A 例 求F AB C A B B A 的最小函数依赖集Fm 解 1 去掉F中冗余的函数依赖 判断AB C是否冗余 设 G1 A B B A 得 AB G1 AB C AB G1 AB C不冗余判断A B是否冗余 设 G2 AB C B A 得 AG2 A B ABG2 A B不冗余判断B A是否冗余 设 G3 AB C A B 得 BG3 B A BG3 B A不冗余经过检验后的函数依赖集仍然为F AB C A B B A 例 求F AB C A B B A 的最小函数依赖集Fm 解 2 去掉各函数依赖左部冗余的属性 本题只需考虑AB C的情况 方法1 在决定因素中去掉B 若C AF 则以A C代替AB C 求得 AF ABC C AF 以A C代替AB C故 Fm A C A B B A 方法2 在决定因素中去掉A 若C BF 则以B C代替AB C 求得 BF ABC C BF 以B C代替AB C故 Fm B C A B B A 7 2 3判定分解服从规范的方法 1 关系分解的无损连接性设关系模式R 如果把它分解为两个 或多个 子模式R1和R2 相应一个R关系中的数据就要被分成R1 R2两个 或多个 子表 假如将这些子表自然连接 即进行R1R2操作 得到的结果与原来关系中的数据一致 信息并没有丢失 则称该分解具有无损连接性 否则如果R R1R2 则称该分解不具有无损连接性 2 判断分解成两个关系具有无损连接性的方法定理 R U F 的一个分解 R1 U1 F1 R2 U2 F2 具有无损连接性的充分必要条件是 U1 U2 U1 U2 F 或U1 U2 U2 U1 F 3 判断分解保持函数依赖的方法设 U F 的分解 R1 U1 F1 R1 U2 F2 Rk UK FK 若F Fi 则称分解 保持函数依赖 例 关系模式R CITY ST ZIP 其中CITY为城市 ST为街道 ZIP为邮政编码 F CITY ST ZIP ZIP CITY 如果将R分解成R1和R2 R1 ST ZIP R2 CITY ZIP 检查分解是否具有无损连接和保持函数依赖 解 1 检查无损连接性 求得 R1 R2 ZIP R2 R1 CITY ZIP CITY F 分解具有无损连接性2 检查分解是否保持函数依赖求得 R1 F R2 F ZIP CITY R1 F R2 F ZIP CITY F 该分解不保持函数依赖 7 2 4关系模式的分解方法 1 将关系模式转化为3NF的保持函数依赖的分解1 对R U F 中的F进行极小化处理 处理后的函数依赖集仍用F表示 2 找出不再在F中出现的属性 把这样的属性构成一个关系模式 并把这些属性从U中去掉 3 若F中有一个函数依赖涉及R全部属性 则R不能再分解 4 如果F中含有X A 则分解应包含模式XA 如果X A1 X A2 X An均属于F 则分解应包含模式XA1A2 An 例 设R U F U C T H R S G X Y Z F C T CS G HR C HS R TH R C X 将R分解为3NF 且保持函数依赖 解 设该函数依赖集已经是最小化的 则分解 为 YZ CTX CSG HRC HSR THR 2 将关系转化为3NF 且既具有无损连接性又能保持函数依赖的分解 对于给定的关系模式R U F 将其转换为3NF 且既具有无损连接性又能保持函数依赖的分解算法为 1 设X是R U F 的码 R U F 先进行保持函数依赖的分解 结果为 R1 U1 F1 R2 U2 F2 Rk Uk Fk 令 R X Fx 2 若有某个Ui X Ui 将R X Fx 从 中去掉 就是所求的分解 例 有关系模式R U F U C T H R S G F C T CS G HR C HS R TH R 将R分解为3NF 且既具有无损连接性又能保持函数依赖 解 求得关系模式R的码为HS 它的一个保持函数依赖的3NF为 CT CSG HRC HSR THR HS HSR CT CSG HRC HSR THR 为满足要求的分解 33 可编辑 3 将关系模式转换为BCNF的无损连接的分解 1 令 R U F 2 检查 中各关系模式是否均属于BCNF 若是 则算法终止 3 假设 中Ri Ui Fi 不属于BCNF 那么必定有X A Fi A X 且X非Ri的码 对Ri进行分解 S1 S2 US1 XA US2 Ui A 以 代替Ri Ui Fi 返回第2 步 例 关系模式R U F U CTHRSG F C T HR C HT R CS G HS R 把R分解成具有无损连接的BCNF 解 令 CTHRSG1 由于R的码为HS 选择CS G分解 得出 S1 S2 其中 S1 CSG F1 CS G S2 CTHRS F2 C T HR C HT R HS R S2不服从BCNF 需要继续分解 2 对S2分解 S2的码为HS 选择C T分解 得 S1 S3 S4 其中 S3 CT F3 C T S4 CHRS F4 HR C HS R S4不服从BCNF 还需要继续分解 3 对S4分解 码为HS 选择HR C分解 S1 S3 S5 S6 其中 S5 HRC F5 HR C S6 HRS F6 HS R 4 最后的分解为 CSG CT HRC HRS 习题7 7 2答 正确 因为学号能够多值决定课程号 且除了学号和课程号外还有成绩属性 它不是平凡的多值依赖 7 3设有关系模式R A B C 数据依赖集F AB C C A R属于第几范式 为什么 7 3答 BCNF 由于A多值依赖于C 而C不是码 故不服从4NF 但在函数依赖式中 C依赖于码AB 故该模式服从BCNF 7 4答 正确 正确 正确 正确 正确 正确 正确 不正确 例如 学号 课程号 成绩 则不存在 学号 成绩 课程号 成绩 7 7答 把查询转换成语法树表示 把语法树转换成标准 优化 形式 选择低层的存取路径 生成查询计划 选择代价最小的查询计划 7 8试述查询优化的一般准则 7 8答 选择运算尽可能先做 在执行连接前对关系适当地预处理 即在连接属性上建立索引和对关系进行排序 把投影运算和选择运算同时进行 把投影同其前或其后的双目运算结合起来 把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算 找出公共子表达式 7 13答 是BCNF 二元关系中或为全码 或为一个单属性码候选码 是BCNF 关系模式中只有一个候选码 不是BCNF 因为模式中存在候选码为AD BCD和BE 显然C对AD是部分依赖 7 22答 1 关系STUDENT是1NF 2 消除部分函数依赖 S CNAME SNAME SDEPT MNAME 将关系分解为 R1 S SNAME SDEPT MNAME R2 S CNAME GRADE 由于在关系R1中 存在非主属性对候选码的传递函数依赖 S SDEPT SDEPT MNAME 所以以上关系模式还不是BCNF 进一步分解R1为 R11 S SNAME SDEPT R12 SDEPT MNAME R11 R12都是3NF 对于关系模式 R2 S CNAME GRADE F2 S CNAME GRADE R11 S SNAME SDEPT F11 S SNAME S SDEPT R12 SDEPT MNAME F12 SDEPT MNAME 上述函数依赖都是非平凡的 并且决定因素是候选码 所以上述关系模式属于BCNF 7 23设有关系模式R A B C D 其函数依赖集 F A C C A B AC D AC 1 求F的最小等价依赖集FC 2 将R分解为满足3NF且具有无损连接并保持函数依 答 FC A C C A B A D A F1 A C F2 B A F3 D A F4 B D 7 24设有关系模式R U F 其中 U C T H R S G F CS G C T TH R HR C HS R 请根据算法将R分解为满足BCNF且具有无损连 答 F1 C S G F2 C T F3 C H R F4