《SQL数据依赖》PPT课件.ppt

第11章关系数据库设计理论,引入：问题的提出,针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具关系数据库的规范化理论,问题,如何将所涉及到的数据组织存入到数据库中？是放在一个表中存放还是分在几个表中存放？每个表应由哪些属性组成？怎样设计才是科学合理的呢？,一个例子,学生关系模式,关系模式：学生(学号，姓名，课程号，课程名，成绩)语义说明如下：(1)一个学生可以选修多门课程，每门课程有多个学生选修(2)每个学生选修每门课程都有一个成绩,学生关系实例,该关系模式存在的问题,(1)插入异常如果存在某个学生因为某些原因没有选课，课程号为空，因此该学生的信息无法插入(2)删除异常如果学生毕业，删除学生信息的同时将课程的相关信息也删除了,该关系模式存在的问题,(3)数据冗余课程的信息重复出现，浪费存储空间。(4)更新异常更新时系统要付出很大的代价。,11.2函数依赖,11.1函数依赖的定义,设R(U)是属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作XY。X称为这个函数依赖的决定属性集。,举例,关系模式：学生(学号，姓名，性别，年龄)函数依赖：学号姓名学号性别学号年龄,说明,(1)函数依赖是指关系模式R的所有关系实例均要满足的约束条件(2)函数依赖要根据数据的语义来确定例如，在关系模式学生中，姓名性别、姓名年龄这两个函数依赖在什么条件下才成立？,补充：如何判断函数依赖,判断函数依赖的规则：如果两属性集X,Y之间有(1)1:1的联系，则XY(2)n:1的联系，则XY(3)m:n的联系，则XY，YX,属性间是一对一联系学号与姓名关系：1:1（不允许有同名学生）,存在函数依赖：学号姓名姓名学号，此时记作学号姓名,属性间是一对多联系学号与所在系关系：n:1(一个系有多名学生),存在函数依赖：学号所在系，多方为决定因素,属性间是多对多联系学号和课程号关系：m:n,函数依赖的分类,非平凡函数依赖/平凡函数依赖完全函数依赖/部分函数依赖传递函数依赖/直接函数依赖,(1)非平凡函数依赖/平凡函数依赖,关系模式R（U），U是R的属性集合，X，Y是U的子集，如果XY，但Y不包含于X，则称XY是非平凡函数依赖。若Y是X的子集，则称XY是平凡函数依赖。,说明,(1)对任一关系模式，平凡函数依赖必然成立(2)本节只讨论非平凡函数依赖(3)非平凡函数依赖易产生问题,举例,例如：对关系模式：选修(学号，课程号，成绩)来说，存在下面的函数依赖：(学号，课程号)学号(学号，课程号)课程号(学号，课程号)成绩,(2)完全函数依赖/部分函数依赖,在关系模式R(U)中，如果XY，并且对于X的任何一个真子集Z，ZY都不成立，则称Y完全函数依赖于X。如果XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X。,说明,(1)部分函数依赖易产生问题(2)完全函数依赖要求在函数依赖的决定因素中没有多余属性,举例,例如：对关系模式：选修(学号，姓名，课程号，成绩)来说，存在下面的函数依赖：(学号，课程号)成绩学号姓名,函数依赖图,该关系模式的码为(学号，课程号)，(学号，课程号)姓名是部分函数依赖,(3)传递函数依赖/直接函数依赖,关系模式R(U)，X、Y和Z是属性集U的子集，如果XY，YZ，Y不是X的子集，YX不成立，则称Z传递函数依赖于X。如果XY，YZ，YX，Y不是X的子集，则称Z直接函数依赖于X。,举例,例如：关系模式：学生(学号，所在系，系主任姓名)中存在下列函数依赖：学号所在系所在系系主任姓名,函数依赖图,11.2.2码,在关系模式R(U)中，K是U的子集，如果U完全函数依赖于K，则称K为R的一个候选码。,说明,(1)一个关系模式可以有多个候选码，可以选定其中的一个作为主码。(2)候选码可以有一个属性，也可以有多个属性。当候选码包含关系模式的所有属性时，称为全码。(3)候选码中的属性称为主属性，不在任何候选码中的属性称为非主属性。,11.3范式,范式(NormalForm)是对关系模式的规范形式的简称。关系模式的范式主要有4种：第一范式(1NF)、第二范式(2NF)、第三范式(3NF)和BC范式(BCNF)。,(1)第一范式(1NF),如果一个关系模式R的所有属性都是不可分的基本数据项，则称这个关系模式为第一范式，记为1NF。第一范式是对关系模式的最基本要求，不满足第一范式的数据库模式不能称为关系数据库。,(2)第二范式(2NF),如果关系模式R是1NF，并且每一个非主属性都完全函数依赖于R的码，则称R为第二范式，记为2NF。,举例,例如：关系模式：选修(学号，姓名，课程号，成绩)，存在下面的函数依赖：(学号，课程号)成绩学号姓名思考：码是什么？主属性是什么？非主属性是什么？,分析存在的问题,插入异常。删除异常。数据冗余。更新异常。,产生问题的函数依赖,(学号，课程号)姓名想想为什么？解决的方法：将这个关系模式分解为两个关系模式：学生(学号，姓名)选修(学号，课程号，成绩),分解后的函数依赖图,(3)第三范式(3NF),如果关系模式R是第二范式，并且每一个非主属性都不传递函数依赖于R的码，则称R为第三范式，记为3NF。,分析存在的问题,学生(学号，所在系，系主任姓名)中存在下列函数依赖：学号所在系所在系系主任姓名,解决方法,对关系模式进行分解，得到下面两个关系模式：学生(学号，所在系)系(系名，系主任姓名),分解后的函数依赖图,(4)BC范式(BCNF),设关系模式R1NF，如果对于R的每个非平凡函数依赖XY，X必为候选码，那么RBCNF,根据定义，每个决定因素都是候选码，可得,1、所有非主属性都完全函数依赖于每个候选码2、所有主属性都完全函数依赖于每个不包含它的候选码3、没有任何属性完全函数依赖于非码的任何一组属性,说明BCNF不存在部分函数依赖,若RBCNF每一个函数依赖的决定因素都是候选码R中的所有属性（主属性、非主属性）都完全函数依赖于候选码不存在部分函数依赖肯定是2NF,说明BCNF不存在传递函数依赖,若RBCNF，R3NF证明：采用反证法。设R不是3NF。则必然存在如下条件的函数依赖，XY（YX），YZ，其中X是候选码，Y是任意属性组，Z是非主属性。因为YX，所以Y不是候选码。又因为YZ，根据RBCNF,决定因素Y是候选码。二者相互矛盾，所以如果RBCNF，则R也是3NF,举例,例如：考虑关系模式：教学(学号，教师，课程)中，根据语义：每位教师只讲授一门课每门课由多个老师讲授某个学生选定某门课，就确定了一个固定的教师,函数依赖,(学号，课程)教师教师课程(学号，教师)课程分析：候选码是？主属性是？非主属性是？达到第几范式？,（学生S，教师T，课程J）,(1)数据冗余。虽然每个教师只开一门课，但每个选修教师这门课程的学生元组都要记录这一信息,（学生S，教师T，课程J）,(2)插入异常。当某门课程本学期不开，自然就没有学生选修。没有学生选修，因为主属性S不能为空，教师教课的信息就无法插入。同样原因，学生刚入校,尚未选课，有关信息也不能输入,（学生S，教师T，课程J）,(3)删除异常。如果选修某门课程的学生全部毕业，删除学生记录的同时,随之也删除了教师开设该门课程的信息。(4)更新异常。当某个教师开设的某门课程改名后，所有选修该教师该门课程的学生元组都要进行修改，如果漏改某个数据，则破坏了数据的完整性。,解决办法,将该关系模式分解为：讲授(教师号，课程号)学习(学号，教师号)分解后的函数依赖图：,如果R3NF，且R只有一个候选码，则R必属于BCNF（由于该候选码是唯一的决定因素，所以是BCNF）可用反证法证明,BCNF是函数依赖中最高级别,3NF已在很大程度上消除了插入异常和删除异常，但由于可能存在主属性对候选码的部分依赖和传递依赖，因此关系模式的分离仍不够彻底BCNF在函数依赖的范畴内，已经实现了模式的彻底分解，消除了产生插入异常和删除异常的根源，数据冗余也减少到极小程度,11.6数据依赖的公理系统,1.逻辑蕴含,对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖XY都成立,则称F逻辑蕴含XY（1）F本身包含的函数依赖（2）根据F可以推导出来的函数依赖,2.Armstrong公理系统,一套推理规则，是模式分解算法的理论基础用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖,Al.自反律（平凡函数依赖）：若YXU，则XY为F所蕴含A2.增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含A3.传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含,导出规则,合并规则：由XY，XZ，有XYZ（A2，A3）伪传递规则：由XY，WYZ，有XWZ（A2，A3）分解规则：由XY及ZY，有XZ（A1，A3）,3.求属性集关于F的闭包,引理,XA1A2Ak成立的充分必要条件是XAi成立（i=l，2，k）,F的闭包,在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+,计算F+是NP完全问题,属性集X关于函数依赖集F的闭包,设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包,引理,设F为属性集U上的一组函数依赖，X,YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+,用途,将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题,算法,求属性集X（XU）关于U上的函数依赖集F的闭包XF+输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B=A|(V)(W)(VWFVX（i）AW)；（3）X（i+1）=BX（i）,（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止（6）若否，则i=i+l，返回第（2）步,例,已知关系模式R，其中U=A，B，C，D，EF=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子集的那些函数依赖，又得到ABC，BD，CE，ACB，于是X（2）=X（1）BCDE=ABCDE(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE,练习,设F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG,求BDF+,如果BD的任一个子集都不能函数确定U,则属性集BD可作为候选码证明BD是一个候选码(怎么证明？),(1)求BDF+=U(2)求BF+和DF+，判断结果是否为U，如果不是，那么BD就是候选码,4.判断关系模式的规范化级别,设关系模式的函数依赖集F=ABCE,EAB,CD试问R最高属于第几范式？步骤：求候选码；判断主属性、非主属性判断是否存在非主属性对码的部分和传递函数依赖，从而判断R属于第几范式,关系模式的函数依赖集F=ABCE,EAB,CD试问R最高属于第几范式？(1)求函数依赖集中决定因素是否为候选码即求ABF+、EF+、CF+由于ABF+=U、EF+=U,求AF+和BF+，判断是否为U,结果不是，所以AB和E是候选码(2)主属性A、B、E,非主属性C、D(3)判断非主属性对候选码有没有部分函数依赖E就不必判断;判断AB决定因素中没有A或B,所以达到2NF(4)判断非主属性对候选码有没有传递函数依赖ABCE,CD所以ABC,CD存在D对候选码AB的传递函数依赖只能达到2NF,5.求最小函数依赖集,函数依赖集等价,如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价,引理,F+=G+的充分必要条件是FG+和GF+,极小函数依赖集,如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集（最小依赖集/最小覆盖）(1)F中任一函数依赖的右部仅含有一个属性(2)F中不存在这样的函数依赖XA，使得F与F-XA等价(3)F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZA与F等价,定理,每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集,构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY,F=ABC，BD,CE,ECB,ACB，求极小函数依赖集,先分解右端F=ABC，BD,CE,ECB,ACB,(2)逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖,F=ABC，BD,CE,ECB,ACB,(1)去掉ABC，得到G=BD,CE,ECB,ACB,求ABG+,ABG+中不包含C，不可以去掉ABCF不变(2)去掉BD，得到G=ABC，CE,ECB,ACB，求BG+,BG+中不包含D，不可以去掉BDF不变,F=ABC，BD,CE,ECB,ACB,(3)去掉CE，得到G=ABC，BD,ECB,ACB，求CG+,CG+中不包含E，不可以去掉CEF不变(4)去掉ECB，得到G=ABC，BD,CE,ACB，求ECG+,ECG+中不包含B，不可以去掉ECBF不变,F=ABC，BD,CE,ECB,ACB,(5)去掉ACB，得到G=ABC，BD,CE,ECB，求ACG+,ACG+中包含B，可以去掉ACBF=G=ABC，BD,CE,ECB,(3)逐一取出F中各函数依赖FDi：XA，设X=B1B2Bm，逐一考查Bi（i=l，2，m），若A（X-Bi）F+，则以X-Bi取代X,F=ABC，BD,CE,ECB,(1)ABC求AF+=A,不包含C,不能去掉B求BF+=BD,不包含C,不能去掉A(2)ECB求EF+=E,不包含B,不能去掉C求CF+=BCDE,包含B,可以去掉EF变为F=ABC，BD,CE,CB,最后剩下的F就一定是极小依赖集因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价定理的证明过程也是求F极小依赖集的过程,注意,F的最小依赖集不一定是唯一的它与对各函数依赖FDi及XA中X各属性的处置顺序有关,最小函数依赖集和候选码的确定,准则1：如果属性A只在F中各个函数依赖的左端出现，则A必是候选码中的属性准则2：如果属性A不在F中各个函数依赖中出现，则A必是候选码中的属性准则3：如果属性A只在F中各个函数依赖的右端出现，则A必不是候选码中的属性,Example,最小函数依赖集F=ABC，BD,CE,CB1)A只在左端出现，A肯定在候选码中2)D、E只在右端出现，肯定不在候选码中3)剩余的属性是BC，记为属性集M4)判断A是否是候选码，不是5)从M中选择属性加入A中，即判断AB和AC是不是候选码,4.模式的分解,规范化,低一级范式的关系模式,高一级范式的关系模式,模式分解,规范化,低一级范式的关系模式,高一级范式的关系模式,模式分解,分解方法不唯一,模式分解的原则,合理选择规范化程度考虑到存取效率，低级模式冗余度大，因此希望子模式的属性越少越好，即选择高级范式考虑到查询效率，低级范式连接运算的代价小，比高级范式要好保证分解后的关系模式与原关系模式等价，分解方法才有意义,三种“等价”的定义,分解具有无损连接性避免信息丢失,如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息分解要保持函数依赖避免数据关系丢失分解既要保持函数依赖，又要具有无损连接性,Example,R（Sno，Sdept，Mn）学号Sno，学生所在系Sdept，系主任姓名Mn函数依赖集F=SnoSdept,SdeptMnR2NF(存在传递函数依赖),R（Sno，Sdept，Mn）,方法一：分解为三个关系模式R1(Sno)R2(Sdept)R3(Mn),分解后的三个表经过自然连接(笛卡儿积)得到4*3*3个元组，元组增加了，信息丢失了,分解不具有无损连接性不是等价的分解,R（Sno，Sdept，Mn）,方法二：分解为两个关系模式R1(Sno,Sdept)R2(Sno,Mn),没有丢失信息，这两个关系模式经过自然连接还可以恢复到原来的关系模式分解具有无损连接性,R1(Sno,Sdept),R2(Sno,Mn),但是函数依赖SdeptMn丢掉了,R1(Sno,Sdept),R2(Sno,Mn),R（Sno，Sdept，Mn）,方法三：分解为两个关系模式R1(Sno,Sdept)R2(Sdept,Mn)既具有无损连接性，又保持函数依赖,R（Sno，Sdept，Mn）F=SnoSdept,SdeptMn,R1(Sno,Sdept),R2(Sdept,Mn),说明,分解具有无损连接性和分解保持函数依赖是两个互相独立的标准具有无损连接性的分解不一定能保持函数依赖保持函数依赖的分解也不一定具有无损连接性,定义,关系模式R的一个分解：=R1，R2，RnU=U1U2Un，且不存在UiUj，Fi为F在Ui上的投影,定义,函数依赖集合XY|XYF+XYUi的一个覆盖Fi叫作F在属性Ui上的投影,算法：判断是否无损分解,(1)建立一张k行n列的表每一列对应一个属性每一行对应分解后的一个关系模式,R(U,F)，U=A,B,C,D,EF=ABC,CD,DER的一个分解为R1(A,B,C),R2(C,D),R3(D,E)U1=A,B,C,U2=C,D,U3=D,E1)构造初始表3行R分解为3个关系模式5列R中有五个属性,初始表,如果属性Aj属于Ui，则在i行j列处填aj，否则填bij,R1(A,B,C),R2(C,D),R3(D,E)U1=A,B,C,U2=C,D,U3=D,E,R1,R2,R3,(2)逐个检查F中函数依赖XY，修改表中的元素。检查X属性对应的列，如果找到相等的多行，就把这些行与Y属性列的交叉位置上的符号改为一致。如果其中之一为aj，就全部改为aj；否则改为bmj，m为最小行号,ABC：找不到相等的多行，表不变,CD,CD修改后的表,DE,DE修改后的表,(3)在某次更改之后，有一行成为a1,a2,a3an，则算法终止。那么该分解具有无损连接性。,第一行满足算法终止条件，该分解具有无损连接性,定理,R(U,F)的一个分解=R1(U1,F1)，R2(U2,F2)具有无损连接性的充分必要条件是U1U2U1-U2F+或U1U2U2-U1F+,设有关系模式R(A,B,C)F=AB,CB1=R1(A,B),R2(B,C)2=R1(A,C),R2(B,C)判断1和2是否无损分解。(1)对于1有U1=AB,U2=BCU1U2=BU1-U2=AU2-U1=C判断BA，BF+=B,所以BA不属于F+判断BC，BF+=B,所以BC不属于F+因此1不是无损分解(2)对2的判断留作课后完成（用两种方式判断）,保持函数依赖的判断,定理设关系模式R(U)，=R1，R2，Rn是R的一个分解，每个Ri的属性集合是Ui，Fi是F在Ui上的投影，如果F+=(F1F2Fn)+，则称这个分解保持了函数依赖。,模式分解的算法,三种方法,1）达到3NF保持函数依赖的分解2）达到3NF保持函数依赖和无损连接性的分解3