关系数据理论(5)

第五章关系数据理论2020年2月24日25.1问题的提出问题：如何构造系统的数据库模式？关系数据库由几个关系组成？每个关系由几个属性（字段、目、度、栏）？关系定义：关系是五元组：R(U,D,dom,Σ)其中：R是关系模式的名称；U是组成关系模式的属性；D是属性U取值的域；dom是属性U到域D的映射；Σ是数据依赖关系。关系简记：R(U,Σ)数据依赖Σ主要有：函数依赖F（FunctionalDependency）多值依赖MVD（MultivaluedDependency）连接依赖JD（JoinDependency）分层依赖HD（HierarchicalDependency）相互依赖MD（MutualDependency）第五章关系数据理论2020年2月24日35.1问题的提出关系规范化的必要性若关系的每个属性都是原子属性，则称此关系是规范化的。根据数据依赖，可以把关系模式分为：第五章关系数据理论1NF2NF3NFBCNF4NF5NF关系的全体第五范式(5NF)；{JD}第一范式(1NF)；{FD}第二范式(2NF)；{FD}第三范式(3NF)；{FD}改进的第三范式(BCNF)；{FD}第四范式(4NF)；{MVD}2020年2月24日45.1问题的提出示例：学生选课数据库的模式结构为：Student_Course(Sno,Sname,Cno,Ccredit,Grade)由现实系统的事实知道：第五章关系数据理论Sno(学号)Sname(姓名)Cno(课程号)Ccredit(学分)Grade(分数)2020年2月24日55.1问题的提出实例：Student_Course第五章关系数据理论SnoSnameCnoCcreditGrade001张明A1２78001张明A2482001张明A3368002李强A2492002李强A3367007邦德A9498分析事实知道：存在操作异常(OperatingAnomalcy)(1)数据冗余大；(2)插入异常；(3)删除异常；(4)修改异常；2020年2月24日65.2规范化理论关系规范化理论最早由E.F.Codd1971年提出。1.函数依赖（FunctionalDependency简记为FD）：定义1：设关系模式为R(U)，U是属性集，X,YU,若R(U)上任一关系值r，存在任意两个元组t1、t2，有t1[X]=t2[X]，则必有t1[Y]=t2[Y]，则称X函数确定Y，或Y函数依赖X，记为X→Y。其中：X称为决定因素，Y称为依赖因素。（R.X→R.Y）定义2：设关系模式为R(U)，U是属性集，X,YU,如果对于R中X的每一个值都有Y的唯一值与之对应，则称X函数确定Y，或Y函数依赖X，记为X→Y。（R.X→R.Y）其他定义：(1)X→Y，若YX，则称X→Y是平凡函数依赖(TrivialFD)；否则称X→Y是非平凡函数依赖(NontrivialFD)。第五章关系数据理论2020年2月24日75.2规范化理论(2)X→Y，若对X’X，不存在函数依赖X’→Y，则称Y完全函数依赖(FullFD)于X，记为：第五章关系数据理论否则称Y部分函数依赖(PartlyFD)于X，记为：YXFYXP(3)若X→Y(YX)，Y↛X，且Y→Z，X,Y,ZU，则称Z传递函数依赖(TransitiveFD)于X，记为：(4)码(Key)：设关系模式为R(U)，U是属性集，KU，若ZX传递则称K是关系模式R的码（关键字）。UKF否则称Z非传递函数依赖(NontransitiveFD)于X。通常，一个关系模式R的可以有多个码（关键字），统称这些码为关系模式的候选码(CandidateKey)，可以在候选码中指定一个作为关系模式的主码(PrimaryKey)。2020年2月24日85.3函数依赖的推理规则第五章关系数据理论1.函数依赖的逻辑蕴涵定义：设关系模式为R(U,F)，U是属性集，F是R上的函数依赖集。对R的任一关系值r，r满足F，若r满足X→Y，则称F逻辑蕴涵X→Y；或称函数依赖X→Y可由F导出。F的闭包F+：所有被F逻辑蕴涵的函数依赖的集合称为F的闭包，记为F+。通常FF+，当F＝F+时，称F为函数依赖的满族(FullFamily)。如何由F导出函数依赖X→Y？1974年，W.W.Armstrong发表了题为《DependencyStructuresofDataBaseRelationships》的论文，提出了由F推导函数依赖X→Y的一组规则，证明了规则的有效性和完备性。2020年2月24日95.3函数依赖的推理规则第五章关系数据理论2.Armstrong推导公理设关系模式为R(U,F)，U是属性集，X,Y,Z,WU,F是R上的函数依赖集。则有如下推理规则：基本的Armstrong公理：公理1：自反规则(ReflexivityRule)——自反律若YXU，则F逻辑蕴涵X→Y；记为：X→Y∈F+。证明：由函数依赖定义知对关系r的任意两个元组t1、t2，若有t1[X]=t2[X]，且YX，则必有t1[Y]=t2[Y]，由函数依赖定义知X→Y存在，可由F导出。#不可能存在这样的关系，在关系r中存在两个元组t1、t2，它们在属性集X上的值相等，而在其子集Y上的值不相等。#2020年2月24日105.3函数依赖的推理规则第五章关系数据理论公理2：扩展规则(AugmentationRule)——增广律若X→Y∈F，且ZU，则XZ→YZ∈F+。证明：设t1、t2为关系的任意两个元组，∵X→Y，由函数依赖定义知：有t1[X]=t2[X]，t1[Y]=t2[Y]；若t1[XZ]=t2[XZ]，则有：t1[Z]=t2[Z]；∵t1[Y]=t2[Y]，∴t1[YZ]=t2[YZ]；由函数依赖定义知XZ→YZ存在，可由F导出。(即XZ→YZ∈F+)#反证法：假设关系模式R(U)的任意关系r满足X→Y，不满足XZ→YZ，则关系r中存在这样的元组t1、t2，它们在属性集XZ上的值相等，而在属性集YZ上的值不相等。若元组t1、t2在属性集XZ上的值相等，则它们在属性集Z上的值相等，则必然得出在属性集Y上的值不相等。即：它们在属性集X上的值相等，而在属性集Y上的值不相等。而这与给定条件X→Y相悖。因此，XZ→YZ存在。#2020年2月24日115.3函数依赖的推理规则第五章关系数据理论公理3：传递规则(TransitivityRule)——传递律若X→Y，Y→Z，则X→Z∈F+。证明：设t1、t2为关系的任意两个元组，∵X→Y，Y→Z，由函数依赖定义知：有t1[X]=t2[X]，t1[Y]=t2[Y]，t1[Z]=t2[Z]；∵t1[X]=t2[X]，t1[Z]=t2[Z]；则X→Z∈F+。由上述三条基本的Armstrong公理，可以推导出：证明公理4：合并规则(TransitivityRule)若X→Y，X→Z，则X→YZ∈F+。公理5：伪传递规则(TransitivityRule)若X→Y，YW→Z，则XW→Z∈F+。公理6：分解规则(TransitivityRule)若X→Y，ZY，则X→Z∈F+。NEXT2020年2月24日125.3函数依赖的推理规则第五章关系数据理论公理4证明：∵X→Y，由扩展规则知：XX→XY；即：X→XY；∵X→Z，由扩展规则知：XY→YZ；由传递规则知：X→YZ。#公理5证明：∵X→Y，由扩展规则知：XW→YW；∵YW→Z，由传递规则知：XW→Z。#公理6证明：∵ZY，由自反规则知：Y→Z；∵X→Y，由传递规则知：X→Z。#返回2020年2月24日135.3函数依赖的推理规则第五章关系数据理论3.推论1)Y=A1A2…An，X→Y成立的充要条件是X→Ai成立(i=1..n)。证明：充分性可由合并规则导出；必要性可由分解规则导出。#定义：设关系模式为R(U,F)，U是属性集，F是R上的函数依赖集。XU，XF+={Ai|X→AiF+}，XF+称为X关于函数依赖集F的属性集闭包。简记为X+。2)X→Y成立的充要条件是YXF+。证明：(充分性)设Y=A1A2…An，且YXF+，根据XF+的定义知X→Ai成立，由合并规则可得X→Y成立；(必要性)设X→YF+，若Y=A1A2…An，由分解规则知X→Ai成立，由XF+的定义知AiXF+，所以YXF+成立。#2020年2月24日145.3函数依赖的推理规则第五章关系数据理论4.判断X→YF+的算法X→Y是否成立？F+难以确定；但XF+容易确定，改为判断YXF+。算法5.1：求XF+。[输入X，F；输出XF+](1)令X(0)=X，i=0；(2)B={A|(V)(W)(VWFVX(i)AW)}；(3)X(i+1)=X(i)B(4)判断X(i+1)=X(i)X(i+1)=U？(5)成立，XF+=X(i+1)，算法结束。(6)不成立，i=i+1，转到(2)。示例2020年2月24日155.3函数依赖的推理规则第五章关系数据理论5.定理结论定理5.1：Armstrong推理规则是正确的。证明：由六个推理规则的证明可以得出结论。#定理5.2：Armstrong公理系统是有效的、完备的。证明：有效性是指：利用Armstrong推理规则，从已知的函数依赖推导出的函数依赖是成立的。这可以由定理5.1得到证明。完备性是指：利用Armstrong推理规则，从已知的函数依赖可以推导出全部的函数依赖。2020年2月24日165.3函数依赖的推理规则第五章关系数据理论完备性证明：若X→Y不能由F导出，则必然存在一个关系r，满足F而不满足X→Y，即X→YF+。设R(U，F)，对R的任一关系r，不失一般性，可以如下表所示：元组X+的属性其它属性t111…1111…11t211…1100…002020年2月24日175.3函数依赖的推理规则第五章关系数据理论1.证关系r满足F中所有的函数依赖设V→WF，V有两种情况：1）VX+，由推论2知：X→V成立；V→WX→W成立；WX+由关系r知：t1[v]=t2[v]，且t1[w]=t2[w]，根据函数依赖的定义有：V→W在关系r中成立。2）VX+，由关系r知：t1[v]≠t2[v]，根据函数依赖的定义有：V→W在关系r中自然成立。2020年2月24日185.3函数依赖的推理规则第五章关系数据理论2.证关系r不满足不能由F按推理规则导出的函数依赖XYX→Y不能由F导出，YX+，而XX+，由关系r知：t1[X]=t2[X]，且t1[Y]≠t2[Y]，根据函数依赖的定义有：X→Y在关系r中不成立。结论：关系r满足F中所有的函数依赖；不满足不能由F按推理规则导出的函数依赖。即，凡是被F逻辑蕴涵的函数依赖一定能用Armstrong公理导出。#2020年2月24日195.3函数依赖的推理规则第五章关系数据理论5.定理结论定义5.14：对函数依赖集F、G，若F+=G+，则称：函数依赖集F覆盖G，或F与G等价。记为：FG。引理5.3：F+=G+的充要条件是：FG+且GF+。证明：必要性是显然的。充分性证明：若FG+则XF+XG++对XYF+有YXF+XG++XY（G+）+=G+即F+G+成立。同理有G+F+成立。F+=G+（互为子集相等）#2020年2月24日205.3函数依赖的推理规则第五章关系数据理论5.定理结论推论3：每个函数依赖集F可以被一个右部只有单个属性的函数依赖集G所覆盖。定义5.15：若函数依赖集F满足下列条件，则称F为最小函数依赖集。记为：F‘或Fm。(不唯一)(1)F‘的所有函数依赖的右部均为单属性；(2)对XAF‘，F‘与F‘-{XA}不等价；(3)对XAF‘，ZX，F‘与F‘-{XA}{ZA}不等价。2020年2月24日215.3函数依赖的推理规则第五章关系数据理论5.定理结论定理5.3：每个函数依赖集F与它的最小函数依赖集F‘等价。证明：构造性证明。按定义由F构造F'：(1)利