第4章 关系数据库设计理论 本章内容 4.1 问题的提出 4.2 规范化 4.3 数据依赖的公理系统* 4.4 小结 习 题.

Slides:



Advertisements
Similar presentations
九十五年國文科命題知能 研習分享.
Advertisements

《审计专业相关知识》 考前点题班 张京.
2011年会计初级职称全国统考 初级会计实务 教案 主讲:高峰 2010年12月.
2013届高考复习方案(第一轮) 专题课件.
鲁班培训-培训类项目 一级建造师 二级建造师 监理工程师 安全工程师 造价工程师 物业工程师 造 价 员 职称英语
人民教育出版社义务教育新课程标准 实验教科书《数学》九年级上册第25章 回顾与思考 授课教师:临潼区陕缝学校 徐联君.
全国一级建造师执业资格考试 《建设工程法规及相关知识》 高 唱
行政诉讼法.
服务热线: 菏泽教师招聘考试统考Q群: 菏泽教师统考教育基础模拟题解析.
复习重点; 1. 关系模型、ER模型 2. SQL 3. 事务管理 4. 函数依赖与规范化 5. 数据库设计  复习题 一、单项选择题
2011年广西高考政治质量分析 广西师范大学附属外国语学校 蒋 楠.
第七章:数据库设计理论基础.
知识回顾 1、通过仔细观察酒精灯的火焰,你可以发现火焰可以分为 、 、 。 外焰 内焰 焰心 外焰 2、温度最高的是 。
2016届高三期初调研 分析 徐国民
第三章 仓储技术作业过程.
物理精讲精练课件 人教版物理 八年级(下).
软件设计师培训.
第六章 关系数据理论 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解.
An Introduction to Database System
专题二 识图题增分技巧.
第五章 电流和电路 制作人 魏海军
第一章 民法概述 一、民法概念 P4 二、民法的调整对象 三、民法的分类 四、民法的渊源 P10 五、民法的适用范围(效力范围)
第七章 财务报告 财务报告 第一节 财务报告概述 一、财务报告及其目标: 1、概念:财务报告是指企业对外提供的反映企业某一特定日期
统计法基础知识 主讲:胡燕 二0一五年八月.
线索一 线索二 复习线索 专题五 线索三 模块二 第二部分 考点一 高考考点 考点二 考点三 配套课时检测.
发展心理学 王 荣 山.
出入口Y27 往塔城街口/中興醫院 出入口Y25 往延平北路一段/中興醫院 出入口Y23往延平北路一段 出入口Y21往延平北路一段
第十课 创新意识与社会进步 1.辩证的否定观:辩证否定、形而上学的否定观
课标版 政治 第一课 美好生活的向导.
圓的線段乘冪性質.
An Introduction to Database System An Introduction to Database System
政治第二轮专题复习专题七 辩 证 法.
第七章 财务报告 主讲老师:王琼 上周知识回顾.
第四章 关系数据理论 4.1 关系模式的设计问题 4.2 关系模式的规范化 4.3 数据依赖的公理系统 4.4 关系模式的分解 本章小结.
數位邏輯簡介.
課程名稱:資料庫系統 授課老師:李春雄 博士
課程名稱:資料庫系統 授課老師:李春雄 博士
第7章 關聯式資料庫的正規化 7-1 正規化的基礎 7-2 功能相依 7-3 第一階到第三階正規化型式 7-4 多重值相依與第四階正規化型式
教 师:曾晓东 电 话: 数据库技术 教 师:曾晓东 电 话:
第四章关系数据库设计理论 4.1 数据依赖 4.2 范式 4.3 关系模式的规范化.
資料表正規化.
吉林大学远程教育课件 数 字 逻 辑 (第十九讲) 主讲人 : 魏 达 学 时:48.
正規化 Normalization.
Chapter 3 正規化與各種合併.
資料庫簡介 郭士煒 助教.
表格正規化簡介 講授大綱: 第一正規化 資料表的切割 第二正規化 第三正規化 Boyce/Codd正規化 第四正規化 第五正規化
数字电子技术 Digital Electronics Technology
30 利用畢氏定理,計算下列各直角三角形中, 未知邊長 x 的值: (1) x2+( )2=( )2 x= 因為 x>0, 所以 x=3。
第五章 关系数据理论 关系模型有严格的数学理论基础,也是目前应用最广泛的数据模型,关系规范化是指导数据库设计的重要理论。一个好的关系数据库是应该既可以供人们方便地获取信息,而又不产生过多的不必要的重复存储问题。可以说,规范化理论是数据模型优化的理论基础,对其他数据库的逻辑设计同样具有理论上的意义。 2018年12月6日7时18分.
高等数学提高班 (省专升本) 教师: 裴亚萍 数学教研室: 东校区 2118 电话: 长号:
10.2 排列 2006年4月6日.
练习: 由三个不同的英文字母和三个不同的阿拉伯数字组成一个六位号码(每位不能重复),并且3个英文字母必须合成一组出现,3个阿拉伯数字必须合成一组出现,一共有多少种方法?
第26讲 解直角三角形的应用 考点知识精讲 中考典例精析 举一反三 考点训练.
二元一次聯立方程式 代入消去法 加減消去法 自我評量.
乘法公式 (1) 乘法分配律 (2) 和的平方公式 (3) 差的平方公式 (4) 平方差公式.
2 轴向拉伸和压缩 2-1 轴向拉伸与压缩的概念 2-2 内力-轴力·轴力图 2-3 拉、压杆内的应力 2-4 拉、压杆的变形·胡克定律
直线与平面平行的判定 市一中 徐小银.
中级会计实务 ——第三章 固定资产 主讲:孙文静
等腰三角形的判定.
第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式
第五章 相交线与平行线 三线八角.
第二十三章 旋转 图形的旋转 北京大学附属中学 鲍敬谊.
基础会计.
会计实务(第七讲) ——固定资产 讲师:天天老师.
孟 胜 奇.
9.1.2不等式的性质 周村实验中学 许伟伟.
1.理解力和运动的关系,知道物体的运动不需要力来维持。
第3章 关系数据库 内容提要 关系模型的数据结构 关系模型的常用术语 关系数据库的完整性概念 数据库的关系运算 函数依赖的定义
第五章关系数据库设计理论 5.1 数据依赖 5.2 范式 5.3 关系模式的规范化.
平行四边形判定的应用 (三角形的中位线定理).
Presentation transcript:

第4章 关系数据库设计理论 本章内容 4.1 问题的提出 4.2 规范化 4.3 数据依赖的公理系统* 4.4 小结 习 题

4.1 问题的提出 如何设计一个合适的关系数据库系统呢? 关键是关系数据库模式的设计,即应该构造几个关系模式,每个关系模式由哪些属性组成,又如何将这些相互关联的关系模式组建成一个适合的关系框,这些都是决定了整个系统的运行的效率,也是应用系统开发设计成败的因素之一。 实际上,关系数据库的设计必须在关系数据库规范化理论的指导下进行。

4.1.1 规范化理论概述 关系数据库设计理论主要包括三个方面的内容:函数依赖、范式(Normal Form)和模式设计。其中函数依赖起着核心作用,是模式分解和模式设计的基础,范式是模式分解的标准。 BACK

4.1.2 不合理的关系模式存在的问题 [例1] 要求设计学生-课程数据库,其关系模式SDC如下: SDC(SNO,SN,AGE,DEPT,MN,CNO,SCORE) 其中:SNO 表示学生学号 SN 表示学生姓名 AGE 表示学生年龄 DEPT 表示学生所在的系别 MN 表示系主任名 CNO 表示课程号 SCORE 表示成绩。

根据实际情况,这些数据有如下语义规定: 1)一个系有若干个学生,但一个学生只属于一个系; 即sno->dept. 2)一个系只能有一个系主任,但一个系主任可以同时兼几个系的系主任 ; 即 dept->mn 3) 一个学生可以选修多门功课,每门课程可被若干个学生选修; 4) 每个学生学习每门课程有一个成绩。 即(sno,cno)->score

SNO SN AGE DEPT MN CNO SCORE S1 赵红 20 计算机 张文斌 C1 90 C2 85 S2 王小明 17 外语 刘伟华 C5 57 C6 80 C7 C4 70 S3 吴小林 19 信息 75 S4 张涛 22 自动化 钟志强 93 图4.1 关系SDC

在进行数据库的操作时,会出现以下几方面的问题。 (1) 数据冗余。 系名, 学生姓名、年龄等等都要重复存储多次 (2) 插入异常。 (SNO,CNO)是主键。缺少一个都无法插入数据另外,若学生未选课,同样也不能进行插入操作。 (3) 删除异常。 删去学生数据,导致课程及教师信息丢失。如果某个学生不再选修某课程,有关该学生的其他信息也随之丢失。 (4) 修改异常。 如果某学生改名,则该学生的所有记录都要逐一修改SN的值;稍有不慎,就有可能漏改某些记录。 鉴于存在以上种种问题,我们可以得出这样的结论:SDC关系模式不是一个好的模式。一个“好”的模式应当不会发生插入异常、删除异常、更新异常、数据冗余应尽可能少。

为什么会发生这些问题呢? 这是因为这个模式中的函数依赖存在某些不好的性质。假设把这个单一的模式改造一下,分解成3个关系模式: 学生关系 S (SNO,SN,AGE,DEPT) 系关系 D (DEPT,MN) 选课关系 SC(SNO,CNO,SCORE)

S SNO SN AGE DEPT S1 赵红 20 计算机 S2 王小明 17 外语 S3 吴小林 19 信息 S4 张涛 22 自动化

D DEPT MN 计算机 张文斌 外语 刘伟华 信息 自动化 钟志强

图4.2 关系SDC经分解后的三关系S、D与SC SNO CNO SCORE S1 C1 90 C2 85 S2 C5 57 C6 80 C7 C4 70 S3 75 S4 93 图4.2 关系SDC经分解后的三关系S、D与SC

分解后的关系模式集是一个好的关系数据库模式。这三个关系模式都不会发生插入异常、删除异常的毛病,数据冗余也得到了尽可能地控制。 但要注意,一个好的关系模式并不是在任何情况下都是最优的,比如查询某个学生选修课程名及所在系的系主任时,要通过连接操作来完成(即由图4.2中的三张表,连接形成图4.1中的一张总表),而连接所需要的系统开销非常大,因此要以实际设计的目标出发进行设计。 练习题: 课后选择题1

4.2 规范化 4.2.1 函数依赖 定义4.1 设关系模式R(U,F),U是属性全集,F是U上的函数依赖集,X和Y 是U的子集,如果对于 ⒈ 函数依赖 定义4.1 设关系模式R(U,F),U是属性全集,F是U上的函数依赖集,X和Y 是U的子集,如果对于 R(U)的任意一个可能的关系r,对于X的每一个具体值,Y都有唯一的具体的值与之对应,则称X函数决定Y,或Y函数依赖于X,记X→Y。我们称X为决定因素,Y为依赖因素。当Y不函数依赖于X时,记作:X Y。当X→Y且Y→X时,则记作:X Y。

对于关系模式SDC: U={SNO,SN,AGE,DEPT,MN,CNO,SCORE} F={SNO→SN,SNO→AGE,SNO→DEPT,DEPT→MN,SNO→MN,(SNO,CNO)→SCORE} 一个SNO有多个SCORE的值与之对应,因此SCORE不能唯一地确定,即SCORE不能函数依赖于SNO,所以有:SNO SCORE, 同样有:CNO SCORE。 但是SCORE可以被(SNO,CNO)唯一地确定。所以可表示为:(SNO,CNO)→SCORE。

练习: 设有关系模式:商品(商品编号,商品大类,商品小类,商品名称,单价,数量,总价),试结合实际,分析该关系模式上可能存在的函数依赖。 商品编号→商品名称 商品编号→商品小类 商品小类→商品大类 商品编号→单价 (单价,数量) →总价

函数依赖有几点需要说明: (1) 平凡的函数依赖与非平凡的函数依赖 当属性集Y是属性集X的子集时,则必然存在着函数依赖X→Y,这种类型的函数依赖称为平凡的函数依赖。 也可表示为:X→Y,但Y⊆X 则称X→Y是平凡的函数依赖。 如:在关系SDC中,(SNO,CNO)→SNO。 如果Y不是X子集,则称X→Y为非平凡的函数依赖。 也可表示为: X→Y,但Y⊆X 则称X→Y是非平凡的函数依赖。 如:(sno,cno)→score 若不特别声明,我们讨论的都是非平凡的函数依赖。 (2) 函数依赖与属性间的联系类型有关 ① 在一个关系模式中,如果属性X与Y有1:1联系时,则存在函数依赖X→Y,Y→X,即X Y。 例如,当学生没有重名时,SNO SN。

练习题: 课后选择题2 ② 如果属性X与Y有m:1的联系时,则只存在函数依赖X→Y。 例如: SNO与AGE,DEPT之间均为m:1联系, 所以有SNO→AGE ,SNO→DEPT。 ③ 如果属性X与Y有m:n的联系时,则X与Y之间不存在任何函数依赖关系。 例如: 一个学生可以选修多门课程,一门课程又可以为多个学生选修,所以SNO与CNO之间不存在函数依赖关系。 由于函数依赖与属性之间的联系类型有关,所以在确定属性间的函数依赖时,可以从分析属性间的联系入手,便可确定属性间的函数依赖。 练习题: 课后选择题2

(3) 函数依赖的语义范畴的概念 我们只能根据语义来确定一个函数依赖,而不能按照其形式化定义来证明一个函数依赖是否成立。例如,对于关系模式S,当学生不存在重名的情况下,可以得到: SN→AGE、SN→DEPT 这种函数依赖关系,必须是在没有重名的学生条件下才成立,否则就不存在函数依赖了。所以函数依赖反映了一种语义完整性约束,是语义的要求。

(4) 函数依赖关系的存在与时间无关 函数依赖是指关系中所有元组应该满足的约束条件,而不是指关系中某个或某些元组所满足的约束条件。 例如:对于关系模式S,假设没有给出无重名的学生这种语义规定,则即使当前关系中没有重名的记录,也不能有“SN->AGE、SN->DEPT”,因为在后续的对表S的操作中,可能马上会增加一个重名的学生的,而使这些函数依赖不能成立。 所以函数依赖关系的存在与时间无关,而只与数据间的语义规定有关。

(5) 函数依赖可以保证关系分解的无损连接性 设R(X,Y,Z),X、Y、Z为不相交的属性集合,如果X→Y或X→Z则有 R(X,Y,Z)=R[X,Y]∞R[X,Z], 其中R[X,Y]表示关系R在属性(X,Y)上的投影,即R等于两个分别含决定因素X的投影关系(分别是R[X,Y]与R[X,Z])在X上的自然连接,这样便保证了关系R分解后不会丢失原有的信息,称作关系分解的无损连接性。

例如,对于关系模式S(SNO,SN,AGE,DEPT), 有SNO->SN,SNO->(AGE,DEPT) S(SNO,SN,AGE,DEPT)=S1(SNO,SN)∞S2(SNO,AGE,DEPT) 也就是说,S的两个投影关系S1、S2在SNO上的自然连接可复原关系S。 这一性质非常重要,在后面的关系规范化中要用到。

⒉ 函数依赖的基本性质 (1) 投影性 根据平凡的函数依赖的定义可知,一组属性函数决定它的所有子集。 例如,在关系SDC中,(SNO,CNO)→SNO和(SNO,CNO)→CNO。 说明:投影性产生的是平凡的函数依赖,需要时也能使用的。 (2) 扩张性 若X→Y且W→Z,则(X,W)→(Y,Z)。 例如,SNO→(SN,AGE),DEPT→MN, 则有(SNO,DEPT)→(SN,AGE,MN)。 说明:扩张性实现了两函数依赖决定因素与被决定因素的分别合并作用。

(3) 合并性 若X→Y且X→Z则必有X→(Y,Z)。 例如,在关系SDC中,SNO→(SN,AGE), SNO→DEPT,则有SNO→(SN,AGE,DEPT)。 说明:决定因素相同的两函数依赖,它们的被决定因素合 并后,函数依赖关系依然保存。 (4) 分解性 若X→(Y,Z),则X→Y且X→Z。很显然,分解性为合并性的逆过程。 说明:决定因素能决定全部,当然也能决定全部中的部分。 由合并性和分解性,很容易得到以下事实: X→A1,A2,…,An成立的充分必要条件是X→Ai(i=1,2,…,n)成立。

3.完全/部分函数依赖和传递/非传递函数依赖 定义4.2 设有关系模式R(U),U是属性全集,X和Y是U的子集,X→Y,并且对于X的任何一个真子集X‘,都有X‘ Y,则称Y对X完全函数依赖,记作 X f Y。 如果对X的某个真子集X‘,有X’→Y,则称Y对X部分函数依赖(Partial Functional Dependency),记作 X p Y。 例如,在关系模式SDC中,因为SNO SCORE, 且 CNO SCORE,所以有:(SNO,CNO) f SCORE。 而因为有SNO→AGE,所以有(SNO,CNO) p AGE。

传递函数依赖 定义4.3 设有关系模式R(U),U是属性全集,X,Y,Z是U的子集,若X→Y,(Y ⊈ X),但Y X,而Y→Z 则称Z对X传递函数依赖(Transitive Functional Dependency),记作:X t Z。 注意:如果有Y→X,则X Y,这时称Z对X直接函数依赖,而不是传递函数依赖。 如:关系模式SDC中, SNO->DEPT,但DEPT→SNO,而DEPT→MN, 则有SNO t MN。 当学生不存在重名的情况下,有SNO→SN,SN→SNO,SNO SN,SN →DEPT,这时DEPT对SNO是直接函数依赖,而不是传递函数依赖。

练习题: 课后选择题5 由F={AB→C,DC→E,D→B} 由投影性可知 AB→C ≡>A →C B→C DC →E ≡>D →E C →E D→B 再由传递函数依赖关系可知 A→E D→E 再由合并性可知 AD →E 练习题: 课后选择题8

4.2.2 码 在第2章中已给出有关码的概念。这里用函数依赖的概念来定义码。 定义4.4 设K为R(U,F)中的属性或属性集合,若K f U则K为R的候选码(或候选关键字或候选键)(Candidate key)。 若候选码多于一个,则选定其中的一个为主码(或称主键,Primary key)。

不包含在任何候选码中的属性称为非主属性或非码属性。 在最简单的情况,单个属性是码。 包含在任何一个候选码中的属性,叫做主属性。 不包含在任何候选码中的属性称为非主属性或非码属性。 在最简单的情况,单个属性是码。 最极端的情况,整个属性组U是码,称为全码(All-key)。 如在关系模式S(SNO,DEPT,AGE)中SNO是码,而在关系模式SC(SNO,CNO,SCORE)中属性组合(SNO,CNO)是码。

一个学生可以选听多门课程,一门课程可 被多个学生选听。 下面举个全码的例子: 关系模式TCS(T,C,S),属性T表示教师,C表示课程,S表示学生。 一个教师可以讲授多门课程, 一门课程可有多个教师讲授, 一个学生可以选听多门课程,一门课程可 被多个学生选听。 教师T,课程C,学生S之间是多对多关系,单个属性T、C、S或两个属性组合(T,C)、(T,S) 、(C,S)等均不能完全决定整个属性组U,只有(T,C,S)→U,所以这个关系模式的码为(T,C,S),即All-key。

找出已知关系模式R(U,F)的所有候选 键的方法: 1、查看函数依赖集F中的每个形如Xi→Yi的(i=1,……,n)函数依赖关系。看哪些属性在所有Yi(i=1,……,n)中没有出现过, 设没出现过的属性集为P(P=U-Y1-Y2……-Yn)。 则当P=φ(表示空集)时,转4 当P≠φ时,转2。 2、根据候选键的定义,候选键中应必含P(因为没有其它属性能决定P)。考察P: 若有P f U成立,则P为候选键,并且候选键只有一个P,转5结束 若P f U不成立,则转3。

3、P可以分别与{U-P}中的每一个属性合并,形成 P1,P2,……,Pm。再分别判断Pj f U(j=1,……,m) 是否成立?能成立则找到了一个候选键,没有则放弃。 合并一个属性若不能找到或不能找全候选键,可进一步 考虑P与{U-P}中的两个(或三个,四个,……)属性的 所有组合分别进行合并,继续判断分别合并后的各属性 组对U的完全函数决定情况……;如此直到找出R的所有 候选键为止。转5结束。(需要提醒的是:如若属性组K 已有K f U,则完全不必去考察含K的其它属性组合了, 显然它们都不可能再是候选键了)。

也可以用Armstrong公理来求候选码 4、若P=φ,则可以先考察Xi→Yi(i=1,……,n)中的单个Xi,判断是否有Xi f U?若成立则Xi为候选键。剩下不是候选键的Xi,可以考察它们两个或多个的组合,查看其是否能完全函数决定U,从而找出其它还有可能的候选键。转5结束。 5、本方法结束。 也可以用Armstrong公理来求候选码

4.3 数据依赖的公理系统* 数据依赖的公理系统是模式分解算法的理论基础, 下面先讨论函数依赖的一个有效而完备的公理系统—— Armstrong公理系统。 定义4.12 对于满足一组函数依赖F的关系模式R(U,F),其 任何一个关系r,若函数依赖X→Y都成立(即r中任意两 元组t,s,若t[X]=s[X],则t[Y]=s[Y]),则称F逻辑蕴 涵X→Y。 为了求得给定关系模式的码,为了从一组函数依赖 求得蕴涵的函数依赖,例如已知函数依赖集F,要问X→Y 是否为F所蕴含,就需要一套推理规则,这组推理规则是 1974年首先由Armstrong提出来的。 BACK

Armstrong公理系统 设U为属性集总体,F是U上的 一组函数依赖,于是有关系模式R(U,F)。对R (U,F)来说有以下的推理规则: l  A1 自反律(Reflexivity):若Y⊆X ⊆U,则 X→Y为F所蕴含。 l  A2 增广律(Augmentation):若X→Y为F所蕴 含,且Z ⊆ U,则XZ→YZ为F所蕴含。 l  A3 传递律(Transitivity):若X→Y及Y→Z为F 所含,则X→Z为F所蕴含。 注意:由自反律所得到的函数依赖均是平凡的 函数依赖,自反律的使用并不依赖于F。

根据A1,A2,A3这三条推理规则可以得到下面很有 用的推理规则: l  合并规则:由X→Y,X→Z,X→YZ。 l  伪传递规则:由X→Y,WY→Z,有XW→Z。 l  分解规则:由X→Y及Z⊆Y,有X→Z。 根据合并规则和分解规则,很容易得到这样一个重要事实: 引理4.1 X→A1A2…AK成立的充分必要条件是X→Ai成立 (i=1,2,…k)。 定义4.13 在关系模式R(U,F)中为F所蕴含的函数依赖的全 体叫做F的闭包,记为:F+。

定义4.14 引理4.2 设F为属性集U上的一组函数依赖,X包含于U, XF+={A|X→A能由F根据Armstrong公理导出},成为属性集 X关于函数依赖集F的闭包。 引理4.2 设F为属性集U上的一组函数依赖,X,Y包含于U, X→Y能由F根据Armstrong公理导出的充分必要条件是Y包 含于XF+。 于是,判定X→Y是否能由F根据Armstrong公理推导 出的问题,就转化为求出XF+的子集的问题。这个问题由 算法4.1解决了。

算法4.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+1) =U,则X(i+1)就是XF+,算法终止。 (6)若否,则i=i+1,返回第(2)步。

所以可知R只有一个候选键是AB。 [例8] 已知关系模式R(U,F), 其中U={A,B,C,D,E};F={AB→C,B→D,C→E, EC→B,AC→B}。 求(AB)F+。 解 由算法4.1,设X(0)=AB; 计算X(1);逐一扫描F集合中各个函数依赖,找左部 为A,B或AB的函数依赖。得到两个:AB→C,B→D。于是 X(1) =AB∪CD=ABCD。 因为X(0)≠ X(1),所以再找出左部为ABCD子集的那些 函数依赖,又得到C→E,AC→B,于是 X(2) = X(1) ∪BE=ABCDE。 因为X(2)已等于全部属性的集合,所以(AB)F+=ABCDE。 所以可知R只有一个候选键是AB。

练习1 设关系模式R(A,B,C,D,E),F={A→CD,BC →E,D →B,E →A}为R上的函数依赖集,试求R上的所有候选键。 R上的候选键有A、BC、E。 分析:属于P=φ情况 设① X(0)=A; 由于A->CD X(1)=ACD; 由于D->B X(2)=ABCD; 由于BC->E X(3)=ABCDE 所以(A)F+=ABCDE。 ② X(0)=BC; 由于BC->E X(1)=BCE; 由于E->A X(2)=ABCE; 由于A->CD X(3)=ABCDE 所以(BC)F+=ABCDE。

练习1 设关系模式R(A,B,C,D,E),F={A→CD,BC →E,D →B,E →A}为R上的函数依赖集,试求R上的所有候选键。 ③ X(0)=E; 由于E->A X(1)=AE; 由于A->CD X(2)=ACDE; 由于D->B X(3)=ABCDE 所以(E)F+=ABCDE。 ④ X(0)=D; 由于D->B X(1)=BD; 所以(D)F+=BD。 所以R的候选码有A、BC、E。

练习2 课后题三(6) 设R(A,B,C,D,E,F), 函数依赖集F={AB →E,AC →F,AD →B,B →C,C →D} R上的候选键有AB、AC、AD。 分析:属于P ≠ φ情况 设① X(0)=A; 所以(A)F+=A。 ② X(0)=AB; 由于AB->E X(1)=ABE; 由于B->C X(2)=ABCE; 由于AC->F,C->D X(3)=ABCDEF 所以(AB)F+=ABCDEF。

练习2 课后题三(6) 设R(A,B,C,D,E,F), 函数依赖集F={AB →E,AC →F,AD →B,B →C,C →D} ③ X(0)=AD; 由于AD->B X(1)=ABD; 由于B->C X(2)=ABCD; 由于AC->F,AB->E X(3)=ABCDEF 所以(E)F+=ABCDEF。 ④ X(0)=AC; 由于AC->F X(1)=ACF; 由于C->D X(2)=ACDF; 由于AD->B X(3)=ABCDF; 由于AB->E X(4)=ABCDEF 所以(AC)F+=ABCDEF。 所以R的候选码有AB、AD、AC。

练习3 R上的候选键有AB和BD。 设R(A,B,C,D,E), 函数依赖集F={AB →C,AB →E,A →D,BD →ACE} 分析:属于P ≠ φ且P f U不成立情况 设① X(0)=B; 所以(B)F+=B。 ② X(0)=AB; 由于AB->C,AB->E,A->D X(1)=ABCDE; 所以(AB)F+=ABCDE。 ③ X(0)=BD; 由于BD->ACE X(1)=ABCDE 所以(BD)F+=ABCDEF。 所以R的候选码有AB、BD。

练习4 设R(A,B,C,D,E),根据所给的函数依赖集,示R的所有候选键。 (1) 函数依赖集F={A →B,C →D,E →A}. (2)F={BC →A,A →BC,E →CD}; (3)F={B →CDE,A →B,C →D} (1) CE (2) EA、EBC (3) A

定义4.5 关系模式R中属性或属性组X并非R的主码,但X是另 外一个关系模式S的主码,则称X是R的外部码或外部关系 键(Foreign Key),也称外码。 如在SC(SNO,CNO,SCORE)中,单SNO不是主码, 但SNO是关系模式S(SNO,SN,SEX,AGE,DEPT)的主 码,则SNO是SC的外码。 主码与外码提供了一个表示关系间联系的手段。如 关系模式S与SC的联系就是通过SNO这个在S中是主码又在 SC中是外码的属性来体现的。

4.2.3 范式 关系数据库的规范化过程中为不同程度的规范化要求设立的不同的标准或准则称为范式(Normal Form)。满足最低要求的叫第一范式,简称1NF。在第一范式中满足进一步要求的为第二范式(2NF),其余以此类推。R为第几范式就可以写成R∈xNF(x表示某范式名)。

各个范式之间的集合关系可以表示为: 5NF⊂4NF ⊂ BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF 图4.3 各范式之间的关系 连接依赖 多值依赖 函数依赖 图4.3 各范式之间的关系

一个低一级范式的关系模式,通过模式分解可以转换为若干个高一级范式的关系模式的集合,这种过程就叫规范化。

4.2.4 第一范式 第一范式(First Normal Form)是最基本的规范化 形式,即关系中每个属性都是不可再分的简单项。 定义4.6 如果关系模式R所有的属性均为简单属性,即每个属 性都是不可再分的,则称R属于第一范式,简称1NF,记 作R∈1NF。 在关系数据库系统中只讨论规范化的关系,凡是非 规范化的关系模式必须转化成规范化的关系。在非规范 化的关系中去掉组合项就能转化成规范化的关系。每个 规范化的关系都是属于1NF。

[例2] 如职工号,姓名,电话号码组成一个表(一个人可 能有一个办公室电话和一个家里电话号码)规范成为1NF 有三种方法: 一是重复存储职工号和姓名。这样关键字是职工号与电话号码的组合。关系模式为:职工(职工号,姓名,电话号码)。 二是职工号为关键字,电话号码分为单位电话和住宅 电话两个属性。关系模式为:职工(职工号,姓名,单位 电话,住宅电话)。 三是职工号为关键字,但强制每条记录只能有一个电 话号码。关系模式为:职工(职工号,姓名,电话号码)。 以上三个方法,可按实际情况选取使用。

4.2.5 第二范式 1.第二范式的定义 定义4.7 如果关系模式R∈1NF,R(U,F)中的所有非主属 是属于第二范式(Second Normal Form),简称2NF, 记作R∈2NF。 从定义可知,满足第二范式的关系模式R中,不可能 有某非主属性对某候选关键字存在部分函数依赖。下面 让我们来分析下4.1.2节中给出的关系模式SDC。

SNO→AGE,(SNO,CNO) p AGE SNO→DEPT,(SNO,CNO) p DEPT,DEPT→MN 在关系模式SDC中,它的关系键是(SNO,CNO)的属性组合,函数依赖关系有: (SNO,CNO) f SCORE SNO→SN,(SNO,CNO) p SN SNO→AGE,(SNO,CNO) p AGE SNO→DEPT,(SNO,CNO) p DEPT,DEPT→MN SNO t MN, (SNO,CNO) p MN 我们可以用函数依赖图表示以上函数依赖关系,如图4.4所示。 由关键字的定义可知SGD中的关键字为(SNO,CNO),因此SN、AGE、DEPT、MN均为非主属性,而非主属性中只有成绩是完全函数依赖于主关键字,其他属性是部分函数依赖于主关键字,因此,关系模式SDG不符合2NF的定义,这种情况往往在数据库中是不允许的,也正是由于关系中存在着复杂的函数依赖,才导致数据操作中出现了数据冗余、插入异常、删除异常、修改异常等弊端。

p DEPT SNO t MN p f SCORE CNO SN p p AGE 图4.4 SDC中函数依赖图

2. 2NF的规范化 2NF规范化是指把1NF关系模式通过投影分解,消除 非主属性对候选关键字的部分函数依赖,转换成2NF关系 模式的集合的过程。 分解时遵循的原则是“一事一地”,让一个关系只描述 一个实体或实体间的联系。如果多于一个实体或联系, 则进行投影分解。 据此我们可以将关系模式SDC分解成两个关系模式: SD(SNO,SN,AGE,DEPT,MN),描述学生实体 SC(SNO,CNO,SCORE),描述学生与课程的联系。

对于分解后的关系模式SD的码为SNO,关系模式SC的候选关键字为(SNO,CNO),非主属性对候选关键字均是完全函数依赖的,这样就消除了非主属性对候选关键字的部分函数依赖。即SD∈2NF,SC∈2NF,它们之间通过SC中的外键SNO相联系,需要时再进行自然联接,能恢复成原来的关系,这种分解不会丢失任何信息,具有无损连接性。 分解后的函数依赖图如图4.5和4.6所示。

图4.5 SD中的函数依赖关系图 图4.6 SC中的函数依赖关系 SN SNO AGE SCORE SNO CNO DEPT MN 图4.5 SD中的函数依赖关系图 图4.6 SC中的函数依赖关系

注意:如果R的候选关键字均为单属性,或R的全体属性均为主属性,则R∈2NF。 例如,在讲述全码的概念时给出的关系模式TCS(T,C,S),(T,C,S)三个属性的组合才是其唯一的候选关键字即关系键,T,C,S均是主属性,不存在非主属性,所以也不可能存在非主属性对候选关键字的部分函数依赖,因此TCS∈2NF。

4.2.6 第三范式 1.第三范式的定义 定义4.8 如果关系模式R∈2NF,R(U,F)中所有非主属性对任 式(Third Normal Form),简称3NF,记作 R∈3NF。 第三范式具有如下性质:

(1) 如果R∈3NF,则R也是2NF。 证明:采用反证法。设R∈3NF,但R∉2NF。则根据判定 2NF的定义知,必有非主属性Ai(Ai∊U,U是R的所有属性 集),候选关键字K和K的真子集K’(即K’⊂K)存在,使得 有K’→Ai。由于Ai是非主属性,所以Ai-K(代表空), Ai- K’  。由于K’ ⊂ K,所以K-K’  ,并可以断定K’ K。这样有K→K’且K’ K,K’→Ai,且Ai-K  ,Ai- K’  ,即有非主属性Ai传递函数依赖于候选键K(若觉得 K’K,则可以在K’上合并一个Aj,设Aj亦为非主属性,此 时仍有K→K’Aj且K’Aj ⊈ K,K’Aj K,K’Aj→Ai),所以 R∉3NF,与题设R∈3NF相矛盾。从而命题得证。

2NF的关系模式解决了1NF中存在的一些问题,但2NF的关系模式SDC在进行数据操作时,仍然存在下面一些问题: (2) 如果R∈2NF,则R不一定是3NF。 例如:前面讲的关系模式SDC分解为SD和SC,其中SC是3NF,但SD就不是3NF,因为SD中存在非主属性对候选关键字的传递函数依赖:SNO→DEPT,DEPT→MN,即SNO t MN。 2NF的关系模式解决了1NF中存在的一些问题,但2NF的关系模式SDC在进行数据操作时,仍然存在下面一些问题: (1) 数据冗余。如果每个系名和系主任的名字存储的次数等于该系学生的人数。 (2) 插入异常。当一个新系没有招生时,有关该系的信息无法插入。 (3) 删除异常。如某系学生全部毕业而没有招生时,删除全部学生的记录也随之删除了该系的有关信息。 (4) 修改异常。如更换系主任时仍需要改动较多的学生记录。 之所以存在这些问题,是由于在SDC中存在着非主属性对候选关键字的传递依赖。消除这种依赖就转换成了3NF。

练习: 设有关系模式R(A,B,C,D,E),R中的属性A、B、D、E均不可再分解,R上的函数依赖集F={AB→C,C →E,AB →D},若只基于函数依赖进行讨论,试分析R最高属于第几范式。 R的候选键是AB,R中非主属性C、D、E均完全函数依赖于候选键,但存在非主属性E对候选键AB的传递函数依赖,因此R最高属于2NF.

2.3NF的规范化 3NF规范化是指把2NF关系模式通过投影分解,消除非主属性对候选关键字的传递函数依赖,而转换成3NF关系模式集合的过程。 3NF规范化同样遵循“一事一地”原则。我们继续将只属于2NF的关系模式SD规范为3NF。根据“一事一地”原则可SD分解为: S(SNO,SN,AGE,DEPT),描述学生实体;D(DEPT,MN),描述系的实体。 分解后S和D的主键分别为SNO和DEPT,不存在传递函数依赖。所以S∈3NF,D∈3NF。S和D的函数依赖分别如图4.7和图4.8所示。

图4.7 S中的函数依赖关系图 图4.8 D中的函数依赖关系图 SN DEPT MN SNO AGE DEPT 图4.7 S中的函数依赖关系图 图4.8 D中的函数依赖关系图

(2)不存在插入异常。如当一个新系没有学生时,该系的信息可以直接插入到关系D中,而与学生关系S无关。 由以上两图可以看出,关系模式SD由2NF分解为3NF后,函数依赖关系变得更加简单,既没有非主属性对码的部分依赖,也没有非主属性对码的传递依赖,解决了2NF中存在的四个问题,因此,分解后的关系模式S和D具有以下特点: (1)数据冗余度降低了。如系主任的名字存储的次数与该系的学生人数无关,只在关系D中存储一次。 (2)不存在插入异常。如当一个新系没有学生时,该系的信息可以直接插入到关系D中,而与学生关系S无关。 (3)不存在删除异常。如当要删除某系的全部学生而仍然保留该系的有关信息时,可以只删除学生关系S中的相关记录,而不影响系关系D中的数据。 (4)不存在修改异常。如更换系主任时,只需修改关系D中一个相应元组的MN属性值,从而不会出现数据的不一致现象。 SDC规范化到3NF后,所存在的异常现象已经全部消失。但是,3NF只限制了非主属性对码的依赖关系,而没有限制主属性对码的依赖关系。如果发生了这种依赖,仍有可能存在数据冗余、插入异常、删除异常和修改异常。这时,则需对3NF进一步规范化,消除主属性对码的依赖关系,向更高一级的范式BCNF转换。

4.2.7 BC范式 1.BC范式的定义 定义4.9 如果关系模式R∈1NF,且所有的函数依赖X→Y(Y不包含于 X,即Y∈X),决定因素X都包含了R的一个候选码,则称R属于BC范 式(Boyce-Codd Normal Form),记作 R∈BCNF。 由BCNF的定义可以得到以下结论,一个满足BCNF的关系模式有: (1)所有非主属性对每一个候选码都是完全函数依赖。 (2)所有的主属性对每一个不包含它的候选码都是完全函 数依赖。 (3)没有任何属性完全函数依赖于非码的任何一组属性。

由于R∈BCNF,按定义排除了任何属性对候选码的传 递依赖与部分依赖,所以R∈3NF。但若R∈3NF,则R未必属于BCNF。下面举例说明。 [例3] 设有关系模式SCS(SNO,SN,CNO,SCORE),其 中SNO代表学号,SN代表学生姓名,并假设不重名,CNO 代表课程号,SCORE代表成绩。可以判定,SCS有两个候 选键(SNO,CNO)和(SN,CNO),其函数依赖如下: SNO SN (SNO,CNO)→SCORE (SN,CNO)→SCORE

唯一的非主属性SCORE对键不存在部分函数 依赖,也不存在传递函数依赖。所以SCS∈3NF。 但是,因为SNO SN,即决定因素SNO或SN不包 含候选键,从另一个角度说,存在着主属性对键 的部分函数依赖:(SNO,CNO) p SN,(SN, CNO) p SNO,所以SCS不是BCNF。正是存在着这 种主属性对键的部分函数依赖关系,造成了关系 SCS中存在着较大的数据冗余,解决这一问题的 办法仍然是通过投影分解进一步提高范式的等 级,将其规范到BCNF。

2.  BCNF规范化 BCNF规范化是指把3NF的关系模式通过投影分解转换 成BCNF关系模式的集合。 下面以3NF的关系模式SCS为例,来说明BCNF规范化 的过程。 [例4] 将SCS(SNO,SN,CNO,SCORE)规范到BCNF。 SCS产生数据冗余的原因是因为在这个关系中存在两个 实体,一个为学生实体,属性有SNO,SN;另一个为选课 实体,属性有SNO,CNO和SCORE。根据分解的原则,我们 可以将SCS分解成如下两个关系: S(SNO,SN),描述学生实体 SC(SNO,CNO,SCORE),描述学生与课程的联系。

图 4.9 S中的函数依赖关系图 图4.10 SC中的函数依赖关系图 对于S,有两个候选码SNO和SN;对于SC,主码为(SNO, CNO)。在这两个关系中,无论主属性还是非主属性都不存在对 码的部分函数依赖和传递依赖,S∈BCNF,SC∈BCNF。 分解后,S和SC的函数依赖分别如图4.9和图4.10所示。 SNO SCORE SNO SN CNO 图 4.9 S中的函数依赖关系图 图4.10 SC中的函数依赖关系图

关系SCS转换成BCNF后,数据冗余度明显降低。学生 一条学生记录中相应的SN值即可,从而不会发生修改异 常。 下面再举一个有关BCNF规范化的实例。 [例5] 设有关系模式STK(S,T,K),S表示学生,T表 示教师,K表示课程。语义假设是,每一位教师只讲授 一门课程;每门课程由多个教师讲授;某一学生选定某 门课程,就对应一个确定的教师。 根据语义假设,STK的函数依赖是:(S,K)→T, (S,T)→K,T→K。 函数依赖图如图4.11所示。

S S T K K T 图4.11 STK中的函数依赖关系

STK是3NF,因为没有任何非主属性对码的传递依赖或部分依 赖(因为STK中没有非主属性)。但STK不是BCNF关系,因为有 这里(S,K),(S,T)都是候选码。 STK是3NF,因为没有任何非主属性对码的传递依赖或部分依 赖(因为STK中没有非主属性)。但STK不是BCNF关系,因为有 T→K ,T是决定因素,而T不包含候选码。 对于不是BCNF的关系模式,仍然存在不合适的地方。非BCNF 的关系模式STK可分解为ST(S,T)和TK(T,K),它们都是 BCNF。 3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分 离程度的测试。一个模式中的关系模式如果都属于BCNF,那么 在函数依赖范畴内,它已实现了彻底的分离,已消除了插入和 删除异常。3NF的“不彻底”性表现在可能存在主属性对候选码的 部分依赖和传递依赖。

R的候选键是AB,且每个函数依赖的决定因素都含有码AB,因此R属于BCNF. 设有关系模式R(A,B,C,D,E),R中属性均不可再分解,若只基于函数依赖进行讨论,试根据给定的函数依赖集F,分析R最高属于第几范式。 (1) F={AB→C,AB→D,ABC→E}; (2) F={AB→C,AB→D,AB→E}; (3) F={AB→C,AB→E,A→D,BD→ACE}. R的候选键是AB,且每个函数依赖的决定因素都含有码AB,因此R属于BCNF. R的候选键是AB,而F中每个函数依赖都是非平凡函数依赖,且左部都包含有候选键AB,因此可判定R属于BCNF. R的候选键是AB和BD,R中非主属性C和E都直接且完全函数依赖于候选键AB和BD,但存在主属性D对候选键AB的部分函数依赖(或说明为:A→D而A不包含任一码),因此R最高属于3NF.

试说明下列关系模式最高属于几范式,并说明理由。 (1)R(X,Y,Z) F={Y->Z,Y->X,X->YZ} R的候选码为X和Y,因为X->YZ,所以X->Y,X->Z,由于F中有Y->Z,Y->X,因此Z是直接函数依赖于X,而不是传递依赖于X。又因为F的每一函数依赖的左部都包含了任一候选码,因些R属于BCNF。 (2)R(X,Y,Z) F={XY->Z} R的候选码为XY,而且F中函数依赖的左部包含了候选码XY,因此R属于BCNF。 (3)R(X,Y,Z) F={Y->Z,XZ->Y} R的候选码为XY和XZ,R中所有属性都是主属性,不存在非主属性对的候选关键字的传递依赖,因些R属于3NF。

4.2.8 多值依赖与4NF 1. 多值依赖 (1) 多值依赖的定义 一个关系属于BCNF范式,是否就已经很完美了呢? 1.     多值依赖 (1) 多值依赖的定义 一个关系属于BCNF范式,是否就已经很完美了呢? 为此,我们先看一个例子。 [例6] 假设学校中一门课程可由多名教师教授,教学中 他们使用相同的一套参考书,这样我们可用如图4.12的 非规范化的关系来表示课程C、教师T和参考书R间的关 系。 如果我们把图4.12的关系CTR转化成规范化的关系, 如图4.13所示。

课程C 教员T 参考书R 数据库系统概论   计算数学 萨师煊 王珊 张平 周峰 数据库原理与应用 数据库系统 SQL Server 2000 数学分析 微分方程 图4.12 关系CTR

课程C 教师T 参考书R 数据库系统概论 计算数学 萨师煊 王珊 张平 周峰 数据库原理与应用 数据库系统 SQL Server 2000 数学分析 微分方程 图4.13 规范后的关系CTR

由此可以看出,规范后的关系模式CTR,只有唯一的一个 函数依赖(C,T,R)→U(U即关系模式CTR的所有属性的集 合),其码显然是(C,T,R),即全码,因而CTR属于BCNF范 式。但是进一步分析可以看出,CTR还存在着如下弊端: ① 数据冗余大。课程、教师和参考书都被多次存储。 ② 插入异常。若增加一名教授“计算数学”的教师“李静” 时,由于这个教师也使用相同的一套参考书,所以需要 添加两个元组,即:(计算数学,李静,数学分析)和 (计算数学,李静,微分方程)。 ③ 删除异常。若要删除某一门课的一本参考书,则与该参 考书有关的元组都要被删除,如:删除“数据库系统概 论”课程的“数据库系统”,则需要删除(数据库系统概 论,萨师煊,数据库系统)和(数据库系统概论,王 珊,数据库系统)两个元组。

产生以上弊端的原因主要有以下两方面: ① 对于关系CTR中的 C的一个具体值来说,有多个T 值与其相对应;同样,C与R间也存在着类似的联系。 ② 对于关系CTR中的一个确定的C值,与其所对应的 一组T值与R值无关。如:与“数据库系统概论”课程对应的 一组教师与此课程的参考书毫无关系。 从以上两个方面可以看出,C与T间的联系显然不是 函数依赖,在此我们称之为多值依赖(Multivalued Dependency,MVD)。

定义4.10 设有关系模式R(U),U是属性全集,X,Y,Z是属性集U的 子集,且Z=U-X-Y,如果对于R的任一关系,对于X的一个确定 值,存在的一组值与之对应,且Y的这组值仅仅决定于X的值而 与Z值无关,此时称Y多值依赖于X,或X多值决定Y,记作: X→→Y。 在多值依赖中,若X→→Y且Z=U-X-Y≠φ,则称X→→Y是非 平凡的多值依赖,否则称为平凡的多值依赖。 如:在关系模式CTR中,对于某一C、R属性值组合(数据库 系统概论,数据库系统)来说,有一组T值{萨师煊,王珊},这 组值仅仅决定与课程C上的值(数据库系统概论)。也就是说, 对于另一个C、R属性值组合(数据库系统概论,SQL Server 2000),它对应的一组T值仍是{萨师煊,王珊},尽管 这时参考书R的值已经改变了。 因此T多值依赖于C,即:C→→T。

练习 设关系模式R的属性集U={A,B,C},r是基于R的一个关系,且R上有多值依赖A→→B成立。若已知r中存在元组(a1,b1,c1),(a1,b2,c2)和(a1,b3,c3),则r中至少还有哪些元组? 至少有(a1,b1,c2) (a1,b1,c3) (a1,b2,c1) (a1,b2,c3)(a1,b3,c1) (a1,b3,c2) 成立。

(2)  多值依赖与函数依赖的区别 ① 在关系模式R中,函数依赖X→Y的有效性仅仅决定 于X、Y这两个属性集,不涉及第三个属性集,而在多值 依赖中,X→→Y在属性集U(U=X+Y+Z)上是否成立,不 仅要检查属性集X、Y上的值,而且要检查属性集U的其余 属性Z上的值。因此,如果X→→Y在属性集W(W⊂U)上 成立,而在属性集U上不一定成立,所以,多值依赖的有 效性与属性集的范围有关。 如果在R(U)上有X→→Y,在属性集W(W ⊂ U)上 也成立,则称X→→Y为R(U)的嵌入型多值依赖。 ② 如果在关系模式R上存在函数依赖X→Y,则任何Y‘ 包含于Y均有X→Y‘成立,而多值依赖X→→Y在R上成立, 但不能断言对于任何Y'包含于Y有X→→Y'成立。

(3)多值依赖的性质 ① 多值依赖具有对称性。即若X→→Y,则X→→Z,其 中Z=U-X-Y。 ② 多值依赖具有传递性。即若X→→Y,Y→→Z,则 X→→Z-Y。 ③ 函数依赖可看作是多值依赖的特殊情况。即若 X→Y,则X→→Y。 ④ 函数依赖合并性。即若X→→Y,X→→Z,则 X→→YZ。 ⑤ 多值依赖分解性。即若X→→Y,X→→Z,则X→→ (Y∩Z),X→→Y-Z,X→→Z-Y均成立。这说明,如 果两个相交的属性子集均多值依赖于另一个属性子集, 则这两个属性子集因相交而分割成的三部分也都多值依 赖于该属性子集。

2.第四范式(4NF) (1) 第四范式(4NF)的定义 在4.2.8节中我们分析了关系CTR虽然属于BCNF,但还存 在着数据冗余、插入异常和删除异常的弊端,究其原因就是 CTR中存在非平凡的多值依赖,而决定因素不是码。因而必 须将CTR继续分解,如果分解成两个关系模式CTR1(C,T) 和CTR2(C,R),则它们的冗余度会明显下降。从多值依赖 的定义分析CTR1和CTR2,它们的属性间各有一个多值依赖 C→→T,C→→R,都是平凡的多值依赖。因此,含有多值依 赖的关系模式中,减少数据冗余和操作异常的常用方法是将 关系模式分解为仅有平凡的多值依赖的关系模式。

定义4.11 设有一关系模式R(U),U是其属性全集,X、Y是U 的子集,D是R上的数据依赖集。如果对于任一多值依赖 X→→Y,此多值依赖是平凡的,或者X包含了R的一个候 选码,则称关系模式R是第四范式的,记作:R∈4NF。 由此定义可知:关系模式CTR分解后产生的CTR1 (C,T)和CTR2(C,R)中,因为C→→T,C→→R均是 平凡的多值依赖,所以CTR1和CTR2都是4NF。 经过上面分析可以得知:一个BCNF的关系模式不一 定是4NF,而4NF的关系模式必定是BCNF的关系模式,即 4NF是BCNF的推广,4NF范式的定义涵盖了BCNF范式的一 定。

(2)  4NF的分解 把一个关系模式分解为4NF的方法与分解为BCNF的方 法类似,就是当把一个关系模式利用投影的方法消去非 平凡且非函数依赖的多值依赖,并具有无损连接性。 [例7] 设有关系模式R(A,B,C,E,F,G),数据依赖 集D={A→→BGC,B→AC,C→G},将R分解为4NF。 解:利用A→→BGC,可将R分解为R1({ABCG}, {A→→BGC,B→AC,C→G})和R2({AEF},{ }),其中 R2既无函数依赖又无多值依赖,其已是4NF的关系模式。 而R1根据4NF的定义还不是4NF的关系模式。 再利用B→AC对R1再分解为R11({ABC},{B→AC}) 和R12({BG},{ }),显然R11、R12都是4NF的关系模式 了。

由此对R分解得到的三个关系模式R11({ABC}, {B→AC})、R12({BG},{ })和R2({AEF}, { }),它们都属于4NF,但此分解丢失了函数依赖 {C→G}。若最后一次分解利用到函数依赖C→G来 做,则由此得到R的另一分解的三个关系模式R11 ({ABC},{B→AC})、R12({CG},{C→G})和R2 ({AEF},{ }),它们同样都是属于4NF的关系模 式,且保持了所有的数据依赖。 这说明,4NF的分解结果不是唯一的,结果与选择数据依赖的次序有关。任何一个关系模式都可无损分解成一组等价的4NF关系模式,但这种分解不一定具有依赖保持性。

4.2.9 规范化小结 1、关系规范化过程 非规范关系 去掉嵌套属性或重复组(使每个属性及其值都成为 1NF 不可再分的数据项) 消去非主属性对候选KEY的部分fd 2NF 消去非主属性对候选KEY的传递fd 3NF 消去主属性对候选KEY的部分和传递fd BCNF

2、结论 1)3NF必定为2NF和1NF,反之不一定; 2)BCNF必为3NF,反之不一定; 3)3NF已在很大程度上控制了数据冗余; 5)3NF分解仍不够彻底(可能存在主属性对候选码的部 分fd和传递fd); 6)在fd范围内,BCNF下已完全消去了插入删除异常; 7)范式并非越高越好;范式越高,异常越少,但查询 操作越麻烦; 8)适可而止: 理论上:一般到3NF 9)分解不唯一。 BACK

4.3 数据依赖的公理系统* 定理4.2 Armstrong公理系统是有效的、完备的。 有效性:由F出发根据Armstrong公理推导出来的 每一个函数依赖一定在F+ 中; 完备性:F+中的每一个函数依赖,必定可以由F 出发根据Armstrong公理推导出来

定义4.16 如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (2) F中不存在这样的函数依赖X→A,使得F与 F-{X→A}等价。 (3) F中不存在这样的函数依赖X→A,X有真子 集Z使得F-{X→A}∪{Z→A}与F等价。

[例9] F={ A→B,B→A,B→C,A→C,C→A} 这里给出了F的两个最小依赖Fm1,Fm2。 Fm1={A→B,B→C,C→A} Fm2={A→B,B→A,A→C,C→A}

函数依赖保持性 定义4.17 设有关系模式R(U,F),Z⊆U,则Z所涉及到的F中 所有函数依赖为F在Z上的投影,记为∏Z(F), 有∏Z(F)={X→Y|(X→Y)∈F+且XY⊆Z}为函数依赖集F在Z 上的投影。 定义4.18 设R(U,F)的一个分解ρ={R1,R2,…,Rk}, 如果F等价于∏R1(F)∪∏R2(F)∪…∪∏Rk(F),则称分解 ρ具有函数依赖保持性。一个无损连接的分解不一定具有函数 依赖保持性;同样地,一个具有函数依赖保持性的分解也不一 定具无损连接性。 检验一个分解是否具有依赖保持性,实际上是检验 ∏R1(F)∪∏R2(F)∪…∪∏Rk(F)是否覆盖F。 BACK

p具有无损连接性。 Ri A B C D E F CF b11 b12 a3 b14 b15 a6 BE b21 a2 b23 b24 a5 设有关系模式R(A,B,C,D,E,F),其函数依赖集: F={A->B, C->F, E->B, CE->A},现有下列分解: p={CF, BE, CDE, AB}. 判断上述分解是否具有无损连接性。 p具有无损连接性。 Ri A B C D E F CF b11 b12 a3 b14 b15 a6 BE b21 a2 b23 b24 a5 b26 CDE b31 b32 a4 b36 AB a1 b43 b44 b45 b46 构造原始表

Ri A B C D E F CF b11 b12 a3 b14 b15 a6 BE b21 a2 b23 b24 a5 b26 CDE

Ri A B C D E F CF b11 b12 a3 b14 b15 a6 BE b21 a2 b23 b24 a5 b26 CDE CE->A的修改

Ri A B C D E F CF a3 a6 BE a2 a5 CDE a1 a4 AB 结果表

分解后的模式不具有无损连接性。 也不能保持原来的函数依赖。 设有关系模式R(U,F), 其中: U={A,B,C,D,E}, F={A->D, E->D, D->B, BC->D, DC->A} (1) 求出R的候选关键字。 (2) 若模式分解为p={AB, AE, CE, BCD, AC},判断其是否为无损连接分解?能保持原来的函数依赖吗? CE为R的候选关键字。 分解后的模式不具有无损连接性。 也不能保持原来的函数依赖。

Ri A B C D E AB a1 a2 AE a5 CE a3 BCD a4 AC Ri A B C D E AB a1 a2 a4 原始构造表 A->D的修改 Ri A B C D E AB a1 a2 a4 AE a5 CE a3 BCD AC Ri A B C D E AB a1 a2 a4 AE a5 CE a3 BCD AC E->D的修改 D->B的修改

Ri A B C D E AB a1 a2 a4 AE a5 CE a3 BCD AC Ri A B C D E AB a1 a2 a4 DC->A的修改 所以不具有无损连接性

设有关系模式R(A,B,C,D), F={A->C, C->A, B->AC, D->AC},试求: (1) 计算(AB)+. (2) 求R的关键字。 (3) 求F的最小函数依赖集。 (4) 将R分解成满足3NF并具有无损连接性与函数依赖依赖性。 (1)令X={AB},X(0)=AB,X(1)=ABC,X(2)=ABC, 故(AB)+=ABC。 (2) BD在F中所有函数依赖的右部均未出现,候选关键字中一 定包含BD,而(BD)+ = ABCD, 因此,BD是R惟一的候选关键字。

(3) 最小依赖集为:{A->C,C->A,B->A,D->A} 将F中的依赖右部属性单一化: F1={ AC,CA,BA,BC,DA,DC }。 去掉多余的函数依赖: 由BA,AC可得BC,所以F1中的BC是多余的; 由DA,AC可得DC,所以F1中的DC是多余的。 可得F2={ AC,CA,BA,DA }。 寻找函数依赖集的最小集: F2中所有依赖的左部都是单属性,不存在依赖左部有多余 的属性。 注:函数依赖集的最小集不是惟一的。

(4) 由(3)可求出满足3NF的具有依赖保持性的分解为 p={AC,AB,AD}。 判断其无损连接性如下图所示,从此表中可知p不具有无损连接性

令p=p {BD},BD是R的候选关键字。 p={AC, AB,DA,BD}。 Ri A B C D AC a1 a3 BA a2 为无损连接

假设某商业集团数据库中有一关系模式R(商店编号,商品编号,数量,部门编号,负责人)。如果规定: (1)每个商店的每种商品只在一个部门销售; (2)每个商店的每个部门只有一个负责人; (3)每个商店的每种商品只有一个库存数量。 试解答下列问题: (1)根据上述规定,写出关系模式R的基本函数依赖; (2)找出关系模式R的候选键; (3)试问关系模式R最高已经达到第几范式?为什么? (4)如果R不属于3NF,请将R分解成3NF模式集。

(1)有三个函数依赖: (商店编号,商品编号) →部门编号 (商店编号,部门编号) →负责人 (商店编号,商品编号) →数量 (2)R的候选码是 (商店编号,商品编号)。 (3)因为R中存在着非主属性“负责人”对候选码 (商店编号、商品编号)的传递函数依赖, 所以R属于2NF,R不属于3NF。 (4)将R分解成: R1(商店编号,商品编号,数量,部门编号) R2(商店编号,部门编号,负责人)

习 题 BACK 一、选择题 1、关系模式中数据依赖问题的存在,可能会导致库中数据插入异常,这是指( )。 A.插入了不该插入的数据   B.数据插入后导致数据库处于不一致状态 C.该插入的数据不能实现插入 D.以上都不对 2、若属性X函数依赖于属性Y时,则属性X与属性Y之间具有( )的联系。 A.一对一  B.一对多  C.多对一  D.多对多 3、关系模式中的候选键( )。 A.有且仅有一个  B.必然有多个   C.可以有一或多个  D.以上都不对 4、规范化的关系模式中,所有属性都必须是( )。 A.相互关联的   B.互不相关的   C.不可分解的   D.长度可变的 5、设关系模式R{A,B,C,D,E},其上函数依赖集F={AB→C,DC→E,D→B},则可导出的函数依赖是( )。 A.AD→E  B.BC→E  C.DC→AB  D.DB→A BACK

BACK 6、设关系模式R属于第一范式,若在R中消除了部分函数依赖,则R至少属于( )。 A.第一范式  B.第二范式  C.第三范式  D.第四范式 7、若关系模式R中的属性都是主属性,则R至少属于( )。 A.第三范式  B.BC范式  C.第四范式  D.第五范式 8、下列关于函数依赖的叙述中,哪一个是不正确的。 A.由X→Y,X→Z,有X→YZ B.由XY→Z,有X→Z或X→Z C.由X→Y,WY→Z,有XW→Z D.由X→Y及Z ⊆ Y,有X→Z 9、在关系模式R(A,B,C)中,有函数依赖集F={AB→C,BC→A},则R最高达到( )。 A.第一范式  B.第二范式  C.第三范式  D.BC范式 10、设有关系模式R(A,B,C),其函数依赖集F={A→B,B→C},则关系R最高达到( )。 A.1NF B.2NF C.3NF D.BCNF BACK

二、填空题 1、数据依赖主要包括________依赖、________依赖和连 接依赖。 2、一个不好的关系模式会存在___________、___________ 和___________等弊端。 3、设X→Y为R上的一个函数依赖,若________________________,则称Y完全函数依赖于X。 4、设关系模式R上有函数依赖X→Y和Y→Z成立,若______且______,则称Z传递函数依赖于X。 5、设关系模式R的属性集为U,K为U的子集,若_____, 则称K为R的候选键。 BACK

三、简答题 BACK 6、包含R中全部属性的候选键称______。不在任何候选键中的属性称______。 7、Armstrong公理系统是______的和______的。 8、第三范式是基于______依赖的范式,第四范式是基于______依赖的范式。 9、关系数据库中的关系模式至少应属于______范式。 10、规范化过程,是通过投影分解,把____________的关系模式“分解”为____________的关系模式。 三、简答题 1. 解释下列术语的含义:函数依赖、平凡函数依赖、非平凡函数依赖、部分函数依赖、完全函数依赖、传递函数依赖、范式、无损连接性、依赖保持性。 2. 给出2NF、3NF、BCNF的形式化定义,并说明它们之间的区别和联系。 3. 什么叫关系模式分解?为什么要做关系模式分解?模式分解要遵循什 么准则? 4.试证明全码的关系必是3NF,也必是BCNF。 BACK

BACK 5. 要建立关于系、学生、班级、研究会等信息的一个关系数据库。规 5. 要建立关于系、学生、班级、研究会等信息的一个关系数据库。规 定:一个系有若干专业、每个专业每年只招一个班,每个班有若干学生,一 个系的学生住在同一个宿舍区。每个学生可参加若干研究会,每个研究会有 若干学生。学生参加某研究会,有一个入会年份。 描述学生的属性有:学号、姓名、出生年月、系名、班号、宿舍区。 描述班级的属性有:班号、专业名、系名、人数、入校年份。 描述系的属性有:系号、系名、系办公室地点、人数。 描述研究会的属性有:研究会名、成立年份、地点、人数。 试给出上述数据库的关系模式;写出每个关系的最小依赖集(即基本的 函数依赖集,不是导出的函数依赖);指出是否存在传递函数 依赖;对于 函数依赖左部是多属性的情况,讨论其函数依赖是完全 函数依赖还是部分 函数依赖,指出各关系的候选键、外部键。 6.设有关系模式R(A,B,C,D,E,F),函数依赖集F={(A,B) →E,(A,C)→F,(A,D)→B,B→C,C→D},求出R的所有候选关 键字。 7.设有关系模式R(X,Y,Z),函数依赖集为F={(X,Y)→Z}。请确定SC的范式等级,并证明。 BACK

8.设有关系模式R(A,B,C,D,E,F),函数依赖集F={A→(B, C),(B,C)→A,(B,C,D)→(E,F),E→C}。试问:关系模式 R是否为BCNF范式,并证明结论。 9.设有关系模式R(E,F,G,H),函数依赖F={E→G,G→E,F→(E, G),H→(E,G),(F,H)→E} (1)  求出R的所有候选关键字; (2)  根据函数依赖关系,确定关系模式R属于第几范式; (3)  将R分解为3NF,并保持无损连接性和函数依赖保持性; (4)  求出F的最小函数依赖集。 10.试问下列关系模式最高属于第几范式,并解释其原因。 (1)R(A,B,C,D),F={B→D,AB→C}。 (2)R(A,B,C,D,E),F={AB→CE,E→AB,C→D}。 (3)R(A,B,C,D),F={B→D,D→B,AB→C}。 (4)R(A,B,C),F={A→B,B→A,A→C}。 (5)R(A,B,C),F={ A→B,B→A,C→A }。 (6)R(A,B,C,D),F={A→C,D→B}。 (7)R(A,B,C,D),F={A→C,CD→B}。 BACK