《关系数据理论》PPT课件

2021/5/26 要点v关 系 规 范 化 理 论 研 究 背 景v数 据 依 赖v规 范 化 (Normalization)理 论u1NF、 2NF、 3NF、 BCNF、 4NF等 范 式u关 系 模 式 规 范 化 的 必 要 性 及 方 法 5.1 问题的提出v问 题 提 出 ：u针 对 一 个 具 体 问 题 ， 如 何 构 造 合 适 的 (更 好的 )数 据 模 式 ， 即 如 何 更 好 地 设 计 数 据 的 逻辑 结 构 ？v关 系 数 据 理 论 的 研 究 背 景u关 系 模 型 建 立 在 严 格 的 数 据 理 论 基 础 上 ， 并可 向 别 的 数 据 模 型 转 换 ， 因 此 常 以 关 系 模 型为 背 景 来 讨 论 这 个 问 题 背景知识v数 据 模 式 (schema)u数 据 库 中 全 体 数 据 的 逻 辑 结 构 和 特 征 描 述 ，如 数 据 记 录 的 构 成 ， 数 据 间 的 联 系 ， 安 全 性 、完 整 性 要 求 等 。 常 以 某 一 种 数 据 模 型 为 基 础v关 系 模 型 的 形 式 化 定 义 ： R(U,D,dom,F)，本 章 简 化 为 R(U, F)v关 系 模 型 R的 一 个 关 系 r： U上 的 一 个 关 系r满 足 F 属 性组一 组数 据依 赖 一个例子：学生-课程-成绩管理v客 观 存 在 的 事 实u一 个 系 有 若 干 学 生 ， 但 一 个 学 生 只 属 于 一 个 系 ； 一个 系 只 有 一 名 负 责 人 ； 一 个 学 生 可 以 选 修 多 门 课 程 ，每 门 课 程 有 若 干 学 生 选 修 ； 每 个 学 生 学 习 每 一 门 课程 有 一 个 成 绩v设 计 如 下 单 个 模 式u属 性 组 U = 学 号 SNO,系 名 SDEPT,系 负 责 人 MN,课 程 名CNAME,成 绩 Gu数 据 依 赖 ),(, GCNAMESNOMNSDEPTSDEPTSNOF v该 模 式 存 在 的 问 题 ？ 怎 么 改 善 这 个 模 式 ？ 问题和改进v该 模 式 存 在 的 问 题u 插 入 异 常 ： 一 个 系 无 学 生 或 未 安 排 课 程 时 ， 无 法 存 入 系 与 负 责 人删 除 异 常 ： 删 除 一 个 系 的 所 有 学 生 信 息 时 ， 系 与 负 责 人 也 丢 失u 冗 余 太 大 ： 负 责 人 姓 名 重 复 存 入u 更 新 异 常 ： 当 某 系 负 责 人 更 换 时 ， 须 更 新 该 系 所 有 学 生 信 息 中 的信 息 ， 更 新 不 完 全 时 ， 易 造 成 数 据 不 一 致v原 因 ： 数 据 依 赖 存 在 一 些 不 合 适 的 性 质 ， 需 寻 找 更 好 的 模式 ， 如S(SNO, SDEPT, )SG(SNO, CNAME, G, ) DEPT(SDEPT, MN, )SDEPTSNO GCNAMESNO ),( MNSDEPT SNO CNAME GSDEPTMN 5.2 规范化v意 图u讨 论 一 个 关 系 属 性 间 不 同 的 依 赖 情 况u讨 论 如 何 根 据 属 性 间 依 赖 关 系 来 判 定 关 系 是 否 有 某些 不 合 适 的 性 质v数 据 依 赖 概 念u反 映 客 观 世 界 数 据 间 的 相 互 关 联u通 过 一 个 关 系 中 属 性 间 值 的 相 等 与 否 来 体 现v两 种 重 要 的 数 据 依 赖 u函 数 依 赖 (Functional Dependency, FD)u多 值 依 赖 (Multivalued Dependency, MVD) 5.2.1 函数依赖v定 义 1u设 R(U)是 属 性 集 U上 的 关 系 模 式 。 X,Y是 U的 子 集 。 若对 于 R(U)的 任 意 一 个 可 能 的 关 系 r， r中 不 可 能 存 在 两个 元 组 在 X上 的 属 性 值 相 等 ， 而 在 Y上 的 属 性 值 不 等 ，则 称 X函 数 确 定 Y或 Y函 数 依 赖 于 X， 记 作v术 语 和 记 号u ， 但 ， 则 称 是 非 平 凡 的 函 数 依 赖u ， 但 ， 则 称 是 平 凡 的 函 数 依 赖 u若 ， 则 X叫 做 决 定 因 素u若 ， ， 则 记 作u若 Y不 函 数 依 赖 于 X， 则 记 作 YX YX XY YX YX XY YX YX YX XY YX YX 对函数依赖的说明v换 句 话 说 ： 任 何 时 候 若 某 一 关 系 中 的 两 个 元 组 中 的 X属性 组 的 值 相 等 ， 则 元 组 中 对 应 的 属 性 组 Y的 值 也 相 等 ，类 似 于 函 数 概 念 ， Y = f(X)v需 要 指 出 的 是 ： 关 系 R中 ， 如 果 属 性 组 X是 一 个 候 选 码或 码 ， 则 属 性 组 Y一 定 函 数 依 赖 于 X（ 这 与 候 选 码 的 定义 一 致 ）v事 实 上 ： 如 果 关 系 R上 有 函 数 依 赖 XY， 而 属 性 X不 是一 个 候 选 码 ， 则 R中 可 能 存 在 一 些 数 据 冗 余u例 如 ： R(Sno, Sdept, MN, Cname, Grade)中 有 函 数 依 赖Sdept-MN， 而 Sdept并 不 是 候 选 码 ， 表 中 数 据 有 大 量冗 余 出 现 函数依赖v定 义 2u在 R(U)中 ， 如 果 ， 并 且 对 于 X的 任 何 一个 真 子 集 X, 都 有 ， 则 称 Y对 X完 全 函数 依 赖 ， 记 作u若 ， 但 Y不 完 全 函 数 依 赖 于 X， 则 称 Y对 X部 分 函 数 依 赖 ， 记 作v定 义 3u在 R(U)中 ， 如 果 ， ( ) ， ， ， u则 称 Z对 X传 递 函 数 依 赖 ， 记 作YX YX YXFYX YX PYX XY ZY XY ZX 传 递 5.2.2 码用 函 数 依 赖 的 概 念 来 定 义 码v定 义 4 u设 K为 R(U,F)中 的 属 性 或 属 性 组 合 ， 若 则 K为R的 候 选 码 (Candidate Key)。u若 候 选 码 多 于 一 个 ， 则 选 定 其 中 的 一 个 为 主 码(Primary Key)v相 关 术 语 u包 含 在 任 何 一 个 候 选 码 中 的 属 性 ， 叫 做 主 属 性u不 包 含 在 任 何 码 中 的 属 性 ， 叫 做 非 主 属 性u整 个 属 性 组 是 码 ， 称 为 全 码 UK F 码v定 义 5u关 系 模 式 R中 属 性 或 属 性 组 X并 非 R的 码 ， 但 X是 另一 个 关 系 模 式 的 码 ， 则 称 X是 R的 外 部 码 (Foreign Key)， 也 称 为 外 码 主 码 与 外 码 提 供 了 一 个 表 示 关 系 间 联 系 的 手 段SC(Sno,Cno,Grade)Studen(Sno,Sname,.)Course(Cno, Cname,.) 5.2.3 范式v范 式 ： 符 合 某 种 级 别 (条 件 、 要 求 )的 关 系模 式v范 式 种 类u1NF, 2NF, 3NF, BCNF, 4NF,5NFu按 级 别 (条 件 、 要 求 )由 低 到 高 ：1NF 2NF 3NF BCNF 4NF 5NFv通 常 称 某 一 关 系 模 式 R为 第 几 范 式 ， 记 作R xNF 1NF(First Normal Form)v定 义 ： 关 系 R中 每 个 分 量 都 是 不 可 分 割 的数 据 项 ， 则 R 1NFv说 明 ： 1NF是 关 系 模 式 的 基 本 要 求v举 例 ：关 系 模 式 S-L-C(学 号 SNO, 系 SDEPT, 住 处 SLOC, 课 程 CNO, 成 绩 G)是 1NF 5.2.4 2NFv定 义 ： 若 R 1NF, 且 每 个 非 主 属 性 完 全 依 赖 于 码 ， 则 R 2NFv说 明 ： 不 存 在 非 主 属 性 部 分 依 赖 于 码 的 关 系 为 2NFv举 例 ： 关 系 模 式 S-L-C(SNO, SDEPT, SLOC, CNO, G)u函 数 依 赖 图G SNOCNO SDEPTSLOC关 系 模 式 S-L-C是 不 是 2NF？不 是 ， 因 为 SDEPT和 SLOC部 分 依 赖 于 码 前 面 的 实 例 是 不 是 2NF？ 不是2NF可能出现的问题v插 入 异 常u某 学 生 没 有 选 课 时 ， 无 法 插 入 其 系 、 住 处 等 信 息v删 除 异 常u某 学 生 所 有 的 选 课 信 息 都 删 除 后 ， 其 系 、 住 处 等 信息 也 被 删 除v修 改 复 杂 （ 更 新 异 常 ）u学 生 转 系 时 ， 除 了 修 改 其 系 名 外 ， 还 需 修 改 其 住 处信 息 ； 另 外 ， 若 该 学 生 选 修 了 多 门 课 程 ， 则 其 对 应的 重 复 存 储 的 系 、 住 处 等 信 息 需 一 一 修 改v冗 余 u同 系 的 所 有 学 生 的 住 处 信 息 重 复 存 储 ， 同 一 学 生 选多 门 课 程 时 ， 其 系 、 住 处 信 息 重 复 存 储 解决办法v模 式 分 解u依 赖 关 系 分 析u上 例 中 的 模 式 分 解 为 下 列 两 个 模 式 ， 该 模 式 是 2NFSC(SNO, CNO, G) (SNO, CNO)GS-L(SNO, SDEPT, SLOC) SNO SDEPT, SNO SLOC, SDEPT SLOCG SNOCNO SDEPTSLOC 分解说明v一 个 1NF， 但 非 2NF的 关 系 总 是 可 以 被 分 解 成 为一 组 2NF的 关 系v规 范 化 过 程 中 通 过 一 组 投 影 运 算 消 除 部 分 依 赖 ，建 议 作 如 下 分 解 (第 一 步 分 解 )u已 知 关 系 R(A,B,C,D), (A,B)为 主 码 ， 即 (A,B)-C, (A,B)-D，且 A-D, 则 将 R分 解 成 为 两 个 投 影 :R1(A,D), A为 主 码R2(A,B,C), (A,B)为 主 码 ， A为 外 码 u 这 样 ， R可 以 通 过 R1和 R2的 自 然 连 接 运 算 得 以 恢 复 ，即 满 足 分 解 的 无 损 连 接 性 5.2.5 3NFv定 义 ： 若 R2NF, 且 它 的 任 何 一 个 非 主 属 性 都 不传 递 依 赖 于 任 何 候 选 码 ， 则 R 3NFv说 明 ： 即 不 存 在 非 主 属 性 部 分 依 赖 和 传 递 依 赖于 码 的 关 系 为 3NFv推 论 ： 不 存 在 非 主 属 性 的 模 式 为 3NFv上 例 中 得 到 的 关 系 模 式 是 2NF SC(SNO, CNO, G); S-L(SNO, SDEPT, SLOC);S-L中 存 在 传 递 传 递 依 赖 ， 故 该 模 式 不 是 3NFSNO SDEPT SLOC可 能 问 题 ？如 何 改 造 ？ 不是3NF可能存在的问题v插 入 异 常u只 有 当 知 道 某 学 生 的 系 时 才 能 插 入 其 住 处 信 息v删 除 异 常u当 删 除 某 系 对 应 的 所 有 学 生 时 ， 有 关 该 系 学 生 住 处 的信 息 也 被 删 除 掉 了v修 改 异 常u一 个 系 及 其 住 处 信 息 重 复 出 现 ， 只 更 新 一 个 元 组 中 对应 的 系 及 其 住 处 时 可 能 导 致 数 据 不 一 致v冗 余 u同 系 学 生 的 住 处 重 复 存 储 解决方法v继 续 模 式 分 解u如 上 例 中 的 模 式 可 分 解 为 3NFSC(SNO, CNO, G); (SNO, CNO) G S-D(SNO, SDEPT); SNO SDEPT D-L(SDEPT, SLOC); SDEPT SLOCSNO SDEPTSLOCSDEPTG SNOCNO 分解说明v一 个 2NF， 但 非 3NF的 关 系 总 是 可 以 被 分 解 成 为一 组 3NF的 关 系v规 范 化 过 程 中 通 过 一 组 投 影 运 算 消 除 传 递 依 赖 ，建 议 作 如 下 分 解 (第 二 步 分 解 )u已 知 关 系 R(A,B,C), A为 主 码 (A-B, A-C)， 且 B-C,则 将 R分 解 成 为 两 个 投 影 :R1(B,C), B为 主 码R2(A,B), A为 主 码 ， B为 外 码 u 这 样 ， R可 以 通 过 R1和 R2的 自 然 连 接 运 算 得 以 恢 复 ，分 解 满 足 分 解 的 无 损 连 接 性 3NF的进一步说明v在 不 考 虑 主 属 性 对 码 的 部 分 依 赖 和 传 递 依 赖 时 ，可 以 认 为 是 实 现 了 彻 底 的 分 离 ， 已 消 除 了 插 入异 常 ， 删 除 异 常 ， 修 改 异 常 ， 冗 余 等 问 题v但 是 ， 当 关 系 中 存 在 两 个 或 更 多 的 候 选 码 时 ，尤 其 是 有 几 个 候 选 码 、 且 候 选 码 内 的 属 性 又 有部 分 复 合 或 交 迭 时 ， 仅 仅 满 足 3NF仍 有 问 题 ，需 要 进 一 步 分 解 成 BCNF 5.2.6 BCNF(Boyce/Codd Normal Form)v定 义 ： 若 每 一 个 决 定 因 素 都 包 含 (或 是 )码 ， 则 R BCNFv说 明uBCNF中 所 有 的 依 赖 都 是 包 含 码 的 依 赖u一 个 BCNF范 式 必 是 3NF， 但 一 个 3NF范 式 不 一 定 是BCNF (3NF中 可 能 存 在 主 属 性 对 码 的 部 分 和 传 递 依 赖 )uBCNF是 在 函 数 依 赖 范 畴 内 对 关 系 模 式 的 彻 底 分 离 ， 已消 除 了 插 入 和 删 除 异 常 u通 常 认 为 BCNF是 扩 充 的 第 三 范 式 ， 一 般 数 据 库 设 计 达到 BCNF已 足 够 实例v例 1: SJP(学 生 S, 课 程 J, 名 次 P)u(S,J)和 (J,P) 均 为 候 选 码u函 数 依 赖 为 (S,J)P, (J,P) S其 中 ， 两 个 决 定 因 素 均 包 含 (是 )候 选 码可 见 SJP BCNFv例 2: STJ(学 生 S, 教 师 T, 课 程 J)u (S,T)和 (S,J) 均 为 候 选 码 u函 数 依 赖 为 (S,J) T, (S,T) J, T J其 中 ， T为 决 定 因 素 ， 但 不 包 含 任 何 一 个 候 选 码可 见 STJ 3NF, 但 STJ BCNF 例子v前 例 是 3NF, 也 是 BCNFSC(SNO, CNO, G); (SNO, CNO) GS-D(SNO, SDEPT); SNO SDEPTD-L(SDEPT, SLOC); SDEPT SLOCSNO SDEPTSLOCSDEPTG SNOCNO 5.2.7 多值依赖v属 于 BCNF的 关 系 模 式 是 不 是 很 完 美 了 呢 ？v教 材 P178例 子v存 在 问 题 ？v如 何 解 决 ？ 5.2.8 4NFv4NF就 是 限 制 关 系 模 式 的 属 性 之 间 不 允 许 有 非平 凡 且 非 函 数 依 赖 的 多 值 依 赖v如 果 一 个 关 系 模 式 是 4NF， 必 定 为 BCNFv一 个 关 系 模 式 是 BCNF， 但 不 是 4NF， 依 然 有 不好 的 性 质 ， 可 以 用 投 影 分 解 的 办 法 解 决v例 ： WSC(仓 库 W, 保 管 员 S, 商 品 C)u全 码 (W,S,C) u存 在 多 值 依 赖 WS, WC， WSC 4NF可 进 一 步 分 解 使 之 满 足 4NF: WS(W,S), WC(W,C)v4NF是 多 值 依 赖 范 畴 内 最 高 程 度 的 规 范 化 5.2.9 规范化理论v规 范 化u概 念 ： 将 一 个 低 一 级 范 式 的 关 系 模 式 分 解 为若 干 个 高 一 级 范 式 的 关 系 模 式 的 过 程u目 的 ： 设 计 正 确 、 良 好 的 关 系 模 式u基 本 思 想 ： 逐 步 消 除 关 系 模 式 的 数 据 依 赖 中不 合 适 的 部 分 ， 使 模 式 达 到 一 定 程 度 的 分 离 ，但 又 不 丢 失 原 模 式 中 的 信 息u模 式 分 解 的 实 质 ： 投 影 几个事实v模 式 分 解 可 以 消 除 冗 余 ， 解 决 更 新 异 常 等 问 题 ，但 也 要 付 出 做 连 接 运 算 等 昂 贵 的 代 价v需 要 强 调 的 是 ： 对 已 知 关 系 模 式 的 范 式 等 级 是语 义 上 的 ， 而 不 仅 仅 是 看 某 个 时 刻 关 系 中 的 数据 值 ， 必 须 考 察 数 据 间 的 依 赖v即 便 是 知 道 了 数 据 依 赖 ， 也 不 能 证 明 一 个 关 系是 否 3NF。 我 们 只 能 首 先 假 设 这 个 关 系 是 3NF，而 去 验 证 给 出 的 关 系 中 没 有 违 反 数 据 依 赖 的 情形 规范化理论v如 何 辨 别 一 个 关 系 模 式 的 “ 好 坏 ” ？u不 存 在 部 分 和 传 递 函 数 依 赖 等 “ 不 好 ” 的 性 质 的 模式 是 “ 好 ” 模 式 ， 否 则 会 出 现 冗 余 和 插 入 、 删 除 、更 新 等 异 常 现 象v规 范 化 过 程 是 用 于 设 计 好 的 数 据 库 的 有 力 辅 助 ，但 并 不 是 唯 一 的 方 法v 最 初 的 设 计 中 尽 量 做 到 “ 概 念 单 一 化 ” ， 即 做到 让 一 个 关 系 描 述 一 个 概 念 、 一 个 实 体 或 实 体间 的 一 种 联 系 ， 这 样 所 设 计 的 关 系 模 式 将 会 接近 或 达 到 第 三 范 式 ， 甚 至 达 到 BCNF 规范化过程小结1NF2NF3NFBCNF4NF 消 除 非 主 属 性 对 码 的 部 分 函 数 依 赖消 除 非 主 属 性 对 码 的 传 递 函 数 依 赖消 除 主 属 性 对 码 的 部 分 和 传 递 函 数 依 赖消 除 多 值 依 赖 练习一v设 计 关 于 供 应 商 供 应 零 件 的 数 据 库 ， 要 求 达 到 3NFv最 初 的 设 计 ：R(S#, Sname, City, Status, P#, Pname, Color, Weight, QTY)u主 码 ： (S#, P#)u函 数 依 赖 ：S#Sname, S# Status, S# City, City Status, P# Pname, P# Color, P# Weight v可 见 ， 其 中 有 部 分 依 赖 ， 还 有 传 递 依 赖 。 该 模 式 仅 为1NF 分解第 一 步 分 解 ， 消 除 部 分 依 赖 ， 得 到 ：R1(S#, P#, QTY)， (S#, P#)为 码R2(S#, Sname, City, Status)， S#为 码R3(P#, Pname, Color, Weight)， P#为 码其 中 ， R1和 R3都 已 达 到 3NF， 但 R2还 存 在 传 递 依 赖 ，仅 仅 是 2NF第 二 步 分 解 ， 消 除 R2中 的 传 递 依 赖 ， 得 到 ：R2-1(S#, Sname, City)， S#为 码R2-2(City, Status)， City为 码这 样 ， R1, R2-1, R2-2和 R3就 是 达 到 3NF的 关 系 模 式 。 此 例 中 也 已 达 到 BCNF 练习二设 计 订 货 系 统 的 数 据 库 ， 包 括 顾 客 、 货 物 和 订 货 单 信 息v初 模 式 ：顾 客 (顾 客 号 ， 收 货 地 址 ， 赊 购 限 额 ， 余 额 ， 折 扣 )货 物 (货 物 号 ， 制 造 厂 商 ， 实 际 存 货 量 ， 规 定 的 最 低 存 货 量 ， 货 物 描 述 )订 货 单 (订 货 单 号 ， 顾 客 号 ， 货 物 号 ， 订 货 数 量 ， 订 货 细 则 ， 未 发 数 量 ， 订 货 日 期 ， 经 办 人 )问 题 分 析 ：v 顾 客 模 式 中 ， 顾 客 号 不 能 唯 一 决 定 收 货 地 址v 货 物 模 式 中 ， 货 物 描 述 部 分 依 赖 于 码v 订 货 单 模 式 中 ， 未 发 数 量 将 随 发 货 过 程 更 新 ， 而 其 他 信 息 相 对 静态 ； v 订 货 细 则 有 多 条 改进模式q顾 客 及 其 地 址 (顾 客 号 ， 收 货 地 址 )q顾 客 及 其 余 额 (顾 客 号 ， 赊 购 限 额 ， 余 额 ， 折 扣 )q货 物 及 其 厂 商 (货 物 号 ， 制 造 厂 商 ， 实 际 存 货 量 ， 规 定的 最 低 存 货 量 )q货 物 及 其 描 述 -2(货 物 号 ， 货 物 描 述 )q订 货 单 (订 货 单 号 ， 顾 客 号 ， 货 物 号 ， 订 货 数 量 ， 订 货日 期 ， 经 办 人 )q发 货 (订 货 单 号 ， 未 发 货 量 )q发 货 (订 货 单 号 ， 订 货 细 则 ) 练习三欲 设 计 移 动 公 司 手 机 信 息 管 理 系 统 ， 用 于 管 理 ： 1、 手 机 销 售 信 息 （ 由 营 业 厅 售 给 用 户 ） 2、 手 机 用 户 档 案 信 息 （ 用 户 名 ， 证 件 号 码 等 ） 3、 手 机 通 话 信 息 （ 每 一 次 通 话 的 详 细 情 况 ） 4、 手 机 话 费 信 息 （ 每 月 的 话 费 组 成 ）在 此 基 础 上 实 现 常 用 的 查 询 ， 如 ： 1、 每 月 手 机 的 销 售 情 况 2、 每 种 机 型 的 销 售 情 况 3、 每 个 营 业 厅 的 手 机 销 售 情 况 4、 根 据 手 机 号 码 查 询 其 用 户 信 息 5、 根 据 手 机 号 码 查 询 某 时 间 段 内 的 通 话 情 况 6、 每 月 手 机 话 费 收 入 7、 欠 费 用 户 查 询 试 设 计 合 适 的 数 据 库 ， 并 在 此 基 础 上 用 SQL实 现 所 有 的 查 询 设计结果q营 业 厅 (营 业 厅 编 号 ， 地 址 ， 负 责 人 )q销 售 记 录 (营 业 厅 编 号 ， 机 型 ， 数 量 ， 日 期 ， 经 办 人 )q手 机 销 售 单 价 (机 型 ， 单 价 )q手 机 用 户 信 息 (手 机 号 码 ， 用 户 名 ， 住 址 ， 证 件 号 码 )q手 机 通 话 记 录 (手 机 号 码 ， 被 叫 号 码 ， 日 期 ， 起 始 时 刻 ，通 话 时 长 )q手 机 话 费 信 息 (手 机 号 码 ， 话 费 ， 漫 游 费 ， 短 信 费 )q话 费 缴 费 信 息 (手 机 号 码 ， 缴 费 日 期 ， 金 额 ， 缴 费 营 业厅 ) 定义回顾：函数依赖v设 R(U)是 属 性 集 U上 的 关 系 模 式 ， X,Y是 U的 子 集 。 若 对 于 R(U)的 任 意 一 个 可 能 的 关系 r， r中 不 可 能 存 在 两 个 元 组 在 X上 的 属性 值 相 等 ， 而 在 Y上 的 属 性 值 不 等 ， 则 称X函 数 确 定 Y或 Y函 数 依 赖 于 X， 记 作 XY 5.3 Armstrong公理系统v定 义 ： 逻 辑 蕴 涵u对 于 满 足 一 组 函 数 依 赖 F的 关 系 模 式 R，其 任 何 一 个 关 系 r， 若 函 数 依 赖 XY都 成 立 ，则 称 F逻 辑 蕴 含 X YvArmstrong公 理 系 统 是 函 数 依 赖 的 一 个 有 效而 完 备 的 公 理 系 统u可 用 于 从 一 组 函 数 依 赖 F求 得 蕴 含 (导 出 )的 函数 依 赖u可 用 于 求 得 关 系 模 式 的 码 Armstrong公理系统vArmstrong公 理 系 统uA1自 反 律 ：uA2增 广 律 ：uA3传 递 律 ：vArmstrong公 理 系 统 的 推 理 规 则u合 并 规 则 :u伪 传 递 规 则 : u分 解 规 则 :v引 理 5.1 (由 合 并 规 则 和 分 解 规 则 可 得 )所 蕴 含为则若 FYXUXY , 所 蕴 含为则且所 蕴 含为若 FYZXZUZFYX , 所 蕴 含为则所 蕴 含为及若 FZXFZYYX ,YZXZXYX 有，由 , ZXWZWYYX 有，由 , ZXYZYX 有及由 , ),.2,1(.21 kiAXAAAX iK 成 立成 立 的 充 分 必 要 条 件 是 Armstrong公理系统v定 义 ： 闭 包u在 关 系 模 式 R中 为 F所 逻 辑 蕴 含 的 函 数 依 赖 的 全体 叫 做 F的 闭 包 ， 记 为 F+vArmstrong公 理 系 统 是 有 效 的 、 完 备 的uArmstrong公 理 系 统 的 有 效 性t由 F出 发 根 据 Armstrong公 理 导 出 的 每 一 个 函 数 依 赖一 定 在 F +中uArmstrong公 理 系 统 的 完 备 性tF+中 的 每 一 个 函 数 依 赖 ， 必 定 可 以 由 F出 发 根 据Armstrong公 理 导 出 或 导 出怎 样 计 算 F+?怎 样 判 断 一 个 函 数 依 赖 一 定 在 闭 包 中 ？ 定义v设 F为 属 性 集 U上 的 一 组 函 数 依 赖 ， XU， X+FAX A能 由 Armstrong公 理 导 出 , X+F称 为 属性 集 X关 于 函 数 依 赖 F的 闭 包v引 理 2： 设 F为 属 性 集 U上 的 一 组 函 数 依 赖 ，X,YU， X Y能 根 据 Armstrong公 理 导 出 的 充 分必 要 条 件 是 Y X +F说 明 ： 如 果 X+F中 含 有 Y， 则 F逻 辑 蕴 含 XY 也 是 用 于 判 定 XY能 否 由 F根 据 Armstrong公 理 导 出 的 算 法 算法：求属性集X关于函数依赖集F的闭包X+F步， 返 回 第） 若 否 ， 则（ 算 法 终 止就 是， 则） 若 相 等 或（ 吗 ？判 断 中 未 出 现 过 的 属 性 集找 出 并子 集 的 函 数 依 赖是中 寻 找 尚 未 用 过 的 左 边即 在 这 里求令 )2(16 ,5)4( )3( ,),)()(|,)2( 0,)1( )()( )()1( )()1( )( )( )0( ii XXUXXX XBX BW WVXF WAXVFWVWVABB iXX Fii ii ii i i, , , , , , , , , , , , ( )FR U F U A B C D EF AB C B D C E EC B AC B AB 例 1： 已 知 求ABCDEAB EBABCDXCDABXABX F )( , )2()1()0(故 FBD AGCEBACDBDCGDBC CBEACEGDCABF GEDCBAR )( , , ),(求已 知 0123( ) ,( ) ,( ) ,( ),( ) FBD BDBD BD EGBD BDEG CBD BDEGC ADBGBD BDEGCA ，结 束 例2 练习v假 设 关 系 模 式 为 R(A,B,C,D), F=AB,B C,B D， 求 蕴 含 于 给 定 函 数 依 赖 的 所 有 非 平 凡 函 数依 赖 。v求 解 方 法 ： 求 所 有 属 性 组 合 的 闭 包 ， 从 中 找 出新 的 非 平 凡 依 赖 。 如 ：1) A+=ABCD,B+=BCD,C+=C, D+=D， 则 有 新 的 非 平 凡 依 赖为 A C, A D2) 两 个 属 性 的 排 列 组 合 ， 8种 新 的 ：AB C, AB D, AC B, AC D, AD B, AD C, BC D, BD C3） 三 个 属 性 的 排 列 组 合 ， 2种 新 的 ： ABC D, ABD C 4） ABCD+=ABCD， 无 定义v如 果 G+=F+， 就 说 函 数 依 赖 集 F覆 盖 G,或 F与 G等 价v引 理 3： FGGFGF ,的 充 分 必 要 条 件 是 GXY YXFGF是 否 属 于考 察 中 的 函 数 依 赖只 需 逐 一 对若 要 判 定 , 用 于 判 定 F与 G是 否 等 价 的 算 法 定义v如 果 函 数 依 赖 集 F满 足 下 列 条 件 ， 则 称 F为 一 个 极 小 函 数 依赖 集 ， 或 称 最 小 依 赖 集v性 质 ： 函 数 依 赖 集 F的 最 小 函 数 依 赖 集 不 一 定 唯 一 ， 它 与求 解 的 次 序 有 关v定 理 ： 每 一 个 函 数 依 赖 集 F均 等 价 于 一 个 最 小 依 赖 集 F m等 价与使 得真 子 集 有赖中 不 存 在 这 样 的 函 数 依等 价与 使 得赖中 不 存 在 这 样 的 函 数 依 仅 含 一 个 属 性中 任 一 函 数 依 赖 的 右 部 FAZAXFZ XAXF AXFF AXFF ,)3( ,)2( )1( 这 样 ， R可 以 用 R来 取 代 算法：求函数依赖F的最小依赖集F多 余 ， 否 则 不 多 余， 若 包 含 则 表 示是 否 包 含察 是 否 多 余 ， 即 考看是 非 单 属 性 的 依 赖 ， 如 中 左 边的 属 性 ： 逐 个 检 查去 掉 各 依 赖 左 边 的 多 余 否 则 不 去 掉若 是 则 去 掉包 含 是 否看， 在 剩 下 的 依 赖 中 求如掉 它 个 依 赖 开 始 ， 去中 多 余 的 依 赖 ： 从 第 一去 掉 右 边 均 改 为 单 属 性 依 赖用 分 解 规 则 将 所 有 依 赖 YAX YAXY FYXY XXYXF ,)3( , ,)()2( )1( 例子1） 考 查 AB， 去 掉 它 ， 计 算 A+=AC， 不 包 含 B， 不 能 去 掉2） 考 查 B A， 去 掉 它 ， 计 算 B B C A， 包 含 A， 可 去掉 它3） 考 查 B C， 去 掉 它 ， 计 算 B B， 不 包 含 C， 不 能 去 掉4） 考 查 A C， 去 掉 它 ， 计 算 B A B C， 包 含 C， 可 去掉 它5） 考 查 C A， 去 掉 它 ， 计 算 C C， 不 包 含 A， 不 能 去 掉的 最 小 函 数 依 赖 集求 , ACCACBABBAF , ,21 ACCAABBAF ACCBBAF 1 2 3 4 5 , , ),( FAGCEBACDBDCGDBC CBEACEGDCABF GEDCBAR 求已 知 , , , ,1 , , GCEBACDDCGDBCCBE ACGDEDCABF GCEBACDDCGDBCCBE ACGDEDCABF AGCEBACDBDCGDBC CBEACEGDCABF 检 查 左 边 非 单 属 性去 掉 多 余 依 赖其它例子 5.4 模式的分解v分 解 的 目 的u解 决 冗 余 和 异 常 ， 提 高 范 式 等 级v分 解 的 概 念u用 原 关 系 模 式 的 若 干 个 投 影 构 成 新 的 关 系 模式 ， 即 UUUU RRUUU URURURUR K KK KK . ,.,., )(),.,(),()( 21 11 2211 的 属 性 集 合 ，的 子 集 ， 分 别 是都 是 ， 其 中 ：分 解 关系模式分解应满足的特性v无 损 连 接 性 (Lossless join)v保 持 函 数 依 赖 性 (Preserve dependency)v相 互 独 立 性 u 分 解 后 的 关 系 模 式 中 ， 当 修 改 某 一 个 关 系 数 据 时 ， 不 会 影 响 其 他关 系为 无 损 连 接 分 解（则 分 解 自 然 连 接 即 可 还 原若 ),., )(,. 22211121 KKKK FURFURFUR RRRR 具 有 保 持 函 数 依 赖 性则 称 ，即 两 者 的 闭 包 相 等的 函 数 依 赖 集若 ，（ 的 一 个 分 解 为设 等 价 )(,. ),., 11 222111 K KKK FFFFR FURFURFUR FUR 例子分析v设 S-C-M（ 学 号 ， 班 级 ， 班 主 任 ）F=学 号 班 级 ， 班 级 班 主 任 ， 学 号 班 主 任12 3 S M 具 有 无 损 连 接 性 和 保 持 函 数 依 赖 性 ， 且 关 系 相 互 独 立具 有 无 损 连 接 性 ， 但 不 具 有 保 持 函 数 依 赖 性 且 关 系 相 互 不 独 立（ 如 当 某 学 生 换 班 时 ， 须 更 新 中 的 该 学 号 对 应 的 班 主 任 信 息 ）不 具 有 无 损 连 接 性 和 保 持 函 数 依 赖 性 ， 但 关 系 相 互 独 立（ 如 果 一 个 老 师 是 多 个 班 的 班 主 任 时 ， 无 法 得 知 某 个 学 生 的 班 级 ）存 在 传 递 依 赖 ， 为 2NF1 ( ) ( )2 ( ) ( )3 ( ) ( )S C C MS C S MS M C M 学 号 ， 班 级 ， 班 级 ， 班 主 任学 号 ， 班 级 ， 学 号 ， 班 主 任学 号 ， 班 主 任 ， 班 级 ， 班 主 任有 三 种 分 解 ：该 关 系 属 于 几 范 式 ？范 式 ？ 3NF三 种 特 性 ?问 题 ： 如 何 用 理 论 的 方 法 求 得 关 系 模 式 的 最 优 分 解 呢 ？ 例子v教 材 P188， 例 4 算法：检验一个分解是否具有无损连接性1 2 1 2, , , ,. , , ,. (1) , ,(2) , , n Ki jj i j ij jj mj R U F U A A A R R Rk n i R j AA R i j a bFF X Y XY aa b m 设 构 造 一 个 行 列 的 表 ， 第 行 代 表 ， 第 列 代 表若 则 在 第 行 第 列 上 放 置 符 号 否 则 放 置逐 个 检 查 中 每 一 个 函 数 依 赖 ， 并 修 改 元 素 ， 方 法 是 ：取 中 一 函 数 依 赖 找 出 所 对 应 的 列 中 具 有 相 同 符号 的 行 ， 考 察 这 些 行 中 列 的 元 素 ， 若 其 中 有 则 全 部改 为 否 则 全 部 改 ， 其 中 是 这 些 行 的 1 2(3) (2) , ,., ,ka a a 行 号 最 小 值 。反 复 ， 直 至 某 行 出 现 则 表 示 具 有 无 损 连接 性 ； 若 检 验 完 所 有 函 数 依 赖 都 没 有 出 现 这 样 的 行 ， 则表 示 不 具 有 无 损 连 接 性 无 损 连 接 性 。验 证 该 分 解 是 否 具 有的 一 个 分 解 为已 知 : ),(3),(2),(1: , , EDRDCRCBARR EDDCCABF EDCBAUFUR A B C D Ea1 a2 a3 b14 b15b21 b22 a3 a4 b25b31 b32 b33 a4 a5A B C D Ea1 a2 a3 a4 a5b21 b22 a3 a4 a5b31 b32 b33 a4 a5初 始 表 ：最 后 结 果 ： R1R2R3R1R2R3 1 22例子：判断无损连接性 无 损 连 接 性 。验 证 该 分 解 是 否 具 有的 一 个 分 解 为已 知 : ),(3),(2),(1: , , EDRDCRCBARR EDDCCABF EDCBAUFUR A B C D Ea1 a2 a3a3 a4a4 a5A B C D Ea1 a2 a3 a4 a5a3 a4 a5a4 a5初 始 表 ：最 后 结 果 ： R1R2R3R1R2R3 1 22简易方法：只画关注数据 例子vR(A,B,C), F=AB, C Bu分 解 1=(A,B) AB, (A,C)u分 解 2=(A,B) AB, (B,C) CBv分 析 两 种 分 解 的 无 损 连 接 性 ？u分 解 1只 具 有 无 损 连 接 性 , 分 解 2不 具 有 无 损 连 接 性A B Ca1 a2 a1 a3ABAC a2A B Ca1 a2a2 a3ABBC 算法：检验一个分解是否具有保持函数依赖性依 赖 性 具 有 保 持 函 数价 的 ， 即前 后 的 函 数 依 赖 集 是 等 解若 两 者 相 等 ， 则 表 示 分和分 别 求 解 ，（ 的 一 个 分 解 为设 ,)( ),., 1 222111 iki KKKFF FURFURFUR FUR 例子vR(A,B,C), F=AB, C Bu分 解 1=(A,B) AB, (A,C) u分 解 2=(A,B) AB), (B,C) C Bv分 析 两 种 分 解 的 依 赖 保 持 性 ？u分 解 1： 只 有 AB， 显 然 ， 分 解 1不 具 有 依 赖 保 持 性u分 解 2： 保 留 了 所 有 函 数 依 赖 ， 具 有 依 赖 保 持 性 简单练习：判定无损连接性和函数依赖性v设 S-C-M（ S学 号 ， C班 级 ， M班 主 任 ）F=S学 号 C班 级 ， C班 级 M班 主 任 ， S学 号 M班 主 任 1 23 具 有 无 损 连 接 性 和 保 持 函 数 依 赖 性具 有 无 损 连 接 性 ， 但 不 具 有 保 持 函 数 依 赖 性不 具 有 无 损 连 接 性 和 保 持 函 数 依 赖 性1 ( ) ( )2 ( ) ( )3 ( ) ( )S C C MS C S MS M C M 学 号 ， 班 级 ， 班 级 ， 班 主 任学 号 ， 班 级 ， 学 号 ， 班 主 任学 号 ， 班 主 任 ， 班 级 ， 班 主 任 几个命题v一 个 无 损 连 接 的 分 解 不 一 定 具 有 依 赖 保 持 性 ，反 之 亦 然v若 要 求 模 式 分 解 保 持 函 数 依 赖 ， 则 模 式 分 离 总能 达 到 3NF， 但 不 一 定 能 达 到 BCNFv若 要 求 分 解 既 保 持 函 数 依 赖 ， 又 具 有 无 损 连 接性 ， 则 模 式 分 离 可 以 达 到 3NF， 但 不 一 定 能 达 到BCNFv若 要 求 分 解 具 有 无 损 连 接 性 ， 则 模 式 分 离 一 定可 以 达 到 4NF 求解关系模式的候选码v属 性 分 类uL类 ： 只 出 现 在 函 数 依 赖 的 左 边 的 属 性uR类 ： 只 出 现 在 函 数 依 赖 的 右 边 的 属 性uN类 ： 在 函 数 依 赖 的 两 边 均 未 出 现 的 属 性uLR类 ： 出 现 在 函 数 依 赖 的 两 边 的 属 性v函 数 依 赖 图 FDGu用 有 向 图 表 示 的 函 数 依 赖 ， 如X Y 即 X Y 快速求解候选码的充分条件v对 于 给 定 的 关 系 模 式 R及 其 函 数 依 赖 集 Fu如 果 X是 L或 N类 属 性 ， 则 X必 为 R的 任 一 候 选码 的 成 员u如 果 X是 R类 属 性 ， 则 X必 不 在 任 何 候 选 码 中u如 果 X是 L和 N类 组 成 的 属 性 组 ， 且 X+包 含 了全 部 属 性 ， 则 X是 R的 唯 一 候 选 码 算法：对左边为单属性的函数依赖集求所有候选码 (1) 求 F的 最 小 依 赖 集 F(2) 作 出 函 数 依 赖 图 FDG(3) 从 FDG图 中 找 出 无 入 边 的 属 性 集 X(4) 察 看 FDG图 中 有 无 回 路 ， 若 无 ， 则 输 出 X并 结 束 ,否 则进 行 下 一 步(5) 从 各 独 立 回 路 中 各 取 一 个 结 点 的 属 性 与 X组 成 一 个 候 选码 ， 重 复 取 得 所 有 可 能 的 组 合 ， 即 R的 全 部 候 选 码 单 属 性 下 求 解 候 选 码 的 充 要 条 件 和 所 有 的 候 选 码求已 知 ,),(F WXZWYZWYXWYYWFXYWZR 和 所 有 的 候 选 码求已 知 ,),(F IQQOOBBIDSFSDBIOQR 和 所 有 的 候 选 码求已 知 ,),(F DSQIOBBIFIBOQSDR ZX WZYXWYYWF唯 一 的 候 选 码 为 , SQSOSBSIFF ,候 选 码 为 ISFF候 选 码 为, Z WYXS DI B O QI B OQ S D 算法：对左边为多属性的函数依赖集求所有候选码 (1) 将 R所 有 属 性 分 为 L,R,N,LR四 类 ， 并 令 X代 表 L,N两 类 ，令 Y代 表 LR类(2) 求 X+， 若 X+包 含 R全 部 属 性 ， 则 X即 为 R的 唯 一 候 选 码 ，结 束 ， 否 则 转 下 一 步(3) 在 Y中 取 一 属 性 A， 求 (XA)+,若 它 包 含 R的 全 部 属 性 ， 则转 下 一 步 ， 否 则 换 一 个 属 性 重 试 ， 直 至 试 完 所 有 Y中 的属 性(4) 若 已 找 出 所 有 候 选 码 ， 则 结 束 ， 否 则 在 Y中 依 次 取 两 个 、三 个 、 ， 求 它 们 的 属 性 闭 包 ， 直 至 其 闭 包 包 含 R的 全 部 属 性 多 属 性 下 求 解 候 选 码 的 充 分 条 件 的 所 有 候 选 码求已 知F AGCEBACDBDCGDBC CBEACEGDCABF GEDCBAR , , ),( 使 用 ， 需 要 其 他 解 法 。类 属 性 ， 故 该 算 法 不 能和没 有 可 知根 据 已 经 求 得 的NL GCEBACDDCGDBCCBE ACGDEDCABF , , 唯 一 的 候 选 码 。为， 故且即 。类 属 性 包 括和类 属 性 包 括其 中 ： RECECDBAECECX BDALRCENL FF )(, , ,所 有 的 候 选 码求已 知F ADCDBCBDDEDAFABCDER ,),( 算法：求R的保持函数依赖的3NF分解结 束都 构 成 一 个 关 系中 每 一 个对 中 分 离 出 去并 从则 它 们 构 成 一 个 关 系 ， 右 边 都 无 关 ，所 有 函 数 依 赖 的 左 边 和中 某 些 属 性 与若 结 束则且中 有 一 个 函 数 依 赖若 的 最 小 函 数 依 赖 集求 ,)4( )3( ,)2( )1( iiiii AXRAXF RFR RRXAAXF FF 算法：求R的无损连接且保持函数依赖的3NF分解的 分 解性 又 有 保 持 函 数 依 赖 性就 是 一 个 既 有 无 损 连 接 ， 即的 候 选 关 键 字再 加 上 一 个 分 解的 保 持 函 数 依 赖 的先 求 得 ,., ,.,3 21 21 XRRRXR RRRNFR K K 分 解保 持 函 数 依 赖 的 性 和分 解 ， 和 具 有 无 损 连 接赖 的， 候 选 码 ， 保 持 函 数 依求已 知 NF NFF ADCDBCBDDEDAFABCDER 3 3 ,),( 分 解 。数 依 赖 性 的 函为 具 有 无 损 连 接 且 保 持，因 此 ， 唯 一 的 候 选 码 。为， 故且即 。类 属 性 包 括和类 属 性 包 括另 外 ， 分 解 。为 保 持 函 数 依 赖 性 的，首 先 ， NF ECDCABCDDBEDAD RECECDBAECECX BDALRCENL NFDCABCDDBEDAD FF 3 , )(, , 3, 分 解依 赖 的的 无 损 连 接 且 保 持 函 数求已 知 NFR OBQISBIDSFBDQSIOR 3 ,),( 分 解 。且 保 持 函 数 依 赖 的 的 无 损 连 接即 为的 基 础 上 增 加为 唯 一 的 候 选 码 。 在故 包 含 所 有 属 性且类 属 性 为中另 外 ， 分 解的 保 持 函 数 依 赖 的故 可 得求 得 NF RISIS ISDBOQISSINLF BOISQIBSDNFR OBQISBIDSFF 3 ,)(, ,3 , 作业vP196 习 题 1， 2， 9， 12v思 考 ： 10， 11， 自 由 选 做