数据库课件第六讲.ppt

第六章 逻辑数据库设计,关系数据库逻辑设计 针对具体问题，如何构造一个适合于它的数据模式 数据库逻辑设计的工具关系数据库的规范化理论,逻辑数据库设计分为6步： 1、将概念结构转换为初始的关系数据库模式 2、关系模式规范化 3、关系模式优化 4、定义关系上的完整性和安全性约束 5、子模式定义 6、性能估计,6.1 形成初始关系数据库模式,初始关系数据库模式指直接由概念数据库模式生成的关系数据库模式。 E-R图向关系模型的转换 转换一般遵循如下原则： 1、一个实体型转换为一个关系模式，实体的 所有简单属性和复合属性的简单子属性就 是关系的属性，实体的键就是关系的键。,T(名字,身份证号, 工资,职称,邮编, 市,区,学校,信箱) G(名字,编号,地点,所 属系),2、弱实体的转换：将弱实体转换为一个关系 模式，弱实体的属性和识别实体的主键作 为关系模式的属性。弱实体的属性和识别 实体的键作为关系模式的键。,R(身份证号,名字,性别),3、多值属性的转换：如果多值属性是简单属 性则将每个多值属性和包含该多值属性的 实体的键属性形成一个关系模式。实体的 键和多值属性作为关系模式的键。如果多 值属性是复合属性，则简单子属性和包含 该多值属性的实体的键属性形成一个关系 模式。去掉多值属性的其他属性和实体 键形成一个关系模式。实体的键作为关系 模式的键。,E为一个实体； K,A,D,F为其属性； A,D为多值属性，K为实体E的键；A又是复合属性； 关系 S(K,F) T1(K,B,C) T2(K,D),4、实体间联系的转换： 1：1联系：转换为一个独立的关系模式，也 可以与任意一端对应的关系模式合并。如果 转换为一个独立的关系模式，则与该关系相 连的各实体的键以及联系本身的属性均转换 为关系的属性，每个实体的键均是该关系的 候选键。如果与某一端实体对应的关系模式 合并，则需要在该关系模式的属性中加入另 一个关系模式的键和联系本身的属性。,1：n联系：可以转换为一个独立的关系模式， 也可以与n端对应的关系模式合并。如果转 换为一个独立的关系模式，则与该联系相连 的各实体的键以及联系本身的属性均转换为 关系的属性，而关系的键为n端实体的键。 如果与n端实体合并则将1端实体的键和联系 的属性均加入n端实体，关系的键为n端实体 的键。,工作天数,1,n,仓库号,职工号,m：n联系：转换为一个独立的关系模式。与该联系相连的各实体的键以及联系本身的属性均转换为关系的属性，而关系的键为各实体键的组合。,三个或三个以上实体间的一个多元联系 可以转换为一个关系模式。与该多元联系 相连的各实体的键以及联系本身的属性均 转换为关系的属性，而关系的键为个实体 键的组合。,5、具有相同键的关系模式可合并。,实例：工厂管理系统,部门(部门号，部门名，经理的职工号) 包含了 联系“领导”所对应的关系模式 职工(职工号,部门号,职工名,职务) 包含了属 于的关系模式) 项目(项目号,项目名,项目组长的职工号) 供应商(供应商号,姓名) 零件(零件号,零件名) 职工工作(职工号,项目号,工作天数) 供应(项目号,供应商号,零件号,供应量),实例：公司车队信息系统的E-R模型,为某货运公司设计车队管理系统，对车辆、司机、维修、保险、报销等信息和业务活动进行管理。现实语义为：货运公司有多个部门多个车队；每个部门可以调用多个车队，每个车队可以被多个部门调用；每个车队可以聘用多个司机，一个司机只能在一个车队工作；一个车队可以拥有多辆车，但每辆车只能属于一个车队；每辆车可以报销多种费用；一个保险公司可以为多个司机，多辆车保险，但每个司机，每辆车只能在一个公司保险；,一个维修公司可以维修多辆车，但每辆车 只能在一个维修公司维修。其中部门编 号、名称、负责人等属性描述部门；车队 编号、名称、地址等属性描述车队；车牌 号、车型、颜色、载重等属性描述车辆； 执照号、姓名、电话、工资等属性描述司 机；保险公司编号、名称、地址等属性描 述保险公司；维修公司编号、名称、地址 等属性描述维修公司；顺序号、费用类型、 费用、日期、经手人等属性描述开销；,部门调用车队有出车编号、出车日期、车程、费用、出车数目；车辆和司机参保有投保日期、保险种类、费用。（1）根据现实语义设计E-R模型，其中实体的属性不要求画出，联系的属性要求画出；（2）将E-R模型转化为关系模式，并给出各关系模式的主键和外部键,部门（部门号，名称，负责人）； 车队（车队号，名称，地址）； 车辆（车牌号，车型，颜色，载重，车队号， 维修公司号，保险公司号，投保日期， 保险种类，费用）； 司机（司机号，姓名，执照号，电话，工资， 车队号，保险公司号，投保日期， 保险种类，费用）； 保险公司（保险公司号，名称，地址）；,维修公司（维修公司号，名称，地址）； 开销（顺序号，费用类型，费用，日期， 经手人，车辆号）； 调用（出车编号，部门号，车队号，出车 日期，车程，费用，车辆数目）；,实例：现实语义：某公司业务概况如下公司下设有几个部门每个部门承担多个工程项目，每个工程项目直属于一个部门每个部门有多名职工，每个职工直属于一个部门一个职工能参加多个工程项目，每个项目有多名职工参加每个部门有一个部门经理，他是职工中的一员一名职工可能有多名亲属，也可能没有亲属一名职工可能有多种技能，很多职工可能有同一种技能。,局部E-R图,部门,项目,承担,部门,职工,聘用,职工,工程,施工,n,n,m,1,1,n,m,1,1,n,1,n,弱实体,逻辑设计（转换成关系模型） 部门（部门代号，部门名，地址，电话，经理职工号） 工程（工程号，工程名，经费预算，部门代号） 职工（职工号，姓名，性别，生日，部门代号） 技能（技能代号，技能名称） 亲属（职工号，亲属名，亲属关系） 人才（职工号，技能号，从事年限） 施工（职工号，工程号，工时）,6.2 关系数据库设计理论,一、问题的提出 例：建立一个描述学校教务的数据库，该数据库 涉及的对象包括学生的学号（sno），所在 系（sdept），系主任姓名（mn）,课程名 （cname），成绩（grade）。假设用一个单 一的关系模式student来表示，则该关系模 式的属性集合为： U=sno,sdept,mn,cname,grade,由现实世界的已知事实（语义）可以推知： 一个系有若干学生，但一个学生只属于一个系 一个系只有一名系主任 一个学生可以选修多门课程，每门课程有若干 学生选修 每个学生所学的每门课程都有一个成绩,关系模式student(sno,sdept,mn,cname,grade) 某一时刻关系模式student的一个实例，即数据表,但是这个关系模式存在以下问题： 插入异常（insert anomalies）：如果一个系刚成立，尚无学生，就无法把这个系及其系 主任的信息存入数据库。 删除异常：如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,数据冗余大：比如，每一个系的系主任姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同，这将浪费大量的存储空间 更新异常：由于数据冗余，当更新数据库中的数据时，系统要付出很大的代价来维护数据库的完整性，否则会面临数据不一致的危险。比如，系更换系主任后，必须修改与该系学生有关的每一个元组。,数据依赖：一个关系内部属性与属性之间的一种 约束关系。这种约束关系是通过属性 值的相等与否体现出来的数据间的相 关联系。 数据依赖 函数依赖(Functional Dependency,FD) 多值依赖(Multivalued Dependency,MVD),函数依赖举例： 描述一个学生的关系student(sno,sname,sdept) 由于一个学号只对应一个学生,一个学生只在一 个系。因此当学号值确定之后，学生的姓名及 所在系的值也就被唯一地确定了。属性间的这 种依赖关系类似于数学中的函数y=f(x),自变量 x确定之后，相应的函数值y也就为一地确定 了。,类似的有sname=f(sno),sdept=f(sno),即sno函 数决定sname,sno函数决定sdept,或者说sname 和sdept函数依赖于sno，记为： sno sname,sno sdept.,上例根据语义可以得到属性组U上的一组函数依赖 F= sno sdept,sdept mn,(sno,cname) grade 分成三个关系模式: s(sno,sdept);sc(sno,cname,grade);dept(sdept,mn),一个关系模式之所以会产生上述问题，是由 存在于模式中的某些数据依赖引起的。规范化理 论正是用来研究和分析各种数据依赖，研究改造 关系模式的方法，研究消除关系模式中不合适的 数据依赖的方法，避免产生异常和数据冗余等问 题。,这里提出了两个问题：一个是怎样评价一个关系 模式的优劣；第二个问题是怎样将一个不太好的 关系模式分解为一组较理想的关系模式。这正是 本章要解决的问题。为此，在下一节首先介绍模 式设计理论的基础函数依赖。,关系模式的形式化定义,关系模式由五部分组成，即它是一个五元组： R(U, D, DOM, F) R：关系名 U：组成该关系的属性名集合 D：属性组U中属性所来自的域 DOM：属性向域的映象集合 F：属性间数据的依赖关系集合,关系模式的简化表示,关系模式R（U, D, DOM, F） 简化为一个三元组： R（U, F） 当且仅当U上的一个关系r 满足F时，r称为关系模式 R（U, F）的一个关系,二、函数依赖,定义：设R(U)是属性集U上的关系模式，X ,Y U， r是R(U) 上的任意一个关系，如果成立 对t , s r，若tX = sX，则tY = sY 那么称“X函数决定Y”，或“Y函数依赖于X”， 记作XY.称X为决定因素 如Sno Sname， （Sno，Cname） G 即对于关系模式R中的属性子集X的每一个值，任何 时刻只有一个确定的Y 值与之对应。,一个错误的student表,函数依赖与联系之间的关系,如果X和Y之间的联系是1：1，则存在函数依赖X Y和Y X。例如：课程号C#与课程名CN 如果X和Y之间的联系是m：1，则它们之间只存在函数依赖X Y。例如：一个教师可上几门课，则C#与教师Tname之间是m：1，所以C# Tname 如果X和Y之间的联系是m：n，则它们之间不存在函数依赖。,说明：,1. 函数依赖不是指关系模式R的某个或某些关系 实例满足的约束条件，而是指R的所有关系实 例均要满足的约束条件。 2. 函数依赖是语义范畴的概念。只能根据数据 的语义来确定函数依赖。 例如“姓名年龄”这个函数依赖只有在不允 许有同名人的条件下成立,3. 数据库设计者可以对现实世界作强制的规定。 例如规定不允许同名人出现，函数依赖“姓 名年龄”成立。所插入的元组必须满足规定 的函数依赖，若发现有同名人存在， 则拒绝 装入该元组。,常用概念和记号,例: Student(Sno, Sname, Ssex, Sage, Sdept) 假设不允许重名，则有: SnoSsex，SnoSage,SnoSdept， SnoSname,SnameSsex，SnameSage Sname Sdept 但Ssex Sage 若XY，并且YX, 则记为XY。 若Y不函数依赖于X, 则记为XY。,平凡函数依赖与非平凡函数依赖 在关系模式R(U)中，对于U的子集X和Y， 如果XY，但Y X，则称XY是非平凡的函数依赖 若XY，但Y X, 则称XY是平凡的函数依赖 例：在关系SC(Sno, Cno, Grade)中， 非平凡函数依赖：(Sno, Cno) Grade 平凡函数依赖：(Sno, Cno) Sno (Sno, Cno) Cno,对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖 若XY则X称为这个函数依赖的决定属性组,也成为决定因素(Determinant),几种函数依赖,完全函数依赖与部分函数依赖 在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有X Y, 则称Y完全函数依赖于X，记作X Y。 若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y。,例：在s(sno,sname,sdept,cname,grade) 中,(sno,cname) f grade是完全函数 依赖，(sno,cname) p sdept是部分函 数依赖，因为sno sdept成立，而sno 是（sno,cname）的真子集。,传递函数依赖 在关系模式R(U)中，如果XY，YZ，且Y X， YX，则称Z传递函数依赖于X。记作X t Y。 注: 如果YX， 即XY，则Z直接依赖于X。 例: 在关系Std(Sno, Sdept, Mn)中，有： Sno Sdept，Sdept Mn Mn传递函数依赖于Sno,三、用函数依赖定义关系模式的键,候选键：设K为R属性集，若K U，则称K为R的候选键,主键：若R(U , F)有多个候选键，则可以从中选定一个作为R的主键,键属性：包含在每一个候选键中的属性，称作键属性,全键：关系模式的键由整个属性组构成,外部键：设X是关系模式R的属性子集合，如果X是另一个关系模式的候选键，则称X是R的外部键。,例如：关系模式S（学号，姓名，系名称，出生 日期）中，学号是主键。 在关系模式SC（学号，课程号，成绩，教师编号） 中，属性组合（学号，课程号）是主键。 学号是SC相对于S的外部键。 设有关系模式A（作者，书籍，读者），这个关 系模式的主键为（作者，书籍，读者）,四、关系模式的规范形式（范式）,范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。 范式的种类： 第一范式(1NF) 第二范式(2NF) 第三范式(3NF) BC范式(BCNF) 第四范式(4NF) 第五范式(5NF),各种范式之间存在联系： 某一关系模式R为第n范式，可简记为RnNF。,第一范式：,定义：如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。 例：有一关系模式SC1（学号，课程），学生 和选修课程的记录如下： 学号 课 程 007501 程序设计、操作系统、数据库 007501 电路分析、数字电路 ,在上述模式中，课程属性值是可分解的，因此 SC1不属于1NF。 SC2 学 号 课程 007501 程序设计 007501 操作系统 007501 数据库 007501 电路分析 007501 数据电路 ,第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。 但是满足第一范式的关系模式并不一定是一个好的关系模式。,例: 关系模式SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc为学生住处，假设每个系的学生住在同一 个地方。 函数依赖包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc,SLC的键为(Sno, Cno) SLC满足第一范式。 非键属性Sdept和Sloc部分函数依赖于键(Sno, Cno),SLC不是一个好的关系模式,(1) 插入异常 假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程号是键属性，因此该学生的信息无法插入SLC。 (2) 删除异常 假定某个学生本来只选修了3号课程这一门课。现在因身体不适，他连3号课程也不选修了。因课程号是键属性，此操作将导致该学生信息的整个元组都要删除。,(3) 数据冗余度大 如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。 (4) 修改复杂 例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。,原因 Sdept、 Sloc部分函数依赖于键。 解决方法 SLC分解为两个关系模式，以消除这些部分函数依赖 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）,函数依赖图：,第二范式,定义: 若关系模式R1NF，并且每一个非键属性 都完全函数依赖于R的键，则R2NF。 例：SLC(Sno, Sdept, Sloc, Cno, Grade)1NF SLC(Sno, Sdept, Sloc, Cno, Grade)2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。,结论 (1)从1NF关系中消除键属性对关系键的部分函数依赖，则可得到2NF。 (2)如果R的关系键为单属性，或R的全体属性均键属性，则R 2NF。,例：2NF关系模式SL(Sno, Sdept, Sloc)中 函数依赖： SnoSdept SdeptSloc SnoSloc Sloc传递函数依赖于Sno，即SL中存在非键属性对键的传递函数依赖。,函数依赖图：,解决方法 采用投影分解法，把SL分解为两个关系模式， 以消除传递函数依赖： SD（Sno， Sdept） DL（Sdept， Sloc） SD的键为Sno， DL的键为Sdept。,SD的码为Sno， DL的码为Sdept。,第三范式,定义：关系模式R 中若不存在这样的键X、属性组Y及非键属性Z（Z Y）, 使得XY，Y X，YZ，成立，则称R 3NF。 例， SL(Sno, Sdept, Sloc) 3NF SL(Sno, Sdept, Sloc) 2NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF,若R3NF，则R的每一个非键属性既不部分函数依赖于候选键也不传递函数依赖于候选键。 不存在非键属性的关系模式一定是3NF. 如果R3NF，则R也是2NF。 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,BC范式（BCNF）,定义：设关系模式R1NF，如果对于R的 每个函数依赖XY，若Y X，则X必 含有候选键，那么RBCNF。 若RBCNF 每一个决定属性集（因素）都包含（候选）键 R中的所有属性（键，非键属性）都完全函数依赖于键 R3NF（证明） 若R3NF，则R不一定BCNF,定理 一个BCNF的关系模式必是3NF的。 证明：用反证法。设RBCNF，但不属于3NF，则必存在非键属性A和键X以及属性组Y，使得XY，Y X，YA。但根据BCNF的定义，有YA，则Y必是R的关键字，于是有YX，这与 Y X矛盾，定理得证。,例：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。 每一教师只教一门课。每门课由若干教师教， 某一学生选定某门课，就确定了一个固定的 教师。某个学生选修某个教师的课就确定了 所选课的名称 ： (S，J)T，(S，T)J，TJ,STJ3NF (S，J)和(S，T)都可以作为候选键 S、T、J都是键属性 STJBCNF TJ，T是决定属性集，T不是候选键,解决方法：将STJ分解为二个关系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 没有任何属性对键的部分函数依赖和传递函数依赖,如果关系模式RBCNF， 必定有R3NF 如果R3NF，且R只有一个候选键， 则R必属于BCNF。,BCNF的关系模式所具有的性质, 所有非键属性都完全函数依赖于每个候选键 所有键属性都完全函数依赖于每个不包含它的候选键 没有任何属性完全函数依赖于非键的任何一组属性,例：有一关系模式SJP（学生，课程，名次）。 在SCP中有如下对应关系： （1）每个学生选修每门课程的成绩有一定的名次 （2）每门课中每一名次只有一个学生（即没有并 列名次） 由语义可得到如下函数依赖： （S，J）P （J，P）S,显然，这个关系模式有2个候选键（S，J） 、 （J，P），并且没有非键属性对键的部分函数依 赖或传递函数依赖，因此，SCP3NF。 另外，除（S，J）和（J，P）之外没有其他决定 因素，所以SJP BCNF,规范化,关系数据库的规范化理论是数据库逻辑设计的工具。 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。 规范化程度可以有多个不同的级别,规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化,关系模式规范化的基本步骤,规范化的基本思想,消除不合适的数据依赖，使各关系模式达到某种程度的“分离” 采用“一事一地”的模式设计原则 让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去 所谓规范化实质上是概念的单一化,不能说规范化程度越高的关系模式就越好 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式 上面的规范化步骤可以在其中任何一步终止,练习：,1、判定S(sno,sname,sdept,sage),C(cno,cname,cpno), SC(sno,cno,grade)的范式等级。 解：S关系的候选键为sno,函数依赖为sno sname, sno sdept,sno sage,非键属性 sname,sdept,sage对键sno没有部分或传递函数 依赖。所以S3NF。而且决定因素都是键，所以 SBCNF 。 同理，C关系和SC关系都属于BCNF,2、设有关系模式project(工程号,材料号,数量,开工日期,完工日期,单价). 语义:每项工程可以使用多种材料,每种材料可以供多项工程使用;每项工程开工前必须确定开工日期和完工日期;每种材料有确定的价格. 请写出函数依赖,并判断该关系模式的范式等级， 分析是否存在操作异常？并分解为高一级范式。,解：候选键为（工程号，材料号）， 函数依赖为：工程号 开工日期; 工程号 完工日期; 材料号 单价 （工程号，材料号） 数量; (工程号,材料号) p 开工日期; (工程号,材料号) p 完工日期; (工程号,材料号) p 单价,因为存在非键属性对键的部分函数依赖,所以， 如果工程项目确定后，若暂时未用到材料，则该工程的数据因缺少关键字的一部分材料号，而不能进入到数据库中，出现插入异常。工程下马，则删去该工程的操作也可能丢失材料方面的信息。 分解后project1(工程号,材料号,数量) project2(工程号,开工日期,完工日期) project3(材料号,单价),3、设关系R（CN,TN,TD）其中CN表示课程名，TN表示教师名字（没有重名教师），TD表示教师地址。语义：一门课只被一个教师讲，一个教师可以讲多门课。判断为几范式？为什么？是否存在删除异常？分解为高一级范式。,解：R的候选键为CN;CN TN,TN CN, TN TD,所以CN t TD 因为存在非键属性对键的传递函数依赖， 所以R3NF。又因为不存在非键属性对键 的部分函数依赖，所以R2NF 。 存在删除异常，当删除某门课时会删除教 师的有关信息。 分解后R1(CN,TN);R2(TN,TD),4、关系模式R（职工号，职工名，年龄，性别，部门号，部门名），职工名允许重复，R是否属于3NF？为什么？并规范化为3NF。 解：R的候选键为职工号；函数依赖为： 职工号 部门号，部门号 职工号， 部门号 部门名，存在非键属性对键的传 递函数依赖，所以R3NF 。不存在非键属性 对键的部分函数依赖，所以R2NF 。 分解后R1（职工号，职工名，年龄，部门号， 性别） R2（部门号，部门名）,五、数据依赖的公理系统,如何判断关系模式的范式级别？ 如何求关系模式的候选键？ 问题 给定一组函数依赖，是否能导出另外一些函数依赖，或另外的函数依赖是否成立？ 如FD=A B，B C，A C是否成立？,逻辑蕴含 Armstrong公理系统 闭包的计算 函数依赖的等价和覆盖,逻辑蕴涵,定义 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立, 则称F逻辑蕴含X Y 被F所逻辑蕴含的函数依赖的全体所构成的集合称作F的闭包，记作F+,Armstrong公理系统,一套推理规则，是模式分解算法的理论基础 用途 求给定关系模式的键 从一组函数依赖求得蕴含的函数依赖,Armstrong公理,设有关系模式R（U，F），属性集X，Y，Z，WU 自反律(reflexivity)：若YX，则XY为F所蕴含 增广律(augmentation)：若XY为F所蕴含，则XZYZ为F所蕴含 传递律(transitivity)：若XY，YZ为F所蕴含，则XZ为F所蕴含 注意：由自反律所得到的函数依赖均是平凡的函 数依赖，自反律的使用并不依赖于F,关于Armstrong公理正确性,按函数依赖定义r是R上的任一关系，t，s r,定理6.2.1 Armstrong公理是正确的,推理规则,由Armstrong公理导出的推理规则 合并律(union rule) 若X Y，X Z，则X YZ 分解律(decomposition rule) 若X Y，ZY,则X Z 伪传递律(pseudo transitivity rule) 若X Y，WY Z，则WX Z,定理6.2.2 Armstrong推理规则是正确的,示例 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？（传递律） CG HI？（合并律） AG I？（ AGCG, CGI,增广律，传递律）,引理6.2.1 XA1 A2 Ak成立 XAi成立(i=1, 2, ,k) 证明： 由合并律 由分解律 ,定理6.2.4：Armstrong公理系统是有效的、完备的。 有效性：由F出发根据Armstrong公理推导出的每一个函数依赖一定在F+中。 完备性：F+中的每一个函数依赖，必是由F出发根据Armstrong公理推导出的。 要证明完备性首先要解决如何判定一个函数依赖是否属于由F根据公理推导出的函数依赖的集合。如果能求出这个集合问题就解决了。但是这是一个NP完全问题。,属性集的闭包,设F为属性集U上的一组函数依赖，X U， XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包,示例 属性集U=A，B，C， 函数依赖集F=A B，B C则 A+ = ABC B+ = BC C+ = C,关于闭包的引理,引理6.2.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+ 证明：充分性。设Y XF+ ，并设Y=B1B2Bk 。根据属性闭包的定义可知， XB1， XB2， ，XBk是用Armstrong公理从F推出的。由合成规则，有XY。所以，当Y XF+时， XY可以用Armstrong公理从F推出。 必要性。设XY是用Armstrong公理从F推出的，Y=B1B2Bk。根据分解规则有XB1， XB2， ，XBk,由XF+定义可知BiXF+ (i=1,2, ,k),所以Y XF+,用途 将判定XY是否能由F根据Armstrong公理导出的问题,就转化为求出XF+ ，判定Y是否为XF+的子集的问题 例：X=B,D U=A,B,C,D,E,XF+=A,B,C,D 所有的(B,D) Y(只要Y XF+),求闭包的算法,算法:求属性集X（X U）关于U上的函数依 赖集F 的闭包XF+ 输入：X，F 输出：XF+ 步骤： （1）令X（0）=X，i=0 （2）求B，这里B = A |( V)( W)(VWF V X（i）A W)；,（3）X（i+1）=BX（i） （4）判断X（i+1）= X （i）吗? （5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。 （6）若否，则 i=i+l，返回第（2）步。 判断算法终止的条件：算法至多执行|U-X|次 X(i+1)=X(i)；求得的XF+包含U的全部；F中再没有 可用的函数依赖。,例1 已知关系模式R，其中 U=A，B，C，D，E； F=ABC，BD，CE，ECB，ACB。 求（AB）F+ 。 解 设X（0）=AB； (1)计算X（1）: 逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：ABC，BD。 于是X（1）=ABCD=ABCD。,(2)因为X（0） X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD， CE，ACB， 于是X（2）=X（1）BCDE=ABCDE。 (3)因为X（2）=U，算法终止 所以（AB）F+ =ABCDE。,例2 设R,其中U=A,B,C,D,E,I; F=AD,ABE,BIE,CDI,EC 求：(AE)F+ 解：令X=AE,X(0)=AE,在F中找出左边是AE子集的函数依 赖，其结果是：AD,EC，所以X(1)=X(0)CD=ACDE, X(0)X(1)在F中找出左边是AEDC子集的函数依赖，其 结果是CDI,所以X(2)=X(1)I=ACDEI,显然X(2)X(1), 但F中未用过的函数依赖的左边属性已没有X(2)的子 集，所以不必在计算下去。即(AE)F+=ACDEI.,快速求解候选键的方法,对于给定的关系模式R(A1,A2,An)和函数 依赖集F，可将其属性分为四类： L类：仅出现在F的函数依赖左部的属性 R类：仅出现在F的函数依赖右部的属性 N类：在F的函数依赖左右两边均未出现的属性 LR类：在F的函数依赖左右两边均出现的属性,定理1：对于给定的关系模式及其函数依赖集F， 若X(XR)是L类属性，则X必为R的任一 候选关键字的成员。 例：设R(A,B,C,D),F=DB,BD,ADB,ACD 求R的候选键 解：考察F发现，A,C两属性是L类属性，AC必为 R的候选键成员，又因为(AC)F+=ACBD.所以 AC是候选键。,定理2：对于给定的关系模式R及其F，如果X(XR) 是R类属性，则X不在任何候选关键字中。 定理3：设有R及其F，如果X是R的N类属性，则X必 包含在R的任一候选键中。 推论：对于给定的关系模式R及其函数依赖集F,如 果X是R的N类和L类组成的属性集，且XF+ 包 含了R的全部属性，则X是R的唯一候选键。,例：设R(A,B,C,D,E,P), F=AD,ED,DB,BCDDCA, 求R的候选键。 解：C,E是L类属性，P是N类属性。 (CEP)F+=ABCDEP。所以CEP是候选键。,函数依赖集等价,定义 如果G+=F+，就说函数依赖集F覆盖G（F是G 的覆盖，或G是F的覆盖），或F与G等价。,函数依赖集等价的充要条件 引理6.2.3 F+ = G+ 的充分必要条件是 F G+ ，和G F+ 证: 必要性显然，只证充分性。 （1）若FG+ ，则XF+ XG+ 。 （2）任取XYF+ 则有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。 （3）同理可证G+ F+ ，所以F+ = G+。,要判定F G+，只须逐一对F中的函数依赖XY，考察 Y 是否属于XG+ 就行了。因此引理3 给出了判断两个函数依赖集等价的可行算法。,最小依赖集,定义 如果函数依赖集F满足下列条件，则称F为 一个极小函数依赖集。亦称为最小依赖集 或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与 F-XA等价。 (3) F中不存在这样的函数依赖XA， X有真 子集Z使得F-XAZA与F等价。,例关系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 设F=SNOSDEPT，SNOMN，SDEPTMN， (SNO，CNAME)G，(SNO，SDEPT)SDEPT F是最小覆盖，而F 不是。 因为：F -SNOMN与F 等价 F -(SNO，SDEPT)SDEPT也与F 等价 F -(SNO，SDEPT)SDEPT SNOSDEPT也与F 等价,定理6.2.5 每一个函数依赖集F均等价于一个极 小函数依赖集Fm。此Fm称为F的最小依 赖集 证:构造性证明，依据定义分三步对F进行“极小 化处理”，找出F的一个最小依赖集。 (1)逐一检查F中各函数依赖FDi：XY， 若Y=A1A2 Ak，k2， 则用 XAj |j=1，2， k 来取代XY。,极小化过程,(2)循环地检查F中各函数依赖FDi：XA， 令G=F-XA， 若AXG+， 则从F中去掉此函数依赖。直到F不再改变。 由于F与G =F-XA等价的充要条件是AXG+ 因此F变换前后是等价的。,(3)循环地取出F中各函数依赖FDi：XA， 设X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 则以X-Bi A 取代X A 。直到F不再改变。 由于F与F-XAZA等价的充要条件 是AZF+ ，其中Z=X-Bi 因此F变换前后是等价的。,由定义，最后剩下的F一定是极小依赖集。 因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价。 证毕 定理的证明过程 也是求F极小依赖集的过程,例 F = AB，BA，BC，AC，CA Fm1、Fm2都是F的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依赖集Fm不一定是唯一的。它与对各函数依赖FDi 及XA中X各属性的处置顺序有关,极小化过程( 定理6.2.5的证明 )也是检验F是否为极小依赖集的一个算法 若改造后的F与原来的F相同，说明F本身就是一个最小依赖集,例，设有关系模式R（U，F），其中U=ABC，F = A B，C，BC，AB，A，BC，求Fmin 将F中所有的函数依赖的依赖关系因素写成单属性集形式： G=AB，A C， BC，AB，A，BC 这里多出一个AB，可以删除，得到 G=AB，A C， BC，A，BC G中的AC可以从AB和BC推导出，AC冗余的，删除 G=AB， BC，A，BC G中的A，BC可以从BC推导出来，是冗余的，删除 G = AB，BC 所以 Fmin = AB，BC,6.3 关系模式规范化方法,模式分解 把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义,模式分解,定义 关系模式R的一个分解： = R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影 定义 函数依赖集合XY | XY F+X，Y Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上 的投影,例: SL（Sno， Sdept， Mn） F= SnoSdept,SdeptMn,SnoMn SL2NF 存在插入异常、删除异常、冗余度大和修改复 杂等问题 分解方法可以有多种,SL Sno Sdept Mn 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH D ,1. SL分解为下面三个关系模式： SN(Sno) SD(Sdept) SM(Mn),分解后的关系为：,SN SD SO Sno Sdept Mn 95001 CS A 95002 IS B 95003 MA C 95004 PH D 95005 ,分解后的数据库丢失了许多信息 例如无法查询95001学生所在系的系主任。 如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息,2. SL分解为下面二个关系模式： SD(Sno, Sdept) SM(Sno, Mn),分解后的关系为：,SD SM Sno sdept sno Mn 95001 CS 95001 A 95002 IS 95002 B 95003 MA 95003 C 95004 IS 95004 B 95005 PH 95005 D -,SD SM Sno Mn Sdept 95001 A CS 95002 B IS 95003 C MA 95004 B IS 95005 D PH,问题: 这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖SdeptMn 没有投影到关系模式SD、SM上,3. 将SL分解为下面二个关系模式： SD(Sno, Sdept) DM(Sdept,Mn),分解后的关系为：,SD DM Sno Sdept Sdept Mn 95001 CS CS A 95002 IS IS B 95003 MA MA C 95004 IS PH D 95005 PH ,SD DM Sno Sdept Mn 95001 CS A 95002 IS B 95003 MA C 95004 IS A 95005 PH D 与SL关系一样，因此没有丢失信息 这种分解方法保持了函数依赖, 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性,三种模式分解的等价定义,定义 设 = R1,R2,Rn是关系模式R的一个分解，r 是R的一个关系。定义m( r )= R1(r) R2(r) Rn(r),即m( r )是r在中各关系模式 上投影的连接。 定义 关系模式R ，U = Ui ， = R1 , R2, , Rn是R的一个分解，r是R的一个 关系定义m(r) = Ri(r) ,若对于R 的任一个关系r，都有r = m(r)，则称是R的一个无损连接分解。,具有无损连接性的模式分解,关系模式R的一个分解 = R1，R2， ，Rn若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Lossless join） 具有无损连接性的分解保证不丢失信息 无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题,1、当分解为两个或两个以上关系模式时，可以用建初始矩阵，并通过对矩阵转化进行判断。 （判定算法6.3.1） 输入:关系模式R(A1,A