第六章 关系数据理-2

1、An Introduction to Database System数据库系统概论数据库系统概论An Introduction to Database System第六章第六章 关系数据理论关系数据理论- -续续2 2An Introduction to Database System回顾回顾v规范化规范化v函数依赖函数依赖v范式范式v1NFv2NFv3NFvBCNFAn Introduction to Database System练习一练习一v 设计关于供应商供应零件的数据库，要求达到设计关于供应商供应零件的数据库，要求达到3NFv 最初的设计：最初的设计：R(S#, Sname, Cit

2、y, Status, P#, Pname, Color, Weight,QTY ) 主码：主码：(S#, P#) 函数依赖：函数依赖：S#Sname, S# Status, S# City, City Status, P# Pname, P# Color, P# Weight (S#,P#)QTYAn Introduction to Database System分解分解可见，其中有部分依赖，还有传递依赖。该模式仅为可见，其中有部分依赖，还有传递依赖。该模式仅为1NF第一步分解第一步分解，消除部分依赖，得到：，消除部分依赖，得到：R1(S#, P#, QTY)，(S#, P#)为码为码R2(S

3、#, Sname, City, Status)， S#为码为码R3(P#, Pname, Color, Weight)， P#为码为码其中，其中，R1和和R3都已达到都已达到BCNF，但，但R2还存在传递依赖，还存在传递依赖，仅仅是仅仅是2NF第二步分解第二步分解，消除，消除R2中的传递依赖，得到：中的传递依赖，得到：R2-1(S#, Sname, City)， S#为码为码R2-2(City, Status)， City为码为码这样，这样，R1, R2-1, R2-2和和R3就是达到就是达到BCNF的关系模式的关系模式An Introduction to Database System6.2

4、 规范化规范化6.2.1 函数依赖函数依赖6.2.2 码码6.2.3 范式范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖多值依赖6.2.8 4NF6.2.9 规范化小结规范化小结An Introduction to Database System6.2.7 多值依赖多值依赖例9 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。An Introduction to Database System课课 程程 C教教 员员 T参参 考考 书书 B 物理物理数学数学 计算数学计算数学李李 勇勇王王 军军

5、 李李 勇勇张张 平平 张张 平平周周 峰峰李勇李勇 普通物理学普通物理学光学原理光学原理 物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析. 多值依赖（续）多值依赖（续）v 非规范化关系An Introduction to Database System普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李

6、 勇勇张张 平平张张 平平张张 平平李勇李勇 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学计算数学计算数学 参考书B教员T课程C多值依赖（续）多值依赖（续）v 用二维表表示Teachingv Teaching候选码？v 具有唯一候选码(C，T，B)， 即全码v Teaching属于什么范式？v TeachingBCNF An Introduction to Database System多值依赖（续）多值依赖（续） Teaching模式中存在的问题(1)数据冗余度大 (2)插入操作复杂(3) 删除操作复杂(4) 修改操

7、作复杂存在多值依赖普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李 勇勇张张 平平张张 平平张张 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学 参考书B教员T课程CAn Introduction to Database System多值依赖（续）多值依赖（续）v 定义定义6

8、.9 设R(U)是一个属性集U上的一个关系模式， X、 Y和Z是U的子集，并且ZUXY。关系模式R(U)中多值依赖 XY成立，当且仅当对R(U)的任一关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关v 例 Teaching（C, T, B）An Introduction to Database System多值依赖（续）多值依赖（续）v多值依赖的另一个等价的形式化的定义： 在R（U）的任一关系r中，如果存在元组t，s 使得tX=sX，那么就必然存在元组 w，v r，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（

9、即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。 这里，X，Y是U的子集，Z=U-X-Y。多值依赖数学定义解释多值依赖数学定义解释An Introduction to Database System普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李 勇勇张张 平平张张 平平张张 平平 物物 理理物物 理理物物 理理物物 理理物

10、物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学 参考书B（Z）教员T（Y）课程C（X）StVWAn Introduction to Database System多值依赖多值依赖v多值依赖理解多值依赖理解ABCa1b1c1a1b1c2a2b1c1a2b1c3 若使BC成立，需加入哪些元组？c3c2Cb1a2b1a1BAtsc2c3Cb1a2b1a1BAt.Cs.CCs.Bs.At.Bt.ABAwvwvAn Introduction to Database System多值依赖（续）多值依赖（续）v平凡多值依赖和非平凡的多值依赖若XY，而Z，则称 XY为平凡的多值

11、依赖否则称XY为非平凡的多值依赖An Introduction to Database System多值依赖（续）多值依赖（续）例10关系模式WSC（W，S，C）n W表示仓库，S表示保管员，C表示商品n 假设每个仓库有若干个保管员，有若干种商品 n 每个保管员保管所在的仓库的所有商品n 每种商品被所有保管员保管 An Introduction to Database System多值依赖（续）多值依赖（续）WSCW1S1C1W1S1C2W1S1C3W1S2C1W1S2C2W1S2C3W2S3C4W2S3C5W2S4C4W2S4C5An Introduction to Database Sys

12、temAn Introduction to Database System多值依赖（续）多值依赖（续）WS且WC用下图表示这种对应 An Introduction to Database SystemAn Introduction to Database System多值依赖的性质多值依赖的性质（1）多值依赖具有对称性若XY，则XZ，其中ZUXY（2）多值依赖具有传递性若XY，YZ， 则XZ Y（3）函数依赖是多值依赖的特殊情况。若XY，则XY。（4）若XY，XZ，则XY Z。（5）若XY，XZ，则XYZ。（6）若XY，XZ，则XY-Z，XZ -Y。An Introduction to Dat

13、abase SystemAn Introduction to Database System多值依赖与函数依赖的区别多值依赖与函数依赖的区别1）多值依赖的有效性与属性集的范围有关AB在在ABC上成上成立，而在立，而在ABCD上不上不成立成立An Introduction to Database SystemAn Introduction to Database System多值依赖多值依赖 Vs 函数依赖函数依赖ABCDa1b1c1d1a1b1c1d2a1b2c2d1a1b2c2d2ABC成立成立AB不不成立成立2）若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立多值依赖XY若在

14、R(U)上成立，不能断言对于任何Y Y有XY 成立An Introduction to Database System6.2 规范化规范化6.2.1 函数依赖函数依赖6.2.2 码码6.2.3 范式范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖多值依赖6.2.8 4NF6.2.9 规范化小结规范化小结An Introduction to Database System6.2.8 4NFv 定义定义6.10 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有码，则R4NF。v 如果R 4NF， 则R BCNFn不允许有非平凡且非函数依赖的多

15、值依赖n允许的非平凡多值依赖是函数依赖An Introduction to Database System4NF（续）（续）例： Teaching(C,T,B) 4NF 存在非平凡的多值依赖CT，且C不是码n 用投影分解法把Teaching分解为如下两个关系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依赖 An Introduction to Database System6.2 规范化规范化6.2.1 函数依赖函数依赖6.2.2 码码6.2.3 范式范式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖多值依赖6.2.8 4NF

16、An Introduction to Database System规范化小结（续）规范化小结（续）v 关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对码的传递函数依赖凡函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NFAn Introduction to Database SystemAn Introduction to Database System第六章第六章 关系数据理论关系数据理论6.1 问题的提出问题的提出6.2 规范化规范化6.3 数据依赖的公理系统数据依赖的公理

17、系统*6.4 模式的分解模式的分解6.5 小结小结An Introduction to Database SystemAn Introduction to Database System6.3 数据依赖的公理系统数据依赖的公理系统v逻辑蕴含定义定义6.11 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立, （即r中任意两元组t，s，若tX=sX，则t Y=sY），则称F逻辑蕴含X YAn Introduction to Database SystemAn Introduction to Database System1. Armstrong公理系统公理系统 A

18、rmstrong公理系统（Armstrongs axiom）设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R 来说有以下的推理规则： A1.自反律（Reflexivity）：若Y X U，则X Y为F所蕴含。 A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。An Introduction to Database SystemAn Introduction to Database System定理定理 6.1 Armstrong推理规则是正确的推理规则是正确

19、的（l）自反律: 若Y X U，则X Y为F所蕴含 证: 设Y X U 对R 的任一关系r中的任意两个元组t，s：若tX=sX，由于Y X，有ty=sy，所以XY成立，自反律得证An Introduction to Database SystemAn Introduction to Database System定理定理 6.l Armstrong推理规则是正确的（续）推理规则是正确的（续）(2)增广律: 若XY为F所蕴含，且Z U，则XZYZ 为F所蕴含。 证：设XY为F所蕴含，且Z U。 设R 的任一关系r中任意的两个元组t，s：若tXZ=sXZ，则有tX=sX和tZ=sZ；由XY，于是有

20、tY=sY，所以tYZ=sYZ，所以XZYZ为F所蕴含，增广律得证。An Introduction to Database SystemAn Introduction to Database System定理定理 6.l Armstrong推理规则是正确的（续）推理规则是正确的（续）(3) 传递律：若XY及YZ为F所蕴含，则 XZ为 F所蕴含。证：设XY及YZ为F所蕴含。对R 的任一关系 r中的任意两个元组 t，s：若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以XZ为F所蕴含，传递律得证。An Introduction to Database SystemAn Intro

21、duction to Database System2. 导出规则导出规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由XY，XZ，有XYZ。 （A2， A3） 伪传递规则：由XY，WYZ，有XWZ。 （A2， A3） 分解规则：由XY及 ZY，有XZ。 （A1， A3）An Introduction to Database SystemAn Introduction to Database System导出规则导出规则2.根据合并规则和分解规则，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要条件是XAi成立（i=l，2，k）An Introduct

22、ion to Database SystemAn Introduction to Database SystemArmstrong公理系统公理系统vArmstrong公理系统是有效的、完备的n有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；n完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来An Introduction to Database SystemAn Introduction to Database System3. 函数依赖闭包函数依赖闭包定义定义6.l2 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，

23、记为F+。F=XY, YZF+=X,Y,Z,XY, XZ, YZ, XYZ, XX, YY, ZZ,XYX, XZX, YZY, XYZX,XY,Y Z,XYY, XZY, YZZ, XYZY,XZ,YYZ,XYZ, XZZ, YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY, XXZ,XYYZ,XZXZ,XYZYZ,XYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ F=XA1, , XAn的闭包F+计算是一个NP完全问题An Introduction to Database System定义定义6.13 设F为属性集U上的一组函数依赖，X U，

24、 XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包3. 函数依赖闭包函数依赖闭包An Introduction to Database SystemAn Introduction to Database System关于闭包的引理关于闭包的引理v 引理引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能 由F 根据Armstrong公理导出的充分必要条件是Y XF+v 用途 将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ 、判定Y是否为XF+的子集的问题An Introduction to Databa

25、se SystemAn Introduction to Database System求闭包的算法求闭包的算法算法算法6.1 求属性集X（X U）关于U上的函数依赖集F 的闭包XF+ 输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B = A |( V)( W)(VWFV 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）步。An Introduction to Database SystemAn Introduction

26、 to Database System函数依赖闭包函数依赖闭包例1 已知关系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+ 。解 设X（0）=AB；(1) X（1）=ABCD=ABCD。(2) X（0） X（1） X（2）=X（1）BE=ABCDE。(3) X（2）=U，算法终止（AB）F+ =ABCDE。An Introduction to Database SystemAn Introduction to Database System闭包的计算闭包的计算v示例2R, U = (A, B, C, D, E), F = ABC, BD, CE, C

27、EB, ACB,计算所用依赖 ABCABC BDABCD CEABCDE= ABCDEFAB)(FAB)(FAB)(An Introduction to Database SystemAn Introduction to Database System闭包的计算闭包的计算v示例3R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,计算所用依赖 AEABE BEAGABEG GDABEGD= ABEGDFAB)(FAB)(FAB)(An Introduction to Database SystemAn Introduction to Databas

28、e System闭包的计算闭包的计算v练习 1R, U = (C, T, H, R, S), F = CT, HRC, HTR, HSR，HR是码吗？HS呢？v练习 2设有关系模式R (A，B，C，D)，F是R上成立的FD集，F = DA，DB，试写出关系模式R的候选键，并说明理由。An Introduction to Database SystemAn Introduction to Database SystemArmstrong公理系统公理系统v示例R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH, A H？ CG HI？ AG I？

29、An Introduction to Database SystemAn Introduction to Database System5. 函数依赖集等价函数依赖集等价定义定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理引理6.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+。An Introduction to Dat

30、abase SystemAn Introduction to Database System6. 最小依赖集最小依赖集定义定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与F-XA等价。 (3) F中不存在这样的函数依赖XA， X有真子集Z使得F-XAZA与F等价。 An Introduction to Database SystemAn Introduction to Database System最小依赖集最小依赖集例2 关系模式S，其中： U=

31、 Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，SdeptMname，(Sno，Cno)Grade 设F=SnoSdept，SnoMname，SdeptMname， (Sno，Cno)Grade，(Sno，Sdept)SdeptF是最小覆盖，而F不是。因为：F - SnoMname与F 等价 F - (Sno，Sdept)Sdept也与F 等价 An Introduction to Database SystemAn Introduction to Database System7. 极小化过程极小化过程定理定理6.3 每一个函数依赖集F均等价于一个极小函数依

32、赖 集Fm。此Fm称为F的最小依赖集。证明: 构造性证明，找出F的一个最小依赖集。 An Introduction to Database SystemAn Introduction to Database System极小化过程（续）极小化过程（续）(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2， 则用 XAj |j=1，2， k 来取代XY。(2)逐一检查F中各函数依赖FDi：XA，令G=F-XA， 若AXG+， 则从F中去掉此函数依赖。(3)逐一取出F中各函数依赖FDi：XA，设X=B1B2Bm， 逐一考查Bi （i=l，2，m），若A （X-Bi ）F+ ， 则

33、以X-Bi 取代X。An Introduction to Database SystemAn Introduction to Database System极小化过程（续）极小化过程（续）例3 F = AB，BA，BC，AC，CAFm1、Fm2都是F的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA v F的最小依赖集Fm不唯一v 极小化过程( 定理6.3的证明 )也是检验F是否为极小依赖集的一个算法An Introduction to Database SystemAn Introduction to Database System函数依赖的等价和覆盖函数依赖的等价

34、和覆盖v函数依赖集的等价性函数依赖集的等价性 函数依赖集函数依赖集F，G，若，若F+= G+，则称，则称F与与G等价。等价。 F+ = G+ F G+，G F+v最小覆盖最小覆盖满足下列条件的函数依赖集满足下列条件的函数依赖集F称为最小覆盖，记作称为最小覆盖，记作Fmin：F中任一函数依赖中任一函数依赖X A，A必是单属性必是单属性：F中不存在这样的函数依赖中不存在这样的函数依赖X A，使得，使得F与与F X A等价等价：F中不存在这样的函数依赖中不存在这样的函数依赖X A，在，在X中有真子集中有真子集Z，使，使得得F与与F X A Z A等价等价An Introduction to Database SystemAn