数据库设计理论

数据库的设计理论 第一节 关系模式的设计问题第一节 关系模式的设计问题 一 概念 1 关系模型 关系模型 用二维表来表示实体集 用外键来表示实体间的联系 这样 的数据模型 叫做关系数据模型 关系模型包含内涵和外延两个方面 外延 就是关系或实例 或当前值 它与时间有关 随时间的变化而变化 主要是由于元组的插入 删除 修改等操作引起的 内涵 内涵是与时间独立的 它包括关系属性 以及域的一些定义和说明 还有数据的各种完整性约束 数据的完整性约束分为静态约束和动态约束 静态约束包括数据之间的联系 称为数据依赖 主键的设计和各种限制 动态约束主要定义如插入 删除和修改等操作的影响 通常我们称内涵为关系模式 2 关系模式 关系模式 是对一个关系的描述 二维表的表头那一行称为关系模式 又称为表的框架或记录类型 关系模式的定义包括 模式名 属性名 值域名和模式的主键 关系模式仅 仅是对数据特征的描述 关系模式的一般形式为 R U D DOM F R 是关系名 U 是全部属性的集合 D 是属性域的集合 DOM 是 U 和 D 之间的映射关系 关系运算的安全限制 F 是属性间的各种约束关系 也称为数据依赖 关系模式可以表示为 关系模式 属性名 1 属性名 2 属性名 n 示例 学生 学号 姓名 年龄 性别 籍贯 当且仅当 U 上的一个关系 r 满足 F 时 r 就称为关系模式 R U F 上的一个关系 R 是关系的型 r 是关系的值 每个值称为 R 的一个关系 关系数据库模式 一个数据库是由多个关系构成的 一个关系数据库对应多个不同的关系模式 关系数据库模式是一个数据库中 所有的关系模式的集合 它规定了数据库的全局逻辑结构 关系数据库模式可以表示为 S Ri i 1 2 n 3 关系子模式关系子模式 关系子模式是用户所用到的那部分数据的描述 外模式是关系子模式的集合 4 存储模式存储模式 存储模式及内模式 关系数据库理论的主要内容 关系数据库理论的主要内容 1 数据依赖 数据依赖起着核心的作用 2 范式 3 模式的设计方法 如何设计一个合理的数据库模式 如何设计一个合理的数据库模式 1 与实际问题相结合 泛关系模式 把现实问题的所有属性组成一个关系模式 泛关系 泛关系模式的实例称为泛关系 泛关系模式中存在的问题 a 数据冗余 b 更新异常 c 插入异常 d 删除异常 2 数据库设计理论 借助近代代数工具 把抽象的数据理论同实际问题结合起来 理论基础 数据依赖 数据的相关性 二 关系模式及其评价 1 关系数据库设计的核心 关系模式的设计 2 关系模式的设计 按照一定的原则 从数量众多的而又互相关联的数据中构造出一组即能 较好的反映现实世界 而又有良好的操作性能的关系模式 3 关系模式的优劣 评价 改进 冗余度高 修改困难 插入问题 删除问题 这些问题的产生原因是 属性间的约束关系太强 即数据间的依赖关系太强 解决的方法 将关系模式分解为一组较理想的关系模式 第二节第二节 函数依赖函数依赖 一 函数依赖一 函数依赖 Functional Dependency 函数依赖是数据依赖的一种 反映属性或属性之间的依存 互相制约的关系 既反映现实世界的约束关系 二二 函数依赖的定义函数依赖的定义 设 R U 是属性 U 上的一个关系模式 X 和 Y 均为 U A1 A2 An 的子集 r 为 R 的任一关系 如果对于 r 中的任意两个元组 u 和 v 只要有 U X V X 就有 U Y V Y 则称 X 函数决定 Y 或称 Y 函 数依赖于 X 记作 X Y 三三 函数依赖的语义范畴 函数依赖的语义范畴 1 语义 数据所反映的现实世界事务本质的联系 2 根据语义来确定函数依赖型的存在与否 3 函数依赖反映属性之间的一般规律 必须在关系模式 F 的任何一个关 系 r 都满足约束条件 回顾概念回顾概念 键键 由一个或多个属性组成 由一个或多个属性组成 设 R U 为一个关系模式 F 为 R 的函数依赖集 X 为 属性集 U 的 子集 1 超键 超键 能唯一标识元组的属性集 能唯一标识元组的属性集 如果 X U F 则 X 是 R 的超键 2 候选键 候选键 不含有多余属性的超键 不含有多余属性的超键 a X 是 R 的超键 b 且不存在 X 的真子集 Y 使得 Y U F 则称 X 是 R 的候选键 3 主键 主键 用户选作元组标识的一个候选键 用户选作元组标识的一个候选键 4 主属性 包含任何一个候选键的属性 主属性 包含任何一个候选键的属性 5 非主属性 不包含任何一个候选键的属性 非主属性 不包含任何一个候选键的属性 6 外键 如果关系 R 的某一个属性组不是该关系本身的候选键 而是 另一个关系的候选键 则称该属性组是 R 的外来关键码 或称为外键 外码 如何确定候选码 如何确定候选码 1 如果有属性不在函数依赖集中出现 那么它必定包含在候选码中 2 如果有属性不在函数依赖集中任何函数依赖的右边出现 那么它必定 包含在候选码中 3 如果该属性或属性组能唯一标识元组 则它就是候选码 根据对数据库的语义描述 确定其中候选码 同时还可以写出该关系模式的 函数依赖集 四四 函数依赖的关系函数依赖的关系 属性间的关系决定函数依赖关系 设 X 和 Y 都是 U 的子集 1 X 和 Y 的联系是 1 1 则 X Y Y X 2 X 和 Y 的联系是 M 1 M 1 则 X Y 3X 和 Y 的联系是 M N M N 1 则 X Y 之间不存在函数依 赖 五 函数依赖 图 FD 图 六六 完全函数依赖完全函数依赖 和部分函数依赖和部分函数依赖 在 R U 中 如果 X Y 并且对于 X 的任何真子集 X 都不存在 X Y 则称 Y 完全依赖于 X 记作 X Y 箭头上加个 F 表示 FULL 完全函数依赖 否则 如果 X Y 且 X 中存在一个真子集 X 使得 X Y 则 Y 部分函数依赖 X X Y 箭头上面加一个 P 表示 PART 部分函数依赖 七七 平凡函数依赖平凡函数依赖 和非平凡函数依赖和非平凡函数依赖 设 X Y 均为某关系的属性集 并且 X Y 若 Y 包含于 X 则称 X Y 为平凡函数依赖 Y 是 X 的子集 若 Y 不包含于 X 则称 X Y 为非平凡函数依赖 Y 不是 X 的子集 第三节 函数依赖的蕴涵与公理体系 一 函数依赖的逻辑蕴含一 函数依赖的逻辑蕴含 定义 设有关系模式 R U 及其函数依赖集 F 如果对于 R 的任何一 个满足 F 的关系 r 函数依赖 X Y 都成立 则称 F 逻辑蕴含 X Y 或 称 X Y 可以由 F 推出 记作 例题 关系模式 R A B C 函数依赖集 F A B B C 则 F 逻辑蕴含 A C 记作 二二 F 闭包闭包 定义 若 F 为关系模式 R U 的函数依赖集 我们把 F 以及所有被 F 逻辑蕴含的函数依赖的集合称为 F 的闭包 记作 F F X Y F X Y 三 三 Armstrong 公理公理 F1 自反律自反律 若 Y 包含于 X 则 X Y Y 是 X 的子集 F2 增广律增广律 若 X Y 为 F 所蕴含 则 XZ YZ 在 R 上成立 F3 传递律传递律 若 X Y Y Z 在 R 上成立 则 X Z 在 R 上成立 F4 伪增律伪增律 Z 是 W 的子集 X Y 为 F 所蕴含 则 XW YZ 在 R 上成 立 F5 伪传律伪传律 若 X Y YW Z 为 F 所蕴含 则 XW Z 在 R 上成立 F6 合并律合并律 若 X Y X Z 为 F 所蕴含 则 X YZ 在 R 上成立 F7 分解律分解律 若 Z 是 Y 的子集 X Y 为 F 所蕴含 则 X Z 在 R 上成立 四 属性集的闭包四 属性集的闭包 定义 若 F 为关系模式 R U 的函数依赖集 X 是 U 的子集 则由 Armstrong 公理推导出来的所有 X Ai 所形成的属性集 Ai i 1 2 n 称 为 X 关于 F 的闭包 记为 X 属性集闭包的举例 设 R ABC F A B B C 当 X 分别是 A B C 时 求 X 解 当 X A 时 X ABC 当 X B 时 X BC 当 X C 时 X C 定理定理 X Y 能根据能根据 Armstrong 推理规则导出的充要条件是 推理规则导出的充要条件是 只要 Y 是 X 的子集 则 X Y 只要 X Y 则 Y 一定是 X 的子集 定理定理 Armstrong 公理的完备性定理公理的完备性定理 函数依赖推理规则系统 自反律 增广律 传递律 是完备的 函数依赖公理体系函数依赖公理体系 Armstrong 公理体系 由于 Armstrong 公理的完备性 Armstrong 公理及其推论构成了一个完备的 逻辑推理体系 称为 Armstrong 公理体系 A 一套形式推理规则 B 利用这些推理规则可以求出给定关系模式的关键字 C 而且可以从关系模式的一组已知函数依赖出发 求得它蕴含的所有函 数依赖 D 或者对于给定的 F 和 X Y 判断 X Y 是否在 F 中 E 是关系规范化理论的依据 计算计算 X 的算法的算法 1 依据 若 F 为关系模式 R U 的函数依赖集 X Z W 是 U 的子集 对于 任意的 Z W F 若 Z 是 X 的子集 则 X XW 2 算法的实现 输入 关系模式 R 上的子集 X R 上的函数依赖 F 输出 X 关于 F 的闭包 X 3 算法 a 令 X 0 X X b 如果 X 0 X 置 X 0 X 否则 转到 d c 对于 f 中的每个未被访问过的函数依赖 Y Z 若 Y 包含于 X 则令 X X Z 为被访问过的函数依赖设置访问标志 转 b d 输出 X 结论结论 判定函数依赖 X Y 是否能由 F 导出的问题 可以转化为求 X 的闭包 并判定 Y 是否是 X 子集的问题 即求闭包的问题可以转化为求属性集的问题 判定给定函数依赖 X Y 是否蕴含与函数依赖集 F 算法实现 输入 函数依赖集 F 函数依赖 X Y 输出 若 X Y F 输出真 否则输出假 四四 函数依赖的等价和覆盖 函数依赖的等价和覆盖 定义 设 F 和 G 是关系模式 R U 上的两个函数依赖集 如果 F G 则 称 F 等价于 G 亦称 F 覆盖 G 或者 G 覆盖 F 记作 F G 定理定理 1 设设 F 和和 G 是关系模式是关系模式 R U 的两个函数依赖集 那么的两个函数依赖集 那么 F G 的充分必要条件是 的充分必要条件是 定理定理 2 设设 F 和和 G 是关系模式是关系模式 R U 的两个函数依赖集 那么的两个函数依赖集 那么 F G 的充分必要条件是的充分必要条件是 定理定理 3 每个函数依赖集 每个函数依赖集 F 都可以被一个右部只有单属性的函数依赖集都可以被一个右部只有单属性的函数依赖集 G 所覆盖 所覆盖 五 最小函数依赖集五 最小函数依赖集 设 F 是函数依赖集 如果 F 满足 1 F 中每个函数依赖 X Y 的右边均为单个属性 2 F 中的任何一个函数依赖 X A 其 F X A 都与 F 不等价 3 F 中的任何一个函数依赖 X A Z 为 X 的真子集 F X A Z A 都与 F 不等价 则称 F 为最小函数依赖集 2 是消除右侧冗余 3 是消除左侧冗余 因为 2 3 没有先后顺序 所以 最小函数依赖不是唯一的 第四节第四节 关系模式的分解关系模式的分解 一一 关系模式分解的衡量标准 关系模式分解的衡量标准 1 仅具有无损连接性 不增减信息 2 仅保持函数的依赖集 不破坏属性间存在的依赖关系 3 即具有无损连接性 又保持函数依赖集 二 分解的无损连接性 二 分解的无损连接性 1 定义 设 F 是关系模式 R 的函数依赖集 R1 U1 F1 R2 U2 F2 Rk Uk Fk 是 R 的一个 分解 或者 如果 R 满足 F 的任何 一个关系均有 则分解具有无损连接性 定理 设 R1 R2 Rk 为关系模式的一个分解 r 为 R 的任何一个关系 ri ui r 则 1 2 如果 S m r 则 ui S ri 3 m m r m r m r m r 结论结论 分解后的关系作自然联结必包含分解前的关系 即分解不会丢失信息 但 可能增加信息 只有 r m r 时 分解才具有无损连接性 为什么要进行关系分解 一个关系分解后 可以存放原来不能存放的信息 通常称为 悬挂 的元组 这是实际所需要的 正是分解的优点 在做自然联结时 这类 悬挂 元组自然丢失了 但不是信息的丢失 而是 合理的 检验分解无损联结的算法检验分解无损联结的算法 设关系模式 R A1 A2 An F 是他的函数依赖集 R1 R2 R3 Rk 为 R 的一个分解 算法算法 1 构造初始表 构造初始表 构造一个 k 行 n 列的初始表 其中每列对应于 R 的一个属性 每行用于 表示分解后的一个模式组成 如果属性 Aj 属于关系模式 Ri 则在表的第 i 行 第 j 列置符号 aj 否则 置符号 bij 2 根据 根据 F 中的函数依赖修改表的内容中的函数依赖修改表的内容 考察 F 中的每一个函数依赖 X Y 在属性组 X 所在的那些列上寻 找具有相同符号的行 如果找到这样的两行或更多行 则修改这些行 使这些行 上的属性组 Y 所在的列上的元素相同 修改规则 如果 Y 所在的要修改的行中有一个为 aj 则这些元素均 变为 aj 否则 改动为 bmj 其中 m 为这些行的最小行号 注意 若某个 bij 被改动 则该列中凡是与 bij 相同的符号均作相同的 改动 循环的对 F 中的函数依赖进行逐个处理 直到发现表中有一行变为 a1 a2 a3 an 或者不能再被修改为止 3 断分解是否无损联结断分解是否无损联结 如果通过修改 发现表中有一行变为 a1 a2 an 则分解是无损 联结的 否则 分解不具有无损联结性 定理 检验分解无损联结的算法 能够正确判定一个分解是否具有无损联结性 定理 设 R1 R2 是模式 R 的一个分解 F 是 R 的函数依赖集 那么 是 R 关于 F 的 的无损分解的充要条件是 R1 R2 R1 R2 F 或者 R1 R2 R2 R1 F 保持函数依赖的分解保持函数依赖的分解 定义 设 F 是关系模式 R 在所有属性集 U 上的函数依赖集 Z 是 U 的子集 F 在 Z 上的一个投影用 z F 表示 定义为 z F X Y X Y F 且 XY 是 Z 的子集 设关系模式 R 的一个分解 R1 R2 Rk 如果 Fi Ri 的并集 F1 F2 Fk F 则 分解保持函数依赖集 F 关系模式满足的确定条件称为范式 根据满足的约束条件不同 范式可以 分为 1NF 2NF 3NF BCNF 4NF 5NF 等 不同的范式 性质不同 关系模式规范化 把一个低一级的关系模式分解为高一级的关系模式的过程 回顾概念回顾概念 1 超键超键 能唯一标识元组的属性集 2 候选键候选键 不含有多余属性的超键 a X 是 R 的超键 b 且不存在 X 的真子集 Y 使得 Y U F 则称 X 是 R 的候选键 3 主键主键 用户选作元组标识的一个候选键 4 主属性主属性 包含在任何一个候选键中的属性 5 非主属性非主属性 不包含在任何一个候选键中的属性 6 外键外键 如果关系 R 的某一个属性组 不是该关系本身的候选关键字 而 是另一关系的候选关键字 则称该属性组是 R 的外来关键字或外部关 键字 完全函数依赖和部分函数依赖完全函数依赖和部分函数依赖 在 R U 中 如果 X Y 而且对于 X 的任意真子集 X 都不存在 X Y 则称 Y 完全依赖于 X 否则 如果 X Y 且存在 X 的真子集 X 使得 X Y 成立 则 Y 部分函数依赖于 Y 如何确定关系模式中的候选码 如何确定关系模式中的候选码 1 如果有属性不在函数依赖集中出现 那么它必须包含在候选码中 2 如果有属性不在函数依赖集中任何函数依赖的右边出现 那么它必定 包含在候选码中 3 如果该属性或属性组能唯一的标识元组 则它就是候选码 未给出关系模式的函数依赖集 如何确定其中的候选码 未给出关系模式的函数依赖集 如何确定其中的候选码 根据对数据库的语义描述 确定其中的候选码 同时还可以写出该关系模式 上的函数依赖集 第一范式 第一范式 1NF 关系模式的所有域为简单域 其元素不可再分 是数据项而不是数据组 这样的关系模式称为第一范式 1NF 存在的问题 数据冗余 插入异常 删除异常 修改异常 第二范式第二范式 2NF 给定关系模式 R 及其上的函数依赖集 F 如果 R 上的任何一个非主属 性都完全依赖于他的每一个候选关键字 则称 R 是第二范式 2NF 若关系模型 H 包含的每个关系模式都是 2NF 的 则称该关系模型是 2NF 的 存在的问题 可能存在数据冗余 插入异常 删除异常 修改异常 结论 若结论 若 R 1NF 且 且 R 中所有的候选码为单一属性 则中所有的候选码为单一属性 则 R 2NF 传递函数依赖传递函数依赖 在 R U 中 如果 X Y Y Z 并且 Z 不是 Y 的子集 那么 称 X Z 传递函数依赖 即 Z 传递函数依赖于 X 第三范式第三范式 给定关系模式 R 及其上的函数依赖 F 如果 R 的任何一个非主属性都 不传递函数依赖于他的任何一个候选码 则称 R 是第三范式 3NF 若关系模型 H 包含的每一个关系模式都是 3NF 的 则称该关系模式是 3NF 的 定理 一个 3NF 的关系模式必定是 3NF 的 BCNF 改进了的改进了的 3NF 给定关系模式 R 及其上的函数依赖集 F 如果 F 中每一个非平凡函数 依赖 X Y 的左部 决定因素 X 中必含有候选码 则称 R 是 Boyde Codd 范式 简称 BCNF R 1NF 若 X Y 且 Y 不是 X 的子集 X 中必含有候选码 则 R BCNF BCNF 的内涵的内涵 1 非主属性对候选码完全函数依赖 2 主属性对不含他的候选码完全函数依赖 3 没有属性完全函数依赖于一组非主属性 4 主属性不传递函数依赖于任何一个候选码 5 主属性不传递函数依赖于任何一个候选码 定理 定理 BCNF 满足满足 3NF 重叠的候选码重叠的候选码 一个模式有两个非单属性的候选码 且二者的交集非空 则称这两个候选码 是重叠的 若模式中没有重叠的候选码时 则 2NF 一定是 BCNF 只有当模式中有重叠的候选码时 3NF 不一定是 BCNF 总结 1NF 消除了非主属性对候选码的部分函数依赖 消除了非主属性对候选码的部分函数依赖 2NF 消除了非主属性对候选码的传递函数依赖 消除了非主属性对候选码的传递函数依赖 3NF 消除了主属性对候选码的部分和传递函数依赖 消除了主属性对候选码的部分和传递函数依赖 BCNF 规范化的基本思想规范化的基本思想 逐步消除不合适的函数依赖 使数据库的各个关系模式达到某种程度上的分 离 模式分解的算法模式分解的算法 模式分解的基本要求 分解后的关系模式与分解前的关系模式等 即分解必须 1 具有无损联结性 2 保持函数依赖 逐步分解的定理 逐步分解的定理 设 F 是关系模式 R 的函数依赖集 R1 R2 Rk 是 R 关于 F 的一个无损连接分解 1 若 1 S1 S2 Sm 是 Ri 关于 Fi 的一个无损连接 分解 其中 Fi Ri F 则 2 R1 Ri 1 S1 Sm Ri 1 Rk 是 R 关于 F 的无损分解 2 设 3 R1 Rk Rk 1 Rn 是 R 的一个分解 其中 是 3 的子集 则 3 也是关于 F 的无损联结分解 面向面向 BCNFBCNF 且具有无损联结的分解且具有无损联结的分解 算法算法 1 1 输入 关系模式 R 函数依赖集 F 输出 R 的一个无损联结的分解 其中每一个子模式都满足 F 在其上投影的 BCNF 算法实现 算法实现 反复运用逐步分解定理 逐步分解关系模式 R 使得每次分解都具有 无损联结性 而且每次分解出来的子关系模式都至少有一个具有 BCNF 范 式 1 置初值 R 2 检查 中的关系模式 如果均属 BCNF 则转到第 4 步 3 在 中找出不属于 BCNF 的关系模式 S 那么 S 中必能找出一 个函数依赖 X A F A 不包含于 X 且 X 不是 S 的候选码 因此 XA 必 然不包含 S 的全部属性 把 S 分解为 S1 S2 设 S1 XA S2 S A 并以 S1 S2 代 替 R 中的 S 返回 2 4 终止分解 输出 算法出现的问题 1 分解结果不是唯一的 2 分解不保证保持函数依赖 面向面向 3NF3NF 且保持函数依赖的分解且保持函数依赖的分解 算法算法 2 输入 关系模式 R 及其上的最小函数依赖集 F 输出 R 的保持函数依赖的分解 其中每个关系模式是关于 F 在其上投影的 3NF 算法实现算法实现 1 如果 R 中存在一些不在 F 中出现的属性 则将他们单独构成一个 关系模式 并从关系模式 R 中消去 2 如果 F 中有一个函数依赖 X A 且 XA R 则 R 不用分解 算法终止 3 对 F 中的每个函数依赖 X A 构造一个关系模式 XA 如果 X A1 X A2 X An 均属于 F 则构造一个关系模式 XA1A2 An 本算法注意 必须是最小函数依赖集 F 否则出错 面向面向 3NF 既有无损联结性 又保持函数依赖分解既有无损联结性 又保持函数依赖分解 算法 输入 关系模式 R 及其上的最小函数依赖集 F 输出 R 的具有无损联结性及保持函数依赖的分解 算法实现 1 按算法 2 对关系模式 R 进行分解 设结果为 R1 R2 Rk 2 X 是 R 的候选码 t u x 是 R 的一个分解 3 求 t 的最小集合 当 Ri 是 Rj 的子集 t 时 消去 Ri 定理定理 算法的正确性 算法的正确性 设 X 是 R 的候选码 则 t u x 是 R 的一个分解 且所有的关系都 满足 3NF 同时具有无损联结性 和保持函数依赖性 由于 中全部模式均为 3NF X 中属性之间不存在传递和部分函数依赖 即 X 也是 3NF 的 分解 t 也具有无损联结性 由于 X 是 R 的候选码 验 证表中模式 X 所对应的行 经修改后全部由 a 组成 模式设计的原则模式设计的原则 关系模式 R 相对于函数依赖 F 分解成数据库模式 R1 R2 Rk 一般具有下面 4 个特性 1 中的每个关系模式 Ri 上应具有某种范式的性质 如 3NF BCNF 2 无损联结性 3 保持函数依赖集 4 最小性 即 中模式个数应最少 且模式中属性总数应最少 一个好的模式设计方法应符合下了三条原则 1 表达性 2 分理性