《关系数据库理论》PPT课件

1、第六章关系数据库理论，6.1问题的建议6.2规范化6.3数据依赖的巩俐系统6.4模式的分解6.5摘要，6.3数据依赖的巩俐系统，逻辑定义6.11。满足函数依赖F的关系模式R，任何关系R，函数依赖XY都成立的话，F逻辑包含X Y，查找Armstrong巩俐系统，推理规则集，模式分解算法的理论基础用途给定关系模式的代码从函数依赖中隐含的函数依赖，1 .对于Armstrong巩俐系统，关系模式R，有以下推理规则：Al .磁反比：A2 .扩增法：如果XY包含在f中，Z U，则XZYZ包含在f中。A3 .传递法：如果XY和YZ包含在f中，则XZ包含在f中。注：自反律所获得的函数依赖都是普通的函数依赖。磁

2、反法的使用不依赖于f。定理6.l Armstrong推理规则是正确的。(l)磁反法： Y X U，X Y在f包含的证据：中设置Y X U与r的关系r中的两个元组t。所以XY成立了。自反法证明，定理6.l(继续)，(2)增广法3360，XY包含在F中，如果XY是Z U，则XZYZ包含在F中。证据：将XY设置为f中包含的Z U。设置r的关系r中的任意两个元组t，s。如果TXZ=sXZ，则tX=sX和tz=SZ由于XY具有tY=sY，因此tYZ=sYZ，因此XZYZ包含在f中。清理6.l(继续)，(3)传递法：如果XY和YZ包含在f中，则XZ包含在f中。证据：将XY和YZ设置为f包含的。r的关系r中

3、的任意两个元组t，S. TX=sX，则由于XY，ty=sy。因为再次有YZ，tZ=sZ，所以XZ是F包含的。转交法律证。2 .导出规则，1 .根据A1、A2和A3的三个茄子推断规则，合并规则：XY、XZ和XYZ。(A2，A3)医生传递规则：XY、WYZ和XWZ。(A2，A3)分解规则：XY和ZY，XZ。(A1，A3)，导出规则，2 .根据合并规则和分解规则，建立6.1辅助6.l XA1 A2Ak所需的条件为XAi成立(i=l，2，K)。3 .函数依赖闭包，6.l2在关系模式R中定义依赖于逻辑包含在F中的函数的整体称为F的闭包，并被写为F。定义6.13 f是属性集U的函数依赖项，X U，XF=A

4、|XA可根据Armstrong公理从f派生。XF称为属性集x。将函数从属集f的闭包、闭包辅助的6.2 f设置为属性集u的函数从属。x，Y U XY根据Armstrong公理导出的充分必要条件是判断Y XF用途是否根据Armstrong公理导出XY的问题。求XF以确定Y是否为XF子集的问题，求闭的算法，算法6.l属性集X(X U)是关于依赖于U的函数的集F的闭X U。f输出：XF阶段：(1) X(0)=X，i=0 (2)请求b，其中b=a | (v) (w) (VWF v x (I) a w)(5)如果等于或X(i)=U，则X(i)为XF，算法结束。(6)否则，返回到i=i l，步骤(2)。对于

5、算法6.l，ai=|X(i)|，ai形成步骤大于1的严格递增序列，序列的上限为| U |，因此算法将结束最大值|U|-|X|差周期。U=A、B、C、D；F=A B，BC D；A=ab.c=C. (AC)=abcd。实例，函数从属闭包，示例1已知关系模式r，其中U=A，b，c，d，e；F=ABC、BD、CE、ECB、ACB。(AB)求F。解决方案x(0)=ab；(1) X(1):计算扫描F集合中的每个函数相关性，以查找左侧具有A、B或AB的函数相关性。得到两件事：ABC，BD。所以X(1)=ABCD=ABCD。函数依赖闭包，(2)因为X(0) X(1)，找到左侧ABCD子集-函数依赖项，从而得到

6、ABC、BD、CE、ACB。因此，因为x (2)=x (1) (3) X(2)=U，所以算法终止(AB)F=ABCDE。，4 .Armstrong公理体系的有效性和完整性，有效性：从F出发，根据Armstrong公理导出的所有函数的依赖性必须从F中/* Armstrong的正确完整性：依赖F的每个函数必须从F出发，根据Armstrong公理导出/*；完全完整：一切不能用Armstrong公理导出，不是真实的。f不能用Armstrong公理导出。F F F F F，5。函数从属集等价物，如果定义6.14 G=F，则函数从属集F定义为G(F是G的coverage，或者G是F的coverage)。函

7、数依赖集等的充分条件，辅助6.3 F=G的充分要求仅证明F G，G F证：的必要性，明确地证明了充分性。(1)如果是FG，则为XF XG。(2)取XYF有Y XF XG。所以XY (G)=G F G。(3)同样，因为可以证明G F，所以，f=g .要判断函数依赖集等价体，F G 的函数，需要逐个地依赖XY，调查Y是否属于XG。(约翰f肯尼迪，函数，函数，函数，函数，函数，函数，函数)因此，辅助定理6.3给出了判断两个函数依赖集等价性的可行算法。6 .如果函数从属关系集f满足以下条件，则f称为最小函数从属关系集：也称为最小从属集或最小重新定义。(1) F的函数依赖的右侧部分只有一个属性。(2)

8、F没有这些函数。因为依赖XA，所以F等于F-XA。(3) F没有这些函数。依赖XA。x具有实际子集Z，因此F-XAZA等于F。最小从属关系集(继续)，示例2 6.l部分中关系模式s的U=SNO、SDEPT、MN、CNAME、g、F=SNOSDEPT、SDEPTMN、(F -SNOMN和F等最小化过程，定理6.3牙齿Fm被称为F的最小从属集合证：配置证明，根据定义，步骤3“最小化处理”F，以找出F的最小依赖集。(1)逐个检查f中的每个函数是否依赖FDI: XY，如果Y=A1A2 Ak，k 2，则将XY替换为xaj | j=1，2，k。辅助定理6.1保证了f变换前后的等价性。最小化过程(继续)，(

9、2)逐个检查F中的每个函数是否依赖FDI: xa，创建G=F-XA，如果是AXG，则从F中删除函数相关性。F转换前后相等，因为F等于G=F-XA的填充条件为AXG。最小化过程(继续)，(3) f中的每个函数都弹出，FDI: xa，X=B1B2Bm，Bi (i=l，2，m)，A(X-Bi)F F F，最小化过程(继续)，按定义，最后剩下的F必须是最小依赖集。f的每个“变换”都与变换前后的两组函数从属关系相同，因此其馀f与原始f相同。证明定理6.3的证明过程也是求F最小依赖集的过程，最小化过程(继续)，示例3 F=AB，BA，BC，AC，CA Fm1，Fm2是F的最小依赖集。Fm1=AB、BC、c

10、c CA F的最小从属集Fm不一定是唯一的。与依赖于每个函数的FDi和XA的X每个属性的处理顺序相关。最小化过程(继续)、最小化过程(清理6.3的证明)是验证F是否为最小从属集的算法。如果变形的F等于原始F，则F本身是最小从属集，这是最小化过程。相反，R2的关系也必须是R1的关系。、第6章关系数据库理论、6.1问题的提出6.2正则化6.3数据依赖的巩俐系统6.4模式的分解6.5摘要、6.4模式的分解3茄子模式分解的定义分解具有无损连接分解。要保持函数依赖分解，必须保持函数依赖关系并保持无损连接。阵列的分解(继续)，6.16关系模式R的分解定义：=R1，R2，Rn U=U1U2Un，没有Ui U

11、j。Fi定义Ui中F投影的6.17函数。集合XY | XY F XY Ui中的复盖Fi称为属性Ui中的F投影。模式分解(继续)，例如： SL(Sno，Sdept，SLOC) F=SNOSDEPT SnoSloc SL2NF存在插入异常、排除异常、冗馀和更正复杂性等问题。有多种分解方法。图案分解(继续)，SL SNOSDEPTSLOC 95001 cs A 95002 ISB 95003 MAC 95004 ISB 95005 PHB，1。SL被分解为SN(Sno) SD(Sdept) SO(Sloc)的三种茄子关系模式，分解的关系为SN SD Sno Sdept Sloc 95001 cs a

12、 95002 is b 95003ma c。如果分解的关系可以通过自然连接恢复为原始关系，则牙齿分解不会丢失任何信息SL分解被分解为NL(Sno，Sloc) DL(Sdept)中的两种茄子关系模式。Sloc)分解后的关系是NL DL SNO SLOC SDEPT SLOC 95001 A CS A 95002 B ISB 95003 c MAC 95004 B PH B 95005 B，模式分解(继续)。Nl dl SnO sloc sdept 95001 a cs 95002 b is 95002 b ph 95003 c ma 95004 b is 95004 b ph 95005 b is 95005 b ph 95005 b is 95005 b ph，模式分解(继续)，NL DL比原始SL关系包含三个元组将SL分解为两个茄子关系模式，称为ND (SNO，SDEPT) NL。Nd nl SnO sdept SnO SLoc 95001 cs 95001 a 95002 is 95002 b 95003ma 95003 c 95004 is 95004 b 95004 b 95005 ph 95005 b，分解模式(继续)，Nd nl SnO sdept SLoc图案分解(继续)第三分解方法有无损连接问题：牙齿。牙齿分解方法不保留原始关系的函数。依赖于SL中的函数的Sde