关系模式设计理论

关系模式设计理论主要内容关系数据库的基本结构是关系模式设计好的关系模式集合控制数据冗余对数据进行有效管理模式设计理论包括：数据依赖、范式、模式设计方法内容1关系模式的设计准则2函数依赖3关系模式的分解特性4范式1关系模式的设计准则1.1关系模式的冗余和异常问题1.2关系模式的非形式化设计准则1.1关系模式的冗余和异常问题数据冗余是指同一个数据在系统中重复出现数据冗余引起的操作异常修改异常插入异常删除异常解决冗余的主要方法：分解什么是最优关系模式？标准是什么？如何实现？1.2关系模式的非形式化设计准则四个非形式化的衡量准则准则1：尽可能只包含有直接联系的属性准则2：尽可能不出现插入、删除、修改异常准则3：尽量避免放置经常为空的属性准则4：尽可能使关系的等值连接在主键和外键的属性上进行2函数依赖函数依赖是关键码概念的推广。内容2.1函数依赖的定义2.2FD的逻辑蕴涵2.3FD的推理规则2.4FD和关键码的联系2.5属性集的闭包2.6FD集的最小依赖集2.1函数依赖的定义数据库中，属性值之间会发生联系，这类联系称为函数依赖（functionaldependency）。函数依赖的定义：设有关系模式R(U)，X,YU，r是R(U)上的任意一个关系，如果成立对t,sr，若t[X]=s[X]，则t[Y]=s[Y]，那么称“X函数决定Y”，或“Y函数依赖于X”，记作XY。称X为决定因素。如果XY和YX同时成立，则可记为XY，即X值与Y值一一对应。2.2FD的逻辑蕴涵设F是在关系模式R上成立的函数依赖的集合，XY是一个函数依赖。如果对于R的每个满足F的关系r也满足XY，那么称F逻辑蕴涵XY，记为F|=XY。设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包，记为F+。即F+={XY|F|=XY}2.3FD的推理规则问题的提出：数据库设计者把ER图转换为关系模式后，根据实际情况确定相应的函数依赖集合。为了更科学合理地分解关系模式，不仅知道函数依赖集合，还要知道这个函数依赖集合所蕴涵的所有函数依赖的集合。那么怎么从给定大的函数依赖集合推导出它所蕴涵的所有函数依赖呢？Armstrong公理系统由若干原始概念和推理规则构成利用Armstrong公理系统中的推理规则，可以由给定的原始函数依赖集合推导出这个函数依赖集合所蕴涵的所有函数依赖。2.3FD的推理规则设U是关系模式R的属性集，F是R的一个函数依赖集合。Armstrong公理系统包含如下三条推理规则：A1自反性：若YXU，XY在R上成立。A2增广性：若XY在R上成立，且ZU，则XZYZ在R上成立。A3传递性：若XY和YZ在R上成立，则XZ在R上成立。给定R的一个函数依赖集F，使用这三条推理规则，可以推出F所蕴含的所有函数依赖关系。2.3FD的推理规则FD推理规则A1、A2、A3是正确的。即，如果XY是从F用推理规则导出，那么XY在F+中。FD的其它五条推理规则A4合并性：{XY，XZ}|=XYZ。A5分解性：{XY，ZY}|=XZ。A6伪传递性：{XY，WYZ}|=WXZ。A7复合性：{XY，WZ}|=XWYZ。A8：{XY，WZ}|=X∪(W-Y)YZ。2.3FD的推理规则对于FDXY，如果YX，那么称XY是一个“平凡的FD”，否则为“非平凡的FD”。“非平凡的FD”和“真正的”完整性约束条件相关。如果A1…An是关系模式R的属性集，那么XA1…An成立的充要条件是XAi(i=1,…,n)成立。例：关系模式R(X,Y,Z)，给定函数依赖集F=(XY,YZ)。根据Armstrong公理的推理规则3，可知XZ也是R上的一个函数依赖。思考：XYY是R上的一个函数依赖吗？为什么？2.4FD和关键码的联系设关系模式R的属性集是U，X是U的一个子集。如果XU在R上成立，那么称X是R的一个超键。如果XU在R上成立，但对于X的任一真子集X1都有X1U不成立，那么称X是R上的一个候选键。一般，键都是指候选键。2.5属性集的闭包规则集{A1、A2、A3}是函数依赖的一个正确的和完备的推理规则集。P74设F是属性集U上的FD集，X是U的子集，那么属性集X的闭包X+是一个从F集使用FD推理规则推出的所有满足XA的属性A的集合：X+={属性A|F|=XA}XY能用FD推理规则推出的充要条件是YX+。计算属性集闭包的算法2.6FD集的最小依赖集如果关系模式R(U)上的两个函数依赖集F和G，有F+=G+，则称F和G是等价的函数依赖集。最小依赖集的形式定义如果函数依赖集G满足以下三个条件，则称G是最小依赖集：（1）G中每个FD的右边都是单属性；（2）G中没有冗余的F，即G中不存在这样的函数依赖XY，使得G-{XY}与G等价；（3）G中每个FD的左边没有冗余的属性，即G中不存在这样的函数依赖XY，X有真子集W使得G-{XY}∪{WY}与G等价；每个函数依赖集至少存在一个最小依赖集，但不一定唯一。2.6FD集的最小依赖集计算F最小依赖集G的算法，分为三个步骤：根据推理规则的分解性(A5)，得到一个与F等价的FD的集G，G中每个FD的右边均为单属性。在G的每个FD中消除左边冗余的属性。在G中消除冗余的FD。3关系模式的分解特性3.1关系模式的分解3.2无损分解3.3模式分解的优缺点3.4无损分解的测试方法3.5保持FD的分解3.6模式分解与模式等价问题3.1关系模式的分解关系模式分解的定义模式分解示意图计算机中的数据存储在数据库σ中。关系模式规范化的目标分解初始关系模式，是分解之后的关系模式满足一定范式条件。关系模式分解的注意事项（1）不要丢失信息。（分解的无损连接性）（2）保持原来关系模式上的函数依赖关系。（分解的函数依赖保持性）3.2无损分解寄生元组定义无损分解、损失分解定义表达方式：πRi(r)表示关系r在模式Ri属性上的投影。r的投影连接mρ(r)=πR1(r)∞…∞πRk(r)=∞πRi(r)ki=1泛关系假设下关系模式分解示意图（1）rmρ(r)（2）设s=mρ(r)，则πRi(s)=ri3.2无损分解悬挂元组是在无泛关系假设时，对两个关系进行自然连接中被丢失的元组。悬挂元组是造成两个关系不存在泛关系的原因。3.3模式分解的优缺点优点（1）模式分解能消除数据冗余和操作异常现象。（2）在分解了的数据库中可以存储悬挂元组，存储泛关系中无法存储的信息。缺点（1）分解后，检索操作需要做笛卡儿积或连接操作，将付出时间代价。（2）有泛关系假设时，可能产生寄生元组；无泛关系假设时，由于悬挂元组，可能就不存在泛关系。模式分解应适可而止。3.4无损分解的测试方法输入：关系模式R=A1…An，F是R上成立的函数依赖集，ρ={R1,…,Rk}是R的一个分解。输出：判断ρ相对于F是否具有无损分解特性。方法：“追踪”过程(1)构造k行n列的表格，每列对应一个属性Aj(1≤j≤n),每行对应一个模式Ri(1≤i≤k)。若Aj在Ri中，则在i行j列处填上符号aj，否则填上bij。(2)把表格看成R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。方法：对于F中一个FDXY，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y之上的改成相等的值。直到表格不能修改为止。(3)最后一张表格有一行是全a，称ρ相对于F是无损分解。3.5保持FD的分解定义：设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用πz(F)表示，定义为πz(F)={XY|XY∈F+，且XYZ}定义：设ρ={R1,…,Rk}是R的一个分解，F是R上的FD集，如果有∪πRi(F)|=F，那么称ρ保持函数依赖集F。ki=13.6模式分解与模式等价问题数据库模式等价数据等价：无损分解依赖等价：有相同的依赖集闭包无损分解与保持FD分解之间没有必然联系4范式使用模式的范式（NormalForms，NF）作为衡量关系模式好坏的标准。内容4.1第一范式（1NF）4.2第二范式（2NF）4.3第三范式（3NF）4.4BCNF4.5模式设计方法小结4.1第一范式（1NF）关系模式R的每个关系r的属性值都是不可分原子值，称R是第一范式模式满足1NF关系的称规范化关系；否则称非规范化关系。目前数据库理论研究的都是规范化关系。例：学习关系模式R(S#,SN,C#,CN,GREAD,TN,TAGE)1NF是关系模式应具备的最起码的条件。4.2第二范式（2NF）局部依赖、完全依赖定义主属性、非主属性定义若R是1NF，且每个非主属性完全依赖于候选键，则称R是2NF（消除非主属性对候选键的部分依赖）。例关系模式S(S#,SN,SD,DEAN,C#,G)（S#,C#）为候选键，S#SN，S#SD，存在部分依赖可将S分解为：SC(S#,C#,G)S_SD(S#,SN,SD,DEAN)4.2第二范式（2NF）不满足2NF的关系模式中必定存在非主属性对关键码的局部依赖。分解成2NF模式集的算法4.3第三范式（3NF）传递依赖定义R是2NF，且其任何一个非主属性都不传递地依赖于任何候选键，则称R是3NF。例：关系模式S_SD(S#,SN,SD,DEAN)有S#SD，SDDEAN，则S#DEAN，存在传递依赖，即DEAN传递地依赖于候选键S#，不是3NF。可以将S分解为：STUDENT(S#,SN,SD)DEPT(SD,DEAN)4.3第三范式（3NF）不满足3NF的关系模式中必定存在非主属性对关键码的传递依赖。3NF的等价定义设F是关系模式R的FD集，如果对F中每个非平凡的FDXY，都有X是R的超键，或者Y的每个属性都是主属性，那么称R是3NF的模式。分解成3NF模式集的算法P84定理：如果R是3NF模式，那么R也是2NF模式。4.4BCNFR是1NF，且每个属性都不传递依赖于R的候选键，则R为BCNF模式。等价定义：R是1NF，若对于R的每个函数依赖XY，X必为候选键，则R为BCNF。例：SPC(S#,T#,C#)，假定有以下函数依赖关系T#C#，每位老师只教授一门课（S#，T#）C#,（S#，C#）T#，学生选定一门课就对应一位老师（S#，T#），（S#，C#）为候选键。所有属性为键属性，为第三范式，但非BCNF可以将S分解为（S#，T#），（T#，C#）。如果R是BCNF模式，那么R也是3NF模式。4.5分解成BCNF模式集的分解算法无损分解为BCNF模式集：分解算法对于关系模式R的分解ρ（初始时ρ={R}），如果ρ中有一个关系模式Ri相对于πRi(F)不是BCNF则说明Ri中存在非平凡的FDXY，有X不包含超键。做法：把Ri分解为XY和Ri-Y两个模式。重复上述操作，直到ρ中每一个模式都是BCNF。保证把R无损分解成ρ，但不能保证ρ能保持FD。4.6分解成3NF模式集的合成算法无损分解且保持依赖的分解成3NF模式集(合并法)（1）对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。（2）对最小依赖集中，每个XY构成一个模式XY。（3）在构成的模式集中，如果每个模式都不包含R的候选键，那么把候选键作为一个模式放入模式集中。4.7模式设计方法小结关系模式R相对于函数依赖集F分解成数据库模式ρ={R1，…,Rk}，一般应具有三个特性：（1）ρ是BCNF模式集，或3NF模式集；（2）无损分解，即对于R上任何满足F的泛关系应满足r=mρ(r)；（3）保持函数依赖集F，即[∪πRi