数据库原理与技术第六章.ppt

第六章关系数据理论 问题 如何才能构造一个良好的关系模式 要回答这个问题就必须要解决以下问题 什么是不好的关系模式 一个不好的关系模式存在哪些弊病 区分一个关系模式设计的优劣程度的标准是什么 如何将一个不好的关系模式转换为一个好的关系模式 关系数据理论借助于数学工具规定了一套关系数据库设计的理论和方法 是数据库逻辑设计的有力工具 关系数据库设计中存在的问题 I 有关学生的关系模式S SNO SNAME DEPT HEAD CNO G 主键 关系数据库设计中存在的问题 问题插入异常 如果一个系刚成立没有学生 或者有了学生但尚未安排课程 那么就无法将这个系及其负责人的信息插入数据库 删除异常 如果某个系的全部学生都毕业了 则删除该系学生及其选修课程的同时 把这个系及其负责人的信息也丢掉了 数据冗余和更新异常 学生及其所选课程很多 而系主任只有一个 但其却要和学生及其所选课程出现的次数一样多 此外 如果某个系要更换系主任 就必须修改这个系学生所选课程的每个元组 修改其中的系主任信息 若有疏忽 就会造成数据的不一致 从而造成更新异常 关系数据库设计中存在的问题 原因 把多个实体型用一个关系模式表示解决之道 分解 函数依赖 一个实体型的诸属性之间具有内在的联系 通过对这些联系的分析 我们可以做到一个关系模式只表示一个实体型的信息 从而消除上述问题 在关系模型中 我们利用数据依赖来描述这些属性间的联系 数据依赖是通过关系中属性间值的相等与否体现出来的数据间的相互关系 它是现实世界属性间相互联系的抽象 是数据内在的性质 是语义的体现 其中最重要的是函数依赖 函数依赖 设有以下关系模式U Sno Sname Dept Head Cno G 现实世界中的语义一个系有若干学生 但一个学生只属于一个系一个系只有一个 正职 负责人一个学生可以选修多门课程 每门课程有若干学生选修每个学生选修每门课程有一个成绩 北京航空航天大学软件开发环境重点实验室 函数依赖 SELECTSNAMEFROMSWHERESNO S01 SELECTSNAMEFROMSWHERESNO S02 SELECTSNOFROMSWHERESNAME 李婉 函数依赖 函数依赖极为普遍地存在于现实生活中 考察关系模式S SNO SNAME DEPT HEAD CNO G 由于一个SNO只对应一个学生 而一个学生只能在一个系中学习 因而当SNO的值确定后 SNAME和DEPT也被唯一地确定了 就像自变量x确定后 相应的f x 也被确定了一样 我们说SNO函数决定 SNAME DEPT 而 SNAME DEPT 函数依赖于SNO 函数依赖 定义函数依赖 设R U 是属性集U上的关系模式 X Y是U的子集 若对于R U 的任意一个可能的关系r r中不可能存在两个元组在X上的属性值相等 而在Y上的属性值不等 则称X函数决定Y 或Y函数依赖于X 记作X Y 如SNO SNAME SNO CNO GSELECTSNO COUNT DISTINCTSNAME FROMSGROUPBYSNO 函数依赖 函数依赖是不随时间而变的 若关系模式R具有函数依赖X Y 那么虽然关系模式R的关系实例r在X Y上的取值各不相同 并且随时间而变化 但X Y在任一特定时刻都保持函数依赖X Y 函数依赖不是指关系模式R的某个或某些关系满足的约束条件 而是指R的一切关系均要满足的约束条件 函数依赖是语义范畴的概念 它反映了一种语义完整性约束 我们只能根据语义来确定一个函数依赖 关系数据库设计中存在的问题 I G SNO G SNAME SNO SNAME 函数依赖 函数依赖于属性间的联系类型有关 当X Y之间是 1对1 联系时 则存在函数依赖X Y和Y X 如 学号和身份证号当X Y之间是 多对1 联系时 则存在函数依赖X Y 如 SNO和DEPT当X Y之间是 多对多 联系时 则不存在函数依赖 如 SNO和CNO 函数依赖 平凡函数依赖 如果X Y 但Y X 则称其为非平凡的函数依赖 否则称为平凡的函数依赖 如 SNO SNAME SNAME是平凡的函数依赖完全函数依赖 在R U 中 如果X Y 且对于X的任何真子集X 都有X Y 则称Y对X完全函数依赖 记作XY 否则称为Y对X部分函数依赖 记作XY SNO CNO G SNO CNO SNAME 函数依赖 传递函数依赖 在R U 中 如果X Y Y X Y Z 且Y X Z Y则称Z对X传递函数依赖 SNO DEPT DEPT HEAD 函数依赖 检验 A C C A AB D 码 定义候选码 设K为R的属性或属性组合 若KU 则称K为R的一个候选码 若候选码多于一个 则选定其中一个作为主码 超码 设K为R的属性或属性组 若K U 则称K为R的超码 码 主属性 包含在任何一个候选码中的属性 称作主属性 非主属性 不包含在任何一个候选码中的属性 称作非主属性 全码 关系模式的码由整个属性组构成 如 P W A 例子 关系模式S SNO SNAME DEPT HEAD CNO G 主码 SNO CNO 函数依赖 SNO CNO GSNO SNAME SNO CNO SNAMESNO DEPT SNO CNO DEPTSNO HEAD SNO CNO HEAD 范式 定义范式是对关系的不同数据依赖程度的要求 如果一个关系满足某个范式所指定的约束集 则称它属于某个特定的范式 规范化 一个低一级范式的关系模式 通过模式分解可以转换为若干个高级范式的关系模式的集合 这一过程称作规范化 1NF 定义关系中每一分量必须是原子的 不可再分 即不能以集合 序列等作为属性值 不满足1NF的关系模式 满足1NF的关系模式 2NF 定义若R 1NF 且每个非主属性完全依赖于码 则称R 2NF将1NF的关系模式规范化为2NF的关系模式 其方法是消除1NF的关系模式中非主属性对码的部分依赖 思考 如果关系R的全体属性都是R的主属性 或者R的所有候选码都只含一个属性 那么 R是否属于第二范式 2NF II 关系模式S SNO SNAME DEPT HEAD CNO G 不良特性插入异常 如果学生没有选课 关于他的个人信息及所在系的信息就无法插入 删除异常 如果删除学生的选课信息 则有关他的个人信息及所在系的信息也随之删除了 数据冗余 如果一个学生选修了k门课 则有关他的所在系的信息重复更新异常 如果学生转系 若他选修了k门课 则需要修改k次 2NF III 原因 S 2NF 因为 SNO CNO GSNO SNAME SNO CNO SNAMESNO DEPT SNO CNO DEPTSNO HEAD SNO CNO HEAD规范化将S分解为 S SD SNO SNAME DEPT HEAD 2NFSC CNO G 2NF SNO 3NF I S SD SNO SNAME DEPT HEAD 不良特性插入异常 如果系中没有学生 则有关系的信息就无法插入 删除异常 如果学生全部毕业了 则在删除学生信息的同时有关系的信息也随之删除了 更新异常 如果学生转系 不但要修改DEPT 还要修改HEAD 如果换系主任 则该系每个学生元组都要做相应修改 数据冗余 每个学生都存储了所在系的系主任的信息 3NF II 定义关系模式R中 若不存在这样的码X 属性组Y及非主属性Z ZY 使得下式成立 X Y Y Z Y X则称R 3NF 将2NF的关系模式规范化为3NF的关系模式 其方法是消除2NF的关系模式中非主属性对码的传递依赖 3NF III 原因 S SD 3NF 因为SNO SNAME SNO DEPTSNOHEAD原因 SNO DEPT DEPT HEAD规范化将S分解为 DEPT DEPT HEAD STUDENT SNAME SNO DEPT BCNF I 示例STJ S T J S表示学生 T表示教师 J表示课程 每位老师只教授一门课 每门课由若干教师教 某一学生选定某门课就确定了一个固定的教师 因此具有以下函数依赖 T J S J T S T S J 为候选码 BCNF 不良特性插入异常 如果没有学生选修某位老师的任课 则该老师担任课程的信息就无法插入 删除异常 删除学生选课信息 会删除掉老师的任课信息 更新异常 如果老师所教授的课程有所改动 则所有选修该老师课程的学生元组都要做改动 数据冗余 每位学生都存储了有关老师所教授的课程的信息 BCNF III 定义若关系模式R 1NF 若X Y 且Y X时 X必含有码 则R BCNF 由BCNF的定义可以看到 每个BCNF的关系模式都具有如下三个性质 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性 BCNF IV 原因 存在主属性对码的不良依赖 STJ BCNF 因为T J 而T不含有码 改造将S分解为 S T T J 思考 S J P 表示学生选修课程的名次 有函数依赖 S J P J P S 它属于BCNF吗 多值依赖 关系模式TEACH C P B 一门课程由多个教师任教 一门课程使用相同的一套参考书 它的码是 C P B 所以属于BCNF 多值依赖 不良特性插入异常 当某门课程增加一名教师时 该门课程有多少本参考书就必须插入多少个元组 同样当某门课程需要增加一本参考书时 它有多少个教师就必须插入多少个元组 删除异常 当删除一门课程的某个教师或者某本参考书时 需要删除多个元组 数据冗余 同一门课的教师与参考书的信息被反复存储多次 更新异常 当一门课程的教师或参考书作出改变时 需要修改多个元组 多值依赖 III 定义设R U 是属性集U上的一个关系模式 X Y Z是U的子集 并且Z U X Y 关系模式R U 中多值依赖X Y成立 当且仅当对R U 的任一关系r 给定的一对 x z 值有一组Y的值 这组值仅仅决定于x值而与z值无关 如在关系模式TEACH中 对 物理 普通物理学 有一组P 值 张明 张平 对 物理 光学原理 也有一组P 值 张明 张平 这组值仅取决于C 的取值 而与B 的取值无关 因此 P 多值依赖于C 记作C P 同样有C B 多值依赖 形式化 在R U 的任一关系r中 如果存在元组t s使得t x s x 那么就必然存在元组w v r w v可以与s t相同 使得 w X s X v X t X w Y t Y v Y s Y w Z s Z v Z t Z 则称Y多值依赖与X 记作X Y 若X Y 而Z 则称X Y为平凡的多值依赖 多值依赖 性质多值依赖具有对称性 即若X Y 则X Z 其中Z U X Y 函数依赖是多值依赖的特例 即若X Y 则X Y 若X Y X Z 则X YZ若X Y X Z 则X Y Z若X Y X Z 则X Y Z X Z Y若X Y Y Z 则X Z Y 多值依赖Vs函数依赖 函数依赖有效性范围X Y的有效性仅决定于X Y属性集上的值 它在任何属性集W XY W U 上都成立 若X Y在R U 上成立 则对于任何Y Y 均有X Y 成立 多值依赖Vs函数依赖 多值依赖有效性范围X Y的有效性与属性集范围有关 X Y在U上成立 X Y在属性集W XY W U 上成立 反之则不然 若在R U 上 X Y在属性集W XY W U 上成立 则称X Y为R U 的嵌入式多值依赖 若X Y在R U 上成立 则不能断言对于Y Y 是否有X Y 成立 4NF 定义关系模式R 1NF 如果对于R到每个非平凡的多值依赖X Y Y X 是 X都含有码 则称R 4NF 4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖 因为根据定义 对于每一个非平凡的多值依赖X Y X都含有候选码 于是就有X Y 所以4NF所允许的非平凡的多值依赖实际上是函数依赖 4NF 如关系模式CPB C P C B 码为 C P B 所以CPB 4NF 如果一门课Ci有m个教师 n本参考书 则关系中分量为Ci的元组共有m n个 数据冗余非常大 改造将CPB分解为CP C P CB C B 数据依赖的公理系统 定义对于满足一组函数依赖F的关系模式R 其任何一个关系r 若函数依赖X Y都成立 则称F逻辑蕴涵X Y Armstrong公理X Y Z是属性集 自反律 若Y X U 则X Y为F所蕴含 增广律 若X Y为F所蕴含 且Z U 则XZ YZ为F所蕴含 传递律 若X Y及Y Z为F所蕴含 则X Z为F所蕴含 数据依赖的公理系统 在关系模式R中 为F所逻辑蕴涵的函数依赖的全体称作F的闭包 记作F 例 F X Y Y Z 则 X Z F Armstrong公理的有效性及完备性有效性 由F出发根据Armstrong公理推导出来的函数依赖一定在F 中 完备性 F 中的每一个函数依赖都可以由F出发根据Armstrong公理从F中导出 数据依赖的公理系统 关于Armstrong公理有效性的证明设Y X U R上的任一关系r的两个元组t s若t X s X 由Y X 有t Y s Y 所以X Y成立 自反律得证 设X Y为F所蕴含 且Z U 设R上的任一关系r的两个元组t s若t XZ s XZ 则有t X s X 和t Z s Z 由X Y 有t Y s Y 所以t YZ s YZ 因此XZ YZ为F所蕴含 增广律得证 数据依赖的公理系统 设X Y及Y Z为F所蕴含 设R上的任一关系r的两个元组t s 若t X s X 且由X Y 有t Y s Y 再由Y Z 有t Z s Z 所以X Z为F所蕴含 传递律得证 由Armstrong公理导出的推理规则合并律 若X Y X Z 则X YZ 分解律 若X YZ 则X Y X Z 伪传递律 若X Y WY Z 则XW Z 数据依赖的公理系统 示例R U A B C G H I F A B A C CG H CG I B H A H CG HI AG I 数据依赖的公理系统 问题 有没有一般性的算法判定X Y是否能由F根据Armstrong公理导出 属性集的闭包设F为属性集U上的一组函数依赖 X U A X A能由F根据Armstrong公理导出 称为属性集X关于函数依赖集F的闭包 数据依赖的公理系统 引理一 X A1A2 Ak成立 X Ai成立 i 1 2 k 引理二 设F为属性集U上的一组函数依赖 X Y U X Y能由F根据Armstrong公理导出的充分必要条件是Y 数据依赖的公理系统 算法 求属性集的闭包 Input X FOutput 步骤 1 令X 0 X i 0 2 求B B A V W V W V X i A W 3 X i 1 B X i 4 判断X i 1 X i 5 若相等 或X i 1 U 则X i 1 就是 算法终止 6 若否 则i i 1 返回第二步 数据依赖的公理系统 示例R U A B C D E F AB C B D C E CE B AC B 计算 所用依赖AB CABCB DABCDC EABCDE ABCDE 数据依赖的公理系统 Armstrong公理完备性的证明证明 用反证法 假定存在函数依赖X Y被F逻辑蕴涵 但X Y不能用Armstrong公理从F中导出 1 若V W F 且V 则W 证 因为V 所以有X V 于是X W成立 所以W 数据依赖的公理系统 2 构造一张二维表r 它由下列两个元组构成 可以证明r必是R U F 的一个关系 即F中的全部函数依赖在r上成立 r U t11 100 0s11 111 1若r不是R U F 的关系 则必由于F中有函数依赖V W在r上不成立所致 由r的构成可知 V必定是的子集 而W不是的子集 可是由第 1 步可知 W 矛盾 所以r必是R U F 的一个关系 数据依赖的公理系统 3 若X Y不能由F从Armstrong公理导出 则Y不是的子集 因此必有Y的子集Y 满足Y U 则X Y在r中不成立 即X Y必不为R U F 所蕴含 数据依赖的公理系统 定义函数依赖集的等价性函数依赖集F G 若F G 则称F与G等价 F G F G G F 最小依赖集 最小覆盖 满足下列条件的函数依赖集F称为最小覆盖 记作Fm F中任一函数依赖的右部仅含有一个属性 F中不存在这样的函数依赖X A 使得F与F X A 等价 F中不存在这样的函数依赖X A 在X中有真子集Z 使得F与F X A Z A 等价 数据依赖的公理系统 算法 求解函数依赖集F的最小覆盖Fm逐个检查F中各函数依赖FDi X Y 若Y A1A2 Ak k 2 则用诸X Ai代替Y 逐个检查F中各函数依赖X A 令G F X A 若A 则从F中去掉该函数依赖 逐个检查F中各函数依赖X A 设X B1 Bm 逐个考查Bi 若A 则以 X Bi 取代X 数据依赖的公理系统 示例F A B B A A C B C C A 求Fm Fm A B C A B C 或者Fm A B B A A C C A 模式分解中的问题 实例设R是一个关系模式 R的属性集合U SNO DEPT HEAD R的函数依赖集合F SNO DEPT DEPT HEAD R的候选码为SNO 由于R中存在非主属性HEAD对码的传递函数依赖 因此存在异常 需要进行模式分解 其方式可以有 分解一 SNO DEPT HEAD 分解二 SNO DEPT SNO HEAD 分解三 SNO DEPT DEPT HEAD 模式分解中的问题 分解一所形成的三个关系无法通过自然连接恢复成原来的关系 实际上是它们三个的笛卡尔积 元组增加了 信息却丢失了 模式分解中的问题 分解二能够通过自然连接恢复到原来的关系 但仍然具有插入和删除等异常 原因在于丢失了函数依赖DEPT HEAD 模式分解中的问题 分解三既可以通过自然连接恢复到原来的关系 同时也保持了原关系的函数依赖 消除了原关系的异常 关系模式的分解算法 分解的目标无损连接分解保持函数依赖达到更高级范式 关系模式的分解算法 模式分解函数依赖集合Fi X Y X Y F XY Ui 称为F在Ui上的投影关系模式R的一个分解是指 R1 R2 Rn 其中U Ui 并且没有Ui Uj 1 i j n Fi是F在Ui上的投影 设 R1 R2 Rn 是R U F 的一个分解 r是R U F 的一个关系 定义m r Ri r 即m r 是r在 中各关系模式投影上的连接 这里 Ri r t Ui t r 关系模式的分解算法 一般定义关系模式R U Ui R1 R2 Rn 是R的一个分解 r是R的一个关系 定义m r Ri r 若对于R的任一个关系r 都有r m r 则称 是R的一个无损连接分解 关系模式的分解算法 算法 判别一个分解的无损连接性 U A1 A2 An F FD1 FD2 FD 不妨设F是一个最小依赖集 记FDi为Xi Aj R1 R2 Rk 建立一个n列k行的矩阵 每一列对应一个属性 每一行对应于分解中的一个关系模式 若属性Aj属于Ui 则在j列i行交叉处填上aj 否则填上bij Cij 若Aj Ui Cij aj 否则Cij bij 关系模式的分解算法 对每一个FDi做下列操作 找到Xi所对应的列中具有相同符号的那些行 考察这些行中j列的元素 若其中有aj 则全部改为aj 否则全部改为bmj m是这些行的行号最小值 注意 如果某个bij被修改 则该列中所有的bij都必须做同样的修改如果在某次更改之后 有一行成为a1 a2 an 则算法终止 为无损分解 否则为有损分解 关系模式的分解算法 3 比较扫描前后 表有无变化 如有变化 则返回第二步 否则算法终止 关系模式的分解算法 示例 U A B C D E F AB C C D D E A B C C D D E AB C C D D E 关系模式的分解算法 U A B C D E F A C B C C D DE C CE A R1 A D R2 A B R3 B E R4 C D E R5 A E 关系模式的分解算法 关系模式的分解算法 A C 关系模式的分解算法 B C 关系模式的分解算法 C D 关系模式的分解算法 DE C 关系模式的分解算法 CE A 关系模式的分解算法 定理若U1 U2 U1 或U2 则r U1 r U2 r 关系模式的分解算法 保持函数依赖的分解定义若F Fi 则称R的分解 R1 Rn 保持函数依赖 如表 职工 级别 工资 的分解 分解一 职工 工资 工资 级别 丢失函数依赖 职工 级别分解二 职工 级别 工资 级别 保持函数依赖 关系模式的分解算法 算法 达到3NF且保持函数依赖的分解 对R中的函数依赖集F进行 极小化处理 处理后得到的依赖集仍记为F 找出不在F中出现的属性 将它们构成一个关系模式 并从U中去掉它们 剩余属性仍记为U 若有X A F 且XA U 则 R 算法终止 关系模式的分解算法 否则 对F按具有相同左部的原则进行分组 设为k组 每一组函数依赖Fi 所涉及的全部属性为Ui 若Ui Uj i j 就去掉Ui 由于经过了步骤2 故U Ui 于是 R1 Rk 是R的一个保持函数依赖的分解 并且每个Ri 3NF 关系模式的分解算法 示例U SNO DEPT HEAD CNO G F SNO DEPT SNO HEAD DEPT HEAD SNO CNO G FC SNO DEPT DEPT HEAD SNO CNO G 分组 SNO DEPT SNO DEPT DEPT HEAD DEPT HEAD SNO CNO G SNO CNO G 关系模式的分解算法 示例 R ABC A C B C 按保持无损连接分解码为AB 分解为 AC A C AB 丢失了函数依赖B C 按保持函数依赖分解进行分组 AC A C BC B C 分解是有损的 关系模式的分解算法 算法 达到3NF且同时保持无损连接与函数依赖的分解 设X为R的码 设 R1 Rk 是R的一个保持函数依赖的3NF分解 令 R 若有某个Ui X Ui 则将R 从 去掉 R 即为所求的解 关系模式的分解算法 示例 求R ABC A C B C 的保持无损连接和函数依赖的3NF分解 按保持函数依赖分解进行分组 AC A C BC B C 键为AB AB 最后的分解为 AC A C BC B C AB 关系模式的分解算法 算