北京工业大学研究生数据库复试笔试课件chap4 关系数据库理论_128

1、1 第第4章章 关系数据库理论关系数据库理论 数据库模式数据库模式: 一组相关的关系模式一组相关的关系模式 关系模式关系模式 R(A1,A2,An) 2 4.1 函数依赖函数依赖4.1.1 4.1.1 函数依赖的基本概念函数依赖的基本概念一、关系模式的优劣与数据依赖一、关系模式的优劣与数据依赖 1.1.关系模式集性能比较关系模式集性能比较3例例1：学生数据库：学生数据库方案方案1：各类数据放在一个关系模式中：各类数据放在一个关系模式中 Students(Sno,Sname,Cno,Grade,Sdept,Sloc) 键键 (Sno，Cno)4问题：问题： 冗余：冗余： 一个学生选一个学生选20

2、门课门课 学生学生 系系 宿舍区的信息宿舍区的信息 重复存储重复存储 5潜在不一致潜在不一致(修改复杂修改复杂) 学生改名学生改名 对于所选的若干门课对于所选的若干门课 若干行若干行 到处修改到处修改 潜在的不一致潜在的不一致 修改复杂修改复杂 6插、删异常插、删异常 没选课没选课 Cno为为NULL 学生信息无法插入学生信息无法插入 选课信息输入错误选课信息输入错误 删除删除 同时删学生信息同时删学生信息7方案方案2：选课信息单独存放：选课信息单独存放 Students(Sno,Sname,Sdept,Sloc) 键：键： Sno SC(Sno,Cno,Grade) 键：键： (Sno,Cn

3、o) 有所改进有所改进: 与选课无关的信息只存一次与选课无关的信息只存一次8仍有问题仍有问题: 1.冗余冗余 系与宿舍区的对应关系系与宿舍区的对应关系 一个系一个系1000个学生个学生 系与宿舍区的对应关系存放系与宿舍区的对应关系存放1000次次 9 2.潜在不一致潜在不一致 系换宿舍区系换宿舍区 到处修改到处修改 潜在的不一致潜在的不一致 修改修改1000次次 复杂复杂103.删插异常删插异常 有相应学生的信息有相应学生的信息 才能插入系以及宿舍区的信息才能插入系以及宿舍区的信息 学生全部毕业学生全部毕业 系与宿舍区的联系同时删除系与宿舍区的联系同时删除112.产生冗余及更新异常的原因产生冗

4、余及更新异常的原因关系模式内部属性值之间的内在联系关系模式内部属性值之间的内在联系 数据依赖数据依赖 主要的数据依赖：主要的数据依赖： 函数依赖、多值依赖函数依赖、多值依赖12一个一个Sno，m个个Cno m行学生信息行学生信息一个系一个系1000个个Sno,1000行行 系与宿舍区的系与宿舍区的n:1联系联系键键SnoCnoGradeSlocSdeptSname133.关于数据依赖关于数据依赖 属性值之间相关联系的表达属性值之间相关联系的表达 语义的体现语义的体现 构成数据的约束构成数据的约束 大多数数据依赖是函数依赖大多数数据依赖是函数依赖14 二、函数依赖的定义二、函数依赖的定义 1.函

5、数依赖函数依赖 设设 R(U)R(U)是一个关系模式，是一个关系模式，U U 是关系是关系 R R 的属性全集；的属性全集； X X，Y Y 是是R R 的的属性组属性组（X X，Y Y U U）；）； 若对于若对于R R上任意一个可能的上任意一个可能的关系实例关系实例 r r 满足：满足： t t1 1,t,t2 2 r ,tr ,t1 1X=tX=t2 2X X 则则 t t1 1Y=tY=t2 2YY 则称则称“ X X 函数决定函数决定 Y Y ”或或“Y Y 函数依赖于函数依赖于 X X” 记为：记为：X X Y Y X X 称为决定因素称为决定因素 对关系模式对关系模式15函数依赖

6、函数依赖 X X Y Y 的含义为的含义为: : 任何时刻任何时刻表表中任一元组中任一元组: : 属性组属性组X X上的值上的值（a1 a2 .an） 唯一地决定唯一地决定 在属性组在属性组Y Y上的值上的值 (b1 b2 .bm) 16 R(A,B,C,D)一个实例一个实例: A B C D t1 a1 b1 c1 d1 t2 a2 b2 c2 d2 t3 a2 b2 c2 d3 t4 a3 b2 c2 d4 ? 元组元组t2,t3 A的取值相同的取值相同 B,C的取值相同的取值相同 实例判定函数依赖？实例判定函数依赖？no17 若若 对于任何时刻对于任何时刻(任意任意实例实例)有有 A的取

7、值相同时的取值相同时 B,C上的取值相同上的取值相同 则则 A ( (B,C)18函数依赖的例：函数依赖的例： 例例 Movies(title,year ,length, genre, studioName,starName) (title,year) length ? 决定决定 ？ (title,year) genre ? 函数依赖函数依赖 ？ (title,year) studioName 即即 (title,year) ( ( length, genre, studioName) 关系实例关系实例 P38 图图3-2 1-3行行 5-6行行19例例: Students(Sno,Sname

8、,Sage,Class_no,Sdept) 此关系模式上有许多函数依赖此关系模式上有许多函数依赖 如：如： Sno (Sname,Sage,Class_no,Sdept) Class_no Sdept (Sno,Sname)(Sage,Class_no ) 202.2.平凡函数依赖平凡函数依赖 如果函数依赖如果函数依赖X X Y Y，Y Y X X ； 则称为平凡函数依赖则称为平凡函数依赖 否则称为否则称为非平凡的函数依赖非平凡的函数依赖 例例：(Sno,Sname) Sname 平凡函数依赖平凡函数依赖 (Sno,Cno) Cno 平凡函数依赖平凡函数依赖 Sno Sname 非平凡的函数依

9、赖非平凡的函数依赖21 所有平凡的函数依赖保持所有平凡的函数依赖保持“恒真恒真” 通常我们讨论的都是通常我们讨论的都是非平凡非平凡的函数依赖的函数依赖 包含平凡的函数依赖有时简化规则的陈述包含平凡的函数依赖有时简化规则的陈述 A A1 1A A2 2A An n B B1 1B B2 2B Bm m 平凡平凡: : B B1 1B B2 2B Bm m是是A A1 1A A2 2A An n子集子集 非平凡非平凡: :每一个每一个BiBi不不是是A A1 1A A2 2A An n子集子集 ( (通常讨论通常讨论) ) 224.1.2 4.1.2 函数依赖与键函数依赖与键 设设 R(U)R(U

10、)是一个关系模式，是一个关系模式，U U 是关系是关系 R R 的的属性属性全集全集；X X 是是R R 的属性组（的属性组（X X U U）；）；若若X X U U , ,且不存在且不存在 X X X ,X X ,X U U 则称则称X X为为R R的的键键( (候选键候选键) )。 X X 能决定所有属性能决定所有属性 X X 中属性缺一则不可决定所有属性中属性缺一则不可决定所有属性23键键举例：举例： 例例 Movies(title,year,length,genre, studioName, StarName) 影片影片 影星影星 键键 : (title,year , StarName

11、) 能决定所有属性能决定所有属性 三个属性缺一不可三个属性缺一不可 所以所以 是是 键键 24例：例： Students(Sno,Sname,Sage,Class_no,Sdept) 键键 Sno ( (Sno,Sname ) ) 是是 超键超键 不是键不是键 真子集真子集Sno可以决定所有属性可以决定所有属性25 设设 R(U)R(U)是一个关系模式，是一个关系模式，U U 是关系是关系 R R 的属性的属性全集；全集；X X 是是R R 的属性组（的属性组（X X U U）；）； 若若X X U , U ,则称则称X X为为R R的的超键超键。 与键比较与键比较26超键超键举例：举例： S

12、tudents(Sno, Sname, sage, Class_no, Sdept) 超键有：超键有： Sno(含自身含自身) (Sno,Sname) (Sno,Class_no) (Sno, Sname,Sage, Class_no, Sdept) 27 4.1.3 函数依赖的规则函数依赖的规则P40 如何推导函数依赖如何推导函数依赖 已知某关系所满足的函数依赖已知某关系所满足的函数依赖,推出它满足的推出它满足的另一些函数依赖。另一些函数依赖。例例 3.4 R(A,B,C) 由由A B, B C 推导推导 A C思路思路:考察考察R的任意两个的任意两个A上取值相同的元组上取值相同的元组 看看

13、看看C上取值是否相同上取值是否相同28 假设假设 这样的两个元组为这样的两个元组为 (a,b1,c1 ) (a,b2,c2) 由由 A B A上值相同则上值相同则B上值相同上值相同 有有b1=b2 记为记为 b 得到得到 (a,b,c1 ) (a,b,c2) 由由B C B上值相同则上值相同则C上值相同上值相同 有有 c1=c2 即即C上取值相同上取值相同 所以所以 A上取值相同的元组上取值相同的元组 C上取值相同上取值相同 所以所以A C29函数依赖集函数依赖集S 蕴涵于蕴涵于 函数依赖集函数依赖集T: 满足满足T中函数依赖中函数依赖 的关系实例的关系实例 也满足也满足S中函数依赖中函数依赖

14、 R(A,B,C) T:A B, B C SA B, B C ,A C30函数依赖集函数依赖集等价等价: 函数依赖集函数依赖集S蕴涵于蕴涵于函数依赖集函数依赖集T 函数依赖集函数依赖集T蕴涵于蕴涵于函数依赖集函数依赖集S S与与T是是等价等价的的31P40 分解规则分解规则: A1A2An B1B2.Bm 则则A1A2An Bi i=1,m 例例: (title,year,length,genre) (title,year) (length,genre) 则则 (title,year) length (title,year) genre32合并规则合并规则: P40 组合组合/结合结合 A1A

15、2An Bi i=1,m 则则A1A2An B1B2.Bm例例: (title,year,length,genre) (title,year) length (title,year) genre 则则 (title,year) (length,genre)33P42 平凡依赖规则平凡依赖规则: A1A2An B1B2.Bm 等价于等价于A1A2An C1C2.Ck 去掉去掉A中出现的属性中出现的属性 非平凡非平凡 例例: (title,year) (studioName,year) (title,year) (studioName)34 *属性集的闭包属性集的闭包 函数依赖集函数依赖集F 属性

16、组属性组X 若有属性组若有属性组Y 包含包含所有所有满足下述条件的属性满足下述条件的属性A X A 蕴涵于蕴涵于F中的函数依赖中的函数依赖 称称Y为属性组为属性组X对于函数依赖集对于函数依赖集F的闭包的闭包, 记为记为XF+35P43 例例3.8: R(A,B,C,D,E,G) F=AB C , BC AD, D E, CG B A,B+=A,B,C,D,EF36闭包与键闭包与键 例例: R(A,B,C,D) F=A D, BC A B,C+=A,B,C,D 决定属性全集决定属性全集 B +=B C +=C 最小性最小性 BC 是是键键FFF37求键时的一些考虑：求键时的一些考虑： 1.一个属

17、性不在函数依赖右边出现，则一定是一个属性不在函数依赖右边出现，则一定是键属性键属性 2.此外，考虑此外，考虑含含函数依赖左边属性的属性集函数依赖左边属性的属性集的的闭包闭包（不含（不含不在左边、在右边不在左边、在右边的属性）的属性） 3.不必考虑不必考虑以键作为真子集的属性集以键作为真子集的属性集的闭包的闭包 4.不必考虑不必考虑属性全集属性全集的闭包的闭包(全键情况除外全键情况除外)38例例: R(A,B,C,D) F=A C, C B,B A 求所有键求所有键 分析：键中必含分析：键中必含D 键属性涉及左边的键属性涉及左边的A，B，C 解解: A,D+ =A,C,B,D B,D+ =B,A

18、,C,D C,D+ =C,B,A,D D不是键，不含不是键，不含D的属性组也不能作键的属性组也不能作键 A,DB,DC,D为键为键 不必考虑以上述键作为真子集的属性组不必考虑以上述键作为真子集的属性组 这是所有的键这是所有的键FFF39定理定理: 当且仅当当且仅当 Bi 在在A+中中 i=1.m A B1B2.Bm ?蕴涵于蕴涵于? 函数依赖集函数依赖集FF40定理的例定理的例: 例：例： R(A,B,C,D,E,G) F=AB C, BC AD, D E, CG B 1) AB D是否是否蕴涵于蕴涵于?上述函数依赖上述函数依赖? A,B+=A,B,C,D,E AB D蕴涵于蕴涵于. 2) D

19、 A是否是否蕴涵于上述函数依赖蕴涵于上述函数依赖? D+=DE D A不蕴涵于不蕴涵于.FF41 传递规则传递规则: A1A2An B1B2.Bm B1B2.Bm C1C2.Ck 则则 A1A2An C1C2.Ck 42P44 例例3.10 Movies(title,year,length,genre, studioName, StudioAddr) (title,year) studioName studioName StudioAddr (title,year) StudioAddr43 *函数依赖集的闭包函数依赖集的闭包: 由给定的函数依赖集由给定的函数依赖集推导出的推导出的所有函数依赖

20、的所有函数依赖的集合集合*对于关系模式对于关系模式: 能导出关系模式的所有函数依赖的给定的函数能导出关系模式的所有函数依赖的给定的函数依赖集依赖集,称为称为“基本集基本集” , 如果如果基本集基本集的任何真子的任何真子集不能导出关系上的所有依赖集不能导出关系上的所有依赖,此此基本集基本集为为最小的最小的. 最小基本集最小基本集又称为又称为极小的函数依赖集极小的函数依赖集 等价等价44极小的函数依赖集极小的函数依赖集 (1)F中任一函数依赖的右部仅含一个属性中任一函数依赖的右部仅含一个属性(3)F中每个函数依赖的左部都没有多余的属性中每个函数依赖的左部都没有多余的属性 即：不存在这样的函数依赖即

21、：不存在这样的函数依赖X A， 对于对于X的真子集的真子集Z 使使F 与与 F-X A ZA 等价等价(2)F中没有多余的函数依赖中没有多余的函数依赖 即：不存在这样的函数依赖即：不存在这样的函数依赖X A 使使F 与与 F-X A 等价等价45计算极小函数依赖集的算法：计算极小函数依赖集的算法： (1)应用分解规则，使应用分解规则，使F中每一个函数依赖的中每一个函数依赖的 右部属性单一化右部属性单一化(3)F3=F2=A B, B C 极小集极小集(2)F2=F1= A B, A C, B C,A C =A B, A C, B C(1) F1=F= A B, A C, B C,AB C例：例

22、：F=A BC,B C,AB C (3)去掉多余的函数依赖去掉多余的函数依赖 (2)去掉各函数依赖左部多余的属性去掉各函数依赖左部多余的属性46Armstrong公理公理: 推导函数依赖的规则推导函数依赖的规则 自反律自反律 B A 则则 A B 增长律增长律(增广律增广律) A B 则则 任意任意C AC BC 传递律传递律 A B B C 则则 A CA，B，C为属性组为属性组47 4.2 关系数据库模式设计关系数据库模式设计4.2.1 有关函数依赖有关函数依赖完全函数依赖完全函数依赖 设设 R(U)是一个是一个关系模式关系模式，U 是关系是关系 R 的属性全的属性全集；集；X,Y 是是R

23、 的属性组（的属性组（X，Y U）；）； 若若X Y ,且不存在且不存在 X X ,X Y 则称则称 Y 完全函数依赖完全函数依赖于于 X ；记作：；记作： X Y 。 f48完全函数依赖完全函数依赖含义含义： 元组元组在属性组在属性组Y Y上的值上的值 依赖于依赖于 在属性组在属性组X X中中所有属性所有属性上的值上的值。49部分部分函数依赖函数依赖 设设 R(U)R(U)是一个是一个关系模式关系模式，U U 是关系是关系 R R 的属性全集；的属性全集； X,YX,Y 是是R R 的属性组（的属性组（X X，Y Y U U）；）； 若若X X Y , Y ,且且存在存在 X X X ,X

24、X ,X Y Y 则称则称 Y Y 部分部分函数依赖函数依赖于于 X X ；记作：；记作： X X Y Y 。P50部分函数依赖部分函数依赖含义含义： 元组元组在属性组在属性组Y Y的值的值， 只只依赖于依赖于 属性组属性组X X的的一部分属性一部分属性的值的值。51例：例： Students(Sno,Sname,Cno,Grade,Sdept,Sloc) 键键(Sno，Cno) Sno Sname 完全函数依赖完全函数依赖 (Sno，Cno) Sname 部分函数依赖部分函数依赖 由于由于Sno Sname fp52 传递函数依赖传递函数依赖 R(U)R(U)是一个关系模式，是一个关系模式，

25、U U 是关系是关系 R R 的属性的属性全集；全集；X,Y,ZX,Y,Z 是是R R 的属性组（的属性组（X X，Y,Z Y,Z U U）；）； 若若X X Y ,Y Y ,Y Z Z且且Z Z Y Y,Y ,Y X X 则称则称 Z Z 传递函数依赖传递函数依赖于于 X X ；记作：；记作： X X Z Z t53关于传递函数依赖的解释关于传递函数依赖的解释: : Z Z Y: Y:不考虑平凡函数依赖不考虑平凡函数依赖 Y Y X X: :例例：Sno SSN SSN (Sname, Sage)， 由于由于SSN Sno Sno （Sname, Sage） 是直接函数依赖，是直接函数依赖，

26、同一实体两个键同一实体两个键 存储上没有冗余！存储上没有冗余！? ?54传递函数依赖的含义传递函数依赖的含义： Z Z上的值可上的值可间接地依赖间接地依赖于于X X上的值，上的值， 关系模式中含两个关系模式中含两个多对一多对一联系形成的链，联系形成的链， 从而导致数据冗余。从而导致数据冗余。 55例：例：Students(Sno,Sname,Sdept,Sloc) 有有Sno Sdept Sdept Sloc 于是于是Sno Sloc是传递函数依赖，是传递函数依赖， 这里这里SlocSloc不仅依赖于键不仅依赖于键SnoSno 还依赖于非键属性还依赖于非键属性SdeptSdept56不同不同S

27、no 可以对应可以对应 相同的相同的Sdept 不同的不同的Sdept对应对应 相同的相同的Sloc。 表中表中 同一同一Sdept与与Sloc的信息的信息 对不同对不同Sno多次重复。多次重复。 数据冗余，由此带来潜在不一致性数据冗余，由此带来潜在不一致性( (修改时修改时) )。574.2.2 关系模式的规范化关系模式的规范化 为区分关系模式的优劣分为为区分关系模式的优劣分为 不同的范式不同的范式(Normal Form)一、第一范式到第三范式一、第一范式到第三范式1.第一范式第一范式(1NF) 关系模式关系模式R属于属于1NF，当且仅当当且仅当R中的每一属性中的每一属性A的值域只包含原子

28、项的值域只包含原子项(即不可分割的数据项即不可分割的数据项) 1NF是关系模式的基本标准是关系模式的基本标准58例：例： Students(Sno,Sname,Cno,Grade,Sdept,Sloc) Student 1NF P 存在问题：存在问题： (Sno，Cno) Sname 非键属性非键属性部分依赖于部分依赖于键键 由于由于Sno Sname 冗余、更新异常冗余、更新异常 实体集实体集 多对多联系多对多联系?592.第二范式第二范式(2NF) 关系模式关系模式R属于属于2NF当且仅当当且仅当 R属于属于1NF 且且每一非键属性每一非键属性完全完全函数依赖于键函数依赖于键。*去掉非键属

29、性对键的部分函数依赖去掉非键属性对键的部分函数依赖*R 1NF 且没有且没有组合组合键键 R2NF60 2NF的另一个定义的另一个定义: 不允许不允许非平凡函数依赖的左边非平凡函数依赖的左边 是是键的真子集键的真子集（右边不是键属性）（右边不是键属性） *两种定义的等价性两种定义的等价性61例：例： Students(Sno,Sname,Sdept,Sloc) 2NF SC(Sno,Cno,Grade) 2NF 性能改善性能改善但是但是:Sno Sdept Sdept Sloc 于是于是Sno Sloc 是传递函数依赖是传递函数依赖 这里这里非键属性非键属性Sloc不仅依赖于键不仅依赖于键Sn

30、o 还依赖于非键属性还依赖于非键属性Sdept 冗余冗余 异常异常623.第三范式第三范式(3NF) 关系模式关系模式R属于属于3NF当且仅当当且仅当 R属于属于1NF，且，且每一非键属性都非传递函数依每一非键属性都非传递函数依赖于键。赖于键。 去掉了非键属性对键的部分依赖去掉了非键属性对键的部分依赖与与传递依赖。传递依赖。关系模式关系模式R属于属于3NF必有必有R属于属于2NF633NF的另一个定义的另一个定义:? 任何非平凡的函数依赖任何非平凡的函数依赖 A1A2An B A1A2An 是是超键超键 (键键 决定决定 B) 或或 B是某个键的组成部分是某个键的组成部分 (键属性键属性/主属

31、性主属性)两种定义的等价性两种定义的等价性64例：例： Students(Sno,Sname,Sdept) 3NF 实体集和一个多对一实体集和一个多对一 SL(Sdept,Sloc) 3NF 一个多对一一个多对一 多个系在一个宿舍区多个系在一个宿舍区 多对多？多对多？ SC(Sno,Cno,Grade) 3NF 多对多多对多65 例：例： MovieStudios( title,year,length,genre, studioName,studioAddr) 函数依赖：函数依赖： (title,year) studioName studioName studioAddrMovieStudio

32、s 2NF2NF66分解为分解为: MS1(title,year,length,genre,studioName) 3NF3NF 实体实体 一个多对一一个多对一 MS2(studioName,studioAddr) 3NF3NF 一个多对一一个多对一多对一、多对多？多对一、多对多？674. DB模式中模式中每一关系模式为第每一关系模式为第N范式范式，称该，称该DB模模式为第式为第N范式范式。 通常通常DB设计设计要求达到要求达到3NF。 例：例： Students(Sno,Sname,Sdept,Sloc) 2NF SC(Sno,Cno,Grade) 3NF DB模式模式2NF 1NF 2NF

33、 3NF 逐级判定？逐级判定？ 68二、二、Boyce-Codd范式范式(BCNF) 关系模式关系模式R（U,F） 1NF， 若若 X Y F 且且Y X时时， 必有必有 X含有键含有键； 则则R（U,F） BCNF。换句话说，换句话说，每一非平凡函数依赖每一非平凡函数依赖决定因素都含有键决定因素都含有键，则则R（U,F） BCNF消除主属性对消除主属性对键键的部分依赖与传递依赖。的部分依赖与传递依赖。键可以多个键可以多个 含任意一个即可含任意一个即可69例：例：3NF的不足的不足 学生教师课程学生教师课程 STJ(S,T,J) J: subject 键键: (S,J ) (S,T) F: (

34、S,J) T, (S,T) J, T J 无非主属性无非主属性 是是3NF (左左:含键含键 右右:键的一部分键的一部分 3NF)P (S,T) J 主属性部分依赖于键主属性部分依赖于键70 有主属性对键的部分依赖有主属性对键的部分依赖 冗余冗余 ( (教师与课程的关系教师与课程的关系) ) 没有学生选修没有学生选修 TJ TJ 不可存不可存 TJ TJ 存多次存多次 修改不方便修改不方便 且且 易导致不一致易导致不一致 S T J - s1 t1 j1 s2 t1 j1 s3 t1 j1 s1 t2 j2 s4 t3 j271改进：改进： ST(S,T) BCNF TJ(T,J) BCNF

35、单一事物单一事物 单一联系单一联系 S T T J - - s1 t1 t1 j1 s2 t1 t2 j2 s3 t1 t3 j2 s1 t2 s4 t3 72 分解后没有分解后没有任何属性任何属性 对对键键的的部分依赖和传递依赖部分依赖和传递依赖 没有学生选修没有学生选修 TJ TJ 可存可存 TJ TJ 只存一次只存一次 修改方便修改方便 且且 不导致不一致不导致不一致73例：例： Movies(title,year,length,genre, studioName,starName) 键键: (title,year,starName) (title,year) studioName 左边

36、不包含键左边不包含键 由此说明由此说明 Movies 不是不是BCNF 常称常称 (title,year) studioName 为为BCNF违例违例 注意注意: 范式是对关系模式而言的范式是对关系模式而言的74 例：例： Movies1(title,year,length,genre,studioName)键键:(title,year) (title,year) (length,genre,studioName)左边为键左边为键 极小函数依赖集？极小函数依赖集？ 没有没有BCNF的违例的违例 所以所以 是是BCNF75 例：例： 双属性关系双属性关系 BCNF 设设R(A,B) 1)无非平凡

37、函数依赖无非平凡函数依赖 (A,B)是键是键 R BCNF 2) F: A B A是键是键 左边含键左边含键 R BCNF 3) F:B A B是键是键 左边含键左边含键 R BCNF 4)F:A B B A A或或B是键是键 左边含键左边含键 R BCNF76例：例： Students(Sno,Sname,Ssex,Sage,Sdept) BCNF Courses(Cno,Cname,Cpno,Ccredit) BCNF SC(Sno,Cno,Grade) BCNF DB 模式模式 BCNF77例：学生课程名次例：学生课程名次 SJP(S,J,P) 键键:(S,J) (J,P) F:(S,J

38、) P (J,P) S SJP(S,J,P) BCNF 决定因素含有键决定因素含有键78定理：若定理：若R属于属于BCNF，必有，必有R属于属于3NF。 反证法反证法: 假设假设R不是不是3NF X :键键 Z:非键属性非键属性 则则: 存在非平凡函数依赖存在非平凡函数依赖 X Y Y Z Y X Y 不含有不含有键键 有非平凡函数依赖有非平凡函数依赖 Y Z 左边不含有左边不含有键键 则则R 不属于不属于BCNF 矛盾矛盾! 命题成立命题成立79 4.2.3 关系模式的分解关系模式的分解 将一个关系模式分解为几个子模式将一个关系模式分解为几个子模式 达到更高的范式达到更高的范式 提高性能提高

39、性能 80一、一、 分解规则分解规则: R(U)分解为子关系分解为子关系 S(U1 )和和 T(U2 ) 要求要求:1. U= U1 U22. S(U1 )中的元组是中的元组是R(U )中元组中元组 在在 U1 上的投影。上的投影。 T(U2 )中的元组是中的元组是 R(U)中元组中元组 在在U2上的投影。上的投影。81 例：例： Movies(title,year,length,genre, studioName,starName) 影片影片 影星与影片影星与影片(多对多多对多)分解为分解为: Movies1(title,year,length,genre,studioName) 影片影片

40、Movies2(title,year,starName) 影星与影片影星与影片(多对多多对多) 关系实例关系实例Movies在子关系上的投影在子关系上的投影82 二、分解为二、分解为BCNF的方法的方法 R(U)没有达到没有达到BCNF，将其分解为一组达到，将其分解为一组达到BCNF 的子关系模式。的子关系模式。 1）求键）求键 2）寻找）寻找BCNF的违例的违例 833）分解）分解 假定假定: XY 为为BCNF的一个违例的一个违例 Y=X + -X 从从X Y 分解分解 R1(X Y) R2(X (-X-Y)F844)分别对分别对R1，R2 求求R的极小函数依赖集的极小函数依赖集 在其上的

41、投影在其上的投影F1，F2 重复重复1) 2) 3) 直至得到一组达直至得到一组达 BCNF的子关系模式的子关系模式85三、函数依赖集的投影三、函数依赖集的投影 设有关系模式设有关系模式R(U,F)， S(U1,F1)为分解后得到的为分解后得到的子关系模式之一，求子关系模式之一，求F1 方法：方法： 对对S上的每一个属性集上的每一个属性集X，求，求X+ 再求再求X+ U1 若若S上的任何一个属性上的任何一个属性A X+ U1 A X 则则X A是是F1中的一个函数依赖中的一个函数依赖,依次计算得依次计算得F1 如果我们不能确定一个关系上成立的函数依赖，就无法判定是否属如果我们不能确定一个关系上

42、成立的函数依赖，就无法判定是否属于于BCNF。FFF86例例 设：设：R（U，F），），U=A，B，C，D， F=AB，BC，CD，DA =R1(A,B,C)，R2(C,D) 求：求：F在在R1、R2上的投影上的投影F1、F2 解：解： 令令: U1=A,B,C, U2=C,D 87对于对于U1=ABC： A+F = ABCD, A+FU1=ABC B+F = ABCD， B+F U1=ABC C+F = ABCD， C+F U1=ABC (AB)+F = ABCD， (AB)+F U1=ABC (AC)+F = ABCD， (AC)+F U1=ABC (BC)+F = ABCD， (BC)+

43、F U1=ABC88 F1 = AB，AC, BA, BC, CA, CB, ABC, ACB, BCA = AB， BC, CA 89对于对于U2 = CD： C+F = ABCD, C+FU2 =CD D+F = ABCD， D+F U2 =CD F2 = CD，DC 90 简化搜索依赖的过程简化搜索依赖的过程 1.不必考虑不必考虑S的属性全集的属性全集的闭包的闭包 2.只考虑只考虑函数依赖左边属性的属性集函数依赖左边属性的属性集的闭包的闭包91 例例: R(A,B,C,D) F=A B , B C S(U1,F1) U1=A,C 求求F1 解：解： A+=A,B,C A+ U1 = A,

44、C C不在左边不在左边 不考虑含不考虑含C的属性集的闭包的属性集的闭包 F1=AC FF92 例例: R(A,B,C,D,E) F=A D, B E, DE C S(U1,F1) U1=ABC 求求F1解：不考虑含解：不考虑含C的属性集的属性集 A+=A,D A+ U1=A B+=B,E B+ U1=B A,B+ =A,B,C,D,E A,B+ U1=A,B,C F1=AB CFFFFFF93四、分解为四、分解为BCNF的例的例例：例：R(A,B,C,D,E) F=ABC, BD, CD, DE 1）求）求R的键的键右侧不含右侧不含A，键含，键含A。A+=A,B,C,D,E A是键是键F2）

45、BD是是BCNF的违例的违例从从BD分解分解R1(B,D,E) R2(B,A,C)943) 对于对于R1(B,D,E)求函数依赖集的投影求函数依赖集的投影F1不考虑含的属性集不考虑含的属性集 B+=B,D,E B+ U1=B,D,E B D B E D+=D,E D+ U1=D,E D E B,+ =B,D,E B,D+ U1=B,D,E BD EFFFFFF化简化简 F1=B D, D E可求得可求得R1键为键为B(过程略过程略)D E为为BCNF违例，违例，由由D E分解分解R11(D,E),R12(D,B) 双属性双属性BCNF95) 对于对于R2(B,A,C)求函数依赖集的投影求函数依

46、赖集的投影F2 A+=A,B,C,D,E A+ U2=A,B,C A BC B+=B,D,E B+ U2=B C+=C,D,E C+ U2=C A,B+ =A,B,C,D,E A,B+ U2=A,B,C AB C B,C+ =B,C,D,E B,C+ U2=B,C A,C+ =A,B,C,D,E A,C+ U2=A,B ,C AC B FFFFFF化简化简 F2=A B,A C可求得可求得R2键为键为A(过程略过程略)无无BCNF违例违例R2达达BCNFFFFFFF5)结果结果 =R11(D,E),R12(D,B), R2(B,A,C)96例：例： Movies(title,year,leng

47、th,genre, studioName,starName) (title,year,starName)是唯一键是唯一键 (title,year) (length,genre,studioName) 是是BCNF违例违例分解为分解为: M1title,year, length,genre,studioName 和和M2title,year, starName 用算法可印证用算法可印证M1，M2都属于都属于BCNF97例：例： MovieStudios(title,year,length,genre, studioName,studioAddr) (title,year)唯一键唯一键 studi

48、oName studioAddr 是是BCNF违例违例分解为分解为: S1studioName, studioAddr 和和S2studioName, title,year,length,genre用算法可印证用算法可印证S1，S2都是都是BCNF98例：例： MSPtitle,year,studioName,president,presAddr title,year是键是键 title,year studioName studioName president是是BCNF违例违例 president presAddr是是BCNF违例违例由由studioName president,presAd

49、dr分解分解 选不满足选不满足BCNF的函数依赖时的函数依赖时,右侧应含尽量多右侧应含尽量多属性（闭包）属性（闭包）99MSPtitle,year,studioName,president,presAddr 由由studioName president,presAddr分解为分解为: MSP1studioName, president,presAddr 经算法判定经算法判定 不是不是BCNF 和和 MSP2studioName, title,year 经算法判定是经算法判定是BCNF100对于对于MSP1studioName, president,presAddr 由由BCNF违例违例 pre

50、sident presAddr 分解为分解为MSP11president, presAddr 和和MSP12president, studioName 都是都是BCNF最终分解为最终分解为: MSP2 studioName, title,year MSP11president, presAddr MSP12president, studioName101 五、五、 从分解中恢复信息从分解中恢复信息模式分解的标准：模式分解的标准： * 保持依赖的分解保持依赖的分解 子关系的函数依赖集可蕴涵原函数依赖集子关系的函数依赖集可蕴涵原函数依赖集 * 无损连接的分解无损连接的分解 由子关系经连接运算可恢复

51、原关系由子关系经连接运算可恢复原关系102考虑：考虑：R（A，B，C） B C是是BCNF的违例的违例 分解为分解为R1（A，B） R2（B，C） 若若A是键是键 A B B C 若（若（A,B）是键）是键 只有只有 B C R=R1 R2 即无损连接的即无损连接的 P53 证明不可能出现伪元组证明不可能出现伪元组103 看一个实例看一个实例,便于理解便于理解 R A B C R1 A B R2 B C a1 b1 c1 a1 b1 b1 c1 a2 b2 c2 a2 b2 b2 c2 a3 b2 c2 a3 b2 A B B C R1 R2: A B C a1 b1 c1 a2 b2 c2

52、与与R相同相同 a3 b2 c2104 一个实例一个实例 (A,B)是键是键 R A B C R1 A B R2 B C a1 b1 c1 a1 b1 b1 c1 a1 b2 c2 a1 b2 b2 c2 a2 b2 c2 a2 b2 a3 b2 c2 a3 b2 B C R1 R2: A B C a1 b1 c1 a1 b2 c2 a2 b2 c2 与与R相同相同 a3 b2 c2105 推广：推广： A，B，C 是属性组是属性组 B C是是BCNF的违例的违例 A是是B、C中没有出现的属性中没有出现的属性 R(A,B,C) 分解为分解为R1(A,B) R2(B,C) R=R1 R2 即即将

53、关系模式分解为将关系模式分解为BCNF的算法是无损连接的算法是无损连接的的106* 但不一定保持函数依赖但不一定保持函数依赖 R(A,B,C,D,E) AB C DE C B D ABE是键是键 由AB CD 分解为 R1（A,B,C,D） AB C B D R2（A,B,E） 对R1 由B D分解为 R11(B,D) B D R12(B,A,C) AB C DE C丢失丢失 (不蕴涵于子模式函数依赖集不蕴涵于子模式函数依赖集)107判断一个分解具有无损连接性的算法判断一个分解具有无损连接性的算法算法的输入：算法的输入： 关系模式关系模式R(A1,A2,An), R上的函数依赖集上的函数依赖集

54、F, R的一个分解的一个分解 =R1,R2,Rk算法的输出：算法的输出： true 或或 false108算法算法 LOSSLESSTEST(R,F , )构造一个构造一个k行行n列的二维表列的二维表T，第，第i行对应于关系模式行对应于关系模式Ri，第，第j列对应于属性列对应于属性Aj，令，令Tij=aj 若若Aj Ribij 若若Aj Ri109 c1:=true do while c1 c1:=false; for 每一个每一个XY F do for 每一对每一对ti, tk T do if tiX = tkX and tiY tkY then EQUY(ti, tk); c1=true

55、for 任一个任一个t T do if t=a1a2.an then return(true) return(false)110EQUY (ti,tk)是使是使ti, tk两个元组的两个元组的Y值相等的子处理过程，值相等的子处理过程，处理原则如下：处理原则如下： 若若tiY与与tjY 有一个为有一个为aj 则将另一个也改为则将另一个也改为aj 否则，否则，tkY=tiY 假定假定ik111例：关系模式例：关系模式 R(A,B,C,D,E) F=AC,BC,CD,DEC,CEA 分解为分解为 =R1(A,D)，R2(A,B)，R3(B,E), R4(C,D,E),R5(A,E ) 用上述算法用上

56、述算法 判断判断 是否具有无损连接性是否具有无损连接性112构造二维表构造二维表 A B C D ER1R2R3a1a3a2a1b23R4R5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41113由由AC,做的修改做的修改 A B C D ER1R2R3a1a3a2a1b23R4R5a5a4a2a4a1a5a5b13b33b53b12b15b24b25b34b31b54b52b42b41b13b13114由由CD做的修改做的修改 A B C D ER1R2R3a1a3a2a1b13R4R5a5a4a2a4a1a5a5b13b13b13b

57、12b15b24b25b34b31b54b52b42b41a4a4a4F=AC,BC,CD,DEC,CEA115结果二维表结果二维表 A B C D ER1R2R3a1a3a2a1R4R5a5a4a2a4a1a5a5b12b15b25b52b42a3a3a3a3a1a1a4a4a4算法输出算法输出true 是无损的是无损的116定理：关系模式定理：关系模式R(U)，分解为，分解为 =R1(U1),R2(U2) 是无损连接的是无损连接的当且仅当当且仅当U1 U2 U1-U2 或或U1 U2 U2-U1117保持依赖分解成保持依赖分解成3NF的算法：的算法： 1)对对R(U,F)求最小依赖集求最小

58、依赖集F2)若若F只有只有XA，且，且XA=U 转转4)3)若若U中有某些属性与中有某些属性与F中所有依赖的中所有依赖的 左部与右部都无关，则将它们构成一个关系模式左部与右部都无关，则将它们构成一个关系模式 4)将将F左部相同的依赖分组左部相同的依赖分组 每一组形成一个每一组形成一个 子关系子关系Ri(Ui,Fi) =R1(U1,F1),R2(U2,F2),.Rn(Un,Fn)118例：例：Students(Sno,Sname ,Sage,Dno,Classno,Tno,Cno,Grade) 给出一个保持依赖的分解给出一个保持依赖的分解左部相同的分为一组左部相同的分为一组 =R1(Sno,Sname,Sage,Classno), R2(Classno,Tno,Dno), R3(Sno,Cno,Grade )解：最小依赖集解：最小依赖集 F= Sno Sname,Sno Sage,Sno Classno Classno Tno, Tn