数据库第07章

第7章关系数据库设计理论 7 1数据依赖对关系模式的影响7 2函数依赖7 3范式7 4多值依赖与第4范式 4NF 7 5关系模式的规范化7 6数据依赖的公理系统 退出 7 1数据依赖对关系模式的影响 关系数据库规范化理论中的重要概念是数据依赖 数据依赖是一个关系内部属性与属性之间的一种约束关系 这种约束关系是通过属性值之间的依赖关系来体现的 数据依赖中最重要的是函数依赖 FunctionalDependency FD 和多值依赖 MultivaluedDependency MVD 属性间的这种依赖关系类似于数学中的函数y f x 自变量x确定之后 相应的函数值y也就惟一地确定了 现在我们建立一个描述学校教务的数据库 该数据库涉及的对象包括学生的学号 Sno 所在系 Sdept 系主任姓名 Mname 课程名 Cname 和成绩 Grade 假设我们用一个单一的关系模式Student来表示 则该关系模式的属性集为 U Sno Sdept Mname Cname Grade 现实世界的已知事实 语义 告诉我们 1 一个系有若干学生 但一个学生只属于一个系 2 一个系只有一名主任 3 一个学生可以选修多门课程 每门课程有若干学生选修 4 每个学生所学的每门课程都有一个成绩 从上述事实我们可以得到属性集U上的一组函数依赖F 如图7 1所示 F Sno Sdept Sdept Mname Sno Cname Grade 如果只考虑函数依赖这一种数据依赖 我们就得到了一个描述学生的关系模式 Student 1 数据冗余太大例如 每一个系主任的姓名重复出现 2 更新异常 UpdateAnomalies 例如 某系更换系主任后 系统必须修改与该系学生有关的每一个元组 3 插入异常 InsertionAnomalies 如果一个系刚成立 尚无学生 我们就无法把这个系及其系主任的信息存入数据库 4 删除异常 DeletionAnomalies 如果某个系的学生全部毕业了 我们在删除该系学生信息的同时 把这个系及其系主任的信息也丢掉了 一个关系模式之所以会产生上述问题 是由存在于模式中的某些数据依赖引起的 规范化理论正是用来改造关系模式 通过分解关系模式来消除其中不合适的数据依赖 以解决插入异常 删除异常 更新异常和数据冗余问题 7 2函数依赖 7 2 1函数依赖定义7 1设R U 是属性集U上的关系模式 X Y是U的子集 若对于R U 的任意一个可能的关系实例r r中不可能存在两个元组在X上的属性值相等 而在Y上的属性值不等 则称X函数确定Y或Y函数依赖于X 记作X Y 对于函数依赖 需要说明以下几点 1 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件 而是指R的所有关系实例均要满足的约束条件 2 函数依赖和别的数据之间的依赖关系一样 是语义范畴的概念 我们只能根据数据的语义来确定函数依赖 例如 姓名 年龄 这个函数依赖只有在没有同名人的条件下成立 如果有相同名字的人 则 年龄 就不再函数依赖于 姓名 了 3 X Y 但YX则称X Y是非平凡的函数依赖 4 X Y 但Y X则称X Y是平凡的函数依赖 对于任一关系模式 平凡函数依赖都是必然成立的 它不反映新的语义 若不特别声明 总是讨论非平凡的函数依赖 5 若X Y 则X称为这个函数依赖的决定属性组 也称为决定因素 Determinant 6 若X Y 并且Y X 则记为X Y 7 若Y函数不依赖于X 则记为XY 8 若X Y 并且对于X的任何一个真子集X 都有X Y 则称Y完全函数依赖于X 记作XY 否则称Y部分函数依赖于X 记作XY 9 若X Y Y Z 且Y X YX 则称Z传递函数依赖于X 加上条件YX 是因为如果Y X 则X Y 实际上是X Z 即是直接函数依赖而不是传递函数依赖 属性集U上的关系模式R U 常常表示为R F是属性集U上的一组函数依赖 7 2 2码码是关系模式中一个重要概念 下面我们用函数依赖的概念来定义码 定义7 2设K为关系模式R中的属性或属性组合 若KU 则K称为R的一个候选码 CandidateKey 若关系模式R有多个候选码 则选定其中的一个作为主码 Primarykey 主码用下横线 显示出来 包含在任何一个候选码中的属性 叫作主属性 Primeattribute 不包含在任何码中的属性称为非主属性 Nonprimeattribute 或非码属性 Non keyattribute 最简单的情况 单个属性是码 最极端的情况 全部属性是码 称为全码 All key 例如 在关系模式S Sno Sdept Sage 中Sno是码 关系模式R P W A 属性P表示演奏者 W表示作品 A表示听众 假设一个演奏者可以演奏多个作品 某一作品可被多个演奏者演奏 听众也可以欣赏不同演奏者的不同作品 这个关系模式的码为 P W A 即All key 定义7 3关系模式R中属性或属性组X并非R的码 但X是另一个关系模式S的码 则称X是R的外部码 Foreignkey 也称外码 例如 在SC Sno Cno Grade 中 Sno不是码 但Sno是关系模式Student Sno Sdept Sage 的码 则Sno是关系模式SC的外部码 主码与外部码表示了关系之间的联系 例如 关系模式Student与SC的联系就是通过Sno来体现的 7 3范式 范式是符合某一种级别的关系模式的集合 满足最低要求的叫第1范式 简称为1NF 在第1范式基础上进一步满足一些要求的为第2范式 简称为2NF 其余以此类推 显然各种范式之间存在以下关系 4NF BCNF 3NF 2NF lNF 如图7 2所示 我们通常把某一关系模式R为第n范式简记为R nNF 7 3 1第1范式 1NF 定义7 4如果一个关系模式R的所有属性都是不可分的基本数据项 则R 1NF SLC Sno Cno Sdept Sloc Grade 其中Sloc为学生住处 假设每个系的学生住在同一个地方 SLC的码为 Sno Cno 函数依赖包括 Sno Cno GradeSno Sdept Sno Cno SdeptSno Sloc Sno Cno SlocSdept Sloc 因为每个系只住一个地方 f p p SLC关系存在以下问题 1 插入异常 2 删除异常 3 数据冗余度大 4 修改复杂 7 3 2第2范式 2NF 关系模式SLC出现上述问题的原因是Sdept Sloc对码的部分函数依赖 为了消除这些部分函数依赖 我们可以采用投影分解法 把SLC分解为两个关系模式 SC Sno Cno Grade SL Sno Sdept Sloc 这两个关系模式的函数依赖如图7 4所示 定义7 5若关系模式R 1NF 并且每一个非主属性都完全函数依赖于R的码 则R 2NF 杂的问题 例如2NF关系模式SL Sno Sdept Sloc 中有下列函数依赖 Sno SdeptSdept SlocSno Sloc 1 插入异常 2 删除异常 3 数据冗余度大 4 修改复杂 7 3 3第3范式 3NF 关系模式SL出现上述问题的原因是Sloc传递函数依赖于Sno 为了消除该传递函数依赖 我们可以采用投影分解法 把SL分解为两个关系模式 SD Sno Sdept SD的码为Sno DL Sdept Sloc DL的码为Sdept 定义7 6如果关系模式R中不存在候选码X 属性组Y及非主属性Z Z Y 使得X Y Y X 和Y Z成立 则R 3NF 例如 在关系模式STJ S T J 中 S表示学生 T表示教师 J表示课程 假设每一教师只教一门课 每门课由若干教师教 某一学生选定某门课 就确定了一个固定的教师 于是 我们有函数依赖 S J T T J 同时我们可以发现STJ S T J 中 S J S T 都是候选码 因此 S T J成立 用图7 5表示如下 3NF的STJ关系模式也存在以下问题 1 插入异常 2 删除异常 3 数据冗余度大 4 修改复杂 7 3 4BC范式 BCNF 关系模式STJ出现上述问题的原因在于主属性J依赖于T 即主属性J部分依赖于码 S T 解决这一问题仍然可以采用投影分解法 将STJ分解为两个关系模式 ST S T ST的码为STJ T J TJ的码为T 定义7 7设关系模式R 1NF 如果对于R的每个函数依赖X Y 若Y X 则X必含有候选码 那么R BCNF BCNF的关系模式具有如下3个性质 1 所有非主属性都完全函数依赖于每个候选码 2 所有主属性都完全函数依赖于每个不包含它的候选码 3 没有任何属性完全函数依赖于非码的任何一组属性 如果一个关系数据库中的所有关系模式都属于BCNF 那么在函数依赖范畴内 它已实现了模式的彻底分解 达到了最高的规范化程度 消除了插入异常和删除的异常 7 4多值依赖与第4范式 4NF 例1 设学校中某一门课程由多个教员讲授 他们使用相同的一套参考书 我们可以用一个关系模式Teach C T B 来表示 把这张表变成一张规范化的二维表 如表7 2所示 1 数据冗余度大 2 增加操作复杂 3 删除操作复杂 4 修改操作复杂 7 4 1多值依赖定义7 8设R U 是一个属性集U上的一个关系模式 X Y和Z是U的子集 并且Z U X Y 多值依赖X Y成立 当且仅当对R的任一关系r r在 X Z 上的每个值对应一组Y值 这组值仅仅决定于X值而与Z值无关 多值依赖具有下列性质 1 多值依赖具有对称性 即若X Y 则X Z 其中Z U X Y 2 函数依赖可以看作是多值依赖的特殊情况 即若X Y 则X Y 多值依赖与函数依赖相比 具有下面两个基本区别 1 多值依赖的有效性与属性集的范围有关 若X Y在U上成立则在W XY W U 上一定成立 反之则不然 即X Y在W W U 上成立 在U上并不一定成立 这是因为多值依赖的定义中不仅涉及属性组X和Y 而且涉及U中其余属性Z 2 若函数依赖X Y在R U 上成立 则对于任何Y Y均有X Y 成立 而多值依赖X Y若在R U 上成立 却不能断言对于任何Y Y有X Y 成立 7 4 2第4范式 4NF 定义7 9关系模式R lNF 如果对于R的每个非平凡多值依赖X Y YX X都含有候选码 则称R 4NF 7 5关系模式的规范化 规范化的基本思想是逐步消除数据依赖中不合适的部分 使模式中的各关系模式达到某种程度的 分离 即采用 一事一地 的模式设计原则 让一个关系描述一个概念 一个实体或者实体间的一种联系 若多于一个概念就把它 分离 出去 因此所谓规范化实质上是概念的单一化 关系模式规范化的基本步骤如图7 7所示 1 对1NF关系进行投影 消除原关系中非主属性对码的函数依赖 将1NF关系转换为若干个2NF关系 2 对2NF关系进行投影 消除原关系中非主属性对码的传递函数依赖 从而产生一组3NF关系 3 对3NF关系进行投影 消除原关系中主属性对码的部分函数依赖和传递函数依赖 也就是说 使决定属性都成为投影的候选码 得到一组BCNF关系 以上三步也可以合并为一步 对原关系进行投影 消除决定属性不是候选码的任何函数依赖 4 对BCNF关系进行投影 消除原关系中非平凡且非函数依赖的多值依赖 从而产生一组4NF关系 7 6数据依赖的公理系统 Armstrong公理系统 定义7 10对于满足一组函数依赖F的关系模式R 其任何一个关系r 若函数依赖X Y都成立 即r中任意两元组t s 若t X s X 则t Y s Y 则称F逻辑蕴含X Y Armstrong公理系统设U为属性集总体 F是U上的一组函数依赖 于是有关系模式R 对R来说有以下的推理规则 Al 自反律 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所蕴含 定理7 lArmstrong推理规则是正确的 证 l 设Y X U 对R的任一关系r中的任意两个元组t s 若t X s X 由于Y X 有t y s y 所以X Y成立 自反律得证 2 设X Y为F所蕴含 且Z U 设R的任一关系r中任意的两个元组t s 若t XZ s XZ 则有t X s X 和t Z s Z 由X Y 于是有t Y s Y 所以t YZ s YZ 所以XZ YZ为F所蕴含 增广律得证 3 设X Y及Y Z为F所蕴含 对R的任一关系r中的任意两个元组t s 若t X s X 由于X Y 有t Y s Y 再由Y Z 有t Z s Z 所以X Z为F所蕴含 传递律得证 根据A1 A2 A3这3条推理规则可以得到下面3条很有用的推理规则 合并规则 由X Y X Z 有X YZ 伪传递规则 由X Y WY Z 有XW Z 分解规则 由X Y及Z Y 有X Z 根据合并规则和分解规则 很容易得到这样一个重要事实 引理7 lX A1A2 Ak成立的充分必要条件是X Ai成立 i l 2 k 定义7 l1在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作F的闭包 记为F 人们把自反律 传递律和增广律称为Armstrong公理系统 Armstrong公理系统是有效的 完备的 Armstrong公理的有效性指的是 由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F 中 完备性指的是F 中的每一个函数依赖 必定可以由F出发根据Armstrong公理推导出来 要证明完备性 首先要解决如何判定一个函数依赖是否属于由F根据Armstrong公理推导出来的函数依赖的集合 当然 如果能求出这个集合 问题就解决了 但不幸的是 这是一个NP完全问题 比如从F X A1 X An 出发 至少可以推导出2n个不同的函数依赖为此引入了下面的概念 定义7 12设F为属性集U上的一组函数依赖 X U XF A X A能由F根据Armstrong公理导出 XF 称为属性集X关于函数依赖集F的闭包 由引理7 1容易得出 引理7 2设F为属性集U上的一组函数依赖 X Y U X Y能由F根据Armstrong公理导出的充分必要条件是Y XF 于是 判定X Y是否能由F根据Armstrong公理导出的问题 就转换为求出XF 判定Y是否为XF 的子集的问题 这个问题由算法7 l解决了 算法7 l求属性集X X U 关于U上的函数依赖集F的闭包XF 输入 X F输出 XF 步骤 1 令X 0 X i 0 2 求B 这里B A V W V W F V X i A W 3 X i 1 B X i 4 判断X i 1 x i 吗 5 若相等或X i U则X i 就是XF 算法终止 6 若否 则i i l 返回第 2 步 例1 已知关系模式R 其中U A B C D E F AB C B D C E EC B AC B 求 AB F 解由算法7 1 设X 0 AB 计算X 1 逐一扫描F集合中各个函数依赖 找左部为A B或AB的函数依赖 得到两个 AB C B D 于是X 1 AB CD ABCD 因为X 0 X 1 所以再找出左部为ABCD子集的那些函数依赖 又得到C E AC B 于是X 2 X 1 BE ABCDE 因为X 2 已等于全部属性集合 所以 AB F ABCDE 对于算法7 l 令ai X i ai 形成一个步长大于1的严格递增的序列 序列的上界是 U 因此该算法最多 U X 次循环就会终止 定理7 2Armstrong公理系统是有效的 完备的 Armstrong公理系统的有效性可由定理7 l得到证明 完备性的证明从略 有兴趣的读者请参考 7 Armstrong公理的完备性及有效性说明了 导出 与 蕴含 是两个完全等价的概念 于是F 也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合 从蕴含 或导出 的概念出发 又引出了两个函数依赖集等价和最小依赖集的概念 定义7 13如果G F 就说函数依赖集F覆盖G F是G的覆盖 或G是F的覆盖 或F与G等价 引理7 3F G 的充分必要条件是F G 和G F 证必要性显然 只证充分性 1 若F G 则XF XG 2 任取X Y F 则有Y XF 所以X Y G G 即F G 3 同理可证G F 所以F G 而要判定F G 只须逐一对F中的函数依赖X Y 考察Y是否属于就行了 因此引理7 3给出了判断两个函数依赖集等价的可行算法 定义7 14如果函数依赖集F满足下列条件 则称F为一个极小函数依赖集 亦称为最小依赖集或最小覆盖 1 F中任一函数依赖的右部仅含有一个属性 2 F中不存在这样的函数依赖X A 使得F与F X A 等价 3 F中不存在这样的函数依赖X A X有真子集Z使得F X A Z A 与F等价 例2 考察关系模式S 其中 U Sno Sdept MName Cname Grade F Sno Sdept Sdept MName Sno Cname Grade 设F Sno Sdept