《關(guān)系數(shù)據(jù)理論》PPT課件

《《關(guān)系數(shù)據(jù)理論》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《關(guān)系數(shù)據(jù)理論》PPT課件（121頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、An Introduction to Database System 中 國 人 民 大 學(xué) 信 息 學(xué) 院 數(shù) 據(jù) 庫 系 統(tǒng) 概 論An Introduction to Database System第 六 章 關(guān) 系 數(shù) 據(jù) 理 論 An Introduction to Database System 第 六 章 關(guān) 系 數(shù) 據(jù) 理 論6.1 問 題 的 提 出6.2 規(guī) 范 化6.3 數(shù) 據(jù) 依 賴 的 公 理 系 統(tǒng)*6.4 模 式 的 分 解6.5 小 結(jié) An Introduction to Database System 6.1 問 題 的 提 出關(guān) 系 數(shù) 據(jù) 庫 邏 輯 設(shè)

2、 計 針 對 具 體 問 題 ， 如 何 構(gòu) 造 一 個 適 合 于 它 的 數(shù) 據(jù) 模 式 數(shù) 據(jù) 庫 邏 輯 設(shè) 計 的 工 具 關(guān) 系 數(shù) 據(jù) 庫 的 規(guī) 范 化 理 論 An Introduction to Database System 問 題 的 提 出一 、 概 念 回 顧二 、 關(guān) 系 模 式 的 形 式 化 定 義三 、 什 么 是 數(shù) 據(jù) 依 賴四 、 關(guān) 系 模 式 的 簡 化 定 義五 、 數(shù) 據(jù) 依 賴 對 關(guān) 系 模 式 影 響 An Introduction to Database System 一 、 概 念 回 顧v關(guān) 系v關(guān) 系 模 式v關(guān) 系 數(shù) 據(jù) 庫v

3、關(guān) 系 數(shù) 據(jù) 庫 的 模 式 An Introduction to Database System 二 、 關(guān) 系 模 式 的 形 式 化 定 義關(guān) 系 模 式 由 五 部 分 組 成 ， 即 它 是 一 個 五 元 組 ： R(U, D, DOM, F)R： 關(guān) 系 名U： 組 成 該 關(guān) 系 的 屬 性 名 集 合D： 屬 性 組 U中 屬 性 所 來 自 的 域DOM： 屬 性 向 域 的 映 象 集 合F： 屬 性 間 數(shù) 據(jù) 的 依 賴 關(guān) 系 集 合 An Introduction to Database System 三 、 什 么 是 數(shù) 據(jù) 依 賴1. 完 整 性 約 束

4、的 表 現(xiàn) 形 式v限 定 屬 性 取 值 范 圍 ： 例 如 學(xué) 生 成 績 必 須 在 0-100之 間v定 義 屬 性 值 間 的 相 互 關(guān) 連 （ 主 要 體 現(xiàn) 于 值 的 相 等 與否 ） ， 這 就 是 數(shù) 據(jù) 依 賴 ， 它 是 數(shù) 據(jù) 庫 模 式 設(shè) 計 的 關(guān) 鍵 An Introduction to Database System 什 么 是 數(shù) 據(jù) 依 賴 （ 續(xù) ）2. 數(shù) 據(jù) 依 賴v一 個 關(guān) 系 內(nèi) 部 屬 性 與 屬 性 之 間 的 約 束 關(guān) 系v現(xiàn) 實 世 界 屬 性 間 相 互 聯(lián) 系 的 抽 象v數(shù) 據(jù) 內(nèi) 在 的 性 質(zhì)v語 義 的 體 現(xiàn) An

5、Introduction to Database System 什 么 是 數(shù) 據(jù) 依 賴 （ 續(xù) ）3. 數(shù) 據(jù) 依 賴 的 類 型v函 數(shù) 依 賴 （ Functional Dependency， 簡 記 為 FD）v多 值 依 賴 （ Multivalued Dependency， 簡 記 為 MVD）v其 他 An Introduction to Database System 四 、 關(guān) 系 模 式 的 簡 化 表 示v關(guān) 系 模 式 R（ U, D, DOM, F） 簡 化 為 一 個 三 元 組 ： R（ U, F）v當(dāng) 且 僅 當(dāng) U上 的 一 個 關(guān) 系 r滿 足 F時 ，

6、r稱 為 關(guān) 系 模 式 R（ U, F） 的 一 個 關(guān) 系 An Introduction to Database System 五 、 數(shù) 據(jù) 依 賴 對 關(guān) 系 模 式 的 影 響例 1建 立 一 個 描 述 學(xué) 校 教 務(wù) 的 數(shù) 據(jù) 庫 ：學(xué) 生 的 學(xué) 號 （ Sno） 、 所 在 系 （ Sdept）系 主 任 姓 名 （ Mname） 、 課 程 名 （ Cname）成 績 （ Grade）單 一 的 關(guān) 系 模 式 ： Student U Sno, Sdept, Mname, Cname, Grade An Introduction to Database System 數(shù)

7、 據(jù) 依 賴 對 關(guān) 系 模 式 的 影 響 （ 續(xù) ） 屬 性 組 U上 的 一 組 函 數(shù) 依 賴 F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade Sno CnameSdept Mname Grade An Introduction to Database System 關(guān) 系 模 式 Student中 存 在 的 問 題1. 數(shù) 據(jù) 冗 余 太 大2. 更 新 異 常 （ Update Anomalies）3. 插 入 異 常 （ Insertion Anomalies）4. 刪 除 異 常 （ Deletion Anomalies） An

8、 Introduction to Database System 數(shù) 據(jù) 依 賴 對 關(guān) 系 模 式 的 影 響 （ 續(xù) ）結(jié) 論 ：n Student關(guān) 系 模 式 不 是 一 個 好 的 模 式 。n “ 好 ” 的 模 式 ：不 會 發(fā) 生 插 入 異 常 、 刪 除 異 常 、 更 新 異 常 ，數(shù) 據(jù) 冗 余 應(yīng) 盡 可 能 少原 因 ： 由 存 在 于 模 式 中 的 某 些 數(shù) 據(jù) 依 賴 引 起 的解 決 方 法 ： 通 過 分 解 關(guān) 系 模 式 來 消 除 其 中 不 合 適 的 數(shù) 據(jù) 依 賴 An Introduction to Database System 分 解

9、關(guān) 系 模 式v把 這 個 單 一 模 式 分 成 3個 關(guān) 系 模 式 ： S（ Sno， Sdept， Sno Sdept） ; SC（ Sno， Cno， Grade， （ Sno， Cno） Grade） ; DEPT（ Sdept， Mname， Sdept Mname） An Introduction to Database System 第 六 章 關(guān) 系 數(shù) 據(jù) 理 論6.1 問 題 的 提 出6.2 規(guī) 范 化6.3 數(shù) 據(jù) 依 賴 的 公 理 系 統(tǒng)*6.4 模 式 的 分 解6.5 小 結(jié) An Introduction to Database System 6.2 規(guī)

10、范 化 規(guī) 范 化 理 論 正 是 用 來 改 造 關(guān) 系 模 式 ， 通 過 分 解 關(guān) 系 模 式 來消 除 其 中 不 合 適 的 數(shù) 據(jù) 依 賴 ， 以 解 決 插 入 異 常 、 刪 除 異 常 、更 新 異 常 和 數(shù) 據(jù) 冗 余 問 題 。 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database Syste

11、m 6.2.1 函 數(shù) 依 賴v函 數(shù) 依 賴v平 凡 函 數(shù) 依 賴 與 非 平 凡 函 數(shù) 依 賴v完 全 函 數(shù) 依 賴 與 部 分 函 數(shù) 依 賴v傳 遞 函 數(shù) 依 賴 An Introduction to Database System 一 、 函 數(shù) 依 賴定 義 6.1 設(shè) R(U)是 一 個 屬 性 集 U上 的 關(guān) 系 模 式 ， X和 Y是 U的子 集 。 若 對 于 R(U)的 任 意 一 個 可 能 的 關(guān) 系 r， r中 不 可 能 存 在 兩 個 元組 在 X上 的 屬 性 值 相 等 ， 而 在 Y上 的 屬 性 值 不 等 ， 則 稱 “ X函 數(shù) 確 定 Y

12、” 或 “ Y函 數(shù) 依 賴 于 X”， 記 作 XY。 An Introduction to Database System 說 明 1. 所 有 關(guān) 系 實 例 均 要 滿 足2. 語 義 范 疇 的 概 念3. 數(shù) 據(jù) 庫 設(shè) 計 者 可 以 對 現(xiàn) 實 世 界 作 強(qiáng) 制 的 規(guī) 定 An Introduction to Database System 二 、 平 凡 函 數(shù) 依 賴 與 非 平 凡 函 數(shù) 依 賴在 關(guān) 系 模 式 R(U)中 ， 對 于 U的 子 集 X和 Y，如 果 XY， 但 Y X， 則 稱 XY是 非 平 凡 的 函 數(shù) 依 賴若 XY， 但 Y X, 則

13、稱 XY是 平 凡 的 函 數(shù) 依 賴v 例 ： 在 關(guān) 系 SC(Sno, Cno, Grade)中 ， 非 平 凡 函 數(shù) 依 賴 ： (Sno, Cno) Grade 平 凡 函 數(shù) 依 賴 ： (Sno, Cno) Sno (Sno, Cno) Cno An Introduction to Database System 平 凡 函 數(shù) 依 賴 與 非 平 凡 函 數(shù) 依 賴 （ 續(xù) ） 若 XY， 則 X稱 為 這 個 函 數(shù) 依 賴 的 決 定 屬 性 組 ， 也稱 為 決 定 因 素 （ Determinant） 。 若 XY， YX， 則 記 作 XY。 若 Y不 函 數(shù) 依

14、賴 于 X， 則 記 作 XY。 An Introduction to Database System 三 、 完 全 函 數(shù) 依 賴 與 部 分 函 數(shù) 依 賴定 義 6.2 在 R(U)中 ， 如 果 XY， 并 且 對 于 X的 任 何 一 個 真子 集 X， 都 有 X Y, 則 稱 Y對 X完 全 函 數(shù) 依 賴 ， 記 作 X F Y。 若 XY， 但 Y不 完 全 函 數(shù) 依 賴 于 X， 則 稱 Y對 X部 分 函 數(shù)依 賴 ， 記 作 X P Y。 An Introduction to Database System 完 全 函 數(shù) 依 賴 與 部 分 函 數(shù) 依 賴 （ 續(xù)

15、 ）例 1 中 (Sno,Cno)Grade是 完 全 函 數(shù) 依 賴 ， (Sno,Cno)Sdept是 部 分 函 數(shù) 依 賴 因 為 Sno Sdept成 立 ， 且 Sno是 （ Sno， Cno）的 真 子 集 FP An Introduction to Database System 四 、 傳 遞 函 數(shù) 依 賴定 義 6.3 在 R(U)中 ， 如 果 XY， (Y X) ,YX YZ， 則 稱 Z對 X傳 遞 函 數(shù) 依 賴 。 記 為 ： X Z 注 : 如 果 YX， 即 XY， 則 Z直 接 依 賴 于 X。例 : 在 關(guān) 系 Std(Sno, Sdept, Mname

16、)中 ， 有 ： Sno Sdept， Sdept Mname Mname傳 遞 函 數(shù) 依 賴 于 Sno傳 遞 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.2 碼定 義 6.4 設(shè) K為 R中 的 屬 性 或 屬 性 組 合 。 若 K U， 則 K稱 為 R的 侯 選 碼 （ Ca

17、ndidate Key） 。 若 候 選 碼 多 于 一 個 ， 則 選 定 其 中 的 一 個 做 為 主 碼（ Primary Key） 。 F An Introduction to Database System 碼 （ 續(xù) ）v主 屬 性 與 非 主 屬 性 包 含 在 任 何 一 個 候 選 碼 中 的 屬 性 ， 稱 為 主 屬 性 （ Prime attribute） 不 包 含 在 任 何 碼 中 的 屬 性 稱 為 非 主 屬 性 （ Nonprime attribute）或 非 碼 屬 性 （ Non-key attribute） v全 碼 整 個 屬 性 組 是 碼 ，

18、稱 為 全 碼 （ All-key） An Introduction to Database System 碼 （ 續(xù) ）例 2 關(guān) 系 模 式 S(Sno,Sdept,Sage)， 單 個 屬 性 Sno是 碼 ， SC（ Sno， Cno， Grade） 中 ， （ Sno， Cno） 是 碼例 3 關(guān) 系 模 式 R（ P， W， A） P： 演 奏 者 W： 作 品 A： 聽 眾 一 個 演 奏 者 可 以 演 奏 多 個 作 品 某 一 作 品 可 被 多 個 演 奏 者 演 奏 聽 眾 可 以 欣 賞 不 同 演 奏 者 的 不 同 作 品 碼 為 (P， W， A)， 即 All

19、-Key An Introduction to Database System 外 部 碼定 義 6.5 關(guān) 系 模 式 R 中 屬 性 或 屬 性 組 X 并 非 R的 碼 ， 但 X 是 另 一 個 關(guān) 系 模 式 的 碼 ， 則 稱 X 是 R 的 外 部 碼（ Foreign key） 也 稱 外 碼v如 在 SC（ Sno， Cno， Grade） 中 ， Sno不 是 碼 ， 但Sno是 關(guān) 系 模 式 S（ Sno， Sdept， Sage） 的 碼 ， 則Sno是 關(guān) 系 模 式 SC的 外 部 碼 v主 碼 與 外 部 碼 一 起 提 供 了 表 示 關(guān) 系 間 聯(lián) 系 的

20、手 段 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.3 范 式v范 式 是 符 合 某 一 種 級 別 的 關(guān) 系 模 式 的 集 合v關(guān) 系 數(shù) 據(jù) 庫 中 的 關(guān) 系 必 須 滿 足 一 定 的 要 求 。 滿 足 不 同 程 度要 求 的 為 不 同 范 式v范 式 的 種 類 ：

21、第 一 范 式 (1NF)第 二 范 式 (2NF)第 三 范 式 (3NF)BC范 式 (BCNF) 第 四 范 式 (4NF)第 五 范 式 (5NF) An Introduction to Database System 6.2.3 范 式v各 種 范 式 之 間 存 在 聯(lián) 系 ：v某 一 關(guān) 系 模 式 R為 第 n范 式 ， 可 簡 記 為 R nNF。v一 個 低 一 級 范 式 的 關(guān) 系 模 式 ， 通 過 模 式 分 解 可 以 轉(zhuǎn) 換 為 若干 個 高 一 級 范 式 的 關(guān) 系 模 式 的 集 合 ， 這 種 過 程 就 叫 規(guī) 范 化 NF5NF4BCNFNF3NF2

22、NF1 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.4 2NFv1NF的 定 義如 果 一 個 關(guān) 系 模 式 R的 所 有 屬 性 都 是 不 可 分 的 基 本 數(shù) 據(jù) 項 ，則 R 1NFv第 一 范 式 是 對 關(guān) 系 模 式 的 最 起 碼 的 要 求 。 不 滿 足 第 一

23、范 式的 數(shù) 據(jù) 庫 模 式 不 能 稱 為 關(guān) 系 數(shù) 據(jù) 庫v但 是 滿 足 第 一 范 式 的 關(guān) 系 模 式 并 不 一 定 是 一 個 好 的 關(guān) 系 模式 An Introduction to Database System 2NF（ 續(xù) ）例 4 關(guān) 系 模 式 S-L-C(Sno, Sdept, Sloc, Cno, Grade) Sloc為 學(xué) 生 住 處 ， 假 設(shè) 每 個 系 的 學(xué) 生 住 在 同 一 個 地 方v函 數(shù) 依 賴 包 括 ： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cn

24、o) P Sloc Sdept Sloc An Introduction to Database System 2NF（ 續(xù) ）v S-L-C的 碼 為 (Sno, Cno)v S-L-C滿 足 第 一 范 式 。 v 非 主 屬 性 Sdept和 Sloc部 分 函 數(shù) 依 賴 于 碼 (Sno, Cno)SnoCnoGrade SdeptSlocS-L-C An Introduction to Database System S-L-C不 是 一 個 好 的 關(guān) 系 模 式 （ 續(xù) ）(1) 插 入 異 常(2) 刪 除 異 常(3) 數(shù) 據(jù) 冗 余 度 大(4) 修 改 復(fù) 雜 An I

25、ntroduction to Database System S-L-C不 是 一 個 好 的 關(guān) 系 模 式 （ 續(xù) ）v原 因 Sdept、 Sloc部 分 函 數(shù) 依 賴 于 碼 。v解 決 方 法 S-L-C分 解 為 兩 個 關(guān) 系 模 式 ， 以 消 除 這 些 部 分 函 數(shù) 依 賴 SC（ Sno， Cno， Grade） S-L（ Sno， Sdept， Sloc） An Introduction to Database System 2NF（ 續(xù) ）函 數(shù) 依 賴 圖 ： SnoCnoGradeSC S-LSno SdeptSlocv關(guān) 系 模 式 SC的 碼 為 （ Sn

26、o， Cno）v關(guān) 系 模 式 S-L的 碼 為 Sno v這 樣 非 主 屬 性 對 碼 都 是 完 全 函 數(shù) 依 賴 An Introduction to Database System 2NF（ 續(xù) ）v2NF的 定 義定 義 6.6 若 R 1NF， 且 每 一 個 非 主 屬 性 完 全 函 數(shù) 依 賴 于碼 ， 則 R 2NF。例 ： S-L-C(Sno, Sdept, Sloc, Cno, Grade) 1NF S-L-C(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（ Sno， Cno， Grade） 2NF S-L（ Sno， Sdept， Sl

27、oc） 2NF An Introduction to Database System 2NF（ 續(xù) ）v采 用 投 影 分 解 法 將 一 個 1NF的 關(guān) 系 分 解 為 多 個 2NF的 關(guān) 系 ，可 以 在 一 定 程 度 上 減 輕 原 1NF關(guān) 系 中 存 在 的 插 入 異 常 、 刪除 異 常 、 數(shù) 據(jù) 冗 余 度 大 、 修 改 復(fù) 雜 等 問 題 。v將 一 個 1NF關(guān) 系 分 解 為 多 個 2NF的 關(guān) 系 ， 并 不 能 完 全 消 除關(guān) 系 模 式 中 的 各 種 異 常 情 況 和 數(shù) 據(jù) 冗 余 。 An Introduction to Database Sy

28、stem 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.5 3NFv3NF的 定 義定 義 6.7 關(guān) 系 模 式 R 中 若 不 存 在 這 樣 的 碼 X、 屬 性組 Y及 非 主 屬 性 Z（ Z Y） , 使 得 XY， YZ成 立 ， Y X， 則 稱 R 3NF。n若 R 3NF， 則 每 一 個 非 主 屬 性 既 不 部 分 依 賴 于 碼

29、也 不傳 遞 依 賴 于 碼 。 An Introduction to Database System 3NF（ 續(xù) ）例 ： 2NF關(guān) 系 模 式 S-L(Sno, Sdept, Sloc)中 函 數(shù) 依 賴 ： SnoSdept Sdept Sno SdeptSloc 可 得 ： SnoSloc， 即 S-L中 存 在 非 主 屬 性 對 碼 的 傳 遞 函 數(shù) 依 賴 ， S-L 3NF 傳 遞 An Introduction to Database System 3NF（ 續(xù) ）函 數(shù) 依 賴 圖 ：S-LSno SdeptSloc An Introduction to Databas

30、e System 3NF（ 續(xù) ）v解 決 方 法 采 用 投 影 分 解 法 ， 把 S-L分 解 為 兩 個 關(guān) 系 模 式 ， 以 消除 傳 遞 函 數(shù) 依 賴 ： S-D（ Sno， Sdept） D-L（ Sdept， Sloc）S-D的 碼 為 Sno， D-L的 碼 為 Sdept。 n 分 解 后 的 關(guān) 系 模 式 S-D與 D-L中 不 再 存 在 傳 遞 依 賴 An Introduction to Database System 3NF（ 續(xù) ）S-D的 碼 為 Sno， D-L的 碼 為 SdeptSno SdeptS-D Sdept SlocD-Lv S-L(Sno

31、, Sdept, Sloc) 2NF S-L(Sno, Sdept, Sloc) 3NF S-D(Sno， Sdept) 3NFD-L(Sdept， Sloc) 3NF An Introduction to Database System 3NF（ 續(xù) ）v 采 用 投 影 分 解 法 將 一 個 2NF的 關(guān) 系 分 解 為 多 個 3NF的 關(guān) 系 ， 可以 在 一 定 程 度 上 解 決 原 2NF關(guān) 系 中 存 在 的 插 入 異 常 、 刪 除 異 常 、數(shù) 據(jù) 冗 余 度 大 、 修 改 復(fù) 雜 等 問 題 。v 將 一 個 2NF關(guān) 系 分 解 為 多 個 3NF的 關(guān) 系 后

32、， 仍 然 不 能 完 全 消 除關(guān) 系 模 式 中 的 各 種 異 常 情 況 和 數(shù) 據(jù) 冗 余 。 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.6 BC范 式 （ BCNF）v定 義 6.8 關(guān) 系 模 式 R 1NF， 若 XY且Y X時 X必 含 有 碼 ， 則 R BCNF。

33、v等 價 于 ： 每 一 個 決 定 屬 性 因 素 都 包 含 碼 An Introduction to Database System BCNF（ 續(xù) ）v若 R BCNF 所 有 非 主 屬 性 對 每 一 個 碼 都 是 完 全 函 數(shù) 依 賴 所 有 的 主 屬 性 對 每 一 個 不 包 含 它 的 碼 ， 也 是 完 全 函 數(shù)依 賴 沒 有 任 何 屬 性 完 全 函 數(shù) 依 賴 于 非 碼 的 任 何 一 組 屬 性vR BCNF R 3NF充 分 不 必 要 An Introduction to Database System BCNF（ 續(xù) ）例 5 關(guān) 系 模 式 C（

34、 Cno， Cname， Pcno）n C 3NFn C BCNF例 6 關(guān) 系 模 式 S（ Sno， Sname， Sdept， Sage）n 假 定 S有 兩 個 碼 Sno， Snamen S 3NF。 n S BCNF An Introduction to Database System BCNF（ 續(xù) ） 例 7 關(guān) 系 模 式 SJP（ S， J， P）n函 數(shù) 依 賴 ： （ S， J） P； (J， P） Sn（ S， J） 與 （ J， P） 都 可 以 作 為 候 選 碼 ,屬 性 相 交nSJP 3NF，nSJP BCNF An Introduction to Data

35、base System BCNF（ 續(xù) ）例 8在 關(guān) 系 模 式 STJ（ S， T， J） 中 ， S表 示 學(xué) 生 ， T表示 教 師 ， J表 示 課 程 。 函 數(shù) 依 賴 ： (S， J)T， (S， T)J， TJ (S， J)和 (S， T)都 是 候 選 碼 An Introduction to Database System BCNF（ 續(xù) ） JSJ T STSTJ中 的 函 數(shù) 依 賴 An Introduction to Database System BCNF（ 續(xù) ）vSTJ 3NF 沒 有 任 何 非 主 屬 性 對 碼 傳 遞 依 賴 或 部 分 依 賴 vS

36、TJ BCNF T是 決 定 因 素 ， T不 包 含 碼 An Introduction to Database System BCNF（ 續(xù) ）v解 決 方 法 ： 將 STJ分 解 為 二 個 關(guān) 系 模 式 ： ST(S， T) BCNF， TJ(T， J) BCNF 沒 有 任 何 屬 性 對 碼 的 部 分 函 數(shù) 依 賴 和 傳 遞 函 數(shù) 依 賴S JST T JTJ An Introduction to Database System 3NF與 BCNF的 關(guān) 系vR BCNF R 3NFv如 果 R 3NF， 且 R只 有 一 個 候 選 碼 R BCNF R 3NF充 分

37、不 必 要充 分必 要 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.7 多 值 依 賴?yán)?9 學(xué) 校 中 某 一 門 課 程 由 多 個 教 師 講 授 ， 他 們 使 用 相同 的 一 套 參 考 書 。 每 個 教 員 可 以 講 授 多 門 課 程 ， 每種 參 考 書 可 以 供

38、 多 門 課 程 使 用 。 An Introduction to Database System 課 程 C 教 員 T 參 考 書 B 物 理數(shù) 學(xué) 計 算 數(shù) 學(xué) 李 勇王 軍 李 勇張 平 張 平 周 峰 普 通 物 理 學(xué)光 學(xué) 原 理 物 理 習(xí) 題 集數(shù) 學(xué) 分 析微 分 方 程高 等 代 數(shù)數(shù) 學(xué) 分 析. 多 值 依 賴 （ 續(xù) ）v 非 規(guī) 范 化 關(guān) 系 An Introduction to Database System 普 通 物 理 學(xué)光 學(xué) 原 理物 理 習(xí) 題 集普 通 物 理 學(xué)光 學(xué) 原 理物 理 習(xí) 題 集數(shù) 學(xué) 分 析微 分 方 程高 等 代 數(shù)數(shù) 學(xué)

39、分 析微 分 方 程高 等 代 數(shù)李 勇李 勇李 勇王 軍王 軍王 軍李 勇李 勇李 勇張 平張 平張 平 物 理物 理物 理物 理物 理物 理數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué)數(shù) 學(xué) 參 考 書 B教 員 T課 程 C 多 值 依 賴 （ 續(xù) ）v 用 二 維 表 表 示 Teaching An Introduction to Database System 多 值 依 賴 （ 續(xù) ）vTeaching BCNFvTeaching具 有 唯 一 候 選 碼 (C， T， B)， 即 全 碼 An Introduction to Database System 多 值 依 賴 （ 續(xù) ） Teac

40、hing模 式 中 存 在 的 問 題(1)數(shù) 據(jù) 冗 余 度 大 (2)插 入 操 作 復(fù) 雜(3) 刪 除 操 作 復(fù) 雜(4) 修 改 操 作 復(fù) 雜 存 在多 值 依 賴 An Introduction to Database System 多 值 依 賴 （ 續(xù) ）v 定 義 6.9 設(shè) R(U)是 一 個 屬 性 集 U上 的 一 個 關(guān) 系 模 式 ， X、 Y和 Z是 U的 子集 ， 并 且 Z U X Y。 關(guān) 系 模 式 R(U)中 多 值 依 賴 XY成 立 ，當(dāng) 且 僅 當(dāng) 對 R(U)的 任 一 關(guān) 系 r， 給 定 的 一 對 （ x， z） 值 ， 有 一 組Y的

41、 值 ， 這 組 值 僅 僅 決 定 于 x值 而 與 z值 無 關(guān)v 例 Teaching（ C, T, B） An Introduction to Database System 多 值 依 賴 （ 續(xù) ）v多 值 依 賴 的 另 一 個 等 價 的 形 式 化 的 定 義 ： 在 R（ U） 的 任 一 關(guān) 系 r中 ， 如 果 存 在 元 組 t， s 使 得 tX=sX，那 么 就 必 然 存 在 元 組 w， v r， （ w， v可 以 與 s， t相 同 ） ， 使得 wX=vX=tX， 而 wY=tY， wZ=sZ， vY=sY，vZ=tZ（ 即 交 換 s， t元 組 的

42、Y值 所 得 的 兩 個 新 元 組 必 在 r中 ） ，則 Y多 值 依 賴 于 X， 記 為 XY。 這 里 ， X， Y是 U的 子 集 ，Z=U-X-Y。 An Introduction to Database System 多 值 依 賴 （ 續(xù) ）v平 凡 多 值 依 賴 和 非 平 凡 的 多 值 依 賴 若 XY， 而 Z ， 則 稱 XY為 平 凡 的 多 值 依 賴 否 則 稱 XY為 非 平 凡 的 多 值 依 賴 An Introduction to Database System 多 值 依 賴 （ 續(xù) ） 例 10 關(guān) 系 模 式 WSC（ W， S， C）n W表

43、 示 倉 庫 ， S表 示 保 管 員 ， C表 示 商 品n 假 設(shè) 每 個 倉 庫 有 若 干 個 保 管 員 ， 有 若 干 種 商 品 n 每 個 保 管 員 保 管 所 在 的 倉 庫 的 所 有 商 品n 每 種 商 品 被 所 有 保 管 員 保 管 An Introduction to Database System 多 值 依 賴 （ 續(xù) ）W S CW1 S1 C1W1 S1 C2W1 S1 C3W1 S2 C1W1 S2 C2W1 S2 C3W2 S3 C4W2 S3 C5 W2 S4 C4W2 S4 C5 An Introduction to Database Syst

44、em 多 值 依 賴 （ 續(xù) ）WS且 WC用 下 圖 表 示 這 種 對 應(yīng) An Introduction to Database System 多 值 依 賴 的 性 質(zhì)（ 1） 多 值 依 賴 具 有 對 稱 性若 XY， 則 XZ， 其 中 Z U X Y（ 2） 多 值 依 賴 具 有 傳 遞 性若 XY， YZ， 則 XZ Y（ 3） 函 數(shù) 依 賴 是 多 值 依 賴 的 特 殊 情 況 。若 XY， 則 XY。（ 4） 若 XY， XZ， 則 XY Z。（ 5） 若 XY， XZ， 則 XYZ。（ 6） 若 XY， XZ， 則 XY-Z， XZ -Y。 An Introduc

45、tion to Database System 多 值 依 賴 與 函 數(shù) 依 賴 的 區(qū) 別(1) 多 值 依 賴 的 有 效 性 與 屬 性 集 的 范 圍 有 關(guān)(2) 若 函 數(shù) 依 賴 XY在 R（ U） 上 成 立 ， 則 對 于 任 何Y Y均 有 XY 成 立 多 值 依 賴 XY若 在 R(U)上 成 立 ， 不 能 斷 言 對 于任 何 Y Y有 XY 成 立 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多

46、 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Database System 6.2.8 4NFv定 義 6.10 關(guān) 系 模 式 R 1NF， 如 果 對 于 R的 每 個非 平 凡 多 值 依 賴 XY（ Y X） ， X都 含 有 碼 ， 則R 4NF。v如 果 R 4NF， 則 R BCNFn 不 允 許 有 非 平 凡 且 非 函 數(shù) 依 賴 的 多 值 依 賴 n 允 許 的 非 平 凡 多 值 依 賴 是 函 數(shù) 依 賴 An Introduction to Database System 4NF（ 續(xù) ）例 ： Teachi

47、ng(C,T,B) 4NF 存 在 非 平 凡 的 多 值 依 賴 CT， 且 C不 是 碼n 用 投 影 分 解 法 把 Teaching分 解 為 如 下 兩 個 關(guān) 系 模 式 ： CT(C, T) 4NF CB(C, B) 4NF CT， CB是 平 凡 多 值 依 賴 An Introduction to Database System 6.2 規(guī) 范 化6.2.1 函 數(shù) 依 賴6.2.2 碼6.2.3 范 式6.2.4 2NF6.2.5 3NF6.2.6 BCNF6.2.7 多 值 依 賴6.2.8 4NF6.2.9 規(guī) 范 化 小 結(jié) An Introduction to Da

48、tabase System 6.2.9 規(guī) 范 化 小 結(jié)v關(guān) 系 數(shù) 據(jù) 庫 的 規(guī) 范 化 理 論 是 數(shù) 據(jù) 庫 邏 輯 設(shè) 計 的 工 具v目 的 ： 盡 量 消 除 插 入 、 刪 除 一 場 ， 修 改 復(fù) 雜 ， 數(shù) 據(jù) 冗 余v基 本 思 想 ： 逐 步 消 除 數(shù) 據(jù) 依 賴 中 不 合 適 的 部 分 實 質(zhì) ： 概 念 的 單 一 化 An Introduction to Database System 規(guī) 范 化 小 結(jié) （ 續(xù) ）v關(guān) 系 模 式 規(guī) 范 化 的 基 本 步 驟 1NF 消 除 非 主 屬 性 對 碼 的 部 分 函 數(shù) 依 賴消 除 決 定 屬 性

49、2NF集 非 碼 的 非 平 消 除 非 主 屬 性 對 碼 的 傳 遞 函 數(shù) 依 賴凡 函 數(shù) 依 賴 3NF 消 除 主 屬 性 對 碼 的 部 分 和 傳 遞 函 數(shù) 依 賴 BCNF 消 除 非 平 凡 且 非 函 數(shù) 依 賴 的 多 值 依 賴 4NF An Introduction to Database System 規(guī) 范 化 小 結(jié) （ 續(xù) ）v不 能 說 規(guī) 范 化 程 度 越 高 的 關(guān) 系 模 式 就 越 好v在 設(shè) 計 數(shù) 據(jù) 庫 模 式 結(jié) 構(gòu) 時 ， 必 須 對 現(xiàn) 實 世 界 的 實 際 情 況 和用 戶 應(yīng) 用 需 求 作 進(jìn) 一 步 分 析 ， 確 定 一

50、 個 合 適 的 、 能 夠 反 映現(xiàn) 實 世 界 的 模 式v上 面 的 規(guī) 范 化 步 驟 可 以 在 其 中 任 何 一 步 終 止 An Introduction to Database System 第 六 章 關(guān) 系 數(shù) 據(jù) 理 論6.1 問 題 的 提 出6.2 規(guī) 范 化6.3 數(shù) 據(jù) 依 賴 的 公 理 系 統(tǒng)*6.4 模 式 的 分 解6.5 小 結(jié) An Introduction to Database System 6.3 數(shù) 據(jù) 依 賴 的 公 理 系 統(tǒng)v邏 輯 蘊 含定 義 6.11 對 于 滿 足 一 組 函 數(shù) 依 賴 F 的 關(guān) 系 模 式 R ，其 任 何

51、 一 個 關(guān) 系 r， 若 函 數(shù) 依 賴 XY都 成 立 , （ 即 r中 任 意兩 元 組 t， s， 若 tX =sX ， 則 tY =sY ） ， 則 稱 F邏 輯蘊 含 X Y An Introduction to Database System 1. Armstrong公 理 系 統(tǒng) 關(guān) 系 模 式 R 來 說 有 以 下 的 推 理 規(guī) 則 ： A1.自 反 律 （ Reflexivity） ： 若 Y X U， 則 X Y為 F所 蘊含 。 A2.增 廣 律 （ Augmentation） ： 若 XY為 F所 蘊 含 ， 且 Z U， 則 XZYZ為 F所 蘊 含 。 A3.

52、傳 遞 律 （ Transitivity） ： 若 XY及 YZ為 F所 蘊 含 ， 則XZ為 F所 蘊 含 。 An Introduction to Database System 定 理 6.1 Armstrong推 理 規(guī) 則 是 正 確 的（ l） 自 反 律 : 若 Y X U， 則 X Y為 F所 蘊 含 證 : 設(shè) Y X U 對 R 的 任 一 關(guān) 系 r中 的 任 意 兩 個 元 組 t， s：若 tX=sX， 由 于 Y X， 有 ty=sy，所 以 XY成 立 ， 自 反 律 得 證 An Introduction to Database System 定 理 6.l A

53、rmstrong推 理 規(guī) 則 是 正 確 的 （ 續(xù) ）(2)增 廣 律 : 若 XY為 F所 蘊 含 ， 且 Z U， 則 XZYZ 為 F所蘊 含 。 證 ： 設(shè) XY為 F所 蘊 含 ， 且 Z U。 設(shè) R 的 任 一 關(guān) 系 r中 任 意 的 兩 個 元 組 t， s：若 tXZ=sXZ， 則 有 tX=sX和 tZ=sZ；由 XY， 于 是 有 tY=sY， 所 以 tYZ=sYZ， 所 以XZYZ為 F所 蘊 含 ， 增 廣 律 得 證 。 An Introduction to Database System 定 理 6.l Armstrong推 理 規(guī) 則 是 正 確 的 （

54、 續(xù) ）(3) 傳 遞 律 ： 若 XY及 YZ為 F所 蘊 含 ， 則 XZ為 F所 蘊 含 。證 ： 設(shè) XY及 YZ為 F所 蘊 含 。對 R 的 任 一 關(guān) 系 r中 的 任 意 兩 個 元 組 t， s：若 tX=sX， 由 于 XY， 有 tY=sY；再 由 YZ， 有 tZ=sZ， 所 以 XZ為 F所 蘊 含 ， 傳 遞律 得 證 。 An Introduction to Database System 2. 導(dǎo) 出 規(guī) 則1.根 據(jù) A1， A2， A3這 三 條 推 理 規(guī) 則 可 以 得 到 下 面 三條 推 理 規(guī) 則 ： 合 并 規(guī) 則 ： 由 XY， XZ， 有 X

55、YZ。 （ A2， A3） 偽 傳 遞 規(guī) 則 ： 由 XY， WYZ， 有 XWZ。 （ A2， A3） 分 解 規(guī) 則 ： 由 XY及 ZY， 有 XZ。 （ A1， A3） An Introduction to Database System 導(dǎo) 出 規(guī) 則2.根 據(jù) 合 并 規(guī) 則 和 分 解 規(guī) 則 ， 可 得 引 理 6.1 引 理 6.l XA1 A2Ak成 立 的 充 分 必 要 條 件 是XAi成 立 （ i=l， 2， ， k） An Introduction to Database System Armstrong公 理 系 統(tǒng)vArmstrong公 理 系 統(tǒng) 是 有

56、效 的 、 完 備 的n 有 效 性 ： 由 F出 發(fā) 根 據(jù) Armstrong公 理 推 導(dǎo) 出 來的 每 一 個 函 數(shù) 依 賴 一 定 在 F+中 ；n 完 備 性 ： F+中 的 每 一 個 函 數(shù) 依 賴 ， 必 定 可 以 由F出 發(fā) 根 據(jù) Armstrong公 理 推 導(dǎo) 出 來 An Introduction to Database System 3. 函 數(shù) 依 賴 閉 包定 義 6.l2 在 關(guān) 系 模 式 R中 為 F所 邏 輯 蘊 含 的函 數(shù) 依 賴 的 全 體 叫 作 F的 閉 包 ， 記 為 F+。定 義 6.13 設(shè) F為 屬 性 集 U上 的 一 組 函

57、數(shù) 依 賴 ， X U， XF+ = A|XA能 由 F 根 據(jù) Armstrong公 理 導(dǎo) 出 ，X F+稱 為 屬 性 集 X關(guān) 于 函 數(shù) 依 賴 集 F 的 閉 包 An Introduction to Database System F的 閉 包F=XY, YZF+=X, Y, Z, XY, XZ, YZ, XYZ, XX, YY, ZZ, XYX, XZX, YZY, XYZX,XY, Y Z, XYY, XZY, YZZ, XYZY,XZ, YYZ, XYZ, XZZ, YZYZ,XYZZ,XXY, XYXY,XZXY, XYZXY, XXZ, XYYZ,XZXZ, XYZYZ

58、,XYZ, XYXZ,XZXY, XYZXZ,XZYZ, XYXYZ,XZXYZ, XYZXYZ F=XA1, , XAn的 閉 包 F+計 算 是 一 個 NP完 全 問 題 An Introduction to Database System 關(guān) 于 閉 包 的 引 理v引 理 6.2 設(shè) F為 屬 性 集 U上 的 一 組 函 數(shù) 依 賴 ， X， Y U， XY能 由 F 根 據(jù) Armstrong公 理 導(dǎo) 出 的 充 分 必 要 條 件 是 Y XF+v用 途 將 判 定 XY是 否 能 由 F根 據(jù) Armstrong公 理 導(dǎo) 出 的 問 題 ，轉(zhuǎn) 化 為 求 出 X F+ 、

59、 判 定 Y是 否 為 XF+的 子 集 的 問 題 An Introduction to Database System 求 閉 包 的 算 法算 法 6.1 求 屬 性 集 X（ X U） 關(guān) 于 U上 的 函 數(shù) 依 賴 集 F 的 閉 包 XF+ 輸 入 ： X， F 輸 出 ： XF+步 驟 ：（ 1） 令 X（ 0） =X， i=0（ 2） 求 B， 這 里 B = A |( V)( W)(VWF V X （ i） A W)；（ 3） X（ i+1） =B X（ i） （ 4） 判 斷 X（ i+1） = X （ i） 嗎 ?（ 5） 若 相 等 或 X（ i） =U , 則 X（

60、 i） 就 是 XF+ , 算 法 終 止 。（ 6） 若 否 ， 則 i=i+l， 返 回 第 （ 2） 步 。 An Introduction to Database System 算 法 6.1對 于 算 法 6.1， 令 ai =|X（ i） |， ai 形 成 一 個 步長 大 于 1的 嚴(yán) 格 遞 增 的 序 列 ， 序 列 的 上 界 是 | U |， 因 此 該 算 法 最 多 |U| - |X| 次 循 環(huán) 就 會 終 止 。 An Introduction to Database System 函 數(shù) 依 賴 閉 包例 1 已 知 關(guān) 系 模 式 R， 其 中U=A， B，

61、 C， D， E；F=ABC， BD， CE， ECB， ACB。求 （ AB） F+ 。解 設(shè) X （ 0） =AB；(1) X（ 1） =AB CD=ABCD。(2) X（ 0） X（ 1） X（ 2） =X（ 1） BE=ABCDE。(3) X（ 2） =U， 算 法 終 止（ AB） F+ =ABCDE。 An Introduction to Database System 4. Armstrong公 理 系 統(tǒng) 的 有 效 性 與 完 備 性v定 理 6.2 Armstrong公 理 系 統(tǒng) 是 有 效 的 、 完備 的 v證 明 ：1. 有 效 性 可 由 定 理 6.1得 證2.

62、 完 備 性只 需 證 明 逆 否 命 題 : 若 函 數(shù) 依 賴 XY不 能 由 F從 Armstrong公 理 導(dǎo) 出 ， 那 么 它 必 然 不 為 F所 蘊 含 An Introduction to Database System Armstrong公 理 系 統(tǒng) 完 備 性 證 明(1) 引 理 : 若 VW成 立 ， 且 V XF+， 則 W XF+ (2) 構(gòu) 造 一 張 二 維 表 r， 它 由 下 列 兩 個 元 組 構(gòu) 成 ， 可 以 證 明 r必 是 R（ U， F） 的 一 個 關(guān) 系 ， 即 F+中 的 全 部 函 數(shù) 依 賴 在 r上 成 立 。 XF+ U-XF+

63、 11.1 00.0 11.1 11.1 (3) 若 XY 不 能 由 F從 Armstrong公 理 導(dǎo) 出 ， 則 Y 不 是 X F+ 的 子 集 。 An Introduction to Database System 5. 函 數(shù) 依 賴 集 等 價定 義 6.14 如 果 G+=F+， 就 說 函 數(shù) 依 賴 集 F覆 蓋 G（ F是 G的 覆蓋 ， 或 G是 F的 覆 蓋 ） ， 或 F與 G等 價 。引 理 6.3 F+ = G+ 的 充 分 必 要 條 件 是 F G+ ， 和 G F+ 證 : 必 要 性 顯 然 ， 只 證 充 分 性 。（ 1） 若 FG + ， 則 X

64、F+ XG+ 。（ 2） 任 取 XYF+ 則 有 Y XF+ XG+ 。 所 以 XY (G+） += G+。 即 F+ G+。（ 3） 同 理 可 證 G+ F+ ， 所 以 F+ = G+。 An Introduction to Database System 6. 最 小 依 賴 集定 義 6.15 如 果 函 數(shù) 依 賴 集 F滿 足 下 列 條 件 ， 則 稱 F為 一 個極 小 函 數(shù) 依 賴 集 。 亦 稱 為 最 小 依 賴 集 或 最 小 覆 蓋 。 (1) F中 任 一 函 數(shù) 依 賴 的 右 部 僅 含 有 一 個 屬 性 。 (2) F中 不 存 在 這 樣 的 函

65、數(shù) 依 賴 XA， 使 得 F與 F-XA等 價 。 (3) F中 不 存 在 這 樣 的 函 數(shù) 依 賴 XA， X有 真 子 集 Z使 得F-XA ZA與 F等 價 。 An Introduction to Database System 最 小 依 賴 集例 2 關(guān) 系 模 式 S， 其 中 ： U= Sno， Sdept， Mname， Cno， Grade ， F= SnoSdept， SdeptMname， (Sno， Cno)Grade 設(shè) F=SnoSdept， SnoMname， SdeptMname， (Sno， Cno)Grade， (Sno， Sdept)SdeptF是

66、 最 小 覆 蓋 ， 而 F不 是 。因 為 ： F - SnoMname與 F 等 價 F - (Sno， Sdept)Sdept也 與 F 等 價 An Introduction to Database System 7. 極 小 化 過 程定 理 6.3 每 一 個 函 數(shù) 依 賴 集 F均 等 價 于 一 個 極 小 函 數(shù) 依 賴 集 Fm。 此 Fm稱 為 F的 最 小 依 賴 集 。證 明 : 構(gòu) 造 性 證 明 ， 找 出 F的 一 個 最 小 依 賴 集 。 An Introduction to Database System 極 小 化 過 程 （ 續(xù) ）(1)逐 一 檢 查 F中 各 函 數(shù) 依 賴 FDi： XY， 若 Y=A1A2 Ak， k 2， 則 用 XAj |j=1， 2， ， k 來 取 代 XY。(2)逐 一 檢 查 F中 各 函 數(shù) 依 賴 FDi： XA， 令 G=F-XA， 若 AX G+， 則 從 F中 去 掉 此 函 數(shù) 依 賴 。(3)逐 一 取 出 F中 各 函 數(shù) 依 賴 FDi： XA， 設(shè) X=B1B2Bm， 逐 一 考 查 B