数据库第九章

数据库系统原理1陈岭浙江大学计算机学院关系模型2第一范式关系数据库设计中易犯的错误Armstrong公理系统函数依赖理论关系模式分解函数依赖和关系模式分解第一范式3如果某个域中元素被认为是不可分的，则这个域称为是原子的非原子域的例子：―复合属性：名字集合―多值属性：电话号码―复杂数据类型：面向对象的如果关系模式R的所有属性的域都是原子的，则R称为属于第一范式（1NF）非原子值存储复杂并易导致数据冗余我们假定所有关系都属于第一范式第一范式4如何处理非原子值对于组合属性：让每个子属性本身成为成为一个属性对于多值属性：为多值集合中的每个项创建一条元组原子性实际上是由域元素在数据库中如何被使用决定的例，字符串通常会被认为是不可分割的假设学生被分配这样的标识号：CS0012或EE1127，如果前两个字母表示系，后四位数字表示学生在该系内的唯一号码，则这样的标识号不是原子的当采用这种标识号时，是不可取的。因为这需要额外的编程，而且信息是在应用程序中而不是在数据库中编码关系数据库设计中易犯的错误5关系数据库设计要求我们找到一个“好的”关系模式集合。一个坏的设计可能导致数据冗余插入、删除、修改异常假设，我们用以下模式代替instructor模式和department模式：inst_dept(ID,name,salary,dept_name,building,budget)关系数据库设计中易犯的错误6数据冗余每个系的dept_name,building,budget数据都要重复一次缺点：浪费空间，可能会导致不一致问题关系数据库设计中易犯的错误7更新异常更新复杂，容易导致不一致问题。例，修改dept_name，很多相关元组都需要修改插入/删除异常使用空值(null)：存储一个不知道所在系的教师信息，可以使用空值表示dept_name,building,budget数据，但是空值难以处理模式分解8模式分解例，可以将关系模式(A,B,C,D)分解为：(A,B)和(B,C,D)，或(A,C,D)和(A,B,D)，或(A,B,C)和(C,D)，或(A,B)、(B,C)和(C,D)，或(A,D)和(B,C,D)例，将关系模式inst_dept分解为：―instructor(ID,name,dept_name,salary)―department(dept_name,building,budget)原模式(R)的所有属性都必须出现在分解后的(R1,R2)中：R=R1R2无损连接分解对关系模式R上的所有可能的关系rr=R1(r)R2(r)模式分解9例，分解R=(A,B)，得到R1=(A)和R2=(B)AB121AB12r=A(r)B(r)A(r)B(r)=AB1212≠r不好的分解!因为它不是无损连接分解，是非法的模式分解10目标：设计一个理论以判断关系模式R是否为“好的”形式（不冗余）当R不是“好的”形式时，将它分解成模式集合{R1,R2,...,Rn}使得―每个关系模式都是“好的”形式―分解是无损连接分解我们的理论基于：―函数依赖（functionaldependencies）―多值依赖（multivalueddependencies）函数依赖11设R是一个关系模式，且有属性集R，R函数依赖在R上成立当且仅当对任意合法关系r(R)，若r的任意两条元组t1和t2在属性集上的值相同，则他们在属性集上的值也相同。即，t1[]=t2[]t1[]=t2[]函数依赖于，函数决定借用了数学上的函数概念：x→f(x)fcfahbfa1234函数依赖12函数依赖：一种完整性约束，表示特定的属性值之间的关系，可以用来判断模式规范化和建议改进例，考虑r(A,B)及其下列实例r对此实例，AB不成立，但BA成立141537AB∵若B属性值确定了，则A属性值也唯一确定了。于是有B→A函数依赖13函数依赖是码概念的推广K是关系模式R的超码当且仅当KRK是R的候选码当且仅当KR，并且没有K，使R（不存在K的真子集，使之满足R）函数依赖14函数依赖使我们可以表达用超码无法表达的约束，考虑模式inst_dept(ID,name,salary,dept_name,building,budget)我们期望下列函数依赖成立：dept_namebuildingIDbuilding而不期望下列函数依赖成立：dept_namesalary函数依赖的使用15我们用函数依赖来：检查关系在给定函数依赖之下是否合法―若关系r在函数依赖集F下是合法的，则称r满足Fd4c2b3a3d3c2b3a2d2c2b2a2d2c1b2a1d1c1b1a1DCBAF＝{A→CAB→DABC→D}但，r={A,B}→DA→B,A→D,B→A,C→A,C→D,B→C,C→B,B→D,…函数依赖的使用16对合法关系集合指定约束―如果R上的所有合法关系都满足F,则称F在R上成立F＝{A→C，AB→D，ABC→D}d4c2b3a3d3c2b3a2d2c2b2a2d2c1b2a1d1c1b1a1DCBAr1(R)=r2(R)=…r3(R)=………注：容易判别一个r是否满足给定的F。不易判别F是否在R上成立。不能仅由某个r推断出F。R上的函数依赖F，通常由定义R的语义决定函数依赖17被所有关系实例都满足的函数依赖称为平凡的例，A→A，AB→A（ID,name）IDIDID一般地，若，则是平凡的。即，平凡的函数依赖：若，非平凡的函数依赖：若，函数依赖集的闭包18给定函数依赖集F，存在其他函数依赖被F逻辑蕴含例，如果AB且BC，则可推出AC被F逻辑蕴含的全体函数依赖的集合称为F的闭包，用F+表示F的闭包例，F={AB,BC}，F+={AB,BC,AC,AA,ABA,ABB,ACC,ABC,…}如何计算出F+例，R=(A,B,C,G,H,I)F={ABACCGHCGIBH}，那么F+=?Armstrong公理19可利用Armstrong公理找出F+：若，则(自反律)若，则(增补律)若且，则(传递律)Armstrong公理是正确有效的(不会产生错误的函数依赖)完备的(产生所有成立的函数依赖即F+)Armstrong公理20例，R=(A,B,C,G,H,I)F={ABACCGHCGIBH}F+的某些成员：AH：根据传递规则，由AB和BH得到AGI：用G增补AC得AGCG，再由CGI根据传递规则得到CGHI：由CGH和CGI，可根据函数依赖的定义导出“并规则”得到，或增补CGI得到CGCGI，增补CGH得到CGIHI，再利用传递规则得到Armstrong公理的补充定律21可用下列规则进一步简化F+的手工计算若与成立，则成立(合并律)若成立，则与成立(分解律)若与成立，则成立(伪传递律)以上规则可以从Armstrong公理推出例，考虑到，根据自反律可得到：，；再由传递律可得到：与成立计算F+22下列过程计算函数依赖集F的闭包：F+=FrepeatforeachF+中的函数依赖f对f应用自反律和增补律将结果函数依赖加入F+foreachF+中的一对函数依赖f1和f2iff1和f2可以使用传递律结合起来将结果函数依赖加入F+untilF+不再变化由于包含n个元素的集合含有个2n子集，因此共有2nX2n个可能的函数依赖后面会介绍完成此任务的另一过程属性集的闭包23如何判断集合是否为超码一种方法是：计算F+，在F+中找出所有i，检查{123…}=R。但是这么做开销很大，因为F+可能很大另一种方法是：计算的闭包定义：给定一个属性集，在函数依赖集F下由函数确定的所有属性的集合为F下的闭包(记做+)检查函数依赖是否属于F++判断是否为超码：R属于F+R+属性集的闭包24计算+的算法result:=a;while(result有变化)doforeachinFdobeginifresultthenresult:=resultenda+:=result避免了找F＋(反复使用公理)的麻烦属性集的闭包25例1，R=(A,B,C,G,H,I)F={ABACCGHCGIBH}(AG)+result=AGresult=ABCG(ACandAB)result=ABCGH(CGHandCGAGBC)result=ABCGHI(CGIandCGAGBCH)属性集的闭包26AG是候选码吗?AG是超码吗？―即，AGR？由于(AG)+R，所以AG是超码存在AG的子集是超码吗?―A+R？由于(A)+=ABCH，所以(A)+R，所以A不是超码―G+R？由于(G)+=G，所以(G)+R，所以G不是超码综上，AG是候选码属性集的闭包27例2，R=(A,B,C)，F={AB,BCA}，R的候选码是什么？∵(BC)+=(BCA)R，(AC)+=(ACB)R，(AB)+=(AB)R候选码是AC，BC属性闭包的用法28属性闭包算法有多种用途：测试超码(R?)―为检测是否超码，可计算+并检查+是否包含R的所有属性测试函数依赖(?)―为检测函数依赖是否成立(即是否属于F+)，只需检查是否+―即，可计算+，并检查它是否包含―这个检查简单而高效，非常有用计算F的闭包(F+=?)―对每个R，计算+，再对每个S+，输出函数依赖S正则覆盖29DBMS总是检查确保数据库更新不会破坏任何函数依赖。但如果F很大，其开销就会很大。因此我们需要简化函数依赖集直观地说，F的正则覆盖（记做Fc）是指与F等价的“极小的”函数依赖集合Fc中任何函数依赖都不包含无关属性Fc中函数依赖的左半部都是唯一的―例，11，12，112正则覆盖30如何计算Fc：删除多余属性，存在以下三种情况函数依赖集中存在可由其他函数依赖推导出的函数依赖―例，在F中AC是冗余的F={AC,AB,BC}函数依赖左边部分存在属性冗余―例，F={AB,BC,ACD}，即{AB,BC,ACD,AD}{AB,BC,AD}。所以F蕴涵F’={AB,BC,AD}，因此属性C是多余的Fc={AB,BC}由F:BC,=ABAC,又∵ACD,∴ABD;又∵AB,=AAB,∴AD,∴F蕴涵F’由Armstrong公理,AD蕴涵ACD正则覆盖31函数依赖右边部分存在属性冗余例，F={AB,BC,ACD}，即{AB,BC,AC,AD}，但AC可由AB和BC得到。所以F蕴涵F’={AB,BC,AD}，因此属性C是多余的无关属性32考虑函数依赖集合F及其中的函数依赖如果A并且F逻辑蕴含F’＝(F–{}){(–A)}，则称属性A在中是无关的―例，给定F={AC,ABC}B在ABC中是无关的，因为AC逻辑蕴含ABC如果A并且F’＝(F–{}){(–A)}逻辑蕴含F，则称属性A在中是无关的―例，给定F={AC,ABCD}C在ABCD中是无关的，因为即使删除C也能推出AC检测属性是否无关33为检测属性A在中是否无关计算在F下的(–{A})+检查(A–{})+是否包含。如果是，则A是无关的为检测属性A在中是否无关计算在F’=(F–{}){(