數(shù)據(jù)庫原理及應(yīng)用教案

《數(shù)據(jù)庫原理及應(yīng)用教案》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)庫原理及應(yīng)用教案（194頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù) 據(jù) 庫 原 理 及 應(yīng) 用 教 案河北化工醫(yī)藥職業(yè)技術(shù)學(xué)院 第 2章 關(guān) 系 數(shù) 據(jù) 庫n 2.1 關(guān) 系 數(shù) 據(jù) 庫 與 關(guān) 系 模 型n 2.2 關(guān) 系 的 形 式 定 義n 2.3 關(guān) 系 運(yùn) 算 代 數(shù)n 2.4 查 詢 優(yōu) 化n 2.5 關(guān) 系 數(shù) 據(jù) 庫 的 規(guī) 范 化 理 論 2.1關(guān) 系 數(shù) 據(jù) 庫 與 關(guān) 系 模 型2.1.1 基 本 概 念n 1 關(guān) 系 數(shù) 據(jù) 庫 系 統(tǒng)n 關(guān) 系 數(shù) 據(jù) 庫 系 統(tǒng) 是 支 持 關(guān) 系 數(shù) 據(jù) 模 型 的 數(shù) 據(jù) 庫系 統(tǒng) 。 關(guān) 系 數(shù) 據(jù) 庫 應(yīng) 用 數(shù) 學(xué) 方 法 來 處 理 數(shù) 據(jù) 庫中 的 數(shù) 據(jù) 。n 關(guān) 系 模 型 由

2、 關(guān) 系 數(shù) 據(jù) 結(jié) 構(gòu) 、 關(guān) 系 操 作 集 合 和 關(guān)系 完 整 性 約 束 三 部 分 組 成 。 n 關(guān) 系 數(shù) 據(jù) 庫 管 理 系 統(tǒng) RDBMS如 著 名 的 IBM DB2，Oracle， Ingres， SYBASE， Informix等 。 2 關(guān) 系 的 相 關(guān) 名 詞n 域 ： 域 是 一 組 具 有 相 同 數(shù) 據(jù) 類 型 的 值 的 集 合 。n 一 般 在 關(guān) 系 數(shù) 據(jù) 模 型 中 ， 對 域 還 加 了 一 個(gè) 限 制 ，所 有 的 域 都 應(yīng) 是 原 子 數(shù) 據(jù) （ atomic data） 。n 目 或 度 （ Degree） ： 設(shè) 有 關(guān) 系 R(D1

3、，D2， Dn )， 這 里 的 R表 示 關(guān) 系 的 名 字 ， n是關(guān) 系 的 目 或 度 。n 屬 性 ： 在 現(xiàn) 實(shí) 世 界 中 ， 要 描 述 一 個(gè) 事 物 常 常取 若 干 特 征 來 表 示 。 這 些 特 征 稱 為 屬 性（ attribute） 。 n目 關(guān) 系 必 有 n個(gè) 屬 性 。 2 關(guān) 系 的 相 關(guān) 名 詞n 候 選 碼 （ Candidate Key） ： 若 關(guān) 系 中 的 某一 屬 性 或 屬 性 組 的 值 能 唯 一 的 標(biāo) 識(shí) 一 個(gè) 元 組 ，則 稱 該 屬 性 或 屬 性 組 為 候 選 碼 。n 主 碼 （ Primary Key） ： 若

4、一 個(gè) 關(guān) 系 有 多 個(gè)候 選 碼 ， 則 選 定 其 中 一 個(gè) 為 主 碼 。n 主 屬 性 （ Non-Key attribute） ： 主 碼 的 諸 屬性 稱 為 主 屬 性 。 不 包 含 在 任 何 候 選 碼 中 的 屬性 稱 為 非 碼 屬 性 。 據(jù) (Data)是 數(shù) 據(jù) 庫 中 存 儲(chǔ)的 基 本 對 象 2 關(guān) 系 的 相 關(guān) 名 詞n 外 碼 （ Foreign key） ： 如 果 關(guān) 系 模 式 R中 的屬 性 或 屬 性 組 非 該 關(guān) 系 的 碼 ， 但 它 是 其 它 關(guān)系 的 碼 ， 那 么 該 屬 性 集 對 關(guān) 系 模 式 R而 言 是外 碼 。n

5、例 如 ， 客 戶 與 貸 款 之 間 的 借 貸 聯(lián) 系 c-l（ c-id，loan- no） ， 屬 性 c-id 是 客 戶 關(guān) 系 中 的 碼 ， 所 以c-id是 外 碼 ； 屬 性 loan-no是 貸 款 關(guān) 系 中 的 碼 ， 所以 loan-no也 是 外 碼 。 2 關(guān) 系 的 相 關(guān) 名 詞n 全 碼 （ All-key） ： 關(guān) 系 模 型 的 所 有 屬 性 組 是這 個(gè) 關(guān) 系 模 式 的 候 選 碼 ， 稱 為 全 碼 。n 例 如 ， 關(guān) 系 模 式 R（ T， C， S） ， 屬 性 T表 示 教 師 ，屬 性 C表 示 課 程 ， 屬 性 S表 示 學(xué) 生

6、 。 假 設(shè) 一 個(gè) 教師 可 以 講 授 多 門 課 程 ， 某 門 課 程 可 以 由 多 個(gè) 教 師講 授 ， 學(xué) 生 可 以 聽 不 同 教 師 講 授 的 不 同 課 程 ， 那么 ， 要 想 區(qū) 分 關(guān) 系 中 的 每 一 個(gè) 元 組 ， 這 個(gè) 關(guān) 系 模式 R的 碼 應(yīng) 為 全 屬 性 T、 C和 S， 即 All-key。 3 關(guān) 系 的 三 種 類 型n 基 本 關(guān) 系 （ 通 常 又 稱 為 基 本 表 或 基 表 ） ： 是實(shí) 際 存 在 的 表 ， 它 是 實(shí) 際 存 儲(chǔ) 數(shù) 據(jù) 的 邏 輯 表示 。n 查 詢 表 ： 查 詢 結(jié) 果 對 應(yīng) 的 表 。n 視 圖 表

7、 ： 是 由 基 本 表 或 其 它 視 圖 表 導(dǎo) 出 的 表 。由 于 它 本 身 不 獨(dú) 立 存 儲(chǔ) 在 數(shù) 據(jù) 庫 中 ， 數(shù) 據(jù) 庫中 只 存 放 它 的 定 義 ， 所 以 常 稱 為 虛 表 。 2.1.2 關(guān) 系 模 型n 1 關(guān) 系 模 型 的 三 要 素 關(guān) 系 數(shù) 據(jù) 模 型 由 關(guān) 系 數(shù) 據(jù) 結(jié) 構(gòu) 、 關(guān) 系 操 作 集合 和 關(guān) 系 完 整 性 約 束 三 大 要 素 組 成 。n (1)關(guān) 系 數(shù) 據(jù) 結(jié) 構(gòu)n 關(guān) 系 模 型 的 數(shù) 據(jù) 結(jié) 構(gòu) 單 一 ， 在 關(guān) 系 模 型 中 ， 現(xiàn)實(shí) 世 界 的 實(shí) 體 以 及 實(shí) 體 間 的 各 種 聯(lián) 系 均 用 關(guān)

8、 系來 表 示 ， 在 用 戶 看 來 ， 關(guān) 系 模 型 中 數(shù) 據(jù) 的 邏 輯結(jié) 構(gòu) 是 一 張 二 維 表 。 1 關(guān) 系 模 型 的 三 要 素n (2)關(guān) 系 操 作 集 合n 關(guān) 系 操 作 的 特 點(diǎn) 是 集 合 操 作 方 式 ， 即 操 作 的 對象 和 結(jié) 果 都 是 集 合 。 這 種 操 作 方 式 也 稱 為 一 次一 個(gè) 集 合 的 方 式 。 相 應(yīng) 地 ， 非 關(guān) 系 數(shù) 據(jù) 模 型 的數(shù) 據(jù) 操 作 方 式 則 為 一 次 一 個(gè) 記 錄 的 方 式 。n 關(guān) 系 模 型 中 常 用 的 關(guān) 系 操 作 包 括 ： 選 擇 (select)、投 影 (Proj

9、ect)、 連 接 (join)、 除 (divide)、 并(union)、 交 (intersection)、 差 (differencc)等 ，以 及 查 詢 (query)操 作 和 增 (insert)、 刪 (delete)、改 (update)操 作 兩 大 部 分 。 查 詢 的 表 達(dá) 能 力 是 其中 最 主 要 的 部 分 。 (2)關(guān) 系 操 作 集 合n 關(guān) 系 操 作 能 力 可 用 兩 種 方 式 來 表 示 ： 代 數(shù) 方式 和 邏 輯 方 式 。n 關(guān) 系 代 數(shù) 是 用 對 關(guān) 系 的 運(yùn) 算 來 表 達(dá) 查 詢 要 求 的 方式 。n 關(guān) 系 演 算 是

10、用 謂 詞 來 表 達(dá) 查 詢 要 求 的 方 式 。 關(guān) 系演 算 又 可 按 謂 詞 變 元 的 基 本 對 象 是 元 組 變 量 還 是域 變 量 分 為 元 組 關(guān) 系 演 算 和 域 關(guān) 系 演 算 。 對 于 關(guān)系 代 數(shù) 、 元 組 關(guān) 系 演 算 和 域 關(guān) 系 演 算 均 是 抽 象 的查 詢 語 言 ， 在 表 達(dá) 能 力 上 是 完 全 等 價(jià) 的 。 1 關(guān) 系 模 型 的 三 要 素n (3)關(guān) 系 的 完 整 性 約 束n 數(shù) 據(jù) 庫 的 數(shù) 據(jù) 完 整 性 是 指 數(shù) 據(jù) 庫 中 數(shù) 據(jù) 的 正 確 性 和相 容 性 ， 是 一 種 語 義 概 念 ， 包 括

11、兩 個(gè) 方 面 ：n 與 現(xiàn) 實(shí) 世 界 中 應(yīng) 用 需 求 的 數(shù) 據(jù) 的 相 容 性 和 正 確 性 。n 數(shù) 據(jù) 庫 內(nèi) 數(shù) 據(jù) 之 間 的 相 容 性 和 正 確 性 。n 例 如 ， 學(xué) 生 的 學(xué) 號(hào) 必 須 惟 一 ， 性 別 只 能 是 男 或 女 ，學(xué) 生 所 選 修 的 課 程 必 須 是 已 開 設(shè) 的 課 程 ， 等 等 。 n 數(shù) 據(jù) 庫 中 數(shù) 據(jù) 是 否 具 備 完 整 性 關(guān) 系 到 數(shù) 據(jù) 庫 系 統(tǒng) 能否 真 實(shí) 地 反 映 現(xiàn) 實(shí) 世 界 ， 因 此 ， 數(shù) 據(jù) 庫 的 完 整 性 是十 分 重 要 的 。 (3)關(guān) 系 的 完 整 性 約 束n 數(shù) 據(jù)

12、完 整 性 由 完 整 性 規(guī) 則 來 定 義 ， 關(guān) 系 模 型的 完 整 性 規(guī) 則 是 對 關(guān) 系 的 某 種 約 束 條 件 。 關(guān)系 模 型 中 可 以 有 3類 完 整 性 約 束 :實(shí) 體 完 整 性 、參 照 完 整 性 和 用 戶 定 義 的 完 整 性 。n 實(shí) 體 完 整 性 和 參 照 完 整 性 是 關(guān) 系 模 型 必 須 滿 足 的完 整 性 約 束 條 件 ， 應(yīng) 該 由 關(guān) 系 系 統(tǒng) 自 動(dòng) 支 持 。n 用 戶 定 義 完 整 性 是 應(yīng) 用 領(lǐng) 域 需 要 遵 循 的 約 束 條 件 ，體 現(xiàn) 了 具 體 領(lǐng) 域 中 的 語 義 約 束 ， 一 般 由 關(guān)

13、 系 系 統(tǒng)提 供 編 寫 手 段 、 由 DBMS的 完 整 性 檢 查 機(jī) 制 負(fù) 責(zé)檢 查 。 2 關(guān) 系 模 式n 定 義 2.1 關(guān) 系 的 描 述 稱 為 關(guān) 系 模 式 。 可 以 形 式 化 的表 示 為 R（ U， D， dom， F）n 其 中 ， R表 示 關(guān) 系 名 ； U是 組 成 該 關(guān) 系 的 屬 性 名 集 合 ；D是 屬 性 的 域 ； dom是 屬 性 向 域 的 映 象 集 合 ； F為 屬性 間 數(shù) 據(jù) 的 依 賴 關(guān) 系 集 合 。 2 關(guān) 系 模 式n 通 常 將 關(guān) 系 模 式 簡 記 為 ： R（ U） 或 R(A1， A2， A3， ， An)

14、n 其 中 R為 關(guān) 系 名 ， A1， A2， A3， ， An為 屬 性 名 或域 名 ， 屬 性 的 向 域 的 映 象 常 常 直 接 說 明 屬 性 的 類 型 、長 度 。 通 常 在 關(guān) 系 模 式 主 屬 性 上 加 下 劃 線 表 示 該 屬性 為 主 碼 屬 性 。 舉 例n 【 例 2.1】 學(xué) 生 關(guān) 系 S有 學(xué) 號(hào) Sno、 學(xué) 生 姓 名Same、 性 別 Sex、 系 名 SD、 年 齡 Age屬 性 ； 課程 關(guān) 系 C有 課 程 號(hào) Cno、 課 程 名 Cname、 先 修課 程 號(hào) PCno屬 性 ； 學(xué) 生 選 課 關(guān) 系 SC有 學(xué) 號(hào)Sno、 課

15、程 號(hào) Cno、 成 績 Grade屬 性 。 寫 出 這三 個(gè) 關(guān) 系 模 式 。 舉 例n 解 ：n (1)學(xué) 生 關(guān) 系 模 式 S（ Sno， Sname， Sex， SD， Age） n (2)課 程 關(guān) 系 模 式 C（ Cno， Cname， PCno） Dom（ PCno） =Cno。n (3)學(xué) 生 選 課 關(guān) 系 模 式 SC（ Sno， Cno， Grade） 。SC關(guān) 系 中 的 Sno、 Cno又 分 別 為 外 碼 。 因 為 它 們 分別 是 S、 C關(guān) 系 中 的 主 碼 。 2.1.3關(guān) 系 的 三 類 完 整 性 規(guī) 則n 關(guān) 系 模 型 的 完 整 性 規(guī)

16、 則 是 對 關(guān) 系 的 某 種約 束 條 件 。 關(guān) 系 的 完 整 性 共 分 為 三 類 ：n 實(shí) 體 完 整 性n 參 照 完 整 性 （ 也 稱 引 用 完 整 性 ）n 用 戶 定 義 完 整 性 。 1 實(shí) 體 的 完 整 性 （ Entity Integrity）n 【 規(guī) 則 2.1】 若 屬 性 A是 關(guān) 系 R的 主 屬 性 ， 則 屬 性 A不 能 取 空 值 。n 例 如 ： 關(guān) 系 學(xué) 生 (學(xué) 號(hào) ， 姓 名 ， 性 別 ， 專 業(yè) 號(hào) ， 年齡 )中 ， 主 碼 為 “ 學(xué) 號(hào) ” ， 則 “ 學(xué) 號(hào) ” 不 能 取 空 值 。在 關(guān) 系 選 修 (學(xué) 號(hào) ，

17、課 程 號(hào) ， 成 績 )中 ， “ 學(xué) 號(hào) 、 課程 號(hào) ” 為 主 碼 ， 則 “ 學(xué) 號(hào) ” 和 “ 課 程 號(hào) ” 兩 個(gè) 屬 性都 不 能 取 空 值 。 2 參 照 的 完 整 性 （ Referential Integrity）n 在 關(guān) 系 模 型 中 實(shí) 體 及 實(shí) 體 間 的 聯(lián) 系 是 用 關(guān) 系 來 描 述的 ， 這 樣 自 然 就 存 在 著 關(guān) 系 與 關(guān) 系 間 的 引 用 。n 例 如 ， 員 工 和 部 門 關(guān) 系 模 式 表 示 如 下 ：n 員 工 （ 員 工 號(hào) ， 姓 名 ， 性 別 ， 參 加 工 作 時(shí) 間 ， 部 門 號(hào) ） n 部 門 （ 部

18、門 號(hào) ， 名 稱 ， 電 話 ， 負(fù) 責(zé) 人 ）n 這 兩 個(gè) 關(guān) 系 存 在 著 屬 性 的 引 用 ， 即 員 工 關(guān) 系 中 的“ 部 門 號(hào) ” 值 必 須 是 確 實(shí) 存 在 的 部 門 的 部 門 號(hào) ， 即部 門 關(guān) 系 中 有 該 部 門 的 記 錄 。 也 就 是 說 ， 員 工 關(guān) 系中 的 “ 部 門 號(hào) ” 屬 性 取 值 要 參 照 部 門 關(guān) 系 的 “ 部 門號(hào) ” 屬 性 取 值 。 2 參 照 的 完 整 性 （ Referential Integrity）n 【 規(guī) 則 2.2】 若 F是 基 本 關(guān) 系 R的 外 碼 ， 它 與基 本 關(guān) 系 S的 主

19、碼 Ks相 對 應(yīng) （ 基 本 關(guān) 系 R和 S不 一 定 是 不 同 的 關(guān) 系 ） 則 對 于 R中 每 個(gè) 元 組在 F上 的 值 必 須 為 ： n (1)或 者 取 空 值 （ F的 每 個(gè) 屬 性 值 均 為 空 值 ）n (2)或 者 等 于 S中 某 個(gè) 元 組 的 主 碼 值 。 3.用 戶 定 義 的 完 整 性 （ User defined Integrity）n 實(shí) 體 完 整 性 規(guī) 則 定 義 了 對 關(guān) 系 中 主 屬 性 取 值 的 約 束 ，即 對 主 屬 性 的 值 域 的 約 束 ；n 參 照 完 整 性 規(guī) 則 定 義 了 參 照 關(guān) 系 和 被 參 照

20、 關(guān) 系 的 外 碼與 主 碼 之 間 的 參 照 約 束 ， 即 對 參 照 關(guān) 系 的 外 碼 屬 性 值域 的 約 束 ， 規(guī) 定 外 碼 屬 性 的 值 域 只 能 是 空 值 或 是 相 應(yīng)被 參 照 關(guān) 系 主 碼 屬 性 的 值 。 n 用 戶 定 義 的 完 整 性 就 是 針 對 某 具 體 應(yīng) 用 要 求 來 定 義的 約 束 條 件 ， 它 反 映 某 一 具 體 應(yīng) 用 所 涉 及 的 數(shù) 據(jù) 必 須滿 足 的 語 義 要 求 。 n 例 如 ， 某 個(gè) 屬 性 必 須 取 惟 一 值 ， 某 些 屬 性 值 之 間 應(yīng) 滿足 一 定 的 函 數(shù) 關(guān) 系 ， 某 個(gè) 屬

21、 性 的 取 值 范 圍 在 0 100 之 間 等 。 用 戶 定 義 的 完 整 性 通 常 是 定 義 對 關(guān) 系 中 除 主碼 與 外 碼 屬 性 之 外 的 其 他 屬 性 取 值 的 約 束 ， 即 對 其 他屬 性 的 值 域 的 約 束 。n 對 屬 性 值 域 的 約 束 也 稱 為 域 完 整 性 約 束 ， 是 指 對 關(guān) 系中 屬 性 取 值 的 正 確 性 限 制 ， 包 括 數(shù) 據(jù) 類 型 、 精 度 、 取值 范 圍 、 是 否 允 許 空 值 等 。3.用 戶 定 義 的 完 整 性 （ User defined Integrity） 2 2關(guān) 系 的 形 式

22、定 義2.2.1 關(guān) 系 的 形 式 定 義n 1 笛 卡 爾 積 數(shù) 據(jù) 的 定 義n 定 義 2.2 設(shè) 為 任 意 集 合 ， 定 義 的 笛 卡 兒 積 為 ：nDDDD , 321 nDDDD , 321 ,3,2,1,|),( 321321 niDdddddDDDD iinn 2 2關(guān) 系 的 形 式 定 義n 其 中 每 一 個(gè) 元 素 叫 做 一 個(gè) n 元 組（ n-tuple屬 性 的 個(gè) 數(shù) ） ， 元 組 的 每 一 個(gè) 值 叫 做元 組 的 一 個(gè) 分 量 ， 若 為 有 限 集 ， 其 基數(shù) （ Cardinal number元 組 的 個(gè) 數(shù) ） 為 ，則 的 基

23、 數(shù) 為 ： 。 笛 卡 兒 積可 以 用 二 維 表 來 表 示 。 ),( 321 ndddd id),3,2,1( niDi ),3,2,1( nimi nDDDD 321 ni imM 1 舉 例【 例 2.2】 若 求 ：n 解 :根 據(jù) 定 義 ， 笛 卡 爾 積 中 的 每 一 個(gè) 元 素 應(yīng) 該 是 一個(gè) 三 元 組 ， 每 個(gè) 分 量 來 自 不 同 的 域 ， 因 此 結(jié) 果 為 : n 用 二 維 表 表 示 如 圖 2-1所 示 。 ),(),(),(),( ),(),(),(),(321 fdbedbfcbecb fdaedafcaecaDDD , 321 feDdc

24、DbaD 321 DDD 圖 2-1 笛 卡 爾 積 的 二 維 表 表 示 2 關(guān) 系n 定 義 2.3 的 子 集 叫 做 在 域 上 的 關(guān) 系 ， 記 為 ，稱 關(guān) 系 R為 n元 關(guān) 系 。n 從 定 義 2.3可 以 得 出 一 個(gè) 關(guān) 系 也 可 以 用 二 維 表 來 表 示 。關(guān) 系 中 屬 性 的 個(gè) 數(shù) 稱 為 “ 元 組 ” ， 元 組 的 個(gè) 數(shù) 稱 為“ 基 數(shù) ” 。 關(guān) 系 模 型 中 的 術(shù) 語 與 一 般 術(shù) 語 的 對 應(yīng) 情 況可 以 通 過 圖 2-2中 的 學(xué) 生 關(guān) 系 說 明 。nDDDD 321 nDDDD , 321 ),( 321 nDDD

25、DR 2.2.2 關(guān) 系 模 型 的 優(yōu) 點(diǎn)n 1 關(guān) 系 的 性 質(zhì)n (1)列 是 同 質(zhì) 的 ， 即 每 一 列 中 的 分 量 均 是 同 一 類 型的 數(shù) 據(jù) ， 即 均 來 自 同 一 個(gè) 域 。n (2)不 同 的 列 可 以 出 自 同 一 個(gè) 域 ， 每 一 列 稱 為 一 個(gè)屬 性 ； 屬 性 不 能 重 名 。n (3)列 的 順 序 是 無 關(guān) ， 即 列 的 次 序 可 以 變 換 。 但 順序 一 旦 固 定 ， 就 不 再 變 化 ， 不 能 導(dǎo) 致 沖 突 發(fā) 生 。 n (4)任 意 兩 個(gè) 元 組 不 能 完 全 相 同 。n (5)行 的 順 序 是 無

26、關(guān) 的 ， 即 行 的 次 序 可 以 交 換 。n (6)每 一 分 量 必 須 是 不 可 分 的 數(shù) 據(jù) 項(xiàng) 。 2 關(guān) 系 模 型 的 優(yōu) 點(diǎn)n (1) 關(guān) 系 模 型 使 關(guān) 系 數(shù) 據(jù) 庫 的 研 究 具 有 堅(jiān) 實(shí)的 理 論 基 礎(chǔ) ， 這 一 理 論 有 助 于 關(guān) 系 數(shù) 據(jù) 庫 的設(shè) 計(jì) 和 用 戶 對 數(shù) 據(jù) 庫 信 息 需 求 的 有 效 處 理 。n (2) 關(guān) 系 模 型 的 邏 輯 結(jié) 構(gòu) 與 相 應(yīng) 的 操 作 完 全獨(dú) 立 于 數(shù) 據(jù) 的 存 儲(chǔ) 方 式 ， 具 有 高 度 的 數(shù) 據(jù) 獨(dú)立 性 ， 使 得 用 戶 不 必 關(guān) 心 物 理 存 儲(chǔ) 細(xì) 節(jié) 。

27、2 關(guān) 系 模 型 的 優(yōu) 點(diǎn)n (3) 關(guān) 系 模 型 提 供 單 一 的 數(shù) 據(jù) 結(jié) 構(gòu) 形 式 ， 具有 高 度 的 簡 明 性 和 精 確 性 ， 用 戶 很 容 易 掌 握和 運(yùn) 用 基 于 關(guān) 系 模 型 的 數(shù) 據(jù) 庫 系 統(tǒng) 。n (4) 關(guān) 系 數(shù) 據(jù) 庫 語 言 與 一 階 謂 詞 邏 輯 的 固 有內(nèi) 在 聯(lián) 系 ， 使 得 以 關(guān) 系 數(shù) 據(jù) 庫 為 基 礎(chǔ) 的 推 理系 統(tǒng) 和 知 識(shí) 庫 系 統(tǒng) 的 研 究 提 供 了 良 好 的 基 礎(chǔ) 。 2.2.3 E-R模 型 向 關(guān) 系 模 型 的 轉(zhuǎn) 換n 從 E-R模 型 向 關(guān) 系 模 型 轉(zhuǎn) 換 時(shí) ， 所 有 實(shí)

28、 體 和 聯(lián)系 都 要 轉(zhuǎn) 換 成 相 應(yīng) 的 關(guān) 系 模 式 ， 轉(zhuǎn) 換 規(guī) 則 為 ：n (1) 每 個(gè) 實(shí) 體 類 型 轉(zhuǎn) 換 成 一 個(gè) 關(guān) 系 模 式 ；n (2) 一 個(gè) 1:1的 聯(lián) 系 可 轉(zhuǎn) 換 為 一 個(gè) 關(guān) 系 模 式 ， 或 與 任意 一 端 的 關(guān) 系 模 式 合 并 ， 若 獨(dú) 立 轉(zhuǎn) 換 為 一 個(gè) 關(guān) 系 模式 ， 那 么 ， 兩 端 關(guān) 系 的 碼 及 聯(lián) 系 的 屬 性 為 該 關(guān) 系 的屬 性 ； 若 與 一 端 合 并 ， 那 么 將 另 一 端 的 碼 及 聯(lián) 系 的屬 性 合 并 到 該 端 。 2.2.3 E-R模 型 向 關(guān) 系 模 型 的 轉(zhuǎn)

29、換n (3) 一 個(gè) 1:n的 聯(lián) 系 可 轉(zhuǎn) 換 為 一 個(gè) 關(guān) 系 模 式 ，或 與 n端 的 關(guān) 系 模 式 合 并 。 若 獨(dú) 立 轉(zhuǎn) 換 為 一個(gè) 關(guān) 系 模 式 ， 那 么 ， 兩 端 關(guān) 系 的 碼 及 聯(lián) 系 的屬 性 為 關(guān) 系 的 屬 性 ， 而 n端 的 碼 為 關(guān) 系 的 碼 。n (4) 一 個(gè) n:m的 聯(lián) 系 可 轉(zhuǎn) 換 為 一 個(gè) 關(guān) 系 模 式 ，那 么 ， 兩 端 關(guān) 系 的 碼 及 聯(lián) 系 的 屬 性 為 關(guān) 系 的屬 性 ， 而 關(guān) 系 的 碼 為 兩 端 實(shí) 體 的 碼 的 組 合 。 2.2.3 E-R模 型 向 關(guān) 系 模 型 的 轉(zhuǎn) 換n (5)

30、 三 個(gè) 或 三 個(gè) 以 上 多 對 多 的 聯(lián) 系 可 轉(zhuǎn) 換 為一 個(gè) 關(guān) 系 模 式 ， 那 么 ， 諸 關(guān) 系 的 碼 及 聯(lián) 系 的屬 性 為 關(guān) 系 的 屬 性 ， 而 關(guān) 系 的 碼 為 各 實(shí) 體 的碼 的 組 合 。n (6) 具 有 相 同 碼 的 關(guān) 系 可 以 合 并 。 舉 例 S CCLASSSCm nCTn 1Sno SnameSage Sex SD Grade Cno Cname PcnoDate CLno CLnameTel【 例 2.3】 將 圖 2-3的 E-R圖 轉(zhuǎn) 換 成 關(guān) 系 模 式 。圖 2-3 學(xué) 生 班 級 課 程 的 E-R圖 舉 例n 從

31、 圖 中 可 以 看 出 有 3個(gè) 實(shí) 體 :學(xué) 生 S 、 課 程 C 、 班級 CLASS， 根 據(jù) 轉(zhuǎn) 換 規(guī) 則 轉(zhuǎn) 換 成 3個(gè) 關(guān) 系 模 式 。 聯(lián)系 CT是 一 個(gè) 1:n類 型 ， 根 據(jù) 轉(zhuǎn) 換 規(guī) 則 可 將 CLASS的碼 CLno， 加 上 聯(lián) 系 的 屬 性 Date并 入 n端 。 聯(lián) 系 SC是 一 個(gè) n:m 類 型 ， 根 據(jù) 轉(zhuǎn) 換 規(guī) 則 轉(zhuǎn) 換 成 一 個(gè) 獨(dú) 立的 關(guān) 系 模 式 ， 所 以 將 S的 碼 Sno和 C的 碼 Cno， 加 上聯(lián) 系 的 屬 性 Grade作 為 關(guān) 系 SC的 屬 性 ， 該 關(guān) 系 的碼 是 Sno和 Cno 。

32、舉 例n 根 據(jù) 上 述 分 析 轉(zhuǎn) 換 的 關(guān) 系 模 式 如 下 ：n S(Sno， Sname， SD， Sage， Sex， CLno， Date)n C(Cno， Cname， Pcno)n CLASS(CLno， CLname， Tel) 2 3 關(guān) 系 運(yùn) 算2.3.1關(guān) 系 代 數(shù) 的 五 種 基 本 運(yùn) 算n 關(guān) 系 代 數(shù) 運(yùn) 算 符 有 四 類 ：n 集 合 運(yùn) 算 符n 專 門 的 關(guān) 系 運(yùn) 算 符n 算 術(shù) 比 較 符n 邏 輯 運(yùn) 算 符n 根 據(jù) 運(yùn) 算 符 的 不 同 ， 關(guān) 系 代 數(shù) 運(yùn) 算 可 分 為 n 傳 統(tǒng) 的 集 合 運(yùn) 算n 專 門 的 關(guān) 系

33、 運(yùn) 算 2 3 關(guān) 系 運(yùn) 算n 傳 統(tǒng) 的 集 合 運(yùn) 算 是 從 關(guān) 系 的 水 平 方 向 進(jìn)行 的 ， 包 括 ： 并 、 交 、 差 及 廣 義 笛 卡 爾積 。n 專 門 的 關(guān) 系 運(yùn) 算 既 可 以 從 關(guān) 系 的 水 平 方向 進(jìn) 行 運(yùn) 算 ， 又 可 以 向 關(guān) 系 的 垂 直 方 向運(yùn) 算 ， 包 括 ： 選 擇 、 投 影 、 連 接 以 及 除法 。 如 表 2-1所 示 。 表 2-1 1. 并 （ Union）n 關(guān) 系 R與 S具 有 相 同 的 關(guān) 系 模 式 ， 即 R與 S的 元 數(shù) 相同 （ 結(jié) 構(gòu) 相 同 ） 。 關(guān) 系 R與 S并 由 屬 于 R

34、或 屬 于 S的元 組 構(gòu) 成 的 集 合 組 成 ， 記 作 ， 其 形 式 定 義 如下 ：n 式 中 t 為 元 組 變 量 。 SR StRt|tSR 2.差 （ Difference）n 關(guān) 系 R與 S具 有 相 同 的 關(guān) 系 模 式 ， 關(guān) 系 R與 S的 差 由屬 于 R但 不 屬 于 S的 元 組 構(gòu) 成 的 集 合 ， 記 作 ，其 形 式 定 義 如 下 ： R-S StRt|tR-S 3.廣 義 笛 卡 爾 積（ Extended Cartesian Product）n 兩 個(gè) 元 數(shù) 分 別 為 n目 和 m目 的 關(guān) 系 R 和 S 的 廣 義 笛卡 爾 積 是

35、一 個(gè) （ n+m） 列 的 元 組 的 集 合 。 元 組 的前 n列 是 關(guān) 系 R的 一 個(gè) 元 組 ， 后 m列 是 關(guān) 系 S的 一 個(gè)元 組 。 記 作 ， 其 形 式 定 義 如 下 ： n 如 果 R和 S中 有 相 同 的 屬 性 名 ， 可 在 屬 性 名 前 加 關(guān)系 名 作 為 限 定 。 若 R 有 K1個(gè) 元 組 ， S 有 K2個(gè) 元 組 。則 R和 S的 廣 義 笛 卡 爾 積 有 個(gè) 元 組 。SR StRtttt|tSR mnmn , 21 kk 4.投 影 （ Projection）n 投 影 運(yùn) 算 是 從 關(guān) 系 的 垂 直 方 向 進(jìn) 行 運(yùn) 算 ，

36、 在 關(guān) 系R中 選 擇 出 若 干 屬 性 列 A組 成 新 的 關(guān) 系 ， 記作 ， 其 形 式 定 義 如 下 ： RA R|tAtR A 5.選 擇 （ Selection）n 選 擇 運(yùn) 算 是 從 關(guān) 系 的 水 平 方 向 進(jìn) 行 運(yùn) 算 ， 是從 關(guān) 系 R中 選 擇 滿 足 給 定 條 件 的 諸 元 組 ， 記作 ， 其 形 式 定 義 如 下 ：n 其 中 ， F中 的 運(yùn) 算 對 象 是 屬 性 名 (或 列 的 序 號(hào) )或 常 數(shù) ， 運(yùn) 算 符 算 術(shù) 比 較 府 （ ， ，=， )和 邏 輯 運(yùn) 算 符 ( ， ， ) 。 RF TruetFRt|tR F 5.

37、選 擇 （ Selection）n 例 如 ， 表 示 選 取 R關(guān) 系 中 第 一 個(gè) 屬 性值 大 于 等 于 第 六 個(gè) 屬 性 值 的 元 組 ； 表 示 選 取 R關(guān) 系 中 第 一 個(gè) 屬 性 值 大 于 等 于“ 6”的 元 組 。 )(61 R )(61 R 舉 例 【 例 2.4】 設(shè) 有 關(guān) 系 R、 S如 圖 2-4所 示 ， 請 求 出 ：SR SR SR RCA, RBA SR43 舉 例n 解 : 結(jié) 果 如 圖 2-5所 示 。 其 中 ， 后 生 成 的 關(guān) 系 屬 性名 有 重 復(fù) ， 按 照 關(guān) 系 “ 屬 性 不 能 重 名 ” 的 性 質(zhì) ， 通常 采

38、用 “ 關(guān) 系 名 .屬 性 名 ” 的 格 式 。 對 于 的含 義 是 后 “ 選 取 第 三 個(gè) 屬 性 值 小 于 第 四 個(gè) 屬性 值 ” 的 元 組 。 由 于 的 第 三 個(gè) 屬 性 為 R.C，第 四 個(gè) 屬 性 是 S.A， 因 此 的 含 義 也 是 后 “ 選 取 R.C值 小 于 S.A值 ” 的 元 組 。SR SR SR RCA, RBA SR43SRSR )( 43 SR )(43 SR SRSR 圖 2-5 運(yùn) 算 結(jié) 果 2.3.2關(guān) 系 代 數(shù) 的 組 合 運(yùn) 算n 擴(kuò) 展 的 關(guān) 系 運(yùn) 算 可 以 從 基 本 的 關(guān) 系 運(yùn) 算 中導(dǎo) 出 。 主 要 包

39、 括 ： 選 擇 、 投 影 、 連 接 、 除法 、 廣 義 笛 卡 爾 積 、 外 聯(lián) 接 。 1.交 （ Intersection）n 關(guān) 系 R與 S具 有 相 同 的 關(guān) 系 模 式 ， 關(guān) 系 R與 S的 交 由 屬 于 R同 時(shí) 又 屬 于 S的 元 組 構(gòu) 成 的 集合 ， 關(guān) 系 R與 S的 交 記 作 ， 其 形 式 定 義如 下 ：n 顯 然 ， 或 者SR | StRttSR )( SRRSR )( RSSSR 2. 連 接 （ Join）n 連 接 分 為 ：n 連 接n 等 值 連 接n 自 然 連 接n 連 接 運(yùn) 算 是 從 兩 個(gè) 關(guān) 系 R和 S的 笛 卡

40、爾 積 中 選取 滿 足 條 件 的 元 組 。 笛 卡 爾 積 是 無 條 件 連 接 ，其 它 的 連 接 操 作 認(rèn) 為 是 有 條 件 連 接 。 下 面 分述 如 下 。 2. 連 接 （ Join）n (1) 連 接 ： 從 R與 S的 笛 卡 爾 積 中 選 取 屬 性 間 滿 足 一定 條 件 的 元 組 。 記 作 ：n 其 中 :“ ”為 連 接 條 件 ， 是 比 較 運(yùn) 算 符 ， X和 Y分 別 為 R和 S上 度 數(shù) 相 等 且 可 比 的 屬 性 組 。 表 示R中 元 組 的 相 應(yīng) 屬 性 X的 一 個(gè) 分 量 。 表 示 S中 元 組 的 相 應(yīng) 屬 性 Y

41、的 一 個(gè) 分 量 。 , YtXtStRtttt|tSR mnmnmnYX YX Xt nnt Xtnmt (1) 連 接 ：n 需 要 說 明 的 是 :連 接 也 可 以 表 示 為 ：n 其 中 :i=1， 2， 3， ， n， j=1， 2， 3， ， m 。 “ ” 的 含 義 為 從 兩 個(gè) 關(guān) 系 R和 S中 選 取 R的 第 i列 和S的 第 j列 之 間 滿 足 運(yùn) 算 的 元 組 進(jìn) 行 連 接 。 n 連 接 可 以 由 基 本 的 關(guān) 系 運(yùn) 算 笛 卡 兒 積 和 選 取 運(yùn) 算 導(dǎo)出 ， 因 此 可 表 示 為 : 或 , jtitStRtttt|tSR mnmn

42、mnji ji )( SRSR YXYX )()( SRSR jri 舉 例【 例 2.5】 設(shè) 有 關(guān) 系 R， S如 圖 2-4所 示 ， 求 ： 。n 解 :本 題 連 接 的 條 件 為 R.AS.B， 意 為 將 R關(guān) 系 中 屬 性 A的 值 小 于 S關(guān) 系 中 屬 性 B的 值 的 元 組 取 出 來 作 為 結(jié) 果 集的 元 組 。 結(jié) 果 集 為 后 選 出 滿 足 條 件 的 元 組 ， 并且 結(jié) 果 集 的 屬 性 為 R.A， R.B， R.C， S.A， S.B， S.C 。結(jié) 果 如 圖 2-6所 示 。 圖 2-6 SR SR BSAR . SR BSAR .

43、2. 連 接 （ Join）n (2)等 值 連 接 ： 當(dāng) 為 “ =”時(shí) ,稱 之 為 等 值 連接 ,記 為 ,其 形 式 定 義 如 下 : , YtXtStRtttt|tSR mnmnmnYX SR YX 2. 連 接 （ Join）n (3)自 然 連 接 : 是 一 種 特 殊 的 等 值 連 接 ， 它 要求 兩 個(gè) 關(guān) 系 中 進(jìn) 行 比 較 的 分 量 必 須 是 相 同 的屬 性 組 ， 并 且 在 結(jié) 果 中 將 重 復(fù) 屬 性 列 去 掉 。記 為 ， 其 形 式 定 義 如 下 :SR nnmnmn BSBRBSBRBSBRStRtttt|tSR ., 2211 （

44、 3） 自 然 連 接n 自 然 連 接 可 以 由 基 本 的 關(guān) 系 運(yùn) 算 投 影 、 選 取和 笛 卡 兒 積 導(dǎo) 出 。n 注 意 ： 一 般 連 接 是 從 關(guān) 系 的 水 平 方 向 運(yùn) 算 ，而 自 然 連 接 不 僅 要 從 關(guān) 系 的 水 平 方 向 ， 而 且要 從 關(guān) 系 的 垂 直 方 向 運(yùn) 算 。 因 為 自 然 連 接 要去 掉 重 復(fù) 屬 性 ， 如 果 沒 有 重 復(fù) 屬 性 ， 那 麼 自然 連 接 就 轉(zhuǎn) 化 為 笛 卡 兒 積 。 舉 例 ：【 例 2.6】 設(shè) 有 關(guān) 系 如 圖 2-7所 示 ,求 ： 。SR 舉 例 ：n 解 ： 本 題 要 求

45、R與 S的 自 然 連 接 ， 自 然 連 接 是 一 種 特殊 的 等 值 連 接 ， 它 要 求 兩 個(gè) 關(guān) 系 中 進(jìn) 行 比 較 的 分 量 必須 是 相 同 的 屬 性 組 ， 并 且 在 結(jié) 果 中 將 重 復(fù) 屬 性 列 去 掉 。本 題 R與 S關(guān) 系 中 相 同 的 屬 性 組 為 AC， 因 此 ， 結(jié) 果 集中 的 屬 性 列 應(yīng) 為 ABCD 。 其 結(jié) 果 如 圖 2-8所 示 。 3. 除 （ Division）n 除 運(yùn) 算 是 同 時(shí) 從 關(guān) 系 的 水 平 方 向 和 垂 直 方 向 進(jìn) 行 運(yùn)算 。 給 定 關(guān) 系 R(X， Y)和 S(Y， Z)， X，

46、Y， Z為 屬 性組 。 應(yīng) 當(dāng) 滿 足 元 組 在 X上 的 分 量 值 x的 象 集 Yx包 含 關(guān) 系 S在 屬 性 組 Y上 投 影 的 集 合 。 其 形 式 定 義 如下 ： n 其 中 : Yx為 x在 R中 的 象 集 ， x= ， 且 的 結(jié)果 集 的 屬 性 組 為 X 。 xynn YSRtXtSR |SR SRXtn 舉 例n 【 例 2.7】 設(shè) 有 關(guān) 系 R、 S如 圖 2-9（ a） （ b）所 示 ， 求 ： 。SR 舉 例n 解 :n 根 據(jù) 除 法 定 義 ， 此 題 的 X為 屬 性 AB， Y為 屬 性CD 。 應(yīng) 當(dāng) 滿 足 元 組 在 屬 性 AB

47、上 的 分 量值 x的 象 集 Yx包 含 關(guān) 系 S在 CD上 投 影 的 集 合 。 SR 舉 例n 關(guān) 系 S在 Y上 的 投 影 為 =(c， d)， (e， f) 。對 于 關(guān) 系 R， 屬 性 組 X(即 AB)可 以 取 3個(gè) 值 (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)，

48、所 以 ， =(a， b)， (c， k)， 結(jié) 果 如 圖 2-9(c)所 示 。SR )(SCD )(SCD 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算n 外 連 接 運(yùn) 算 是 連 接 運(yùn) 算 的 擴(kuò) 展 ， 可 以 處 理 缺失 的 信 息 。 對 于 圖 2-10的 S和 SC關(guān) 系 ， 對 其進(jìn) 行 自 然 連 接 時(shí) ， 結(jié) 果 如 圖 2-11所 示 。 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算n 由 圖 2-11可 以 看 出 S與 SC的 自 然 連 接 的 結(jié)果 丟 失 了 黎 明 、 劉 明 遠(yuǎn) 、 趙 國

49、 慶 的 相 關(guān) 信息 。 使 用 外 連 接 可 以 避 免 這 樣 的 信 息 丟 失 。外 連 接 運(yùn) 算 有 3種 ：n 左 外 連 接 n 右 外 連 接n 全 外 連 接 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算n 1)左 外 連 接 (left outer join) n 取 出 左 側(cè) 關(guān) 系 中 所 有 與 右 側(cè) 關(guān) 系 中 任 一 元 組 都 不匹 配 的 元 組 ， 用 空 值 null 填 充 所 有 來 自 右 側(cè) 關(guān) 系的 屬 性 ， 構(gòu) 成 新 的 元 組 ， 將 其 加 入 自 然 連 接 的 結(jié)果 中 。 對 于 圖 2-10的 S和 SC關(guān) 系 ，

50、 對 其 進(jìn) 行 左 外連 接 S SC時(shí) ， 結(jié) 果 如 圖 2-12所 示 。 圖 2-12 S SC 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算n 2)右 外 連 接 (right outer join) n 取 出 右 側(cè) 關(guān) 系 中 所 有 與 左 側(cè) 關(guān) 系 中 任 一 元 組 都不 匹 配 的 元 組 ， 用 空 值 null填 充 所 有 來 自 左 側(cè)關(guān) 系 的 屬 性 ， 構(gòu) 成 新 的 元 組 ， 將 其 加 入 自 然 連接 的 結(jié) 果 中 。 對 于 圖 2-10的 S和 SC關(guān) 系 ， 對 其進(jìn) 行 左 外 連 接 S SC時(shí) ， 結(jié) 果 如 圖 2-13所

51、示 。 圖 2-13 S SC 2.3.3關(guān) 系 代 數(shù) 的 外 連 接 運(yùn) 算n 3)全 外 連 接 (right outer join) n 填 充 左 側(cè) 關(guān) 系 中 所 有 與 右 側(cè) 關(guān) 系 中 任 一 元 組都 不 匹 配 的 元 組 ， 又 填 充 右 側(cè) 關(guān) 系 中 所 有 與左 側(cè) 關(guān) 系 中 任 一 元 組 都 不 匹 配 的 元 組 ， 將 產(chǎn)生 的 新 元 組 加 入 自 然 連 接 的 結(jié) 果 中 。 2.3.4關(guān) 系 代 數(shù) 運(yùn) 算 舉 例n 【 例 2. 8】 設(shè) 學(xué) 生 課 程 數(shù) 據(jù) 庫 中 有 ： 學(xué) 生 S、 課 程 C、 學(xué)生 選 課 SC三 個(gè) 關(guān) 系

52、 ， 如 圖 2-14 所 示 。 請 用 關(guān) 系 代 數(shù) 表達(dá) 式 表 達(dá) 如 下 檢 索 問 題 。n （ 1） 檢 索 選 修 課 程 名 為 “ 數(shù) 學(xué) ” 的 學(xué) 生 號(hào) 和 學(xué) 生 姓名 。n （ 2） 檢 索 至 少 選 修 了 課 程 號(hào) 為 “ 1”和 “ 3”的 學(xué) 生 號(hào) 。n （ 3） 檢 索 選 修 了 “ 操 作 系 統(tǒng) ” 或 “ 數(shù) 據(jù) 庫 ” 課 程的 學(xué) 號(hào) 和 成 績 。 n （ 4） 檢 索 年 齡 在 18到 20之 間 （ 含 18和 20） 的 女 生的 學(xué) 號(hào) 、 姓 名 及 年 齡 。n （ 5） 檢 索 選 修 全 部 課 程 的 學(xué) 生 姓

53、 名 及 所 在 的 系 。n （ 6） 檢 索 選 修 課 程 包 括 “ 1042”學(xué) 生 所 學(xué) 的 課 程 的學(xué) 生 學(xué) 號(hào) 。 圖 2-14 S， C SC關(guān) 系 2 4查 詢 優(yōu) 化2.4.1關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化 問 題n 查 詢 處 理 ： 是 指 從 數(shù) 據(jù) 庫 中 提 取 數(shù) 據(jù) 的 一 系列 活 動(dòng) 。 這 一 系 列 活 動(dòng) 包 括 ： 將 高 級 數(shù) 據(jù) 庫語 言 表 示 的 查 詢 語 句 翻 譯 成 為 能 在 文 件 系 統(tǒng)這 一 物 理 層 次 上 實(shí) 現(xiàn) 的 表 達(dá) 式 ， 為 優(yōu) 化 查 詢進(jìn) 行 各 種 轉(zhuǎn) 換 ， 以 及 查 詢 的 實(shí)

54、 際 執(zhí) 行 。 2 4查 詢 優(yōu) 化n 查 詢 處 理 的 代 價(jià) ： 通 常 取 決 于 磁 盤 的 訪 問 ，磁 盤 的 訪 問 比 內(nèi) 存 訪 問 速 度 要 慢 。 對 于 一 個(gè)給 定 的 查 詢 ， 可 以 有 許 多 可 能 的 處 理 策 略 ，復(fù) 雜 查 詢 更 是 如 此 。 就 所 需 的 磁 盤 訪 問 次 數(shù)而 言 ， 策 略 好 壞 差 別 很 大 ， 有 時(shí) 甚 至 相 差 幾個(gè) 數(shù) 量 級 。 所 以 ， 系 統(tǒng) 多 花 一 點(diǎn) 時(shí) 間 選 擇 一個(gè) 較 好 的 查 詢 策 略 是 很 值 得 的 。 2.4.1關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化 問 題n

55、 查 詢 優(yōu) 化 ： 是 為 了 查 詢 選 擇 最 有 效 的 查 詢 計(jì)劃 的 過 程 。 查 詢 優(yōu) 化 一 方 面 是 在 關(guān) 系 代 數(shù) 級進(jìn) 行 優(yōu) 化 ， 要 做 的 是 力 圖 找 出 與 給 定 表 達(dá) 式等 價(jià) ， 但 執(zhí) 行 效 率 更 高 的 一 個(gè) 表 達(dá) 式 。 查 詢優(yōu) 化 的 另 一 方 面 涉 及 查 詢 語 句 處 理 的 詳 細(xì) 策略 的 選 擇 ， 例 如 選 擇 執(zhí) 行 運(yùn) 算 所 采 用 的 具 體算 法 以 及 將 使 用 的 特 定 索 引 等 等 。 2.4.2關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n 1 優(yōu) 化 的 準(zhǔn) 則n

56、(1) 提 早 執(zhí) 行 選 取 運(yùn) 算 。 對 于 有 選 擇 運(yùn) 算 的 表 達(dá)式 ， 應(yīng) 優(yōu) 化 成 盡 可 能 先 執(zhí) 行 選 擇 運(yùn) 算 的 等 價(jià) 表 達(dá)式 ， 以 得 到 較 小 的 中 間 結(jié) 果 ， 減 少 運(yùn) 算 量 和 從 外存 讀 塊 的 次 數(shù) 。n (2) 合 并 乘 積 與 其 后 的 選 擇 運(yùn) 算 為 連 接 運(yùn) 算 。 在表 達(dá) 式 中 ， 當(dāng) 乘 積 運(yùn) 算 后 是 選 擇 運(yùn) 算 時(shí) ， 應(yīng) 該 合并 為 連 接 運(yùn) 算 ， 使 選 擇 與 乘 積 一 道 完 成 ， 以 避 免做 完 乘 積 后 ， 需 再 掃 描 一 個(gè) 大 的 乘 積 關(guān) 系 進(jìn) 行

57、 選擇 運(yùn) 算 。 1 優(yōu) 化 的 準(zhǔn) 則n (3) 將 投 影 運(yùn) 算 與 其 后 的 其 它 運(yùn) 算 同 時(shí) 進(jìn) 行 ， 以避 免 重 復(fù) 掃 描 關(guān) 系 。n (4) 將 投 影 運(yùn) 算 和 其 前 后 的 二 目 運(yùn) 算 結(jié) 合 起 來 ，使 得 沒 有 必 要 為 去 掉 某 些 字 段 再 掃 描 一 遍 關(guān) 系 。 1 優(yōu) 化 的 準(zhǔn) 則n (5) 在 執(zhí) 行 連 接 前 對 關(guān) 系 適 當(dāng) 地 預(yù) 處 理 ， 就 能 快速 地 找 到 要 連 接 的 元 組 。 方 法 有 兩 種 ： 索 引 連 接法 、 排 序 合 并 連 接 法 。n (6) 存 儲(chǔ) 公 共 子 表 達(dá)

58、式 。 對 于 有 公 共 子 表 達(dá) 式 的結(jié) 果 應(yīng) 存 于 外 存 （ 中 間 結(jié) 果 ） ， 這 樣 ， 當(dāng) 從 外 存讀 出 它 的 時(shí) 間 比 計(jì) 算 的 時(shí) 間 少 時(shí) ， 就 可 節(jié) 約 操 作時(shí) 間 。 2.關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n 優(yōu) 化 的 策 略 均 涉 及 關(guān) 系 代 數(shù) 表 達(dá) 式 ， 所 以 討論 關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則 顯 得 十 分重 要 。 常 用 的 等 價(jià) 變 換 規(guī) 則 有 如 下 10種 ：n （ 1） 連 接 、 笛 卡 爾 積 交 換 率 n 設(shè) E1和 E2是 關(guān) 系 代 數(shù) 表

59、達(dá) 式 ， F是 連 接 運(yùn) 算 的條 件 ， 則 有 12211221 EEEEEEEE FF 2.關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 2） 連 接 、 笛 卡 爾 積 結(jié) 合 率n 設(shè) E1， E2， E3是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， F1， F2是 連 接運(yùn) 算 的 條 件 ， 則 有 )()( )()( 321321 321321 EEEEEE EEEEEE FFFF 2.關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 3） 投 影 的 串 接 定 律n 設(shè) E是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， A1， ， An和 B1， ，Bm ， 且

60、B1， ， Bm是 A1， ， An的 子 集 ， 則 有 n 該 規(guī) 則 的 目 的 是 使 一 些 投 影 消 失 。 )()( , 111 EE nmn AABBAA 2.關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 4） 選 擇 的 串 接 定 律n 設(shè) E是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， F1， F2是 選 取 條 件表 達(dá) 式 ， 選 擇 的 串 接 定 律 說 明 選 擇 條 件 可 以合 并 ， 則 有 )()( 2121 EE FFFF 2.關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 5） 選 擇 與 投 影 的 交 換 律n 設(shè) E是 關(guān)

61、 系 代 數(shù) 表 達(dá) 式 ， F是 選 取 條 件 表 達(dá)式 ， 并 且 只 涉 及 A1， ， An屬 性 ， 則 有)()( , 11 EE FAAAAF nn 2 關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 6） 選 擇 與 笛 卡 爾 積 的 交 換 律n 若 F涉 及 的 都 是 E1中 的 屬 性 ， 則n 如 果 F=F1 F2， 并 且 F1只 涉 及 中 E1的 屬 性 ， F2只 涉 及 E2中 的 屬 性 ， 則 有 2121 )()( EEEE FF )()()( 2121 21 EEEE FFF 2 關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī)

62、 則n （ 7） 選 擇 與 并 的 交 換 律n 設(shè) E=E1 E2 ， E1， E2有 相 同 的 屬 性 ， 則n （ 8） 選 擇 與 差 的 交 換 律 n 設(shè) E1， E2有 相 同 的 屬 性 ， 則 )()()( 2121 EEEE FFF )()()( 2121 EEEE FFF 2 關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) 變 換 規(guī) 則n （ 9） 投 影 與 笛 卡 爾 積 的 交 換 律n 設(shè) E1， E2是 兩 個(gè) 關(guān) 系 代 數(shù) 表 達(dá) 式 ， A1， ， An是 E1中 的 屬 性 ， B1， ， Bm是 E2中 的 屬 性 ， 則n （ 10） 投 影 與 并

63、的 交 換 律 n 設(shè) E1， E2有 相 同 的 屬 性 ， 則 )()()( 2,1,21, 1111 EEEE mnmn BBAABBAA )()()( 2,1,21, 111 EEEE nnn AAAAAA 2.4.3關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化 算 法n 算 法 ： 關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化n 輸 入 ： 一 個(gè) 關(guān) 系 代 數(shù) 表 達(dá) 式 的 語 法 樹n 輸 出 ： 計(jì) 算 該 表 達(dá) 式 的 程 序 。 n 方 法 ：n （ 1） 利 用 規(guī) 則 4將 形 如 變 換 為 ：n （ 2） 對 每 一 選 擇 ， 用 規(guī) 則 48盡 可 能 將 它 移 到

64、 樹的 葉 端 。n （ 3） 對 每 一 個(gè) 投 影 ， 利 用 規(guī) 則 3、 9， 10， 5中 的一 般 形 式 盡 可 能 將 它 移 到 樹 的 葉 端 。)(21 EnFFF )( 21 EnFFF 2.4.3關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化 算 法 n （ 4） 利 用 規(guī) 則 35將 選 擇 和 投 影 的 串 接 合 并 成 單 個(gè)選 擇 、 單 個(gè) 投 影 或 一 個(gè) 選 擇 后 跟 一 個(gè) 投 影 。 使 多 個(gè)選 擇 或 投 影 能 同 時(shí) 進(jìn) 行 ， 或 在 一 次 掃 描 中 全 部 完 成 。n （ 5） 將 上 述 得 到 的 語 法 樹 的 內(nèi) 節(jié) 點(diǎn)

65、分 組 。 每 一 雙 目運(yùn) 算 ( ， ， ， -)和 它 所 有 的 直 接 祖 先 為 一 組（ 這 些 直 接 祖 先 是 ， 運(yùn) 算 ） 。 如 果 其 后 代 直 到 葉子 全 部 是 單 目 運(yùn) 算 ， 則 將 它 并 入 該 組 。方 法 ： n （ 6） 生 成 一 個(gè) 程 序 ， 每 組 節(jié) 點(diǎn) 的 計(jì) 算 是程 序 中 的 一 步 。 各 步 的 順 序 是 任 意 的 ， 只要 保 證 任 何 一 組 的 計(jì) 算 不 會(huì) 在 它 的 后 代 組之 前 計(jì) 算 。方 法 ： 舉 例n 【 例 2.12】 供 應(yīng) 商 數(shù) 據(jù) 庫 中 有 ： 供 應(yīng) 商 、 零件 、 項(xiàng) 目

66、 、 供 應(yīng) 四 個(gè) 基 本 表 （ 關(guān) 系 ） ：nS(Sno，Sname，Status，City)nP(Pno，Pname，Color，Weight)nJ(Jno，Jname，City) nSPJ(Sno，Pno，Jno，Qty) 舉 例n 用 戶 有 一 查 詢 語 句 ： 檢 索 使 用 上 海 供 應(yīng) 商 生產(chǎn) 的 紅 色 零 件 的 工 程 號(hào) 。n (1) 試 寫 出 該 查 詢 的 關(guān) 系 代 數(shù) 表 達(dá) 式 ；n (2) 試 寫 出 查 詢 優(yōu) 化 的 關(guān) 系 代 數(shù) 表 達(dá) 式 ；n (3) 畫 出 該 查 詢 初 始 的 關(guān) 系 代 數(shù) 表 達(dá) 式 的 語 法 樹 ； n (4) 使 用 優(yōu) 化 算 法 ， 對 語 法 樹 進(jìn) 行 優(yōu) 化 ， 并 畫 出優(yōu) 化 后 的 語 法 樹 。 舉 例解 :n (1)該 查 詢 的 關(guān) 系 代 數(shù) 表 達(dá) 式 如 下 :n (2)查 詢 優(yōu) 化 的 關(guān) 系 代 數(shù) 表 達(dá) 式 如 下 : n (3)該 查 詢 初 始 的 關(guān) 系 代 數(shù) 表 達(dá) 式 的 語 法 樹 如 圖 2-221所 示 。n (4)優(yōu) 化 后 的 語 法