第06章 关系数据理论(3)

1数据库系统概论AnIntroductiontoDatabaseSystem第六章关系数据理论（3）2复习1.两个概念逻辑蕴含、函数依赖闭包2.Armstrong公理系统及导出规则自反律、增广律、传递律合并规则、伪传递规则、分解规则3.XF+的概念和计算方法4.函数依赖集的等价3引例：描述一个学校的数据库StudentU、F：U＝{Sno,Sdept,Mname,Cno,Grade}F＝{Sno→Sdept,Sdept→Mname,Sno→Mname,(Sno,Cno)→Grade}6.3数据依赖的公理系统47.最小依赖集：定义6.15如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖。F中任一函数依赖的右部仅含有一个属性。F中不存在这样的函数依赖X→A，使得F与F–{X→A}等价。F中不存在这样的函数依赖X→A，X有真子集Z使得F–{X→A}∪{Z→A}与F等价。6.3数据依赖的公理系统5例：设关系模式SU,F中,U={Sno,Sdept,Mname,Cno,Grade}设：F={Sno→Sdept,Sdept→Mname，(Sno,Cno)→Grade}F’={Sno→Sdept，Sno→Mname，Sdept→Mname,(Sno,Cno)→Grade，(Sno,Sdept)→Sdept}，验证：F是最小覆盖，而F’不是。因为：F’–{Sno→Mname}与F’等价；F’–{(Sno,Sdept)→Sdept}∪{Sno→Sdept}也与F’等价。F’–{(Sno,Sdept)→Sdept}也与F’等价；6.3数据依赖的公理系统68.求F最小依赖集Fm的过程6.3数据依赖的公理系统(1)逐一检查F中各函数依赖FDi：X→Y,若Y=A1A2…Ak,k2，则用{X→Aj|j=1，2，…，k}来取代X→Y。引理6.1保证了F变换前后的等价性。定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。求最小依赖集的步骤：（即定理的证明过程）78.求F最小依赖集Fm的过程6.3数据依赖的公理系统(3)逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考查Bi（i=l，2，…，m），若A（X-Bi）F+，则以X-Bi取代X。因为：F与F-{X→A}∪{Z→A}等价的充要条件是AZF+，其中Z=X-Bi,所以：F变换前后是等价的。(2)逐一检查F中各函数依赖FDi：X→A，令G=F-{X→A}，若AXG+，则从F中去掉此函数依赖。因为：F与G=F-{X→A}等价的充要条件是AXG+所以：F变换前后是等价的。8例：F={A→B，B→A，B→C，A→C，C→A}，确定F的最小依赖集。Fm1={A→B,B→C,C→A}Fm2={A→B,B→A,A→C,C→A}6.3数据依赖的公理系统F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及X→A中X各属性的处理顺序有关。练习：设有关系模式RU,F，其中：U＝｛E,F,G,H｝函数依赖集F={E→G，G→E，F→EG，H→EG，FH→E}，求F的最小依赖集9练习：设有关系模式RU,F，其中：U＝｛E,F,G,H｝函数依赖集F={E→G，G→E，F→EG，H→EG，FH→E}，求F的最小依赖集6.3数据依赖的公理系统(1)将函数依赖右边的属性单一化E→G，G→E，F→E，F→G，H→E，H→G，FH→E(3)去掉函数依赖左边多余的属性E→G，G→E，F→E，F→G，H→E，H→G，FH→E(2)去掉多余的函数依赖Fm={E→G，G→E，F→E，H→E}E→G，G→E，F→E，H→E，FH→E10练习：设有关系模式RU,F，其中：U＝｛E,F,G,H｝函数依赖集F={E→G，G→E，F→EG，H→EG，FH→E}，求F的最小依赖集6.3数据依赖的公理系统Fm=｛E→G，G→E，F→G，H→E｝=｛E→G，G→E，F→G，H→G｝=｛E→G，G→E，F→E，H→E｝=｛E→G，G→E，F→E，H→G｝11练习：F={AB→C，BC→D，ACD→B，D→EG，C→A,BE→C,CG→BD,CE→AG}，计算F的等价的最小依赖集Fm。6.3数据依赖的公理系统(1)将函数依赖右边的属性单一化F1＝AB→C，BC→D，ACD→B，D→E，D→G，C→A，BE→C，CG→B，CG→D,CE→A，CE→GF2＝AB→C，BC→D，CD→B，D→E，D→G，C→A，BE→C，CG→B，CG→D，CE→G(2)去掉F1中函数依赖左边多余的属性(3)去掉F2中多余的函数依赖F3＝AB→C，BC→D，CD→B，D→E，D→G，C→A，BE→C，CG→D，CE→G去掉CG→B去掉：ACD→B中的A,CE→A中的E12第六章关系数据理论6.1数据依赖6.2规范化6.3数据依赖的公理系统6.4模式的分解136.4模式的分解把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的；什么样的分解才有意义？只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义。分解的目的解决关系模式中可能存在的插入、删除和修改时的异常情况。14──────────────SnoSdeptMname──────────────0215121CS张三0215122IS李斯0215123MA王武0215124IS李斯0215125CS张三──────────────6.4模式的分解例:SL（Sno，Sdept，Mname）F={Sno→Sdept，Sdept→Mname}几范式？15分解后的关系为：R1：R2：R3─────────────SnoSdeptMname─────────────0215121CS张三0215122IS李斯0215123MA王武0215124────────0215125─────注意：分解后的数据库丢失了许多信息例如：无法查询0215121学生所在系或系领导。6.4模式的分解(1)SL分解为下面三个关系模式：ρ={R1Sno,φ，R2(Sdept,φ)，R3(Mname,φ)}16(2)SL分解为下面二个关系模式：ρ={R1{Sno,Sdept},{Sno→Sdept}，R2{Sno,Mname}，{Sno→Mname}}分解后的关系为：R1：────────R2：────────SnoSdeptSnoMname────────────────0215121CS0215121张三0215122IS0215122李斯0215123MA0215123王武0215124IS0215124李斯0215125CS0215125张三────────────────6.4模式的分解17R1R2──────────────SnoSdeptMname──────────────0215121CS张三0215122IS李斯0215123MA王武0215124IS李斯0215125CS张三──────────────6.4模式的分解尽管自然连接的结果包含了原来的所有元组，满足了无损连接，但仍然存在数据冗余，这时由于丢失了原来的函数依赖。R1：R2：───────────────SnoSdeptSnoMname───────────────0215121CS0215121张三0215122IS0215122李斯0215123MA0215123王武0215124IS0215124李斯0215125CS0215125张三───────────────18(3)将SL分解为下面二个关系模式：ρ={R1{Sno,Sdept},{Sno→Sdept}，R2{Sdept,Mname}，{Sdept→Mname}}分解后的关系为：R1：─────────R2：──────────SnoSdeptSdeptMname───────────────────0215121CSCS张三0215122ISIS李斯0215123MAMA王武0215124IS──────────0215125CS─────────6.4模式的分解19R1R2──────────────SnoSdeptMname──────────────0215121CS张三0215122IS李斯0215123MA王武0215124IS李斯0215125CS张三──────────────6.4模式的分解分解后的关系可以通过自然连接恢复为原来的关系，又没有丢失函数依赖。与SL关系一样，没有丢失信息206.4模式的分解1.关系模式分解的标准三种模式分解的等价定义(1)分解具有无损连接性(2)分解要保持函数依赖(3)分解既要保持函数依赖，又要具有无损连接性216.4模式的分解定义6.16关系模式RU,F的一个分解是指ρ={R1U1,F1,R2U2,F2,…RnUn,Fn}其中：U=U1∪U2∪…∪Un，且UiUj，Fi为F在Ui上的投影．定义6.17函数依赖集合{X→Y|X→YF+∧XYUi}的一个覆盖Fi叫作F在属性Ui上的投影.22定义6.18：关系模式RU,F的一个分解：ρ={R1U1,F1，R2U2,F2，…，RnUn,Fn}若R与R1、R2、…、Rn自然连接的结果相等，则称关系模式R的这个分解ρ具有无损连接性特点：具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题第二种分解方法具有无损连接性，但存在的问题？6.4模式的分解23关于模式分解的几个重要结论：(1)如果要求分解保持函数依赖，那么总可以达到3NF，但不一定能达到BCNF；(2)如果要求连接具有无损连接的特性，那么一定可以达到BCNF；(3)如果要求分解既保持函数依赖，又具有无损连接的特性，那么分解可以达到3NF，但不一定能达到BCNF。6.4模式的分解246.4模式的分解结论：如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持函数依赖，则它可以减轻或解决操作异常。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。25[练习]设有关系模式RU,F,其中：U={A,B,C},F={AB→C,C→B}1.候选码是什么？2.确定该关系模式是几范式？3.若要求在保持函数依赖的前提下，能分解成BCNF范式吗？6.4模式的分解结论：在实践中BCNF的意义并不大，因为我们对模式分解的要求总是既要满足无损连接性，又要保持函数依赖。262.判断模式分解具有无损连接性的方法算法6.2判断一个分解的无损连接性ρ={R1U1,F1，R2U2,F2，…，RkUk,Fk}是RU,F的一个分解，U={A1，A2…，An}，F={FD1，FD2，…，FDρ}，不妨设F是极小依赖集，记FDi→A1i：(1)建立一张n列k行的表；若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij；(2)对每一个函数依赖做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有ali则全部改为ali；否则全部改为bmli，m是这些行的行号最小值；若有一行成为a1,a2,…an。则算法终止6.4模式的分解276.4模式的分解例：已知RU,F，U={A,B,C,D,E}，F={AB→C,C→D,D→E}，R的一个分解为R1{A,B,C},R2{C,D},R3{D,E}。(1)构造初始表ABCDER1R2R3a1a2a3b14b15b21b22a3a4b25b31b32b33a4a5286.4模式的分解例：已知RU,F，U={A,B,C,D,E}，F={AB→C,C→D,D→E}，R的一个分解为R1{A,B,C},R2{C,D},R3{D,E}。(1)构造初始表(2)对AB→C，因各元组没有相同的分量，所以表不改变。由C→D可以把b14改为a4由D→E可以把b15和b25改为a5ABCDER1R2R3a1b21b31a2b22b32a3a3b33b14a4a4b