关系数据库(2)

AnIntroductiontoDatabaseSystem数据库系统概论AnIntroductiontoDatabaseSystem第六章关系数据理论AnIntroductiontoDatabaseSystem第六章关系数据理论6.1问题的提出6.2规范化6.3数据依赖的公理系统6.4模式的分解6.5小结AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统关系模式的规范化过程是通过关系模式的分解来实现的。这种分解不是唯一的。如何进行模式分解？且使得分解后的关系模式与原关系模式“等价”？数据依赖的公理系统是模式分解算法的理论基础。AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统函数依赖集合的逻辑蕴含Armstrong公理系统闭包的概念和计算函数依赖集合的计算最小函数依赖集关系模型候选码的确定AnIntroductiontoDatabaseSystem数据依赖的逻辑蕴含逻辑蕴含：定义6.11对于满足一组函数依赖F的关系模式RU，F，其任何一个关系r，若函数依赖X→Y都成立,则称：F逻辑蕴含X→Y即：如果F是关系模式R的函数依赖集合，X、Y是R的属性集，如果从F中可以推出函数依赖关系X→Y，就称X→Y被F逻辑隐含。AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统函数依赖集合的逻辑蕴含Armstrong公理系统闭包的概念和计算函数依赖集合的计算最小函数依赖集关系模型候选码的确定AnIntroductiontoDatabaseSystemArmstrong公理系统Armstrong公理系统1974年W.W.Armstrong首先提出了函数依赖的公理系统，称为Armstrong公理。一套推理规则，是模式分解算法的理论基础用途：对于一组已知的函数依赖，利用该公理系统可导出所逻辑蕴函的函数依赖。求给定关系模式的码AnIntroductiontoDatabaseSystemArmstrong公理系统对关系模式RU，F来说有以下的推理规则：①自反律②增广律③传递律AnIntroductiontoDatabaseSystem自反律自反律：在关系模式RU，F中，若：YXU，则：X→Y为F所蕴含。例如：(Sno,Cno)→Sno(Sno,Cno)→Cno注意：由自反律所得到的函数依赖均是平凡的函数依赖AnIntroductiontoDatabaseSystem增广律增广律：在关系模式RU，F中，若：X→Y为F所蕴含，且ZU，则：XZ→YZ为F所蕴含。例如：若：Sno→Sdept则：(Sno,Sname)→(Sdept,Sname)AnIntroductiontoDatabaseSystem传递律传递律：在关系模式RU，F中，若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。例如：若：Sno→Sdept，Sdept→Sloc则：Sno→SlocAnIntroductiontoDatabaseSystem导出规则根据以上三条推理规则，可以得到下面三条很有用的推理规则：合并规则伪传递规则分解规则AnIntroductiontoDatabaseSystem合并规则合并规则：（可由增广律，传递律推出）若：X→Y，X→Z则：X→YZ。例如:若：Sno→Sname，Sno→Ssex，Sno→Sdept则：Sno→(Sname,Ssex,Sdept)AnIntroductiontoDatabaseSystem伪传递规则伪传递规则：（可由增广律，传递律推出）若：X→Y，WY→Z则：XW→Z例如:若：Sno→Sdept，(Sname,Sdept)→Sclass则：(Sno,Sname)→SclassAnIntroductiontoDatabaseSystem分解规则分解规则：（可由自反律，传递律推出）若：X→Y及ZY则：X→Z例如:若：Sno→(Sname,Sdept)则：Sno→Sname，Sno→SdeptAnIntroductiontoDatabaseSystem导出规则引理6.l：（根据合并规则和分解规则，可得）X→(A1A2…Ak)成立的充分必要条件是X→Ai成立（i=l，2，…，k）。例如：在Student中,因为：Sno→Sname，Sno→Sdept，Sno→Sclass，…….所以：Sno→(Sname,Sdept,Sclass,……)AnIntroductiontoDatabaseSystem说明：Armstrong推理规则也称为Armstrong公理系统。可以证明：Armstrong公理系统是有效的、完备的。即：有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统函数依赖集合的逻辑蕴含Armstrong公理系统闭包的概念和计算函数依赖集合的等价最小函数依赖集关系模型候选码的确定AnIntroductiontoDatabaseSystem闭包的概念函数依赖闭包：定义6.l2在关系模式RU，F中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。属性闭包：定义6.13设F为属性集U上的一组函数依赖，XU，XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。AnIntroductiontoDatabaseSystem关于闭包的引理引理6.2：设F为属性集U上的一组函数依赖，X，YU，X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+用途：将判定X→Y是否能由F根据Armstrong公理导出的问题转化为求出XF+，判定Y是否为XF+的子集的问题AnIntroductiontoDatabaseSystem关于闭包引理的例子例如：对于关系模式Student(Sno,Sname,Sdept,Sclass,Ssex)已知：Student中的几个函数依赖Sno→Sname,Sno→Sdept,Sdept→Sclass,Sname→Ssex求解:Sno→Sclass是关系模式Student中的函数依赖AnIntroductiontoDatabaseSystem关于闭包引理的例子求(Sno)F+(Sno)F+={Sno,Sname,Sdept,Sclass,Ssex}由此可知Sclass(Sno)F+由引理6.2可知：Sno→Sclass能由F根据Armstrong公理导出，是Student中的函数依赖AnIntroductiontoDatabaseSystem属性集闭包的计算算法6.l求属性集X（XU）关于U上的函数依赖集F的闭包XF+输入：X，F输出：XF+求由属性集X(i)导出的所有属性的集合AnIntroductiontoDatabaseSystem属性闭包计算举例例:已知关系模式RU，F，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求（AB）F+。AnIntroductiontoDatabaseSystem属性闭包计算举例解：设X（0）=AB；(1)计算X(1)：逐一的扫描F集合中各个函数依赖，找左部为A、B或AB的函数依赖。得到两个：AB→C，B→D于是：X(1)=AB∪CD=ABCD。AnIntroductiontoDatabaseSystem属性闭包计算举例(2)因为：X(1)≠X(0)并且X(1)≠U所以：再找出左部为ABCD子集的那些函数依赖，得到：AB→C，B→D，C→E，AC→B于是：X(2)=X(1)∪BCDE=ABCD∪BCDE=ABCDE(3)因为：X(2)=U所以：算法终止，(AB)F+=ABCDE。由(AB)F+可知：{A,B}→{A,B,C,D,E}为F+所逻辑蕴含所以：{A,B}是关系R的侯选码AnIntroductiontoDatabaseSystem属性闭包计算举例已知关系模式RU，F，其中U={A，B，C，D，E}；F={AB→C，B→D，C→E，EC→B，AC→B}。求：决定因素的属性集的闭包，即求(AB)F+，(B)F+，(C)F+，(EC)F+，(AC)F+FBBDFCBCDEFECBCDEFACABCDEFABABCDEAnIntroductiontoDatabaseSystem属性闭包计算举例由这些属性集的闭包，可知：{A,B}、{A,C}是R中的候选码推出一些函数依赖:{E,C}→{B,C,D,E}{B}→{B,D}{A,C}→{A,B,C,D,E}{C}→{B,C,D,E}{A,B}→{A,B,C,D,E}R属于1NF(存在非主属性对码的部分函数依赖)C→E,B→DAnIntroductiontoDatabaseSystem由XF+所得出的结论给定一组函数依赖，通常可以推导出某些其他的函数依赖，既包括非平凡的函数依赖，也包括平凡的函数依赖。如果某一属性集X的闭包为关系模式的所有属性集合，则该属性集X一定是关系模式的候选码。AnIntroductiontoDatabaseSystem思考题设有关系模式R(U,F)，其中F有8个函数依赖构成：AB→CD→EGC→ABE→CBC→DCG→BDACD→BCE→AG求：FBD,,,,,FBDABCDEGAnIntroductiontoDatabaseSystem6.3数据依赖的公理系统函数依赖集合的逻辑蕴含Armstrong公理系统闭包的概念和计算函数依赖集合的等价最小函数依赖集关系模型候选码的确定AnIntroductiontoDatabaseSystem函数依赖集合的等价为了寻找最合理的函数依赖集合，需要对函数依赖集合进行变换，但每次变换后，必须与原来的集合具有相同的含义，这就是函数依赖集合的等价（或互相覆盖）。AnIntroductiontoDatabaseSystem函数依赖集合的等价定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。引理6.3F+=G+的充分必要条件是FG+，和GF+（函数依赖集合等价的判定方法）AnIntroductiontoDatabaseSystem6.3数据依赖的公理系统函数依赖集合的逻辑蕴含Armstrong公理系统闭包的概念和计算函数依赖集合的等价最小函数依赖集关系模型候选码的确定AnIntroductiontoDatabaseSystem最小函数依赖集最小函数依赖集：是对函数依赖集合进行规范的结果，只有成为最小函数依赖集后，一些规则和方法才是行之有效的。AnIntroductiontoDatabaseSystem最小函数依赖集定义定义6.15若函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖。(1)F的每个函数依赖的右部仅包含一个属性（保证每个函数依赖的右端没有冗余的属性）。(2)在F中不存在这样的函数依赖X→A，使得F与F-{X→A}等价（保证F中没有冗余的函数依赖）。(3)在F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价（保证每个函数依赖的左端没有冗余的属性）。AnIntroductiontoDatabaseSystem最小依赖集举例例：设有关系模式JX（U,F），其中：U＝｛SNO，SDEPT，MN，CNAME，G｝F＝｛SNO→SDEPT，SDEPT→MN,(SNO，CNAME)→G｝设：F’＝｛SNO→SDEPT，SDEPT→MN，SNO→MN，(SNO，CNAME)→G，