第六章关系数据理论 多值依赖与公理系统
第六章 关系数据理论 多值依赖与公理系统
多值依赖及第四范式 二.数据依赖的公理系统 逻辑蕴涵 Armstrong.公理系统 函数依赖集的闭包 函数依赖集的等价及最小函数依赖集
一． 多值依赖及第四范式 二． 数据依赖的公理系统 逻辑蕴涵 Armstrong公理系统 函数依赖集的闭包 函数依赖集的等价及最小函数依赖集
1)多值依赖( Multi Valued Dependency,简记MVD 定义69 设R(U)是一个属性集U上的一个关系模式,X、Y和Z是U的子集, 并且Z=U—X一Y。关系模式R(U)中多值依赖Ⅹ→→Y成立,当且仅 当对R(U)的任一关系r,给定的一对(x,z)值,有一组Y的值,这组 值仅仅决定于ⅹ值而与z值无关; 若X→→Y,而Z=Φ,则称X→→Y为平凡的多值依赖,否则为非平凡的 多值依赖。 例 Teaching(课程C,教师T,参考书B) 对于C的每一个值,T有一组值与之对应,而不论B取何值; 因此C→→T
1）多值依赖（MultiValued Dependency，简记MVD） 定义6.9 设R（U）是一个属性集U上的一个关系模式， X、 Y和Z是U的子集， 并且Z＝U－X－Y。关系模式R（U）中多值依赖 X→→Y成立，当且仅 当对R（U）的任一关系r，给定的一对（x，z）值，有一组Y的值，这组 值仅仅决定于x值而与z值无关； 若X→→Y，而Z=Φ，则称X→→Y为平凡的多值依赖，否则为非平凡的 多值依赖。 例 Teaching（课程C, 教师T, 参考书B） 对于C的每一个值，T有一组值与之对应，而不论B取何值； 因此C →→T
多值依赖具有下列性质 多值依赖具有对称性。若X→→Y,则Ⅹ→→Z,其中Z=U-X-Y; ●函数依赖可以看作特殊的多值依赖。若X→Y,则X→→Y; 多值依赖和函数依赖的基本区别 在关系模式R(U)中,函数依赖X→Y的有效性决定于X,Y这两个属性集 的值。只要在R(U)的任何一个关系中,元组在X和Y上的值满足函数依赖 的定义,则函数依赖X→Y在任何属性集W( XYCWCU)上成立。 对于多值依赖来说,若X→→Y在W(WcU)上成立,而在U上则不一定 成立。所以多值依赖的有效性与属性集的范围有关。X→→Y在U上成立,则 在W( XYCWCU)上成立;反之,则不然 若函数依赖XY在R(U)上成立,则对于任何YcY均有X→Y成立。对 于多值依赖X→→Y,若在R(U)上成立,我们却不能断言对于任何YcY 有X→→Y成立
2)第四范式 定义6.10 关系模式R∈1NF,如果对于R的每个非平凡多值依赖Ⅹ→→Y (Y4X),X都含有候选码,则R∈4NF。 如果R∈4NF,则R∈BCNF 对于每一个非平凡的多值依赖X→→Y,Ⅹ都含有候选码,则有 Ⅹ→Y; 允许的是函数依赖(是非平凡多值依赖),不允许的是非平凡且非 函数依赖的多值依赖; 如果一个关系模式是BCNF,而且至少有一个码是由一个属性组成, 此关系模式就是4NF;
2）第四范式 定义6.10 关系模式R∈1NF，如果对于R的每个非平凡多值依赖X→→Y （Y X），X都含有候选码，则R∈4NF。 如果R ∈ 4NF， 则R ∈ BCNF 对于每一个非平凡的多值依赖X→→Y ，X都含有候选码，则有 X→Y ； 允许的是函数依赖（是非平凡多值依赖），丌允许的是非平凡且非 函数依赖的多值依赖； 如果一个关系模式是BCNF，而且至少有一个码是由一个属性组成， 此关系模式就是4NF;
规范化小结 规范化目的:使结构更合理,消除插入、修改、删除异常,使数据 冗余尽量小,便于插入、删除和更新。 规范化方法:将关系模式投影分解成两个或两个以上的关系模式 规范化原则:遵从概念单一化“一事一地”原则,即一个关系模式 描述一个实体或实体间的一种联系。规范的实质就是概念的单一化。 。规范化要求:分解后的关系模式集合应当与原关系模式“等价”, 即经过自然联接可以恢复原关系而不丢失信息,并保持属性间合理 的联系
规范化小结 规范化目的：使结构更合理，消除插入、修改、删除异常，使数据 冗余尽量小，便于插入、删除和更新。 规范化方法：将关系模式投影分解成两个或两个以上的关系模式。 规范化原则：遵从概念单一化 “一事一地”原则，即一个关系模式 描述一个实体或实体间的一种联系。规范的实质就是概念的单一化。 规范化要求：分解后的关系模式集合应当与原关系模式“等价”， 即经过自然联接可以恢复原关系而不丢失信息，并保持属性间合理 的联系
二、数据依赖的公理系统 问题的提出 在关系模式规范化处理过程中,不仅要知道一个由语义决定的函数 依赖集合,还要知道由这个已知的函数依赖集合所蕴含(或推导出) 的所有函数依赖集合。为此,需要一个有效而完备的公理系统, Armstrong公理系统即是这样的一个系统 °相关定义 个函数依赖可以通过已知的函数依赖推导出来;如利用Ⅹ→Y和 Y→乙可以推导出Ⅹ→Z,可以说,函数依赖Ⅹ→Y和Y→乙逻辑蕴含 ( Logical Implication)了X→Z
二、数据依赖的公理系统 问题的提出： 在关系模式规范化处理过程中，丌仅要知道一个由语义决定的函数 依赖集合，还要知道由这个已知的函数依赖集合所蕴含（或推导出） 的所有函数依赖集合。为此，需要一个有效而完备的公理系统， Armstrong公理系统即是这样的一个系统。 相关定义： 一个函数依赖可以通过已知的函数依赖推导出来；如利用X→Y和 Y→Z可以推导出X →Z，可以说，函数依赖X→Y和Y→Z逻辑蕴含 （Logical Implication）了X →Z
主要内容: 1、逻辑蕴涵 2、 Armstrong公理系统 3、函数依赖集的闭包 4、函数依赖集的等价及最小依赖集
主要内容： 1、逻辑蕴涵 2、Armstrong公理系统 3、函数依赖集的闭包 4、函数依赖集的等价及最小依赖集
1、逻辑蕴涵 定义6.11 对于满足一组函数依赖F的关系模式R,其任何一个关系r, 若函数依赖X→Y都成立(即r中任意两元组t、S,若址Ⅺ]=s[X],则 tY]=s[Y]),则称F逻辑蕴含Ⅹ→Y,记为F=X→Y 例如,设F={A→B,B→C},则函数依赖A→C被F逻辑蕴含,记作 F=A→C。即函数依赖集F逻辑蕴含函数依赖A→C
1、逻辑蕴涵 定义6.11 对于满足一组函数依赖 F 的关系模式R ，其仸何一个关系r， 若函数依赖X→Y都成立（即r中仸意两元组t、s，若t[X]=s[X]，则 t[Y]=s[Y]），则称F逻辑蕴含X→Y，记为F⊨X→Y； 例如，设F={ A→B，B→C }，则函数依赖A→C被F逻辑蕴含，记作： F ⊨A→C。即函数依赖集 F 逻辑蕴含函数依赖A→C
2、 Armstrong公理系统 Armstrong公理系统:-套推理规则,是模式分解算法的理论基础; 关系模式R来说有以下的推理规则: A1.自反律( Reflexivity):若YcⅩgU,则X→}为F蕴藴含。 A2增广律( Augmentation):若X→Y为斤所蕴含,且zU, 则ⅩZ→YZ为「蕴含 A3传递律( Transitivity):若X→Y及γ→z为斤蕴含,则Ⅹ→z 为斤所蕴含
2、Armstrong公理系统 Armstrong公理系统：一套推理规则，是模式分解算法的理论基础； 关系模式R 来说有以下的推理规则： ◦ A1.自反律（Reflexivity）：若Y X U，则X →Y为F所蕴含。 ◦ A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z U， 则XZ→YZ为F所蕴含。 ◦ A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z 为F所蕴含