第6章关系数据理论20142.ppt

第6章关系数据理论 【例3】U={S#，SD，MN，C#，G} F={S#?SD，S#?MN，SD?MN，(S#,C#)?G} U1={S#，SD} , F1={S#?SD} U2={S#, MN, C#, G}, F2={S#?MN, (S#,C#)?G} 解： U1∩U2= {S#} U1-U2= {SD} ∴ U1∩U2?U1?U2∈F+ ∴该分解?具有无损连接性。 如果两个关系模式之间的公共属性集至少包含其中一个关系模式的码，则此分解具有无损连接性。 【例4】U={A，B，C} F={A?B，C?B} U1={A，B} , F1={A?B} U2={B, C}, F2={C?B} 解： U1∩U2= {B} U1-U2= {A} , U2-U1= {C} ∵ B?A, B?C ? F+ ∴该分解?不具有无损连接性。 6.4.3 保持函数依赖的模式分解 【定义6.19】设关系模式RU,F被分解为若干个关系模式R1U1,F1，R2U2,F2，…，RnUn,Fn 若F+ = (∪ Fi)+， 则称R U , F 的分解 ? = {R1U1 , F1 , … , RnUn , Fn} 保持函数依赖。 即F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的（Preserve dependency）。 【例3】 U = (A, B, C, D, E,G), F = {AB?C, C?A, BC?D, ACD?B, D?EG , BE?C , CG?BD, CE?AG }, 计算 (BD)F+ 。 解： X(3)已等于全部属性集合,所以(BD)F+={ABCDEG }。 4. 函数依赖集的覆盖问题 (1) 函数依赖集的等价 从蕴含(或导出)的概念出发，又引出了两个函数依赖集的等价和最小依赖集的概念。 【定义6.14】 如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。 引理6.3： F+=G+ 的充分必要条件是F ? G+ ,和G ? F+ 。 要判定F ? G+，只须逐一对F中的函数依赖X→Y，考察 Y 是否属于XG+ 就行了。 因此引理6.3 给出了判断两个函数依赖集等价的可行算法。 【例4】U = (A, B, C, D), F = {A?B, B?C, C?D, C?B}, G = {A?C, B?D, B?C, C?B},问，F与G是否等价。 解： (1) A?B，AG+={ACBD},B ?AG+, ∴A?B∈G+ (2) B?C，BG+={BDC},C?BG+, ∴B?C∈G+ (3) C?D，CG+={CBD},D?CG+, ∴C?D∈G+ (4) C?B，CG+={CBD},B?CG+, ∴C?B∈G+ ∴F ? G+ 【例4】U = (A, B, C, D), F = {A?B, B?C, C?D, C?B}, G = {A?C, B?D, B?C, C?B},问，F与G是否等价。 同理： (1) A?C，AF+={ABCD},C ?AF+, ∴A?C∈F+ (2) B?D，BF+={BCD},D?BF+, ∴B?D∈F+ (3) B?C，BF+={BCD},C?BG+, ∴B?C∈F+ (4) C?B，CF+={CDB},B?CF+, ∴C?B∈F+ ∴G ? F+ ∴ F ? G （2） 最小函数依赖集 【定义6.15】 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 F中任一函数依赖的右部仅含有一个属性。 F中不存在这样的函数依赖X→A，使得 F与F-{X→A}等价。 F中不存在这样的函数依赖X→A, X有真子集Z使得F-{X→A}∪{Z→A}与F等价。 三个条件的作用： （1）单属性化：保证每个函数依赖X ? A，A不会是组合的属性 。 （2）无冗余化：保证F中没有重复的函数依赖。 （3）既约化：保证每个函数依赖左部的属性最小化 。 【例5】 考察6.l节中的关系模式S〈U,F〉,其中： U={SNO，SDEPT，MN，CNAME，G}, F={SNO→SDEPT，SDEPT→MN，(SNO,CNAME)→G} 设F’={SNO→SDEPT，SNO→MN，SDEPT→MN，(SNO，CNAME)→G，(SNO，SDEPT)→SDEPT} 根据定义6.15可以验证F是最小覆盖，而F’不是。 因为F’-{SNO→MN}与F ’等价, F’-{(SNO,SDEPT)→S