《 关系数据理论()(上海电力学院)》由会员分享，可在线阅读，更多相关《 关系数据理论()(上海电力学院)（91页珍藏版）》请在金锄头文库上搜索。
1、第四章 关系数据理论之二关系模式规范化的基本步骤（考查非平凡函数依赖）1NF 消除非主属性对候选码的部分函数依赖2NF 消除非主属性对候选码的传递函数依赖3NF 消除决定因素不包含候选码的函数依赖BCNF 回顾小结与练习：练习1：问：关系模式R中的属性全部是主属性,则R的 最高范式必定是_。3NF练习2： 如下表所示的关系R，下列选项中关于该关系模 式属于第几范式判断正确的是（ ）。A、不是3NF B、是3NF但不是2NF C、是3NF但不是BCNF D、是BCNF9P425P38P225P1单价零件号任何一个二元关系必 定属于基于函数依赖 最高范式BCNF。D练习3： （3）有如下所示的关系
2、R2，判关系模式属于第 几范式（ ）。A、1NF B、2NF C、3NF D、4NF型材板材型材线材材料名武汉M4广东M3武汉M2武汉M1生产厂材料号B学习要点： （1）理解Armstrong公理系统。（2）掌握闭包计算算法。（3）掌握最小函数依赖集计算算法。（4）掌握关系模式分解无损连接性判定方法。内容提要： 4.1基本知识点 4.2规范化 4.3Armstrong公理系统 4.4模式分解4.4.1无损连接性判定4.4.2函数依赖保持性4.4.3候选码的求解理论和算法4.4.4不同范式的模式分解算法 小结 4.5其它知识点(了解)4.5.1多值依赖4.5.2第四范式4.5.3多值依赖公理(课
3、后阅读)4.5.4第四范式模式分解算法(课后阅读 )4.3Armstrong公理系统函数依赖公理一套推理规则，是模式分解算法的理论基础 。 用途： （1）求函数依赖集闭包、属性集闭包。 （2）求最小函数依赖集。 （3）求给定关系模式的候选码。 （4）模式分解。一、逻辑蕴含的定义（p183） 定义1: 设F是关系模式R 的一个函数依赖 集，X,YU,对r，XY都成立, 则称F逻辑蕴 含X Y。另一等价定义：设F是关系模式R 的一个 函数依赖集，X,YU,若从F中的函数依赖可推 出X Y, 则称F逻辑蕴含X Y。二、推理规则（p183） 设关系模式为R （1）A1自反律（Reflexivity）：
4、 若Y X U，则X Y为F所蕴含。证明: 设Y X U （仅需了解！ ） R 的r中，对元组t，s： 若tX=sX，(1) Y X，则tY=sY，(2) 由(1),(2)可得XY成立，自反律得证。注意：由自反律所得到的 函数依赖均是平凡的函数 依赖，自反律的使用并不 依赖于F。如：(sno,sname)- sname（2）A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则 XZYZ为F所蕴含。证明： （仅需了解！ ） 设R 的r中，元组t，s； 若tXZ=sXZ （1）， 则有tX=sX和tZ=sZ；（2） XY，则有tY=sY，（3） 由(2),(3)可得：tYZ=s
5、YZ （4）由(1)，(4)可得，则XZYZ为F所蕴含， 增广律得证。如：sno-sname， sdeptU,sno,sdept-sname,sdept（3）A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所 蕴含。证明：设XY及YZ为F所蕴含。 对R 的 r，元组 t，s。 若tX=sX （1），XY，则 tY=sY； 又YZ，则有tZ=sZ （2）， 由(1),(2)可得：XZ为F所蕴含，传递律得 证。如：sno-sdept，sdept-dname 可得：sno-dname（4）由Armstrong公理得到以下推论:(p184) 1）、合并律：如果XY和XZ成立
6、，则XYZ 成立。 2）、伪传递律：如果XY和WYZ成立，则 WXZ成立。 3）、分解律：如果XY和ZY成立，则XZ 成立。（5）根据合并规则和分解规则，可得的引理：引理1： XA1 A2Ak成立的充分必要条件是 XAi （i=l，2，k）成立。 若已知：sno-sname,sdept 可得：sno-sname, sno-sdept若已知sno-sname, sno-sdept 可得： sno-sname,sdept三、函数依赖闭包定义定义2：由被F逻辑蕴涵的函数依赖的全体构成 的集合，称为F的闭包，记作F+。思考：关系模式R若有n个属性，则在模式 R上可能成立的函数依赖有_个，其中n个 属性
7、中组合成X有_个,组合成Y有_个。注：求F+是一个 NP-hard问题！2n2n4n四、 Armstrong公理系统的有效性、完备性1、有效性：由F出发可由Armstrong公理推导 出来的每一个函数依赖一定在F+中；2、完备性是指：F+中的每一个函数依赖，必 定可由F根据Armstrong公理推导出来。五、属性集关于函数依赖集闭包定义3：设关系模式R, Ai U(i=1,2,) 则称所有用Armstrong公理从F可推出的函数 依赖XAi，由Ai组成的属性集合称为X关于函 数依赖集F的闭包,记作XF+（或X+）。引理2：设R，X，YU，XY能由F根 据Armstrong公理导出的充分必要条件
8、是Y XF+。六、闭包计算算法1、计算XF+ 算法1：求属性集X关于函数依赖F的属性闭包 XF+。 关系模式R，XU。 输入：X，F。 输出：XF+ 步骤： （1）令X(0)=X，i=0 （2）求B，这里 B=A|(V)(W)(VWFVX(i) A W) 即在F中寻找其左边为X(i)的子集的函数依赖， 将其右边在X(i)中未出现过的属性组成的新集合 B 。实例（3）X(i+1)= X(i) B 。 （4）判断X(i+1)=X(i)吗？ （5）若相等或X(i+1)=U，则X(i+1)就是XF+，算法 终止。 （6）若否，则i+,返回第（2）步。实例实例1、 U=A, B, C, D; F=AB,
9、 BCD， BC; （1）求AF+ 解： X(0)=AX(1)=X(0) B=AB,显然X(1) X(0)。 X(2)=X(1) C=ABC,显然X(1) X(2)。 X(3)=X(2) D=ABCD=U，循环终止。 AF+=ABCD。逐一的扫描F集合中各个 函数依赖，找左部为A，的函 数依赖。其结果是： AB。 B未在闭包中，则将B加入闭 包集中。再逐一的扫描F集合， 在F中找出左边是AB子集 的函数依赖，其结果是： AB， BC。则C将加 入闭包集中。则再在F中找出左边是 ABC子集的函数依赖，其结 果是：AB， BC， BCD 。则D将加入闭包集 中。方法（2）求BF+。 X(0)=B
10、X(1)=BCD X(2)=BCD=X(1),循环终止。所以BF+ =BCD。 （3）求CF+ X(0)=C X(1)=C=X(0),循环终止。所以CF+ =C。方法（4）求(BC)F+。 X(0)=BC X(1)=BCD X(2)=BCD=X(1), (BC)F+ =BCD。（5）求(AC)F+。 X(0)=AC X(1)=ACB X(2)=ACBD=U (AC)F+ =ACBD。实例2、设有关系模式R（A，B，C，D，E） ，其上的函数依赖集： F=ABC，CDE，BD，EA （1）计算(AC)F+。 （2）计算(A)F+。 （3）计算(B)F+。 解： （1） (AC)F+ X(0)=A
11、C X(1)=ACB X(2)=ACBD X(3)=ACBDE=U (AC)F+=ABCDE（2） (A)F+=ABCDE。 （3） (B)F+=BD。 实例3、设关系模式R（U，F）， U=A，B，C，D，E，G，且 F=DG,CA,CDE,AB;求D+,C+,(AD)+ 解： D+=DG C+=CAB (AD)+=ADGB2、计算F+ (会方法即可)实例4:已知关系模式R(ABC),F=AC,BC, 求F+。解：U=A，B，C，左部不同的属性集组合 有23=8种：、A、B、C、AB、BC、AC、 ABC。（1）（2）(A)F+=ACA、AA、AC、AAC。（3）(B)F+=BC B、BB、
12、BC、BBC。 （4）(C)F+=C C、CC。 （5）(AB)F+=ABC AB、ABAB 、ABA、ABB 、 ABC、ABBC 、ABAC、ABABC 。 （6）(BC)F+=BC BC、BCBC、BCB、BCC。 （7）(AC)F+=BC AC、ACBC、ACB、ACC。 （8）(ABC)F+=ABC ABC、ABCABC 、ABCA、 ABCB 、ABCC、ABCBC 、ABCAB 、ABCAC。所以F+共有35个具体如下： 、A、AA、AC、AAC B、BB、BC、BBC C、CC、 AB、ABAB 、ABA 、ABB 、ABC、ABBC 、ABAC、 ABABC 、 BC、BCB
13、C、BCB、BCC、 AC、ACBC、ACB、ACC、 ABC、ABCABC 、ABCA、 ABCB 、ABCC、ABCBC 、 ABCAB、ABCAC七、函数依赖集的等价和覆盖 定义4：一个关系模式R（U）上的两个依赖集 F和G，如果F+=G+，则称F和G是等价的，(函 数依赖集F覆盖G（F是G的覆盖，或G是F的覆 盖）。记作FG。注：表示能力上是完全相同的。引理3:F+=G+的充要条件是FG+，且GF+。如：F1=sno-sname,sno- sdept,sdept-dname F2=sno-sname,sdept- dname,sno-sdept,sno- dname F1F2八、最小函
14、数依赖集 定义5:F为一个极小函数依赖集(或称最小依赖集 或最小覆盖),记作Fm;应满足条件如下：（1）Fm的右部都是单个属性。（2）确保在Fm中没有多余的函数依赖。（不存 在XA，使得Fm-XA与原Fm等价）。（3）Fm中左部没有多余的属性。（不存在XA，ZX，（Fm-XA） ZA 与原Fm等价）实例实例5：对于4.l节中的关系模式St， U=sno,sname,sdept,dname,cname,grade，F= snosdept, snosname, sdeptdname，（sno，cname）grade 设F=snosdept, snodname, sdeptdname， (sno，c
15、name)grade，(sno,sdept)sdept F是最小覆盖，而F 不是。 因为：F -snodname与F 等价F -(sno，sdept)sdept也与F 等价F -(sno，sdept)sdeptsnosdept也与F 等价back九、最小依赖集求解算法定理：每一个函数依赖集均等价于一个极小函 数依赖集m。此m称为的最小依赖集。1、计算最小依赖集算法输入：一个函数依赖集F。输出：F的一个等价最小依赖集Fm。方法：（1）应用分解规则，使中每一个依赖的右部属 性单一化。具体方法：逐一检查中各函数依赖 ，若12k, ( k2),则用XAj|j=1,2,k 来取代。实例（2）去掉多余的依赖。具体方法：逐一检查由每前一步 所得到的新函数依赖集Fi (i=1,
