【数据库系统概论】关系数据理论

1、课间休息,注意时间,第五章 关系数据理论 5.1 问题的提出,一 、关系模式 一个关系模式应当是一个五元组: R(U, D, dom, F) 其中: (1) 关系名R; (2) 一组属性U; (3) 属性组U中属性所来自的域D; (4) 属性到域的映射dom; (5) 属性组U上的一组数据依赖 F,由于(3),(4)队模式设计关系不大，因此本章把关系模式看作是一个三元组： R ,二、 数据依赖的概念,比如描述一个学生的关系，可以有学号(SNO),姓名(SNAME),.系名(SDEPT)等几个属性. 称SNO函数决定SNAME和SDEPT，或者说SNAME、SDEPT函数依赖于SNO，记为：SN

2、OSNAME，SNOSDEPT。,要建立一个数据库来描述学生的一些情况，面临的对象有： 学生，系，系负责人，课程和成绩。于是得到一组属性。 U=SNO, SDEPT, MN,CNAME, G,由现实世界的已知事实,得到属性组U上的一组函数依赖: F=SNO SDEPT, STEPT NM, (SNO,CNAME) G,描述学校的数据库模式: S, 它是一个单一的关系模式,这个模式有三个“毛病”.,把上述单一的关系模式进行改造,分成三个关系模式: S(SNO, SDEPT,SNO SDEPT); SG(SNO,CNAME,G,(SNO,CNAME) G); DEPT(SDEPT,MN,SDEPT

3、 MN);,5.2 规 范 化,5.2.1 函数依赖 定义5.1 设R(U)是属性集U上的关系模式. X,Y是U的子集. 若对于R(U)的任意一个可能的关系r, r中不可能存在两个元组在X上的属性值相等,而在Y上的属性值不等,则称X函数确定Y或Y函数依赖于X,记作X Y.,5.2.2 码 定义5.4 设K为R(U, F)中的属性或属性组合, 若KU,则K为R的候选码(Candidate key)。,定义5.5 关系模式R中的属性或属性组X并非R的码, 但X是另一个关系模式的码，则称X是R的外部码(Foreign key)。也称外码。,5.2.3 范式,图5.2 各种范式之间的关系,5.2.4

4、2NF 定义5.6 若R1NF, 且每一个非主属性完全函数函数依赖于码, 则R2NF。,一个关系模式R不属于2NF,就会产生以下三个问题.,解决的办法是用投影分解把关系模式S-L-C分解为两个关系模式.,SC(SNO, CNO,G) S-L(SNO,SDEPT,CLOC),5.2.6 BCNF BCNF 比 3NF 更进一步，其消除主属性对码的部分与传递依赖。 1. 定义7.8： 关系模式R1NF，若XY且Y X时X必含有码， 则R BCNF 。 即： R 中，每一个决定因素都包含码，则R BCNF。,2. 结论： .所有非主属性对每一个码都是完全函数依赖。 显然，这是3NF的要求所达到的，非

5、主属性不部分、传递函数依赖于码。 .所有主属性对每一个不包含它的码，是完全函数依赖。 .没有任何属性完全函数依赖于非码的任何一组属性。,3. 举例： 例 1：关系模式 SJP（S，J，P）中，S 是学生，J 表示课程，P表示名次。 由语义得到下面的函数依赖： （S，J） P；（J，P） S 这个关系模式中显然没有属性对码传递函数依赖或部分依赖。所以SJP3NF。 又因除（S，J）与（J，P）以外没有其他决定因素。所以SJPBCNF。,例2 关系模式STJ(S,T,J)中,S表示学生,T表示教师, J表示课程. 由语义得到下面的函数依赖： （S，J） T；（S，T） J; T J STJ3NF,

6、 但STJ不是BCNF关系,因为T是决定因素,而T不是码.,5.2.7 多值依赖 一. 引入 例1 P178,二. 定义7.9 设R（U）是属性集U上的一个关系模式。X，Y，Z是U的子集，并且Z=U-X-Y，关系模式R(U)中多值依赖X Y成立, 当且仅当对R（U）的任一关系r, 给定的一对（x, z）值, 有一组Y的值，这组值仅仅决定于x值而与z值无关。,三. 举例 例2. 关系模式WSC(W,S,C)中,W表示仓库,S表示保管员,C表示商品.,四. 多值依赖的性质： (1).多值依赖具有对称性。即若XY，则XZ， 其中ZUXY。,(2). 多值依赖的传递性。 XY，YZ，则XZY。,(3)

7、. 函数依赖是多值依赖的特殊情况。即若XY，则XY.,(4). 若 XY，XZ，则XZY。,(5). 若 XY，XZ，则XZY。,(6). 若 XY，XZ，则XY-Z, XZ-Y 。,五. 多值依赖与函数依赖的基本区别,5.2.8 4NF 4NF 是消除了非平凡且非函数依赖的多值依赖。 1. 定义7.10： 关系模式R1NF，如果对于R的每个非平凡的多值依赖XY（YX） ，X都含有码，则称R 4NF 。 注：一个关系模式若属于4NF，则必然属于BCNF。,5.2.9 规范化小结 规范化的目的是：消除关系模式中存在的插入异常、删除异常、修改复杂和数据冗余等毛病。 基本思想是：逐步消除数据依赖中不

8、合适的部分，使概念单一化。 1NF2NF：消除非主属性对码的部分函数依赖。 2NF3NF：消除非主属性对码的传递函数依赖。 3NFBCNF：消除主属性对码的部分和传递函数依赖。 BCNF4NF：消除非平凡且非函数依赖的多值依赖。 方法：通过对关系模式的投影分解来实现的。,5.3 数据依赖的公理系统,定义5.11： 对于满足一组函数依赖F 的关系模式R ，其任何一个关系r,若函数依赖XY都成立，则称F 逻辑蕴含XY。 1.合并规则：由XY，XZ，有XYZ 2.伪传递规则：由XY，WYZ，有XWZ 3.分解规则：由XY，ZY，有XZ 定义5.12： 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做

9、F的闭包，记为F+ 定义5.13： 设F为属性集U上的一组函数依赖，XU，XF+=AX A能由F根据Armstrong公理导出 ， XF+称为属性集X关于函数依赖集F的闭包。 因此，要判定X Y是否能由F根据Armstrong公理导出，就要求出XF+，判定Y是否为XF+的子集。 这是由算法5.1来完成的。,算法5.1： 求属性集X（XU）关于U上的函数依赖集F的闭包XF+ 输入：X，F 输出： XF+ 步骤： .令X(0)=X，i=0 .求B . X(i+1)=BX(i) .判断X(i+1)=X(i) 吗？ .相等，则XF+ =X(i),算法终止 .不等，则i = i+1，返回,例1 已知关系

10、R ，U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB。 求(AB)F+ 由算法7.1得： 设X(0) =AB， 计算X(1)，扫描F中各函数依赖，找左部为A，B，AB的函数依赖：ABC，BD， 于是X(1)=ABCD=ABCD， 因为X(0) X(1) 计算X(2)，扫描F中各函数依赖，找左部为X(1)的子集的函数依赖：ACB，CE， 于是X(2)= X(1) BE=ABCDE， 因为X(3) X(2) 所以 (AB)F+= X(2) =ABCDE。,补充： 已知关系R ，U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB。 求R 的码？ 解法： 1.求出所有可能存

11、在的闭包X(i) =XF+ ， 2.若X(i) =U，则选出其中的X， 3.在X中选出最简的主属性组Xi , 4. Xi 就是所求的码。 具体解为： (AB)F+=ABCDE (B)F+=BD (C)F+=CBDE (EC)F+=CBDE,(AC)F+=ABCDE (ABC)F+=ABCDE (ABCE)F+=ABCDE (BC)F+=BCDE (BEC)F+=BCDE (AEC)F+=ABCDE 包含全部属性的有(AB)F+ ， (AC)F+ ， (ABC)F+ ， (ABCE)F+ ， (AEC)F+ 挑选出最简的是： (AB)F+ ， (AC)F+ 所以R 的码为： AB 和 AC,定义

12、5.15： 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集Fm ，亦称为最小依赖集，最小覆盖。 .F中任一函数依赖的右部仅含有一个属性。 .F中不存在这样的函数依赖XA，使得F与F-XA等价。 . F中不存在这样的函数依赖XA：X有真子集Z使得F -XA ZA与F等价。,定义5.14： 如果G+ =F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,例2：关系模式S ，U=SNO，SDEPT，MN，CNAME，G， F=SNOSDEPT，SDEPTMN，（SNO ，CNAME）G。 设F=SNOSDEPT，SNOMN，SDEPTMN,（SNO,CNAME）G

13、， （SNO,SDEPT）SDEPT 。 根据定义5.15可以验证F为最小覆盖, 而F不是。,定理5.3： 每一个函数依赖集F均等价于一个极小函数依赖集Fm (此Fm称为F的最小依赖集）。 求极小函数依赖集Fm的步骤：,例3 已知：F=AB，BA，BC，AC，CA 求F 的极小函数依赖集Fm 解： 1.化右部为单一属性：F=AB，BA，BC，AC，CA 2. 在F中去掉AB， (A)F+=AC，B (A)F+ ，不去掉。 在F中去掉BA ， (B)F+=ABC，A (B)F+ ，应去掉。 在F中去掉BC ， (B)F+=B，C (B)F+ ，不去掉。 在F中去掉AC， (A)F+=ABC，C (A)F+ ，应去掉。,在F中去掉CA， (C)F+=C，A (C)F+ ，不去掉。 3.因主属性是单属性，故不用再取其子集去考察。 故极小函数依赖集Fm=AB，BC，CA,例4 已知关系R ，U=A，B，C，D，E，F，G，H，I，J，F=AB，AC，ADE，DE，DEB，AFGHI，IJ。 求F 的极小函数依赖集Fm 解： 1.化右部为单一属性： ADE AD，AE AFGHI AFG， AFH， AFI 则F=A