数据库原理及应用教案

数 据 库 原 理 及 应 用 教 案河北化工医药职业技术学院 第 2章 关 系 数 据 库n 2.1 关 系 数 据 库 与 关 系 模 型n 2.2 关 系 的 形 式 定 义n 2.3 关 系 运 算 代 数n 2.4 查 询 优 化n 2.5 关 系 数 据 库 的 规 范 化 理 论 2.1关 系 数 据 库 与 关 系 模 型2.1.1 基 本 概 念n 1 关 系 数 据 库 系 统n 关 系 数 据 库 系 统 是 支 持 关 系 数 据 模 型 的 数 据 库系 统 。 关 系 数 据 库 应 用 数 学 方 法 来 处 理 数 据 库中 的 数 据 。n 关 系 模 型 由 关 系 数 据 结 构 、 关 系 操 作 集 合 和 关系 完 整 性 约 束 三 部 分 组 成 。 n 关 系 数 据 库 管 理 系 统 RDBMS如 著 名 的 IBM DB2，Oracle， Ingres， SYBASE， Informix等 。 2 关 系 的 相 关 名 词n 域 ： 域 是 一 组 具 有 相 同 数 据 类 型 的 值 的 集 合 。n 一 般 在 关 系 数 据 模 型 中 ， 对 域 还 加 了 一 个 限 制 ，所 有 的 域 都 应 是 原 子 数 据 （ atomic data） 。n 目 或 度 （ Degree） ： 设 有 关 系 R(D1，D2， Dn )， 这 里 的 R表 示 关 系 的 名 字 ， n是关 系 的 目 或 度 。n 属 性 ： 在 现 实 世 界 中 ， 要 描 述 一 个 事 物 常 常取 若 干 特 征 来 表 示 。 这 些 特 征 称 为 属 性（ attribute） 。 n目 关 系 必 有 n个 属 性 。 2 关 系 的 相 关 名 词n 候 选 码 （ Candidate Key） ： 若 关 系 中 的 某一 属 性 或 属 性 组 的 值 能 唯 一 的 标 识 一 个 元 组 ，则 称 该 属 性 或 属 性 组 为 候 选 码 。n 主 码 （ Primary Key） ： 若 一 个 关 系 有 多 个候 选 码 ， 则 选 定 其 中 一 个 为 主 码 。n 主 属 性 （ Non-Key attribute） ： 主 码 的 诸 属性 称 为 主 属 性 。 不 包 含 在 任 何 候 选 码 中 的 属性 称 为 非 码 属 性 。 据 (Data)是 数 据 库 中 存 储的 基 本 对 象 2 关 系 的 相 关 名 词n 外 码 （ Foreign key） ： 如 果 关 系 模 式 R中 的属 性 或 属 性 组 非 该 关 系 的 码 ， 但 它 是 其 它 关系 的 码 ， 那 么 该 属 性 集 对 关 系 模 式 R而 言 是外 码 。n 例 如 ， 客 户 与 贷 款 之 间 的 借 贷 联 系 c-l（ c-id，loan- no） ， 属 性 c-id 是 客 户 关 系 中 的 码 ， 所 以c-id是 外 码 ； 属 性 loan-no是 贷 款 关 系 中 的 码 ， 所以 loan-no也 是 外 码 。 2 关 系 的 相 关 名 词n 全 码 （ All-key） ： 关 系 模 型 的 所 有 属 性 组 是这 个 关 系 模 式 的 候 选 码 ， 称 为 全 码 。n 例 如 ， 关 系 模 式 R（ T， C， S） ， 属 性 T表 示 教 师 ，属 性 C表 示 课 程 ， 属 性 S表 示 学 生 。 假 设 一 个 教师 可 以 讲 授 多 门 课 程 ， 某 门 课 程 可 以 由 多 个 教 师讲 授 ， 学 生 可 以 听 不 同 教 师 讲 授 的 不 同 课 程 ， 那么 ， 要 想 区 分 关 系 中 的 每 一 个 元 组 ， 这 个 关 系 模式 R的 码 应 为 全 属 性 T、 C和 S， 即 All-key。 3 关 系 的 三 种 类 型n 基 本 关 系 （ 通 常 又 称 为 基 本 表 或 基 表 ） ： 是实 际 存 在 的 表 ， 它 是 实 际 存 储 数 据 的 逻 辑 表示 。n 查 询 表 ： 查 询 结 果 对 应 的 表 。n 视 图 表 ： 是 由 基 本 表 或 其 它 视 图 表 导 出 的 表 。由 于 它 本 身 不 独 立 存 储 在 数 据 库 中 ， 数 据 库中 只 存 放 它 的 定 义 ， 所 以 常 称 为 虚 表 。 2.1.2 关 系 模 型n 1 关 系 模 型 的 三 要 素 关 系 数 据 模 型 由 关 系 数 据 结 构 、 关 系 操 作 集合 和 关 系 完 整 性 约 束 三 大 要 素 组 成 。n (1)关 系 数 据 结 构n 关 系 模 型 的 数 据 结 构 单 一 ， 在 关 系 模 型 中 ， 现实 世 界 的 实 体 以 及 实 体 间 的 各 种 联 系 均 用 关 系来 表 示 ， 在 用 户 看 来 ， 关 系 模 型 中 数 据 的 逻 辑结 构 是 一 张 二 维 表 。 1 关 系 模 型 的 三 要 素n (2)关 系 操 作 集 合n 关 系 操 作 的 特 点 是 集 合 操 作 方 式 ， 即 操 作 的 对象 和 结 果 都 是 集 合 。 这 种 操 作 方 式 也 称 为 一 次一 个 集 合 的 方 式 。 相 应 地 ， 非 关 系 数 据 模 型 的数 据 操 作 方 式 则 为 一 次 一 个 记 录 的 方 式 。n 关 系 模 型 中 常 用 的 关 系 操 作 包 括 ： 选 择 (select)、投 影 (Project)、 连 接 (join)、 除 (divide)、 并(union)、 交 (intersection)、 差 (differencc)等 ，以 及 查 询 (query)操 作 和 增 (insert)、 删 (delete)、改 (update)操 作 两 大 部 分 。 查 询 的 表 达 能 力 是 其中 最 主 要 的 部 分 。 (2)关 系 操 作 集 合n 关 系 操 作 能 力 可 用 两 种 方 式 来 表 示 ： 代 数 方式 和 逻 辑 方 式 。n 关 系 代 数 是 用 对 关 系 的 运 算 来 表 达 查 询 要 求 的 方式 。n 关 系 演 算 是 用 谓 词 来 表 达 查 询 要 求 的 方 式 。 关 系演 算 又 可 按 谓 词 变 元 的 基 本 对 象 是 元 组 变 量 还 是域 变 量 分 为 元 组 关 系 演 算 和 域 关 系 演 算 。 对 于 关系 代 数 、 元 组 关 系 演 算 和 域 关 系 演 算 均 是 抽 象 的查 询 语 言 ， 在 表 达 能 力 上 是 完 全 等 价 的 。 1 关 系 模 型 的 三 要 素n (3)关 系 的 完 整 性 约 束n 数 据 库 的 数 据 完 整 性 是 指 数 据 库 中 数 据 的 正 确 性 和相 容 性 ， 是 一 种 语 义 概 念 ， 包 括 两 个 方 面 ：n 与 现 实 世 界 中 应 用 需 求 的 数 据 的 相 容 性 和 正 确 性 。n 数 据 库 内 数 据 之 间 的 相 容 性 和 正 确 性 。n 例 如 ， 学 生 的 学 号 必 须 惟 一 ， 性 别 只 能 是 男 或 女 ，学 生 所 选 修 的 课 程 必 须 是 已 开 设 的 课 程 ， 等 等 。 n 数 据 库 中 数 据 是 否 具 备 完 整 性 关 系 到 数 据 库 系 统 能否 真 实 地 反 映 现 实 世 界 ， 因 此 ， 数 据 库 的 完 整 性 是十 分 重 要 的 。 (3)关 系 的 完 整 性 约 束n 数 据 完 整 性 由 完 整 性 规 则 来 定 义 ， 关 系 模 型的 完 整 性 规 则 是 对 关 系 的 某 种 约 束 条 件 。 关系 模 型 中 可 以 有 3类 完 整 性 约 束 :实 体 完 整 性 、参 照 完 整 性 和 用 户 定 义 的 完 整 性 。n 实 体 完 整 性 和 参 照 完 整 性 是 关 系 模 型 必 须 满 足 的完 整 性 约 束 条 件 ， 应 该 由 关 系 系 统 自 动 支 持 。n 用 户 定 义 完 整 性 是 应 用 领 域 需 要 遵 循 的 约 束 条 件 ，体 现 了 具 体 领 域 中 的 语 义 约 束 ， 一 般 由 关 系 系 统提 供 编 写 手 段 、 由 DBMS的 完 整 性 检 查 机 制 负 责检 查 。 2 关 系 模 式n 定 义 2.1 关 系 的 描 述 称 为 关 系 模 式 。 可 以 形 式 化 的表 示 为 R（ U， D， dom， F）n 其 中 ， R表 示 关 系 名 ； U是 组 成 该 关 系 的 属 性 名 集 合 ；D是 属 性 的 域 ； dom是 属 性 向 域 的 映 象 集 合 ； F为 属性 间 数 据 的 依 赖 关 系 集 合 。 2 关 系 模 式n 通 常 将 关 系 模 式 简 记 为 ： R（ U） 或 R(A1， A2， A3， ， An)n 其 中 R为 关 系 名 ， A1， A2， A3， ， An为 属 性 名 或域 名 ， 属 性 的 向 域 的 映 象 常 常 直 接 说 明 属 性 的 类 型 、长 度 。 通 常 在 关 系 模 式 主 属 性 上 加 下 划 线 表 示 该 属性 为 主 码 属 性 。 举 例n 【 例 2.1】 学 生 关 系 S有 学 号 Sno、 学 生 姓 名Same、 性 别 Sex、 系 名 SD、 年 龄 Age属 性 ； 课程 关 系 C有 课 程 号 Cno、 课 程 名 Cname、 先 修课 程 号 PCno属 性 ； 学 生 选 课 关 系 SC有 学 号Sno、 课 程 号 Cno、 成 绩 Grade属 性 。 写 出 这三 个 关 系 模 式 。 举 例n 解 ：n (1)学 生 关 系 模 式 S（ Sno， Sname， Sex， SD， Age） n (2)课 程 关 系 模 式 C（ Cno， Cname， PCno） Dom（ PCno） =Cno。n (3)学 生 选 课 关 系 模 式 SC（ Sno， Cno， Grade） 。SC关 系 中 的 Sno、 Cno又 分 别 为 外 码 。 因 为 它 们 分别 是 S、 C关 系 中 的 主 码 。 2.1.3关 系 的 三 类 完 整 性 规 则n 关 系 模 型 的 完 整 性 规 则 是 对 关 系 的 某 种约 束 条 件 。 关 系 的 完 整 性 共 分 为 三 类 ：n 实 体 完 整 性n 参 照 完 整 性 （ 也 称 引 用 完 整 性 ）n 用 户 定 义 完 整 性 。 1 实 体 的 完 整 性 （ Entity Integrity）n 【 规 则 2.1】 若 属 性 A是 关 系 R的 主 属 性 ， 则 属 性 A不 能 取 空 值 。n 例 如 ： 关 系 学 生 (学 号 ， 姓 名 ， 性 别 ， 专 业 号 ， 年龄 )中 ， 主 码 为 “ 学 号 ” ， 则 “ 学 号 ” 不 能 取 空 值 。在 关 系 选 修 (学 号 ， 课 程 号 ， 成 绩 )中 ， “ 学 号 、 课程 号 ” 为 主 码 ， 则 “ 学 号 ” 和 “ 课 程 号 ” 两 个 属 性都 不 能 取 空 值 。 2 参 照 的 完 整 性 （ Referential Integrity）n 在 关 系 模 型 中 实 体 及 实 体 间 的 联 系 是 用 关 系 来 描 述的 ， 这 样 自 然 就 存 在 着 关 系 与 关 系 间 的 引 用 。n 例 如 ， 员 工 和 部 门 关 系 模 式 表 示 如 下 ：n 员 工 （ 员 工 号 ， 姓 名 ， 性 别 ， 参 加 工 作 时 间 ， 部 门 号 ） n 部 门 （ 部 门 号 ， 名 称 ， 电 话 ， 负 责 人 ）n 这 两 个 关 系 存 在 着 属 性 的 引 用 ， 即 员 工 关 系 中 的“ 部 门 号 ” 值 必 须 是 确 实 存 在 的 部 门 的 部 门 号 ， 即部 门 关 系 中 有 该 部 门 的 记 录 。 也 就 是 说 ， 员 工 关 系中 的 “ 部 门 号 ” 属 性 取 值 要 参 照 部 门 关 系 的 “ 部 门号 ” 属 性 取 值 。 2 参 照 的 完 整 性 （ Referential Integrity）n 【 规 则 2.2】 若 F是 基 本 关 系 R的 外 码 ， 它 与基 本 关 系 S的 主 码 Ks相 对 应 （ 基 本 关 系 R和 S不 一 定 是 不 同 的 关 系 ） 则 对 于 R中 每 个 元 组在 F上 的 值 必 须 为 ： n (1)或 者 取 空 值 （ F的 每 个 属 性 值 均 为 空 值 ）n (2)或 者 等 于 S中 某 个 元 组 的 主 码 值 。 3.用 户 定 义 的 完 整 性 （ User defined Integrity）n 实 体 完 整 性 规 则 定 义 了 对 关 系 中 主 属 性 取 值 的 约 束 ，即 对 主 属 性 的 值 域 的 约 束 ；n 参 照 完 整 性 规 则 定 义 了 参 照 关 系 和 被 参 照 关 系 的 外 码与 主 码 之 间 的 参 照 约 束 ， 即 对 参 照 关 系 的 外 码 属 性 值域 的 约 束 ， 规 定 外 码 属 性 的 值 域 只 能 是 空 值 或 是 相 应被 参 照 关 系 主 码 属 性 的 值 。 n 用 户 定 义 的 完 整 性 就 是 针 对 某 具 体 应 用 要 求 来 定 义的 约 束 条 件 ， 它 反 映 某 一 具 体 应 用 所 涉 及 的 数 据 必 须满 足 的 语 义 要 求 。 n 例 如 ， 某 个 属 性 必 须 取 惟 一 值 ， 某 些 属 性 值 之 间 应 满足 一 定 的 函 数 关 系 ， 某 个 属 性 的 取 值 范 围 在 0 100 之 间 等 。 用 户 定 义 的 完 整 性 通 常 是 定 义 对 关 系 中 除 主码 与 外 码 属 性 之 外 的 其 他 属 性 取 值 的 约 束 ， 即 对 其 他属 性 的 值 域 的 约 束 。n 对 属 性 值 域 的 约 束 也 称 为 域 完 整 性 约 束 ， 是 指 对 关 系中 属 性 取 值 的 正 确 性 限 制 ， 包 括 数 据 类 型 、 精 度 、 取值 范 围 、 是 否 允 许 空 值 等 。3.用 户 定 义 的 完 整 性 （ User defined Integrity） 2 2关 系 的 形 式 定 义2.2.1 关 系 的 形 式 定 义n 1 笛 卡 尔 积 数 据 的 定 义n 定 义 2.2 设 为 任 意 集 合 ， 定 义 的 笛 卡 儿 积 为 ：nDDDD , 321 nDDDD , 321 ,3,2,1,|),( 321321 niDdddddDDDD iinn 2 2关 系 的 形 式 定 义n 其 中 每 一 个 元 素 叫 做 一 个 n 元 组（ n-tuple属 性 的 个 数 ） ， 元 组 的 每 一 个 值 叫 做元 组 的 一 个 分 量 ， 若 为 有 限 集 ， 其 基数 （ Cardinal number元 组 的 个 数 ） 为 ，则 的 基 数 为 ： 。 笛 卡 儿 积可 以 用 二 维 表 来 表 示 。 ),( 321 ndddd id),3,2,1( niDi ),3,2,1( nimi nDDDD 321 ni imM 1 举 例【 例 2.2】 若 求 ：n 解 :根 据 定 义 ， 笛 卡 尔 积 中 的 每 一 个 元 素 应 该 是 一个 三 元 组 ， 每 个 分 量 来 自 不 同 的 域 ， 因 此 结 果 为 : n 用 二 维 表 表 示 如 图 2-1所 示 。 ),(),(),(),( ),(),(),(),(321 fdbedbfcbecb fdaedafcaecaDDD , 321 feDdcDbaD 321 DDD 图 2-1 笛 卡 尔 积 的 二 维 表 表 示 2 关 系n 定 义 2.3 的 子 集 叫 做 在 域 上 的 关 系 ， 记 为 ，称 关 系 R为 n元 关 系 。n 从 定 义 2.3可 以 得 出 一 个 关 系 也 可 以 用 二 维 表 来 表 示 。关 系 中 属 性 的 个 数 称 为 “ 元 组 ” ， 元 组 的 个 数 称 为“ 基 数 ” 。 关 系 模 型 中 的 术 语 与 一 般 术 语 的 对 应 情 况可 以 通 过 图 2-2中 的 学 生 关 系 说 明 。nDDDD 321 nDDDD , 321 ),( 321 nDDDDR 2.2.2 关 系 模 型 的 优 点n 1 关 系 的 性 质n (1)列 是 同 质 的 ， 即 每 一 列 中 的 分 量 均 是 同 一 类 型的 数 据 ， 即 均 来 自 同 一 个 域 。n (2)不 同 的 列 可 以 出 自 同 一 个 域 ， 每 一 列 称 为 一 个属 性 ； 属 性 不 能 重 名 。n (3)列 的 顺 序 是 无 关 ， 即 列 的 次 序 可 以 变 换 。 但 顺序 一 旦 固 定 ， 就 不 再 变 化 ， 不 能 导 致 冲 突 发 生 。 n (4)任 意 两 个 元 组 不 能 完 全 相 同 。n (5)行 的 顺 序 是 无 关 的 ， 即 行 的 次 序 可 以 交 换 。n (6)每 一 分 量 必 须 是 不 可 分 的 数 据 项 。 2 关 系 模 型 的 优 点n (1) 关 系 模 型 使 关 系 数 据 库 的 研 究 具 有 坚 实的 理 论 基 础 ， 这 一 理 论 有 助 于 关 系 数 据 库 的设 计 和 用 户 对 数 据 库 信 息 需 求 的 有 效 处 理 。n (2) 关 系 模 型 的 逻 辑 结 构 与 相 应 的 操 作 完 全独 立 于 数 据 的 存 储 方 式 ， 具 有 高 度 的 数 据 独立 性 ， 使 得 用 户 不 必 关 心 物 理 存 储 细 节 。 2 关 系 模 型 的 优 点n (3) 关 系 模 型 提 供 单 一 的 数 据 结 构 形 式 ， 具有 高 度 的 简 明 性 和 精 确 性 ， 用 户 很 容 易 掌 握和 运 用 基 于 关 系 模 型 的 数 据 库 系 统 。n (4) 关 系 数 据 库 语 言 与 一 阶 谓 词 逻 辑 的 固 有内 在 联 系 ， 使 得 以 关 系 数 据 库 为 基 础 的 推 理系 统 和 知 识 库 系 统 的 研 究 提 供 了 良 好 的 基 础 。 2.2.3 E-R模 型 向 关 系 模 型 的 转 换n 从 E-R模 型 向 关 系 模 型 转 换 时 ， 所 有 实 体 和 联系 都 要 转 换 成 相 应 的 关 系 模 式 ， 转 换 规 则 为 ：n (1) 每 个 实 体 类 型 转 换 成 一 个 关 系 模 式 ；n (2) 一 个 1:1的 联 系 可 转 换 为 一 个 关 系 模 式 ， 或 与 任意 一 端 的 关 系 模 式 合 并 ， 若 独 立 转 换 为 一 个 关 系 模式 ， 那 么 ， 两 端 关 系 的 码 及 联 系 的 属 性 为 该 关 系 的属 性 ； 若 与 一 端 合 并 ， 那 么 将 另 一 端 的 码 及 联 系 的属 性 合 并 到 该 端 。 2.2.3 E-R模 型 向 关 系 模 型 的 转 换n (3) 一 个 1:n的 联 系 可 转 换 为 一 个 关 系 模 式 ，或 与 n端 的 关 系 模 式 合 并 。 若 独 立 转 换 为 一个 关 系 模 式 ， 那 么 ， 两 端 关 系 的 码 及 联 系 的属 性 为 关 系 的 属 性 ， 而 n端 的 码 为 关 系 的 码 。n (4) 一 个 n:m的 联 系 可 转 换 为 一 个 关 系 模 式 ，那 么 ， 两 端 关 系 的 码 及 联 系 的 属 性 为 关 系 的属 性 ， 而 关 系 的 码 为 两 端 实 体 的 码 的 组 合 。 2.2.3 E-R模 型 向 关 系 模 型 的 转 换n (5) 三 个 或 三 个 以 上 多 对 多 的 联 系 可 转 换 为一 个 关 系 模 式 ， 那 么 ， 诸 关 系 的 码 及 联 系 的属 性 为 关 系 的 属 性 ， 而 关 系 的 码 为 各 实 体 的码 的 组 合 。n (6) 具 有 相 同 码 的 关 系 可 以 合 并 。 举 例 S CCLASSSCm nCTn 1Sno SnameSage Sex SD Grade Cno Cname PcnoDate CLno CLnameTel【 例 2.3】 将 图 2-3的 E-R图 转 换 成 关 系 模 式 。图 2-3 学 生 班 级 课 程 的 E-R图 举 例n 从 图 中 可 以 看 出 有 3个 实 体 :学 生 S 、 课 程 C 、 班级 CLASS， 根 据 转 换 规 则 转 换 成 3个 关 系 模 式 。 联系 CT是 一 个 1:n类 型 ， 根 据 转 换 规 则 可 将 CLASS的码 CLno， 加 上 联 系 的 属 性 Date并 入 n端 。 联 系 SC是 一 个 n:m 类 型 ， 根 据 转 换 规 则 转 换 成 一 个 独 立的 关 系 模 式 ， 所 以 将 S的 码 Sno和 C的 码 Cno， 加 上联 系 的 属 性 Grade作 为 关 系 SC的 属 性 ， 该 关 系 的码 是 Sno和 Cno 。 举 例n 根 据 上 述 分 析 转 换 的 关 系 模 式 如 下 ：n S(Sno， Sname， SD， Sage， Sex， CLno， Date)n C(Cno， Cname， Pcno)n CLASS(CLno， CLname， Tel) 2 3 关 系 运 算2.3.1关 系 代 数 的 五 种 基 本 运 算n 关 系 代 数 运 算 符 有 四 类 ：n 集 合 运 算 符n 专 门 的 关 系 运 算 符n 算 术 比 较 符n 逻 辑 运 算 符n 根 据 运 算 符 的 不 同 ， 关 系 代 数 运 算 可 分 为 n 传 统 的 集 合 运 算n 专 门 的 关 系 运 算 2 3 关 系 运 算n 传 统 的 集 合 运 算 是 从 关 系 的 水 平 方 向 进行 的 ， 包 括 ： 并 、 交 、 差 及 广 义 笛 卡 尔积 。n 专 门 的 关 系 运 算 既 可 以 从 关 系 的 水 平 方向 进 行 运 算 ， 又 可 以 向 关 系 的 垂 直 方 向运 算 ， 包 括 ： 选 择 、 投 影 、 连 接 以 及 除法 。 如 表 2-1所 示 。 表 2-1 1. 并 （ Union）n 关 系 R与 S具 有 相 同 的 关 系 模 式 ， 即 R与 S的 元 数 相同 （ 结 构 相 同 ） 。 关 系 R与 S并 由 属 于 R或 属 于 S的元 组 构 成 的 集 合 组 成 ， 记 作 ， 其 形 式 定 义 如下 ：n 式 中 t 为 元 组 变 量 。 SR StRt|tSR 2.差 （ Difference）n 关 系 R与 S具 有 相 同 的 关 系 模 式 ， 关 系 R与 S的 差 由属 于 R但 不 属 于 S的 元 组 构 成 的 集 合 ， 记 作 ，其 形 式 定 义 如 下 ： R-S StRt|tR-S 3.广 义 笛 卡 尔 积（ Extended Cartesian Product）n 两 个 元 数 分 别 为 n目 和 m目 的 关 系 R 和 S 的 广 义 笛卡 尔 积 是 一 个 （ n+m） 列 的 元 组 的 集 合 。 元 组 的前 n列 是 关 系 R的 一 个 元 组 ， 后 m列 是 关 系 S的 一 个元 组 。 记 作 ， 其 形 式 定 义 如 下 ： n 如 果 R和 S中 有 相 同 的 属 性 名 ， 可 在 属 性 名 前 加 关系 名 作 为 限 定 。 若 R 有 K1个 元 组 ， S 有 K2个 元 组 。则 R和 S的 广 义 笛 卡 尔 积 有 个 元 组 。SR StRtttt|tSR mnmn , 21 kk 4.投 影 （ Projection）n 投 影 运 算 是 从 关 系 的 垂 直 方 向 进 行 运 算 ， 在 关 系R中 选 择 出 若 干 属 性 列 A组 成 新 的 关 系 ， 记作 ， 其 形 式 定 义 如 下 ： RA R|tAtR A 5.选 择 （ Selection）n 选 择 运 算 是 从 关 系 的 水 平 方 向 进 行 运 算 ， 是从 关 系 R中 选 择 满 足 给 定 条 件 的 诸 元 组 ， 记作 ， 其 形 式 定 义 如 下 ：n 其 中 ， F中 的 运 算 对 象 是 属 性 名 (或 列 的 序 号 )或 常 数 ， 运 算 符 算 术 比 较 府 （ ， ，=， )和 逻 辑 运 算 符 ( ， ， ) 。 RF TruetFRt|tR F 5.选 择 （ Selection）n 例 如 ， 表 示 选 取 R关 系 中 第 一 个 属 性值 大 于 等 于 第 六 个 属 性 值 的 元 组 ； 表 示 选 取 R关 系 中 第 一 个 属 性 值 大 于 等 于“ 6”的 元 组 。 )(61 R )(61 R 举 例 【 例 2.4】 设 有 关 系 R、 S如 图 2-4所 示 ， 请 求 出 ：SR SR SR RCA, RBA SR43 举 例n 解 : 结 果 如 图 2-5所 示 。 其 中 ， 后 生 成 的 关 系 属 性名 有 重 复 ， 按 照 关 系 “ 属 性 不 能 重 名 ” 的 性 质 ， 通常 采 用 “ 关 系 名 .属 性 名 ” 的 格 式 。 对 于 的含 义 是 后 “ 选 取 第 三 个 属 性 值 小 于 第 四 个 属性 值 ” 的 元 组 。 由 于 的 第 三 个 属 性 为 R.C，第 四 个 属 性 是 S.A， 因 此 的 含 义 也 是 后 “ 选 取 R.C值 小 于 S.A值 ” 的 元 组 。SR SR SR RCA, RBA SR43SRSR )( 43 SR )(43 SR SRSR 图 2-5 运 算 结 果 2.3.2关 系 代 数 的 组 合 运 算n 扩 展 的 关 系 运 算 可 以 从 基 本 的 关 系 运 算 中导 出 。 主 要 包 括 ： 选 择 、 投 影 、 连 接 、 除法 、 广 义 笛 卡 尔 积 、 外 联 接 。 1.交 （ Intersection）n 关 系 R与 S具 有 相 同 的 关 系 模 式 ， 关 系 R与 S的 交 由 属 于 R同 时 又 属 于 S的 元 组 构 成 的 集合 ， 关 系 R与 S的 交 记 作 ， 其 形 式 定 义如 下 ：n 显 然 ， 或 者SR | StRttSR )( SRRSR )( RSSSR 2. 连 接 （ Join）n 连 接 分 为 ：n 连 接n 等 值 连 接n 自 然 连 接n 连 接 运 算 是 从 两 个 关 系 R和 S的 笛 卡 尔 积 中 选取 满 足 条 件 的 元 组 。 笛 卡 尔 积 是 无 条 件 连 接 ，其 它 的 连 接 操 作 认 为 是 有 条 件 连 接 。 下 面 分述 如 下 。 2. 连 接 （ Join）n (1) 连 接 ： 从 R与 S的 笛 卡 尔 积 中 选 取 属 性 间 满 足 一定 条 件 的 元 组 。 记 作 ：n 其 中 :“ ”为 连 接 条 件 ， 是 比 较 运 算 符 ， X和 Y分 别 为 R和 S上 度 数 相 等 且 可 比 的 属 性 组 。 表 示R中 元 组 的 相 应 属 性 X的 一 个 分 量 。 表 示 S中 元 组 的 相 应 属 性 Y的 一 个 分 量 。 , YtXtStRtttt|tSR mnmnmnYX YX Xt nnt Xtnmt (1) 连 接 ：n 需 要 说 明 的 是 :连 接 也 可 以 表 示 为 ：n 其 中 :i=1， 2， 3， ， n， j=1， 2， 3， ， m 。 “ ” 的 含 义 为 从 两 个 关 系 R和 S中 选 取 R的 第 i列 和S的 第 j列 之 间 满 足 运 算 的 元 组 进 行 连 接 。 n 连 接 可 以 由 基 本 的 关 系 运 算 笛 卡 儿 积 和 选 取 运 算 导出 ， 因 此 可 表 示 为 : 或 , jtitStRtttt|tSR mnmnmnji ji )( SRSR YXYX )()( SRSR jri 举 例【 例 2.5】 设 有 关 系 R， S如 图 2-4所 示 ， 求 ： 。n 解 :本 题 连 接 的 条 件 为 R.AS.B， 意 为 将 R关 系 中 属 性 A的 值 小 于 S关 系 中 属 性 B的 值 的 元 组 取 出 来 作 为 结 果 集的 元 组 。 结 果 集 为 后 选 出 满 足 条 件 的 元 组 ， 并且 结 果 集 的 属 性 为 R.A， R.B， R.C， S.A， S.B， S.C 。结 果 如 图 2-6所 示 。 图 2-6 SR SR BSAR . SR BSAR . 2. 连 接 （ Join）n (2)等 值 连 接 ： 当 为 “ =”时 ,称 之 为 等 值 连接 ,记 为 ,其 形 式 定 义 如 下 : , YtXtStRtttt|tSR mnmnmnYX SR YX 2. 连 接 （ Join）n (3)自 然 连 接 : 是 一 种 特 殊 的 等 值 连 接 ， 它 要求 两 个 关 系 中 进 行 比 较 的 分 量 必 须 是 相 同 的属 性 组 ， 并 且 在 结 果 中 将 重 复 属 性 列 去 掉 。记 为 ， 其 形 式 定 义 如 下 :SR nnmnmn BSBRBSBRBSBRStRtttt|tSR ., 2211 （ 3） 自 然 连 接n 自 然 连 接 可 以 由 基 本 的 关 系 运 算 投 影 、 选 取和 笛 卡 儿 积 导 出 。n 注 意 ： 一 般 连 接 是 从 关 系 的 水 平 方 向 运 算 ，而 自 然 连 接 不 仅 要 从 关 系 的 水 平 方 向 ， 而 且要 从 关 系 的 垂 直 方 向 运 算 。 因 为 自 然 连 接 要去 掉 重 复 属 性 ， 如 果 没 有 重 复 属 性 ， 那 麽 自然 连 接 就 转 化 为 笛 卡 儿 积 。 举 例 ：【 例 2.6】 设 有 关 系 如 图 2-7所 示 ,求 ： 。SR 举 例 ：n 解 ： 本 题 要 求 R与 S的 自 然 连 接 ， 自 然 连 接 是 一 种 特殊 的 等 值 连 接 ， 它 要 求 两 个 关 系 中 进 行 比 较 的 分 量 必须 是 相 同 的 属 性 组 ， 并 且 在 结 果 中 将 重 复 属 性 列 去 掉 。本 题 R与 S关 系 中 相 同 的 属 性 组 为 AC， 因 此 ， 结 果 集中 的 属 性 列 应 为 ABCD 。 其 结 果 如 图 2-8所 示 。 3. 除 （ Division）n 除 运 算 是 同 时 从 关 系 的 水 平 方 向 和 垂 直 方 向 进 行 运算 。 给 定 关 系 R(X， Y)和 S(Y， Z)， X， Y， Z为 属 性组 。 应 当 满 足 元 组 在 X上 的 分 量 值 x的 象 集 Yx包 含 关 系 S在 属 性 组 Y上 投 影 的 集 合 。 其 形 式 定 义 如下 ： n 其 中 : Yx为 x在 R中 的 象 集 ， x= ， 且 的 结果 集 的 属 性 组 为 X 。 xynn YSRtXtSR |SR SRXtn 举 例n 【 例 2.7】 设 有 关 系 R、 S如 图 2-9（ a） （ b）所 示 ， 求 ： 。SR 举 例n 解 :n 根 据 除 法 定 义 ， 此 题 的 X为 属 性 AB， Y为 属 性CD 。 应 当 满 足 元 组 在 属 性 AB上 的 分 量值 x的 象 集 Yx包 含 关 系 S在 CD上 投 影 的 集 合 。 SR 举 例n 关 系 S在 Y上 的 投 影 为 =(c， d)， (e， f) 。对 于 关 系 R， 属 性 组 X(即 AB)可 以 取 3个 值 (a， b)，(b， d)， (c， k)， 它 们 的 象 集 分 别 如 下 :n 象 集 CD(a， b) =(c， d)， (e， f)， (h， k)n 象 集 CD(b， d) =(e， f)， (d， l) n 象 集 CD(c， k) =(c， d)， (e， f)n 由 于 上 述 象 集 包 含 有 (a， b)和 (c， k)， 所 以 ， =(a， b)， (c， k)， 结 果 如 图 2-9(c)所 示 。SR )(SCD )(SCD 2.3.3关 系 代 数 的 外 连 接 运 算n 外 连 接 运 算 是 连 接 运 算 的 扩 展 ， 可 以 处 理 缺失 的 信 息 。 对 于 图 2-10的 S和 SC关 系 ， 对 其进 行 自 然 连 接 时 ， 结 果 如 图 2-11所 示 。 2.3.3关 系 代 数 的 外 连 接 运 算 2.3.3关 系 代 数 的 外 连 接 运 算n 由 图 2-11可 以 看 出 S与 SC的 自 然 连 接 的 结果 丢 失 了 黎 明 、 刘 明 远 、 赵 国 庆 的 相 关 信息 。 使 用 外 连 接 可 以 避 免 这 样 的 信 息 丢 失 。外 连 接 运 算 有 3种 ：n 左 外 连 接 n 右 外 连 接n 全 外 连 接 2.3.3关 系 代 数 的 外 连 接 运 算n 1)左 外 连 接 (left outer join) n 取 出 左 侧 关 系 中 所 有 与 右 侧 关 系 中 任 一 元 组 都 不匹 配 的 元 组 ， 用 空 值 null 填 充 所 有 来 自 右 侧 关 系的 属 性 ， 构 成 新 的 元 组 ， 将 其 加 入 自 然 连 接 的 结果 中 。 对 于 图 2-10的 S和 SC关 系 ， 对 其 进 行 左 外连 接 S SC时 ， 结 果 如 图 2-12所 示 。 图 2-12 S SC 2.3.3关 系 代 数 的 外 连 接 运 算n 2)右 外 连 接 (right outer join) n 取 出 右 侧 关 系 中 所 有 与 左 侧 关 系 中 任 一 元 组 都不 匹 配 的 元 组 ， 用 空 值 null填 充 所 有 来 自 左 侧关 系 的 属 性 ， 构 成 新 的 元 组 ， 将 其 加 入 自 然 连接 的 结 果 中 。 对 于 图 2-10的 S和 SC关 系 ， 对 其进 行 左 外 连 接 S SC时 ， 结 果 如 图 2-13所 示 。 图 2-13 S SC 2.3.3关 系 代 数 的 外 连 接 运 算n 3)全 外 连 接 (right outer join) n 填 充 左 侧 关 系 中 所 有 与 右 侧 关 系 中 任 一 元 组都 不 匹 配 的 元 组 ， 又 填 充 右 侧 关 系 中 所 有 与左 侧 关 系 中 任 一 元 组 都 不 匹 配 的 元 组 ， 将 产生 的 新 元 组 加 入 自 然 连 接 的 结 果 中 。 2.3.4关 系 代 数 运 算 举 例n 【 例 2. 8】 设 学 生 课 程 数 据 库 中 有 ： 学 生 S、 课 程 C、 学生 选 课 SC三 个 关 系 ， 如 图 2-14 所 示 。 请 用 关 系 代 数 表达 式 表 达 如 下 检 索 问 题 。n （ 1） 检 索 选 修 课 程 名 为 “ 数 学 ” 的 学 生 号 和 学 生 姓名 。n （ 2） 检 索 至 少 选 修 了 课 程 号 为 “ 1”和 “ 3”的 学 生 号 。n （ 3） 检 索 选 修 了 “ 操 作 系 统 ” 或 “ 数 据 库 ” 课 程的 学 号 和 成 绩 。 n （ 4） 检 索 年 龄 在 18到 20之 间 （ 含 18和 20） 的 女 生的 学 号 、 姓 名 及 年 龄 。n （ 5） 检 索 选 修 全 部 课 程 的 学 生 姓 名 及 所 在 的 系 。n （ 6） 检 索 选 修 课 程 包 括 “ 1042”学 生 所 学 的 课 程 的学 生 学 号 。 图 2-14 S， C SC关 系 2 4查 询 优 化2.4.1关 系 代 数 表 达 式 的 优 化 问 题n 查 询 处 理 ： 是 指 从 数 据 库 中 提 取 数 据 的 一 系列 活 动 。 这 一 系 列 活 动 包 括 ： 将 高 级 数 据 库语 言 表 示 的 查 询 语 句 翻 译 成 为 能 在 文 件 系 统这 一 物 理 层 次 上 实 现 的 表 达 式 ， 为 优 化 查 询进 行 各 种 转 换 ， 以 及 查 询 的 实 际 执 行 。 2 4查 询 优 化n 查 询 处 理 的 代 价 ： 通 常 取 决 于 磁 盘 的 访 问 ，磁 盘 的 访 问 比 内 存 访 问 速 度 要 慢 。 对 于 一 个给 定 的 查 询 ， 可 以 有 许 多 可 能 的 处 理 策 略 ，复 杂 查 询 更 是 如 此 。 就 所 需 的 磁 盘 访 问 次 数而 言 ， 策 略 好 坏 差 别 很 大 ， 有 时 甚 至 相 差 几个 数 量 级 。 所 以 ， 系 统 多 花 一 点 时 间 选 择 一个 较 好 的 查 询 策 略 是 很 值 得 的 。 2.4.1关 系 代 数 表 达 式 的 优 化 问 题n 查 询 优 化 ： 是 为 了 查 询 选 择 最 有 效 的 查 询 计划 的 过 程 。 查 询 优 化 一 方 面 是 在 关 系 代 数 级进 行 优 化 ， 要 做 的 是 力 图 找 出 与 给 定 表 达 式等 价 ， 但 执 行 效 率 更 高 的 一 个 表 达 式 。 查 询优 化 的 另 一 方 面 涉 及 查 询 语 句 处 理 的 详 细 策略 的 选 择 ， 例 如 选 择 执 行 运 算 所 采 用 的 具 体算 法 以 及 将 使 用 的 特 定 索 引 等 等 。 2.4.2关 系 代 数 表 达 式 的 等 价 变 换 规 则n 1 优 化 的 准 则n (1) 提 早 执 行 选 取 运 算 。 对 于 有 选 择 运 算 的 表 达式 ， 应 优 化 成 尽 可 能 先 执 行 选 择 运 算 的 等 价 表 达式 ， 以 得 到 较 小 的 中 间 结 果 ， 减 少 运 算 量 和 从 外存 读 块 的 次 数 。n (2) 合 并 乘 积 与 其 后 的 选 择 运 算 为 连 接 运 算 。 在表 达 式 中 ， 当 乘 积 运 算 后 是 选 择 运 算 时 ， 应 该 合并 为 连 接 运 算 ， 使 选 择 与 乘 积 一 道 完 成 ， 以 避 免做 完 乘 积 后 ， 需 再 扫 描 一 个 大 的 乘 积 关 系 进 行 选择 运 算 。 1 优 化 的 准 则n (3) 将 投 影 运 算 与 其 后 的 其 它 运 算 同 时 进 行 ， 以避 免 重 复 扫 描 关 系 。n (4) 将 投 影 运 算 和 其 前 后 的 二 目 运 算 结 合 起 来 ，使 得 没 有 必 要 为 去 掉 某 些 字 段 再 扫 描 一 遍 关 系 。 1 优 化 的 准 则n (5) 在 执 行 连 接 前 对 关 系 适 当 地 预 处 理 ， 就 能 快速 地 找 到 要 连 接 的 元 组 。 方 法 有 两 种 ： 索 引 连 接法 、 排 序 合 并 连 接 法 。n (6) 存 储 公 共 子 表 达 式 。 对 于 有 公 共 子 表 达 式 的结 果 应 存 于 外 存 （ 中 间 结 果 ） ， 这 样 ， 当 从 外 存读 出 它 的 时 间 比 计 算 的 时 间 少 时 ， 就 可 节 约 操 作时 间 。 2.关 系 代 数 表 达 式 的 等 价 变 换 规 则n 优 化 的 策 略 均 涉 及 关 系 代 数 表 达 式 ， 所 以 讨论 关 系 代 数 表 达 式 的 等 价 变 换 规 则 显 得 十 分重 要 。 常 用 的 等 价 变 换 规 则 有 如 下 10种 ：n （ 1） 连 接 、 笛 卡 尔 积 交 换 率 n 设 E1和 E2是 关 系 代 数 表 达 式 ， F是 连 接 运 算 的条 件 ， 则 有 12211221 EEEEEEEE FF 2.关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 2） 连 接 、 笛 卡 尔 积 结 合 率n 设 E1， E2， E3是 关 系 代 数 表 达 式 ， F1， F2是 连 接运 算 的 条 件 ， 则 有 )()( )()( 321321 321321 EEEEEE EEEEEE FFFF 2.关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 3） 投 影 的 串 接 定 律n 设 E是 关 系 代 数 表 达 式 ， A1， ， An和 B1， ，Bm ， 且 B1， ， Bm是 A1， ， An的 子 集 ， 则 有 n 该 规 则 的 目 的 是 使 一 些 投 影 消 失 。 )()( , 111 EE nmn AABBAA 2.关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 4） 选 择 的 串 接 定 律n 设 E是 关 系 代 数 表 达 式 ， F1， F2是 选 取 条 件表 达 式 ， 选 择 的 串 接 定 律 说 明 选 择 条 件 可 以合 并 ， 则 有 )()( 2121 EE FFFF 2.关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 5） 选 择 与 投 影 的 交 换 律n 设 E是 关 系 代 数 表 达 式 ， F是 选 取 条 件 表 达式 ， 并 且 只 涉 及 A1， ， An属 性 ， 则 有)()( , 11 EE FAAAAF nn 2 关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 6） 选 择 与 笛 卡 尔 积 的 交 换 律n 若 F涉 及 的 都 是 E1中 的 属 性 ， 则n 如 果 F=F1 F2， 并 且 F1只 涉 及 中 E1的 属 性 ， F2只 涉 及 E2中 的 属 性 ， 则 有 2121 )()( EEEE FF )()()( 2121 21 EEEE FFF 2 关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 7） 选 择 与 并 的 交 换 律n 设 E=E1 E2 ， E1， E2有 相 同 的 属 性 ， 则n （ 8） 选 择 与 差 的 交 换 律 n 设 E1， E2有 相 同 的 属 性 ， 则 )()()( 2121 EEEE FFF )()()( 2121 EEEE FFF 2 关 系 代 数 表 达 式 的 等 价 变 换 规 则n （ 9） 投 影 与 笛 卡 尔 积 的 交 换 律n 设 E1， E2是 两 个 关 系 代 数 表 达 式 ， A1， ， An是 E1中 的 属 性 ， B1， ， Bm是 E2中 的 属 性 ， 则n （ 10） 投 影 与 并 的 交 换 律 n 设 E1， E2有 相 同 的 属 性 ， 则 )()()( 2,1,21, 1111 EEEE mnmn BBAABBAA )()()( 2,1,21, 111 EEEE nnn AAAAAA 2.4.3关 系 代 数 表 达 式 的 优 化 算 法n 算 法 ： 关 系 代 数 表 达 式 的 优 化n 输 入 ： 一 个 关 系 代 数 表 达 式 的 语 法 树n 输 出 ： 计 算 该 表 达 式 的 程 序 。 n 方 法 ：n （ 1） 利 用 规 则 4将 形 如 变 换 为 ：n （ 2） 对 每 一 选 择 ， 用 规 则 48尽 可 能 将 它 移 到 树的 叶 端 。n （ 3） 对 每 一 个 投 影 ， 利 用 规 则 3、 9， 10， 5中 的一 般 形 式 尽 可 能 将 它 移 到 树 的 叶 端 。)(21 EnFFF )( 21 EnFFF 2.4.3关 系 代 数 表 达 式 的 优 化 算 法 n （ 4） 利 用 规 则 35将 选 择 和 投 影 的 串 接 合 并 成 单 个选 择 、 单 个 投 影 或 一 个 选 择 后 跟 一 个 投 影 。 使 多 个选 择 或 投 影 能 同 时 进 行 ， 或 在 一 次 扫 描 中 全 部 完 成 。n （ 5） 将 上 述 得 到 的 语 法 树 的 内 节 点 分 组 。 每 一 双 目运 算 ( ， ， ， -)和 它 所 有 的 直 接 祖 先 为 一 组（ 这 些 直 接 祖 先 是 ， 运 算 ） 。 如 果 其 后 代 直 到 叶子 全 部 是 单 目 运 算 ， 则 将 它 并 入 该 组 。方 法 ： n （ 6） 生 成 一 个 程 序 ， 每 组 节 点 的 计 算 是程 序 中 的 一 步 。 各 步 的 顺 序 是 任 意 的 ， 只要 保 证 任 何 一 组 的 计 算 不 会 在 它 的 后 代 组之 前 计 算 。方 法 ： 举 例n 【 例 2.12】 供 应 商 数 据 库 中 有 ： 供 应 商 、 零件 、 项 目 、 供 应 四 个 基 本 表 （ 关 系 ） ：nS(Sno，Sname，Status，City)nP(Pno，Pname，Color，Weight)nJ(Jno，Jname，City) nSPJ(Sno，Pno，Jno，Qty) 举 例n 用 户 有 一 查 询 语 句 ： 检 索 使 用 上 海 供 应 商 生产 的 红 色 零 件 的 工 程 号 。n (1) 试 写 出 该 查 询 的 关 系 代 数 表 达 式 ；n (2) 试 写 出 查 询 优 化 的 关 系 代 数 表 达 式 ；n (3) 画 出 该 查 询 初 始 的 关 系 代 数 表 达 式 的 语 法 树 ； n (4) 使 用 优 化 算 法 ， 对 语 法 树 进 行 优 化 ， 并 画 出优 化 后 的 语 法 树 。 举 例解 :n (1)该 查 询 的 关 系 代 数 表 达 式 如 下 :n (2)查 询 优 化 的 关 系 代 数 表 达 式 如 下 : n (3)该 查 询 初 始 的 关 系 代 数 表 达 式 的 语 法 树 如 图 2-221所 示 。n (4)优 化 后 的 语 法