260第5章 关系数据库设计理论

1、- 1-第5章 关系数据库设计理论- 2-本章主要讲解内容本章主要讲解内容n 关系数据理论是关系数据库的理论基础，也是设计关系数据库的指南。本章计论关系数据理论的基本概念、方法和题解。n 如何设计数据库模式f1) 设计一个好的关系数据库模式（概念模式）逻辑设计f2) 凭经验设计？f3) 什么是好的关系数据库模式？f4) 好的关系数据库模式应该包括多少关系模式？f5) 每个关系模式应该包含哪些属性？f6) 借助数学工具规定设计的理论和方法规范化- 3-5、1 数据存储异常数据存储异常n 假设有如下关系student：fstudent（sno,sname,sex,cno,score表示学号,姓名,

2、性别,课程,成绩 其中sno,cno是主关键字n 这个关系模式存在如下问题:f数据冗余 一个学生选修多门课程,导致sname和sex多次重复存储.f不一致性 由于数据存储冗余,当更新某些数据项时,就有可能一部分修改了,而另一部分未修改,造成数据不一致性f插入异常 如果某个学生未选课,他的信息(sno,sname,sex)就无法插入f删除异常 当要删除所有学生成绩时,将所有(sno,sname,sex)也都删除了,这便是删除异常- 4-n 为了克服上述这些异常,将student分解为如下两个关系fstudent(sno,sname,sex)fsc(sno,cno,score)n 这是因为stud

3、ent关系中的某些属性间存在数据依赖,数据依赖是现实世界事物之间的相互关联性的一种表达,是属性固有语义的体现.人们只有对一个数据库所要表达的现实世界进行认真的调查与分析,才能归纳与客观事实相符合的数据依赖- 5-5.2 函数依赖函数依赖n 5.2.1 函数依赖(fd)的定义n 1) 函数依赖f定义1 设r(u)是一个关系模式,x,y是r的两个属性集合,x,yr,rx,y是关系r在属性xy上的投影,当任何时刻rx,y中的任意两个元组中的x属性值相同时,则它的y属性值也相同,则称x函数决定y,或称为y函数依赖于x,记作xyf 例子4(1) s(sno,sn,age,sex,dept)4(2) sn

4、o函数决定 (sn,age,sex,dept)4(3) (sn,age,sex,dept)函数依赖于sno4(4)sno(sn,age,sex,dept) n 2) 平凡函数依赖与非平凡函数依赖定义2 在关系r(u)中,对于u的子集x和y,如果xy ,但y不是x的了集,则xy是非平凡函数依赖.若y 是x的子集,则称xy为平凡函数依赖- 6-n 3)完全函数依赖与部分函数依赖f设xy是一个fd,并且对于任何一个xx,x y不成立,则称xy是一个完全函数依赖,记作x yf设xy是一个fd,并且存在一个xx,使x y成立,则称xy是一个部分函数依赖,记作x yf示例41) sc(sno,cno,g)

5、 (sno,cno) g是完全函数依赖4(2)sc(sno,cno,sname,cname,g)qsno,cno是主键 (sno,cno) g qsno snameqcno cnameq所以存在部分函数依赖- 7-n 4)传递函数依赖n 设 x,y,z是r互不相同的属性集合 xy，y x,且 yz 则称属性集合z传递(transfer)函数依赖于x ,记作 x zf(1) un(sno,cn,g,dn,dm) (学号,课程名,成绩,系名,系主任)f(2) snodnf(3) dn snof(4) dndm则dm传递函数依敕于sno - 8-n 5.2.2函数依赖公理n 函数依赖的推导公理-ar

6、mstrong公理（阿姆斯特朗公理）设有关系模式 r（u），x，y，z，wu，则：fa1（自反性）：若yx，则xyfa2（增广性）：若xy，则xz yzfa3（传递性）：若xy， yz，则xzn 由armstrong公理可以得到以下推论f合成规则：若xy， xz，则xyz；f分解规则：若xyz，则xy， xz；f伪传递规则：若xy，yw z，则xw z- 9-n 引理：xa1 a2 an成立的充分必要条件是x ai成立(i=1,2,3.n)n 5、2、3函数依赖与属性关系f如果x和y之间是1-1关系，则存在xy， yxf如果x和y之间是“多对1”关系，则存在xyf如果x和y之间是“多对多”，则

7、x和y 不存在函数依赖- 10-小结小结n 1) 函数依赖是完整性约束的一种特殊形式n 2) 函数依赖分为f (1) 完全函数依赖f (2) 部分函数依赖f (3) 传递函数依赖n 3) 函数依赖是规范化理论的依据n 4) 函数依赖是规范化程度的准则- 11-n 设有如下关系r：请仅在r中已给出数据的范围内分析其函数依赖关系 - 12-5.3 函数依赖的闭包函数依赖的闭包f+ 属性闭包及其计算属性闭包及其计算n 5.3.1函数依赖的闭包f+定义 关系模式r(u,f)中为f所逻辑蕴含的函数依赖的全体称为f的闭包,记为:f+n 例:关系模式s(u,f),其中u=sno,sname,sex,agef

8、=snosname,snosex,snoage- 13-5.3.2 属性闭包及其计算属性闭包及其计算定义 设关系模式r(u),f为其函数依赖集,则称所有用armstrong公理从f推出的函数依赖xai中的ai的属性集合为x的属性闭包,记作x+n 例: 有关系模式 s(sno,sn,sex,age)有 则有sno+=sno,sn,sex,age定理 设关系模式r(u),f为其函数依赖集,x,yu,则从f推出x y的充分必要条件是y x+- 14-算法算法5.1 求属性集求属性集x关于函数依赖关于函数依赖f的属性闭包的属性闭包x+ 算法 求属性的闭包x+q 输入 x,f q 输出 x+q 步骤 q

9、(1)令x(0)=x,i=0q(2)求b,b=a|(v)(w)(v w fv x(i)aw(a是这样的属性:在f中寻找尚未用过的左边是x(i)的子集的函数依赖)q(3)x(i+1)=bx(i)q(4)判断x(i+1)=x(i)吗?q(5)若相等,或x(i)=u,则x(i)为属性集x的属性闭包.且算法终止q(6)若不相等,则i=i+1,返回第2步.- 15-属性闭包计算示例属性闭包计算示例n 例1 已知关系模式r(u,f),u=a,b,c,d,e;f=ab, dc,bc e,ac b求(ae)+ ,(ad)+n 解 求(ae)+ f设x(0)=aef计算x(1) : 逐一扫描f中的各个函数依赖,

10、找出左部为a,e或ae的函数依赖,得到一个: ab.故有x(1)=aeb=abef计算x(2):逐一扫描f中的各个函数依赖,找到左部为a,b,e或ab,ae,be,abe的函数依赖,示发现有新的函数依赖x(2)=x(1)=abe 有 x(1)=x(2),算法终止, (ae)+ =abef(注:因为找不到新的函数依赖,即f中未用过的函数依赖的左边属性已没有x(1)的子集,所以,不必再计算下去,算法终止)练习 求(ad)+- 16-n 解 求(ad)+fx(0)=adf求x(1):逐一扫描f中的各个函数依赖,找出左部为a,d或ad的函数依赖,得到: ab,d c,故有x(1)=abcdf求x(2)

11、:逐一扫描f中的各个函数依赖,找出左部为abcd或其子集的函数依赖,得到: bce,ac b,故有x(2)=abcdef因为x(2)=u,故算法终止, (ad)+=abcde- 17-例例2n 设有关系模式r(u,f),其中u=a,b,c,d,e,i;f=ad,ab e, bie,cd i,e c计算(ae)+n 解:f设x(0)=aef求x(1) 在f的左部找出ae及其子集的函数依赖,有ad,e c 所以x(1)=acdef求x(2) 在f的左部找出acde及其子集的函数依赖,新的依赖有cdi 所以x(2)=acdei f求x(3) 因为在f中未用过的函数依赖左边属性已没有x(2)的子集,所

12、以不必再计算,即x(3)=x(2),算法终止f(ae)+=acdei- 18-练习 设有函数依赖集f=dg,c a,cd e,a b计算闭包d+ ,c+, a+ ,(cd)+ ,(ad)+, (ac)+, (acd)+- 19-5.4 函数依赖的等价与覆盖函数依赖的等价与覆盖 n 5.4.1 等价与覆盖定义: 一个关系模式r(u)上的两个依赖集f和g,如果f+=g+,则称f和g是等价的,记作f g.如果函数依赖集fg.则称g是f的一个覆盖,反之亦然两个等价的依赖集在表示能力上是完全相同的.- 20-5.4.2 函数依赖集的最小集函数依赖集的最小集n 简称为最小函数依赖集定义 :对于给定的函数依

13、赖f,当满足下列条件时,称为f的最小集,记作f:1) f的每个依赖的右部都是单个属性2) 对于f中的任何一个函数依赖xa, f-xa与f都不等价3) 对于f中的任何一个xa和x的真子集z,(f-xa) za与f都不等价q 说明:条件(2)保证了在f中不存在多余的函数依赖;条件(3)保证了f中每个函数依赖的左边没有多余的属性- 21-5.4.3 最小依赖集的求解算法最小依赖集的求解算法算法4.2 计算最小依赖集n 输入:一个函数依赖集fn 输出:f的一个等价最小依赖集fn 方法:f(1)应用分解规则,使f中每一个依赖的右部属性单一化f(2)去掉各依赖左部多余的属性.具体做法是:一个一个地检查f中

14、左边是非单属性的依赖,例如xya,现在要判断y是否为多余的,则以xa代替xya是否等价?只要在f中求x+,若x+包含a,则y是多余的属性;否则y不是多余的属性.依次判断其他属性即可消除各依赖左边的多余属性.f(3)去掉多余的依赖.具体做法是:从第一个依赖开始,从f中去掉它(假设该依赖为xy),然后在剩下的依赖中求x+,看x+是否包含y,若是,则去掉xy;若不包含y,则不能去掉xy.f(4)这样依次做下去.- 22-n 例 设有依赖集:f=abc,c a,bc d,acd b,d eg,be c,cg bd,ce ag计算其等价的最小依赖集.n 解:n (1)将依赖右边属性单一化,结果为 f1=

15、ab c be cc a cg bbc d cg dacd b ce ad e ce gd g- 23-n (2)在f1中去掉依赖左部多余的属性,因为有c a,则对ce a,e是多余的,对于acd b,若去掉a,由于(cd)+=abcdeg,则a是多余的,删除依赖左部多余的依赖后: f2=ab c be cc a cg bbc d cg dcd b c ad e ce gd g- 24- n (3)在f2中去掉多余的依赖.对于cg b,去掉他,仍有(cg)+=abcdeg,则是多余的,删除多余的依赖后: f3=ab c d gc a be cbc d cg dcd b ce gd eab c

16、be cc a cg bbc d cg dcd b c ad e ce gd g注意：f的最小依赖集不一定是惟一的，它与对各函数依赖fd及xa中x各属性的处理顺序有关。f3即是求得的最小函数依赖集f- 25-5.5 候选关键字的求解理论与算法候选关键字的求解理论与算法n 候选关键字: 属性或属性的最小组合,其值能够惟一地标识一个元组.n 对于给定的关系r(a1,a2,an)和函数依赖集f,可将其属性分为四类:fl类:仅出现在f的函数依赖左部的属性fr类:仅出现在f的函数依赖右部的属性fn类:在f的函数依赖左右两边均未出现的属性flr类:在f的函数依赖左右两边均出现的属性n 例:有关系模式r(a

17、,b,c,d,e,f,p) r 的函数依赖集为f=ad,e d,d b,bc d,dc a,d f则fl类属性有:c efr类属性有:fflr类属性有:abdfn类属性:p- 26-n5.5.1 快速求解候选关键字的充分条件n 定理 对于给定的关系模式r及其函数依赖f,若x(xr)是l类属性,则x必为r的任一候选关键字的成员,若y(y r)是r类属性,则y不在任何候选关键字中,若z (z r)是n类属性,则z必包含在r的任一候选关键字中.n 推论1 对于给定的关系模式r及其函数依赖集f，如果x是l类属性，且x+包含了r的全部属性；则x必为r的惟一候选关键字n 推论2 对于给定的关系模式及其函数

18、依赖集f，如果x是r的n类和l类组成的属性集，且x+包含了r的全部属性，则x是r的惟一候选关键字- 27- 设有关系模式r（a,b,c,d),其函数依赖集f=db,bd, adb,ac d,求r的所有候选关键字f解:在f中发现,l 类属性有a,c两属性,则ac必为候选关键字成员,又(ac)+=abcd,所以ac是唯一候选关键字 设有关系模式r(a,b,c,d,e,p)及其函数依赖集f=a d,e d,d b,bc d,dc a,求r的所有全部候选关键字.f解:考察f发现,l 类属性有c,e ,n类属性有p,则cep必在任何候选关键字中,又(cep)+=abcdep,所以cep是r的惟一候选关键

19、字- 28-n 5.5.2 左边为单属性的函数依赖集的候选关键字成员的图论判定方法n 定义:在一个函数依赖图中有下列术语f(1)引出线/引入线:若a b,则a与b是连接的,则(a,b)是引出线,对b而言是引入线f(2)原始点:只有引出线而无引入线的结点,它表示l类属性f(3)终结点:只有引入线而无引出线的结点,它表示r类属性f(4)途中点:即有引入线又有引出线的结点,对应lr类属性f(5)孤立点:既无引入线又无引出线的结点,对应n类属性f(6)关键点:原始点和孤立点统称为关键点f(7)关键属性:关键点对应的属性称为关键属性f(8)独立回路:不能被其他结点到达回路- 29-函数依赖图示例函数依赖

20、图示例abcdef原始点 途中点 终结点孤立点孤立点独立回路r(a,b,c,d,e,f) f=a b,b c,e f,fe- 30- n 算法 单属性依赖集候选关键字图论求解法n 输入:关系模式r,r的单属性函数依赖集fn 输出:r的所有候选关键字n 方法f(1)求f的最小函数依赖集ff(2)构造函数依赖图fdg(functional dependencies graph)f(3)从图中找出关键属性集x(x可为空)f(4)查看图中有无独立回路,若无则输出x即为r的惟一候选关键字,转(6);若有,则转(5)f(5)从各独立回路中各取一结点对应的属性与x组合成一候选关键字,并重复这一过程取尽所有可

21、能的组合,即为r的全部候选关键字f(6)结束.- 31- 设r=o,b,i,s,q,df=sd,d s,i b,b i,b o,o b求r的所有候选关键字.n 解: f(1)f=f= sd,d s,i b,b i,b o,o bf(2)构造函数依赖图如图所示sdoibqo(3)关键属性qo(4)共有两个独立回路,sds,ibobi,所以共有2*3=6个候选关键字o(5)r的所有候选关键字为:qsi,qsb,qso,qdi,qdb,qdo- 32-n 5.5.3 多属性依赖集候选关键字求解法n 算法 多属性依赖集候选关键字求解法n 输入:关系模式r与函数依赖集fn 输出:r的所有候选关键字n 方

22、法:f(1)将r的所有属性分为l,r,n和lr四类,并令x代表l,n两类,y代表lr类f(2)求x+,若x+包含了r的全部属性,则x为r的惟一候选关键字,转(4),否则转(3)f(3)在y任取所有一个属性a,求(xa)+,若它包含了r的全部属性,则为一个候选关键字,否则依次取两个,三个.直至其属性闭包包含了r的全部属性f(4)结束,输出结果- 33- 34-exercises on functional dependenciesn questions:- 35-consider a relation r(a, b, c, d, e) with the following dependencie

23、s:ab c, cd e, de bis ab a candidate key of this relation? if not, is abd? explain your answer. 设有关系r(a,b,c,d,e),f=(ab)-c,(ab)-d,a-e请解答如下问题：（1）指出其全部候选关键字设有关系r(a,b,c,d,e),f=a-b,a-c,（ad）-e 请解答如下问题：（1）指出其全部候选关键字- 36-5.6 关系模式分解的级别关系模式分解的级别-范式范式n 5.6.1. 属性键f1) 全码4(1) 整个属性组合是关系键f2) 主属性(键属性)4(1) 包含在任何一个候选键（

24、候选关键字）中的属性f3) 非主属性(非键属性)4(1) 不包含在任何候选键中的属性f 例子41) s(sno,sn,age,sex,dept)q(1) sno是主属性(2) sn,age,sex,dept是非主属性42) sc(sno,cno,g)q(1) sno,cno是主属性 (2) g是非主属性43) pwa(演奏者p,作品w,听众a)q(1) 之间为多对多关系，无函数依赖(2) 全属性集(p,w,a)是键、主键、全码(3) p,w,a都是主属性- 37-5.6.2范式范式n 1. 范式(nf, normal formula)f1) 定义4(1) 符合某种级别的关系模式的集合4(2)

25、如果一个关系满足某个特定的约束值，则称它属于某种特定的范式f2) 各级范式的要求4(1) 第一范式：关系满足只包含原子值的约束4(2) 第二范式：每个非主属性都完全函数依赖于r的每个键4(3) 第三范式：每个非主属性都不传递依赖于r的任何键4(4) bc范式：r中每个决定因数都是候选键4(5) 第四范式：对于r的每个非平凡多值依赖xy，x都含有候选码4(6) 第五范式：投影连接范式- 38-n 3) 各级范式的关系f(1) 5nf4nfbcnf3nf2nf1nff(2) 如果关系满足某个范式要求，也会满足级别较低的所有范式的要求f(3) 较高层次的范式比较低层次的范式具有更合乎要求n 4) 模

26、式分解（也叫规范化）f 将一个低一级范式的关系模式通过投影运算转化为若干个高一级范式的关系模式的集合的过程- 39-第一范式第一范式(1nf)n 1) 定义f(1) 若关系模式r的所有属性都是不可分的基本数据项f(2) 则r1nfn 2) 说明f(1) 1nf是关系模式的最起码要求f(2) 若r1nf，则r不是关系数据库n 3) 例子f(1) un(sno,cno,dname,dm,g)f(2) (sno,cn)为关系键、候选键、主键f(3) 函数依赖关系41. (sno,cno) g42. snodname43.dndm- 40-n (4) 存在的问题f1. 插入异常f2. 删除异常f3.

27、冗余太大f4. 修改异常- 41-第二范式第二范式(2nf)n 1) 定义f(1) 在关系模式r1nf的基础上f(2) 且每个非主属性都完全依赖于r的每个关系键f(3) 则r2nfn 2) 例子f(1) s(sno,sn,age,sex,dept)1nff(2) sno(sn,age,sex,dept)f(3) sn(sno,age,sex,dept)f(4) sno为候选键f(5) sno,age,sex,dept是非主属性f(6) sno,age,sex,dept完全依赖于每个键f(7) s2nf- 42-n 3) 注意f(1) 如果关系r的全体属性都是r的主属性，或者r的所有键仅含有一个

28、属性，那么r2nf。f(2) 从1nf中消除非主属性对键的部分函数依赖，则可获得2nf关系n 4) 三个问题的解决f1. 插入异常有所改善f2. 删除异常仍然存在f3. 冗余得到改善- 43-n 示例:现有关系模式sc(sno,cno,ctitle,grade)问其属于第几范式,为什么? 解: (1)求候选键 由题意 f=(sno,cno)-g,cno-ctitle，l 类属性为sno,cno,又(sno,cno)+=u,则(sno,cno)为唯一候选关键字 (2)关系模式s最高为1nf 因为存在cno-ctitle,即非主属性对码的部分函数依赖.- 44- 第三范式第三范式(3nf)n (1

29、) 定义f若关系模式r(u,f)中若不存在这样的码x,属性组y及非主属性z(zy),使得x y,y z且y不能函数决定x,则 r3nff即4(1) 若r2nf4(2) 且每个非主属性都不传递依赖于r的任何键4(3) 则r3nfn 2) 说明f(1) 每个非主属性既不部分依赖，也不传递依赖于r的任何键f(2) 从1nf2nf：消除非主属性对键的部分函数依赖f(3) 从2nf3nf：消除非主属性对键的传递函数依赖- 45-n 3) 3nf的题解f设有关系 r(课程名,教师名,教师地址)(注:每门课程只由一名教师讲解)f问:它能否达到第三范式,为什么? 解: (1)求候选键 由题意 f=课程名-教师

30、名,教师名-教师地址 l 类属性为课程名,又(课程名)+=u,则(课程名)为唯一候选关键字 (2)关系模式r最高为2nf 因为存在教师地址传递函数依赖于课程名,即非主属性对码的传递函数依赖.- 46- boyce-codd范式范式(bcnf)简称简称bc范式范式n 1) 3nf的不完善性f(1) 3nf排除了非主属性对键的部分函数依赖和传递函数依赖f(2) 把能够分离的属性尽可能地分解为单独的关系f(3) 但3nf没有限制有些主属性对键具有的函数依赖- 47-n 2) bcnf定义f(1) 若r1nff(2) 如果对于r的每个函数依赖xy，x必含有候选键f(3) r中的每个(决定因素)决定属性

31、集x都是候选键f(4) 则rbcnfn 3) 说明f(1) 在满足bcnf的关系中，除候选键之外没有其他的决定因素(决定属性集)f(2) 满足bcnf的关系将消除任何属性(主属性或非主属性)对键的部分依赖或传递依赖f(3)属于bcnf的关系必然属于3nf，但属于3nf的关系却不一定属于bcnf - 48-consider this relation and fds- 49-outlinen in this section, we describe some of the relational database design algorithms that utilize functional

32、dependency and normalization theory.fwe first describe the two desirable properties of decompositions, namely, the dependency preservation property and the lossless join property.fwe then introduce the decompositions algorithms to achieve higher normal forms like 3nf,and bcnf- 50-what is decompositi

33、on?n decomposition the process of breaking down in parts or elements.n decomposition in database means breaking tables down into multiple tablesn from database perspective means going to a higher normal form- 51-decompositiontwo characteristics of good decompositions1) lossless2) preserve dependenci

34、es- 52-what is lossless?nlossless means functioning without a loss.nin other words, retain everything.nimportant for databases to have this feature. - 53-lossless join decompositions- 54-algorithm : testing for lossless (nonadditive) join propertyn input: a universal relation r, a decomposition 0 =

35、r1, r2, . , rml of r, and a set f of functional dependencies.n 1. create an initial matrix s with one row i for each relation ri in d, and one column j for each attribute aj in r.n 2. set s(i, j):= bij for all matrix entries.n (* each bij is a distinct symbol associated with index (i, j) *)- 55- 56-

36、 57-example 1 for lossless join testing- 58-example 2 for lossless join testingn consider the following relation schema r(a,b,c,d,e) and a set of fds f=ac,b c,c d,de c,ce a. determine whether the following decomposition has the lossless join property.n =r1(a,d)，r2(a,b)，r3(b,e), r4(c,d,e),r5(a,e )- 5

37、9-构造二维表构造二维表 a b c d er1r2r3a1a3a2a1b23r4r5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41- 60-由由ac,做的修改做的修改 a b c d er1r2r3a1a3a2a1b23r4r5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41b13b13- 61-由由bc,做的修改做的修改 a b c d er1r2r3a1a3a2a1b13r4r5a5a4a2a4a1a5a5b13b33b12b15b24b25b34b31b54b52b42

38、b41b13b13- 62-由由cd做的修改做的修改 a b c d er1r2r3a1a3a2a1b13r4r5a5a4a2a4a1a5a5b13b13b13b12b15b24b25b34b31b54b52b42b41a4a4a4- 63-由由dec做的修改做的修改 a b c d er1r2r3a1a3a2a1b13r4r5a5a4a2a4a1a5a5b13b13b13b12b15b25b31b52b42b41a4a4a4a3- 64-结果二维表结果二维表 a b c d er1r2r3a1a3a2a1r4r5a5a4a2a4a1a5a5b12b15b25b52b42a3a3b13a3a1

39、a1a4a4a4算法输出算法输出true 是无损的是无损的- 65-dependency preservationproperty of a decompositionn we say that a decomposition d = r1, r2, . , rm of r is dependency-preserving with respect to f ifn the union of the projections of f on each ri in d is equivalent to f; that is,- 66-example for dependency preservationn consider the relation r(a,b,c,d) with f=ab,cd, determine whether each following decomposition d of r has the dependency-preserving property.n a) r1(a,b) ,r2(c,d)n b) r1(a,b,c),r2(a,d) - 67-algorithm : decomposition into 3nf with dependency preservation and lossless joinn 1. find a minimal c