设计与应用开发篇.ppt_第1页
设计与应用开发篇.ppt_第2页
设计与应用开发篇.ppt_第3页
设计与应用开发篇.ppt_第4页
设计与应用开发篇.ppt_第5页
已阅读5页,还剩146页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2020年3月31日星期二 信息工程学院 数据库系统概论AnIntroductiontoDatabaseSystem第二篇设计与应用开发篇 2020年3月31日星期二 第二篇设计与应用开发篇 第六章关系数据理论第七章数据库设计第八章数据库编程 2020年3月31日星期二 第六章关系数据理论 6 1问题的提出6 2规范化6 3数据依赖的公理系统 6 4模式的分解6 5小结 2020年3月31日星期二 6 1问题的提出 关系数据库逻辑设计针对具体问题 如何构造一个适合于它的数据模式数据库逻辑设计的工具 关系数据库的规范化理论 2020年3月31日星期二 问题的提出 一 概念回顾二 关系模式的形式化定义三 什么是数据依赖四 关系模式的简化定义五 数据依赖对关系模式影响 2020年3月31日星期二 一 概念回顾 关系 描述实体 属性 实体间的联系 从形式上看 它是一张二维表 是所涉及属性的笛卡尔积的一个子集 关系模式 用来定义关系 关系数据库 基于关系模型的数据库 利用关系来描述现实世界 从形式上看 它由一组关系组成 关系数据库的模式 定义这组关系的关系模式的全体 2020年3月31日星期二 二 关系模式的形式化定义 关系模式由五部分组成 即它是一个五元组 R U D DOM F R 关系名U 组成该关系的属性名集合D 属性组U中属性所来自的域DOM 属性向域的映象集合F 属性间数据的依赖关系集合 2020年3月31日星期二 三 什么是数据依赖 完整性约束的表现形式限定属性取值范围 例如学生成绩必须在0 100之间定义属性值间的相互关连 主要体现于值的相等与否 这就是数据依赖 它是数据库模式设计的关键 2020年3月31日星期二 什么是数据依赖 续 2 数据依赖一个关系内部属性与属性之间的约束关系现实世界属性间相互联系的抽象数据内在的性质语义的体现 2020年3月31日星期二 什么是数据依赖 续 3 数据依赖的类型函数依赖 FunctionalDependency 简记为FD 多值依赖 MultivaluedDependency 简记为MVD 其他 2020年3月31日星期二 四 关系模式的简化表示 关系模式R U D DOM F 简化为一个三元组 R U F 当且仅当U上的一个关系r满足F时 r称为关系模式R U F 的一个关系 2020年3月31日星期二 五 数据依赖对关系模式的影响 我们的任务是研究模式设计 研究设计一个 好 的 没有 毛病 的 关系模式的办法 这里通过一个例子来说明一个 不好 的模式会有些什么毛病 分析他们产生的原因 从中找出设计一个 好 的关系模式的办法 例1 建立一个描述学校教务的数据库 学生的学号 Sno 所在系 Sdept 系主任姓名 Mname 课程名 Cname 成绩 Grade 单一的关系模式 StudentU Sno Sdept Mname Cname Grade 2020年3月31日星期二 数据依赖对关系模式的影响 续 属性组U上的一组函数依赖F F Sno Sdept Sdept Mname Sno Cname Grade 2020年3月31日星期二 关系模式Student中存在的问题 1 数据冗余太大2 更新异常 UpdateAnomalies 3 插入异常 InsertionAnomalies 4 删除异常 DeletionAnomalies 2020年3月31日星期二 数据依赖对关系模式的影响 续 结论 Student关系模式不是一个好的模式 好 的模式 不会发生插入异常 删除异常 更新异常 数据冗余应尽可能少原因 由存在于模式中的某些数据依赖引起的解决方法 通过分解关系模式来消除其中不合适的数据依赖 2020年3月31日星期二 分解关系模式 把这个单一模式分成3个关系模式 S Sno Sdept Sno Sdept SC Sno Cno Grade Sno Cno Grade DEPT Sdept Mname Sdept Mname 2020年3月31日星期二 第六章关系数据理论 6 1问题的提出6 2规范化6 3数据依赖的公理系统 6 4模式的分解6 5小结 2020年3月31日星期二 6 2规范化 规范化理论正是用来改造关系模式 通过分解关系模式来消除其中不合适的数据依赖 以解决插入异常 删除异常 更新异常和数据冗余问题 2020年3月31日星期二 6 2 1函数依赖 函数依赖平凡函数依赖与非平凡函数依赖完全函数依赖与部分函数依赖传递函数依赖 2020年3月31日星期二 一 函数依赖 定义6 1设R U 是一个属性集U上的关系模式 X和Y是U的子集 若对于R U 的任意一个可能的关系r r中不可能存在两个元组在X上的属性值相等 而在Y上的属性值不等 则称 X函数确定Y 或 Y函数依赖于X 记作X Y 2020年3月31日星期二 说明 1 所有关系实例均要满足2 语义范畴的概念3 数据库设计者可以对现实世界作强制的规定 2020年3月31日星期二 二 平凡函数依赖与非平凡函数依赖 在关系模式R U 中 对于U的子集X和Y 如果X Y 但Y X 则称X Y是非平凡的函数依赖若X Y 但Y X 则称X Y是平凡的函数依赖例 在关系SC Sno Cno Grade 中 非平凡函数依赖 Sno Cno Grade平凡函数依赖 Sno Cno Sno Sno Cno Cno 2020年3月31日星期二 平凡函数依赖与非平凡函数依赖 续 若X Y 则X称为这个函数依赖的决定属性组 也称为决定因素 Determinant 若X Y Y X 则记作X Y 若Y不函数依赖于X 则记作X Y 例 Student Sno Sname Ssex Sage Sdept 假设不允许重名 则有 Sno Ssex Sno Sage Sno Sdept Sno Sname Sname Ssex Sname Sage Sname Sdept但Ssex Sage 2020年3月31日星期二 三 完全函数依赖与部分函数依赖 定义6 2在R U 中 如果X Y 并且对于X的任何一个真子集X 都有X Y 则称Y对X完全函数依赖 记作XFY 若X Y 但Y不完全函数依赖于X 则称Y对X部分函数依赖 记作XPY 2020年3月31日星期二 完全函数依赖与部分函数依赖 续 例1 中 Sno Cno Grade是完全函数依赖 Sno Cno Sdept是部分函数依赖因为Sno Sdept成立 且Sno是 Sno Cno 的真子集 F P 2020年3月31日星期二 四 传递函数依赖 定义6 3在R U 中 如果X Y Y X Y XY Z 则称Z对X传递函数依赖 记为 X Z注 如果Y X 即X Y 则Z直接依赖于X 例 在关系Std Sno Sdept Mname 中 有 Sno Sdept Sdept MnameMname传递函数依赖于Sno 传递 2020年3月31日星期二 6 2 2码 定义6 4设K为R中的属性或属性组合 若KU 则K称为R的侯选码 CandidateKey 若候选码多于一个 则选定其中的一个做为主码 PrimaryKey F 2020年3月31日星期二 码 续 主属性与非主属性包含在任何一个候选码中的属性 称为主属性 Primeattribute 不包含在任何码中的属性称为非主属性 Nonprimeattribute 或非码属性 Non keyattribute 全码整个属性组是码 称为全码 All key 2020年3月31日星期二 码 续 例2 关系模式S Sno Sdept Sage 单个属性Sno是码 SC Sno Cno Grade 中 Sno Cno 是码 例3 关系模式R P W A P 演奏者W 作品A 听众一个演奏者可以演奏多个作品某一作品可被多个演奏者演奏听众可以欣赏不同演奏者的不同作品码为 P W A 即All Key 2020年3月31日星期二 外部码 定义6 5关系模式R中属性或属性组X并非R的码 但X是另一个关系模式的码 则称X是R的外部码 Foreignkey 也称外码如在SC Sno Cno Grade 中 Sno不是码 但Sno是关系模式S Sno Sdept Sage 的码 则Sno是关系模式SC的外部码主码与外部码一起提供了表示关系间联系的手段 2020年3月31日星期二 6 2 3范式 范式是符合某一种级别的关系模式的集合关系数据库中的关系必须满足一定的要求 满足不同程度要求的为不同范式范式的种类 第一范式 1NF 第二范式 2NF 第三范式 3NF BC范式 BCNF 第四范式 4NF 第五范式 5NF 2020年3月31日星期二 6 2 3范式 各种范式之间存在联系 某一关系模式R为第n范式 可简记为R nNF 一个低一级范式的关系模式 通过模式分解可以转换为若干个高一级范式的关系模式的集合 这种过程就叫规范化 2020年3月31日星期二 6 2 42NF 1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项 则R 1NF第一范式是对关系模式的最起码的要求 不满足第一范式的数据库模式不能称为关系数据库但是满足第一范式的关系模式并不一定是一个好的关系模式 2020年3月31日星期二 2NF 续 例4 关系模式S L C Sno Sdept Sloc Cno Grade Sloc为学生住处 假设每个系的学生住在同一个地方函数依赖包括 Sno Cno FGradeSno Sdept Sno Cno PSdeptSno Sloc Sno Cno PSlocSdept Sloc 2020年3月31日星期二 2NF 续 S L C的码为 Sno Cno S L C满足第一范式 非主属性Sdept和Sloc部分函数依赖于码 Sno Cno Sno Cno Grade Sdept Sloc S L C 2020年3月31日星期二 S L C不是一个好的关系模式 续 1 插入异常 2 删除异常 3 数据冗余度大 4 修改复杂 2020年3月31日星期二 S L C不是一个好的关系模式 续 原因Sdept Sloc部分函数依赖于码 解决方法S L C分解为两个关系模式 以消除这些部分函数依赖 SC Sno Cno Grade S L Sno Sdept Sloc 2020年3月31日星期二 2NF 续 函数依赖图 关系模式SC的码为 Sno Cno 关系模式S L的码为Sno这样非主属性对码都是完全函数依赖 2020年3月31日星期二 2NF 续 2NF的定义定义6 6若R 1NF 且每一个非主属性完全函数依赖于码 则R 2NF 例 S L C Sno Sdept Sloc Cno Grade 1NFS L C Sno Sdept Sloc Cno Grade 2NFSC Sno Cno Grade 2NFS L Sno Sdept Sloc 2NF 2020年3月31日星期二 学生思考 关系模式Activities ID Activity Fee 是否属于第二范式 2020年3月31日星期二 2NF 续 采用投影分解法将一个1NF的关系分解为多个2NF的关系 可以在一定程度上减轻原1NF关系中存在的插入异常 删除异常 数据冗余度大 修改复杂等问题 将一个1NF关系分解为多个2NF的关系 并不能完全消除关系模式中的各种异常情况和数据冗余 2020年3月31日星期二 6 2 53NF 3NF的定义定义6 7关系模式R中若不存在这样的码X 属性组Y及非主属性Z Z Y 使得X Y Y Z成立 Y X 则称R 3NF 若R 3NF 则每一个非主属性既不部分依赖于码也不传递依赖于码 2020年3月31日星期二 3NF 续 例 2NF关系模式S L Sno Sdept Sloc 中函数依赖 Sno SdeptSdept SnoSdept Sloc可得 Sno Sloc 即S L中存在非主属性对码的传递函数依赖 S L 3NF 传递 2020年3月31日星期二 3NF 续 函数依赖图 2020年3月31日星期二 3NF 续 解决方法采用投影分解法 把S L分解为两个关系模式 以消除传递函数依赖 S D Sno Sdept D L Sdept Sloc S D的码为Sno D L的码为Sdept 分解后的关系模式S D与D L中不再存在传递依赖 2020年3月31日星期二 3NF 续 S D的码为Sno D L的码为Sdept S L Sno Sdept Sloc 2NFS L Sno Sdept Sloc 3NFS D Sno Sdept 3NFD L Sdept Sloc 3NF 2020年3月31日星期二 3NF 续 采用投影分解法将一个2NF的关系分解为多个3NF的关系 可以在一定程度上解决原2NF关系中存在的插入异常 删除异常 数据冗余度大 修改复杂等问题 将一个2NF关系分解为多个3NF的关系后 仍然不能完全消除关系模式中的各种异常情况和数据冗余 2020年3月31日星期二 学生思考 关系模式Tenancy ID House Fee 是否属于第三范式 2020年3月31日星期二 6 2 6BC范式 BCNF 定义6 8关系模式R 1NF 若X Y且Y X时X必含有码 则R BCNF 等价于 每一个决定属性因素都包含码 2020年3月31日星期二 BCNF 续 若R BCNF所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码 也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性R BCNFR 3NF 2020年3月31日星期二 BCNF 续 例5 关系模式C Cno Cname Pcno C 3NFC BCNF 例6 关系模式S Sno Sname Sdept Sage 假定S有两个码Sno SnameS 3NF S BCNF 2020年3月31日星期二 BCNF 续 例7 关系模式SJP S J P 函数依赖 S J P J P S S J 与 J P 都可以作为候选码 属性相交SJP 3NF SJP BCNF 2020年3月31日星期二 BCNF 续 例8 在关系模式STJ S T J 中 S表示学生 T表示教师 J表示课程 函数依赖 S J T S T J T J S J 和 S T 都是候选码 2020年3月31日星期二 BCNF 续 J S J T S T STJ中的函数依赖 2020年3月31日星期二 BCNF 续 STJ 3NF没有任何非主属性对码传递依赖或部分依赖STJ BCNFT是决定因素 T不包含码 2020年3月31日星期二 BCNF 续 解决方法 将STJ分解为二个关系模式 ST S T BCNF TJ T J BCNF没有任何属性对码的部分函数依赖和传递函数依赖 2020年3月31日星期二 3NF与BCNF的关系 R BCNFR 3NF如果R 3NF 且R只有一个候选码R BCNFR 3NF 2020年3月31日星期二 3NF与BCNF的关系 3NF的 不彻底 性表现在可能存在主属性对码的部分依赖和传递依赖 非BCNF的关系模式也可以通过分解生成为BCNF 3NF与BCNF的关系 如果关系模式R BCNF 必定有R 3NF如果R 3NF 且R只有一个候选码 则R必属于BCNF 一个模式中的关系模式如果都属于BCNF 那么在函数依赖范畴内 它已实现了彻底的分离 已消除了插入和删除的异常 2020年3月31日星期二 6 2 7多值依赖 以上我们完全是在函数依赖的范畴内讨论问题 在关系数据库中 数据依赖除了包括函数依赖之外还有多值依赖 联接依赖的问题 从而提出了第四范式 第五范式等更高一级的规范化要求 例9 学校中某一门课程由多个教师讲授 他们使用相同的一套参考书 每个教员可以讲授多门课程 每种参考书可以供多门课程使用 2020年3月31日星期二 多值依赖 续 非规范化关系 2020年3月31日星期二 多值依赖 续 用二维表表示Teaching 2020年3月31日星期二 多值依赖 续 Teaching BCNFTeaching具有唯一候选码 C T B 即全码 2020年3月31日星期二 多值依赖 续 Teaching模式中存在的问题 1 数据冗余度大 2 插入操作复杂 3 删除操作复杂 4 修改操作复杂 存在多值依赖 2020年3月31日星期二 多值依赖 续 定义6 9设R U 是一个属性集U上的一个关系模式 X Y和Z是U的子集 并且Z U X Y 关系模式R U 中多值依赖X Y成立 当且仅当对R U 的任一关系r 给定的一对 x z 值 有一组Y的值 这组值仅仅决定于x值而与z值无关例Teaching C T B 2020年3月31日星期二 多值依赖 续 多值依赖的另一个等价的形式化的定义 在R U 的任一关系r中 如果存在元组t s使t X s X 那么就必然存在元组w v r w v可以与s t相同 使得w X v X t X 而w Y t Y w Z s Z v Y s Y v Z t Z 即交换s t元组的Y值所得的两个新元组必在r中 则Y多值依赖于X 记为X Y 这里 X Y是U的子集 Z U X Y txy1z2sxy2z1wxy1z1vxy2z2 2020年3月31日星期二 多值依赖 续 平凡多值依赖和非平凡的多值依赖若X Y 而Z 则称X Y为平凡的多值依赖否则称X Y为非平凡的多值依赖 2020年3月31日星期二 多值依赖 续 例10 关系模式WSC W S C W表示仓库 S表示保管员 C表示商品假设每个仓库有若干个保管员 有若干种商品每个保管员保管所在的仓库的所有商品每种商品被所有保管员保管 2020年3月31日星期二 多值依赖 续 2020年3月31日星期二 多值依赖 续 W S且W C 用下图表示这种对应 2020年3月31日星期二 多值依赖的性质 1 多值依赖具有对称性若X Y 则X Z 其中Z U X Y 2 多值依赖具有传递性若X Y Y Z 则X Z Y 3 函数依赖是多值依赖的特殊情况 若X Y 则X Y 4 若X Y X Z 则X Y Z 5 若X Y X Z 则X Y Z 6 若X Y X Z 则X Y Z X Z Y 2020年3月31日星期二 多值依赖与函数依赖的区别 多值依赖的有效性与属性集的范围有关若X Y在U上成立 则在W XY W U 上一定成立 反之则不然 即X Y在W W U 上成立 在U上并不一定成立多值依赖的定义中不仅涉及属性组X和Y 而且涉及U中其余属性Z 一般地 在R U 上若有X Y在W W U 上成立 则称X Y为R U 的嵌入型多值依赖只要在R U 的任何一个关系r中 元组在X和Y上的值满足定义6 l 函数依赖 则函数依赖X Y在任何属性集W XY W U 上成立 2 若函数依赖X Y在R U 上成立 则对于任何Y Y均有X Y 成立多值依赖X Y若在R U 上成立 不能断言对于任何Y Y有X Y 成立 2020年3月31日星期二 6 2 84NF 定义6 10关系模式R 1NF 如果对于R的每个非平凡多值依赖X Y Y X X都含有码 则R 4NF 如果R 4NF 则R BCNF不允许有非平凡且非函数依赖的多值依赖允许的非平凡多值依赖是函数依赖 2020年3月31日星期二 4NF 续 例 Teaching C T B 4NF存在非平凡的多值依赖C T 且C不是码用投影分解法把Teaching分解为如下两个关系模式 CT C T 4NFCB C B 4NFC T C B是平凡多值依赖 2020年3月31日星期二 6 2 9规范化小结 关系数据库的规范化理论是数据库逻辑设计的工具目的 尽量消除插入 删除一场 修改复杂 数据冗余基本思想 逐步消除数据依赖中不合适的部分实质 概念的单一化 2020年3月31日星期二 规范化小结 续 关系模式规范化的基本步骤1NF 消除非主属性对码的部分函数依赖消除决定属性2NF集非码的非平 消除非主属性对码的传递函数依赖凡函数依赖3NF 消除主属性对码的部分和传递函数依赖BCNF 消除非平凡且非函数依赖的多值依赖4NF 2020年3月31日星期二 规范化小结 续 不能说规范化程度越高的关系模式就越好在设计数据库模式结构时 必须对现实世界的实际情况和用户应用需求作进一步分析 确定一个合适的 能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止 2020年3月31日星期二 第六章关系数据理论 6 1问题的提出6 2规范化6 3数据依赖的公理系统 6 4模式的分解6 5小结 2020年3月31日星期二 6 3数据依赖的公理系统 数据依赖的公理系统是模式分解算法的理论基础 而且为了求得给定关系模式的码 为了从一组函数依赖求得蕴含的函数依赖 例如已知函数依赖集F 要问X Y是否为F所蕴含 就需要一套推理规则 这组推理规则是l974年首先由Armstrong提出来的 下面首先讨论Armstrong公理系统 函数依赖的一个有效而完备的公理系统 2020年3月31日星期二 6 3数据依赖的公理系统 Armstrong公理系统一套推理规则 是模式分解算法的理论基础用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖 2020年3月31日星期二 6 3数据依赖的公理系统 逻辑蕴含定义6 11对于满足一组函数依赖F的关系模式R 其任何一个关系r 若函数依赖X Y都成立 即r中任意两元组t s 若t X s X 则t Y s Y 则称F逻辑蕴含X Y 2020年3月31日星期二 1 Armstrong公理系统 关系模式R来说有以下的推理规则 A1 自反律 Reflexivity 若Y X U 则X Y为F所蕴含 A2 增广律 Augmentation 若X Y为F所蕴含 且Z U 则XZ YZ为F所蕴含 A3 传递律 Transitivity 若X Y及Y Z为F所蕴含 则X Z为F所蕴含 2020年3月31日星期二 6 3数据依赖的公理系统 F 定义 12在关系模式R U F 中为F所逻辑蕴含的函数依赖的全体叫做F的闭包 记作F FA 在关系模式R U F 中 由F出发 根据Armstrong公理导出的所有函数依赖组成的集合记作FA 2020年3月31日星期二 Armstrong公理系统 Armstrong公理系统是有效的 完备的有效性 由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F 中 完备性 F 中的每一个函数依赖 必定可以由F出发根据Armstrong公理推导出来 2020年3月31日星期二 定理6 1Armstrong推理规则是正确的 Armstrong定理的有效性 正确性 即由F出发 根据Armstrong公理推导出来的每一个函数依赖必定为F所逻辑蕴含 FA F 证明Armstrong定理的有效性 正确性 Armstrong公理的其它规则都可以由上述三条规则推导出来 因此 对于FA中的每一个函数依赖也都可以由这三条规则中的某一条或几条推导出来 要证明FA中的每一个函数依赖都是被F所逻辑蕴含 只要证明上述三条规则推导出来的函数依赖是被F所逻辑蕴含的 即证明三条推理规则是正确的 2020年3月31日星期二 定理6 1Armstrong推理规则是正确的 l 自反律 若Y X U 则X Y为F所蕴含证 设Y X U对R的任一关系r中的任意两个元组t s 若t X s X 由于Y X 有t y s y 根据F逻辑蕴含X Y的定义 所以X Y成立 自反律得证 其实A1的正确性是显然的 不可能存在这样的关系 它的两个元组在X的全部属性上的值相等 而在X的部分属性上的值不同 2020年3月31日星期二 定理6 lArmstrong推理规则是正确的 续 2 增广律 若X Y为F所蕴含 且Z U 则XZ YZ为F所蕴含 证 设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所蕴含 增广律得证 2020年3月31日星期二 定理6 lArmstrong推理规则是正确的 续 3 传递律 若X Y及Y Z为F所蕴含 则X Z为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所蕴含 传递律得证 2020年3月31日星期二 定理6 lArmstrong推理规则是正确的 续 由上述证明得到 根据Armstrong公理推导出来的每一个函数依赖必定为F所逻辑蕴含 即FA F Armstrong定理是有效的 正确的 2020年3月31日星期二 2 导出规则 1 根据A1 A2 A3这三条推理规则可以得到下面三条推理规则 合并规则 由X Y X Z 有X YZ 伪传递规则 由X Y WY Z 有XW Z 分解规则 由X Y及Z Y 有X Z 由规则2得 X Y XX XYX Z XY YZ由规则3得 XX YZ 即X YZ 由规则2得 X Y XW WY由规则3得 XW Z 由规则1得 Z Y Y Z由规则3得 X Z 2020年3月31日星期二 导出规则 2 根据合并规则和分解规则 可得引理6 1引理6 lX A1A2 Ak成立的充分必要条件是X Ai成立 i l 2 k 2020年3月31日星期二 定理 2Armstrong公理是有效的 完备的 Armstrong公理的完备性 即F所逻辑蕴含的每一个函数依赖 必定可以由F出发根据Armstrong公理推导出来 即F FA 要证明Armstrong公理的完备性 就首先要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合 当然 如果能求出这个集合 问题就解决了 但不幸的是 这是一个NP完全问题 比如从F X A1 X An 出发 我们至少可以推导出2n个不同的函数依赖 2020年3月31日星期二 F的闭包 F X Y Y Z FA计算是NP完全问题 FA X Y Z XY XZ YZ XYZ X X Y Y Z Z XY X XZ X YZ Y XYZ X X Y Y Z XY Y XZ Y YZ Z XYZ Y X Z Y YZ XY Z XZ Z YZ YZ XYZ Z X XY XY XY XZ XY XYZ XY X XZ XY YZ XZ XZ XYZ YZX YZ XY XZ XZ XY XYZ XZ X XYZ XY XYZ XZ XYZ XYZ XYZ 共43个函数依赖 2020年3月31日星期二 3 函数依赖闭包 定义6 13设F为属性集U上的一组函数依赖 X U XF A X A能由F根据Armstrong公理导出 XF 称为属性集X关于函数依赖集F的闭包 2020年3月31日星期二 关于闭包的引理 引理6 2设F为属性集U上的一组函数依赖 X Y U X Y能由F根据Armstrong公理导出的充分必要条件是Y XF 用途将判定X Y是否能由F根据Armstrong公理导出的问题 转化为求出XF 判定Y是否为XF 的子集的问题 2020年3月31日星期二 求闭包的算法 算法6 1求属性集X X U 关于U上的函数依赖集F的闭包XF 输入 X F输出 XF 步骤 1 令X 0 X i 0 2 求B 这里B A V W V W F V X i A W 3 X i 1 B X i 4 判断X i 1 X i 吗 5 若相等或X i U 则X i 就是XF 算法终止 6 若否 则i i l 返回第 2 步 2020年3月31日星期二 算法6 1 对于算法6 1 令ai X i ai 形成一个步长大于1的严格递增的序列 序列的上界是 U 因此该算法最多 U X 次循环就会终止 2020年3月31日星期二 函数依赖闭包 例1 已知关系模式R 其中U A B C D E F AB C B D C E EC B AC B 求 AB F 解设X 0 AB 1 X 1 AB CD ABCD 2 X 0 X 1 X 2 X 1 BE ABCDE 3 X 2 U 算法终止 AB F ABCDE 2020年3月31日星期二 例 U A B C D F A B BC D 求AF CF AC F AF CF AC F AF AB CF C AC F ABCD 2020年3月31日星期二 候选关键字的求解 给定R U F X U 若满足 1 XF U X能决定所有属性集 2 A X X A F U 没有冗余的属性 则称X是R U F 的候选关键字给定R U F 如何计算R U F 上的候选关键字呢 例 U ABCDES F AB C C ED D A 计算R U F 上的一个候选关键字 求各属性组合关于函数依赖F的闭包 AF A BF B CF CEDA U DF AD EF E ABF ABCDE U ACF ACED U ADF AD AEF AE BCF ABCDE U BDF ABCDE U BEF BE CDF CDEA U CEF ACDE U DEF DEA U ABCF ABDF ABEF 所以 R U F 上的候选关键字为 AB或BC BD 2020年3月31日星期二 问题的提出 在判别关系模式的级别时在对关系模式进行规范化时求解全部候选码是一个N P完全问题 对于一个具有n个属性的关系模式 求解它的全部候选码必须计算2n 1个属性闭包 候选关键字的求解 2020年3月31日星期二 小结 对于给定的关系模式R U F 可以将其属性分为四类 1 仅在F函数依赖左部出现的属性L类2 仅在F函数依赖右部出现的属性R类3 在F函数依赖左右两边均未出现的属性N类4 在F函数依赖左右两边均出现的属性LR类 2020年3月31日星期二 有用的定理和推论 定理1 对于给定的R U F 如果K是L类属性 则K必为R的任一候选码的成员 推论1 对于给定的R U F K是L类属性 且KF U 则K必为R的唯一候选码 定理2 对于给定的R U F 如果K是R类属性 则K不在R的任何候选码中 定理3 对于给定的R U F 如果K是N类属性 则K必包含在R的任一候选码中 推论2 对于给定的R U F 如果K是N类和L类属性组成的属性集 且KF U 则K必为R的唯一候选码 2020年3月31日星期二 例 给定R U F U ABCDEKH F AB CH C D AD BK 求R U F 的所有候选码 解 L类属性 AR类属性 KHN类属性 ELR类属性 BCDA仅在左边出现 E在两边都不出现 故AE是主属性 KH仅在右边出现 故KH是非主属性 AE F AE U AEB F ABECHDK U AEC F AECDBKH U AED F AEDBKCH U所以R U F 的候选码是AEB AEC AED 候选关键字的求解 2020年3月31日星期二 证明Armstrong公理的完备性 证明Armstrong公理的完备性 证明完备性就是证明它的逆否命题 即若函数依赖X Y不能由F从Armstrong公理导出 那么它必然不为F所蕴含 X Y FA X Y F 问题转化为若X Y FA 则X Y F 要使X Y F 即构造一个满足F的关系r 使得r不满足X Y 即X Y不被F所逻辑蕴含 也就是X Y在模式R U F 的某个关系r上不成立 已知X Y FA 证明分三步 1 构造关系r2 证明F中的每一个函数依赖在r中成立 3 证明X Y在关系r中不成立 即X Y F 2020年3月31日星期二 证明Armstrong公理的完备性 1 构造关系r 2020年3月31日星期二 证明Armstrong公理的完备性 2 证明 V W F在r上都是成立的 在r上分情况讨论 a 若V XF 则t V s V 根据函数依赖的定义 P172定义6 1 有 V W 在r中成立 b 若V XF 即V XF 根据引理6 2 因为X XF X V 又因为V W根据Armstrong公理系统的传递律可得所以X W W XF 所以从r中可以看到在XF 属性集上t V s V 有t W s W 即V W在r中成立 根据上面两种情况可知F中的每一个函数依赖在r中均成立 2020年3月31日星期二 证明Armstrong公理的完备性 3 证明X Y在关系r中不成立在R U F 中 由于X Y FA即X Y不能由F出发按照Armstrong公理推导出来 则根据XF 的定义 Y XF 因此Y U XF 然而X XF 所以在r中有t X s X t Y s Y 即X Y在r中不成立 再根据F 的定义 有X Y F X Y FA X Y F 得证 即F FA成立 2020年3月31日星期二 证明Armstrong公理的完备性 因此F FA得证 即Armstrong公理系统是有效的 完备的 从Armstrong公理的有效性及完备性 说明了 导出 与 蕴含 是两个完全等价的概念 于是F 也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合 以后 我们将不加区别地使用这两个概念 2020年3月31日星期二 从蕴含 或导出 的概念出发 可引出以下两个概念 两个函数依赖集等价最小函数依赖集 2020年3月31日星期二 5 函数依赖集等价 定义6 14如果G F 就说函数依赖集F覆盖G F是G的覆盖 或G是F的覆盖 或F与G等价 引理6 3F G 的充分必要条件是F G 和G F 证 必要性显然 只证充分性 1 若F G 则XF XG 2 任取X Y F 则有Y XF XG 所以X Y G G 即F G 3 同理可证G F 所以F G 2020年3月31日星期二 函数依赖集等价 要判定F G 只须逐一对F中的函数依赖X Y 考察Y是否属于XG 就行了 因此引理6 3给出了判断两个函数依赖集等价的可行算法 例1 F AB C C DE A B D E A D G A C C D A B D E 判断F与G等价1 判定G F 因为AF ABCDE 所以A C F A B F 因为CF CDE 所以C D F 因为DF DE 所以D E F G F 成立2 判定F G 因为 AB G ABCDE 所以AB C G 因为CG CDE 所以C DE G 因为DG DE 所以D E G 因为AG ACBDE 所以A D G A B G F G 成立 F G 即F与G等价 2020年3月31日星期二 6 最小依赖集 定义6 15如果函数依赖集F满足下列条件 则称F为一个极小函数依赖集 亦称为最小依赖集或最小覆盖 1 F中任一函数依赖的右部仅含有一个属性 2 F中不存在这样的函数依赖X A 使得F与F X A 等价 3 F中不存在这样的函数依赖X A X有真子集Z使得F X A Z A 与F等价 2020年3月31日星期二 最小依赖集 例2 关系模式S 其中 U Sno Sdept Mname Cno Grade F Sno Sdept Sdept Mname Sno Cno Grade 设F Sno Sdept Sno Mname Sdept Mname Sno Cno Grade Sno Sdept Sdept F是最小覆盖 而F 不是 因为 F Sno Mname 与F 等价F Sno Sdept Sdept 也与F 等价 2020年3月31日星期二 定理6 3每一个函数依赖集F均等价于一个极小函数依赖集Fm 此Fm称为F的最小依赖集证 构造性证明 依据定义分三步对F进行 极小化处理 找出F的一个最小依赖集 1 逐一检查F中各函数依赖FDi X Y 若Y A1A2 Ak k 2 则用 X Aj j 1 2 k 来取代X Y 引理6 1保证了F变换前后的等价性 7 极小化过程 2020年3月31日星期二 2 逐一检查F中各函数依赖FDi X A 令G F X A 若A XG 则从F中去掉此函数依赖 由于F与G F X A 等价的充要条件是A XG 因此F变换前后是等价的 注意 在检查一个函数依赖X A是否冗余时 求X的闭包一定要在F中去掉X A以及已经判定是冗余的函数依赖后进行 否则可能导致错误的结果 极小化过程 2020年3月31日星期二 3 逐一取出F中各函数依赖FDi X A 设X B1B2 Bm 逐一考查Bi i l 2 m 若A X Bi F 则以X Bi取代X 由于F与F X A Z A 等价的充要条件是A ZF 其中Z X Bi因此F变换前后是等价的 最后剩下的F就一定是极小依赖集 因为对F的每一次 改造 都保证了改造前后的两个函数依赖集等价 因此剩下的F与原来的F等价 证毕定理6 3的证明过程也是求F极小依赖集的过程 极小化过程 2020年3月31日星期二 例3 F A B B A B C A C C A 求F的最小依赖集 1 逐一检查F中各函数依赖FDi X Y 若Y A1A2 Ak k 2 则用 X Aj j 1 2 k 来取代X Y 这一步已不用做了 F中所有函数依赖右边都是单个属性的 极小化过程 2020年3月31日星期二 F A B B A B C A C C A 2 逐一检查F中各函数依赖FDi X A 令G F X A 若A XG 则从F中去掉此函数依赖 检查A B 令G F A B B AG AC 所以不能将A B从F中去掉再检查B A 令G F B A A BG ABC 所以将B A从F中去掉 则F A B B C A C C A 再检查B C 令G F B C C BG B 所以不能将B C从F 中去掉再检查A C 令G F A C C AG ABC 所以将A C从F 中去掉 则F A B B C C A 再检查C A 令G F C A A CG C 所以不能将C A从F 中去掉所以F A B B C C A 极小化过程 2020年3月31日星期二 F A B B C C A 3 逐一取出F中各函数依赖FDi X A 设X B1B2 Bm 逐一考查Bi i l 2 m 若A X Bi F 则以X Bi取代X 这一步工作也不用做 因为F A B B C C A 中的函数依赖的左边都是单个属性的 所以得到Fm1 A B B C C A F的最小依赖集Fm不一定是唯一的 它与对各函数依赖FDi的处置顺序 第二步 及X A中X各属性的处置顺序 第三步 都有关 极小化过程 2020年3月31日星期二 例3 F A B B C B A A C C A 求F的最小依赖集 1 逐一检查F中各函数依赖FDi X Y 若Y A1A2 Ak k 2 则用 X Aj j 1 2 k 来取代X Y 这一步已不用做了 F中所有函数依赖右边都是单个属性的 极小化过程 2020年3月31日星期二 F A B B C B A A C C A 2 逐一检查F中各函数依赖FDi X A 令G F X A 若A XG 则从F中去掉此函数依赖 检查A B 令G F A B B AG AC 所以不能将A B从F中去掉再检查B C 令G F B C C BG ABC 所以将B C从F中去掉 则F A B B A A C C A 再检查B A 令G F B A A BG B 所以不能将B A从F 中去掉再检查A C 令G F A C C AG AB 所以不能将A C从F 中去掉再检查C A 令G F C A A CG C 所以不能将C A从F 中去掉所以F A B B A A C C A 极小化过程 2020年3月31日星期二 F A B B A A C C A 3 逐一取出F中各函数依赖FDi X A 设X B1B2 Bm 逐一考查Bi i l 2 m 若A X Bi F 则以X Bi取代X 这一步工作也不用做 因为F A B B A A C C A 中的函数依赖的左边都是单个属性的 所以得到Fm2 A B B A A C C A Fm1 Fm2都是F的最小依赖集 Fm1 A B B C C A Fm2 A B B A A C C A 极小化过程 2020年3月31日星期二 极小化过程 定理6 3的证明 也是检验F是否为极小依赖集的一个算法若改造后的F与原来的F相同 说明F本身就是一个最小依赖集在R中可以用与F等价的依赖集G来取代F原因 两个关系模式R1 R2 如果F与G等价 那么R1的关系一定是R2的关系 反过来 R2的关系也一定是R1的关系 2020年3月31日星期二 练习 1 设关系模式R A B C D E 和R上的函数依赖集F A B DE B CB E E AB B D 求R的候选关键字 2 设有函数依赖集F AB CE A C GP B EP A CDE P HB P D HG ABC PG 求与F等价的最小函数依赖集 3 关系模式P A B C D E F G H I J 满足下列函数依赖 FD ABD B AB G B F C J CJ I G H 求FD的最小函数依赖集 候选码 判断该关系模式属于几范式 2020年3月31日星期二 1 设关系模式R A B C D E 和R上的函数依赖集F A B DE B CB E E AB B D 求R的候选关键字 一个属性的 AF ABD BF BD CF C DF D EF EABD 两个属性的 ABF ABD ACF ACBED U ADF ADB AEF AEBD BCF BCEAD U BDF BD BEF BEAD CDF CD CEF CEABD U DEF DEBA 三个属性的 ABCF ABDF ABEF ACDF ACEF ADEF BCDF BCEF BDEF CDEF 四个属性的 ABCDF ABCEF ABDEF ACDEF BCDEF 五个属性的 ABCDEF 所以 R U F 上的候选关键字为 AC或BC或CE 极小化过程 2020年3月31日星期二 2 设有函数依赖集F AB CE A C GP B EP A CDE P HB P D HG ABC PG 求与F等价的最小函数依赖集 1 逐一检查F中各函数依赖Fdi X Y 若Y A1A2 Ak k 2 则用 X Aj j 1 2 k 来取代X Y F AB C AB E A C GP B EP A CDE P HB P D H D G ABC P ABC G 极小化过程 2020年3月31日星期二 F AB C AB E A C GP B EP A CDE P HB P D H D G ABC P ABC G 2 逐一检查F中各函数依赖FDi X A 令G F X A 若A XG 则从F中去掉此函数依赖 检查AB C 令G F AB C C ABG ABCEPG 所以将AB C从F中去掉 F AB E A C GP B EP A CDE P HB P D H D G ABC P ABC G 再检查AB E 令G F AB E E ABG ABCPG 所以不能将AB E从F 中去掉再检查A C 令G F A C C AG A 所以不能将A C从F 中去掉再检查GP B 令G F GP B B GPG GP 所以不能将GP B从F 中去掉再检查EP A 令G F EP A A EPG EP 所以不能将EP A从F

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论