前言

一個設計良好的數(shù)據(jù)庫模式（database schema），應該要具備以下特點：

• 完整性（Completeness）
• 減少冗余（Redundancy freeness）
• 一致的含義（Consistent understanding）
• 良好的性能（Performance）

一個設計不好的數(shù)據(jù)庫模式，可能會出現(xiàn)以下的問題：

• 數(shù)據(jù)不一致
• 數(shù)據(jù)冗余
• 更新異常

為什么需要函數(shù)依賴（Why Functional Dependencies）

函數(shù)依賴（FD）可以以一種正式的方式來定義關系型數(shù)據(jù)庫的“好（goodness）”與“壞（badness）”。函數(shù)依賴的設計一般有兩種：

• 自上而下（Top down）：從一個大的關系模式和 FD 出發(fā)，在這基礎上按照確切的正規(guī)形式產(chǎn)生較小的數(shù)據(jù)模式。
• 自下而上（Bottom up）： 從屬性和 FD 出發(fā)，逐步產(chǎn)生數(shù)據(jù)模式（現(xiàn)實中不常用）。

定義

一個數(shù)據(jù)庫 R 的一組 FD 可以表示成： X → Y，其中 X 和 Y 是數(shù)據(jù)庫 R 中的兩組屬性集合，其含義是：對于 R 中的任意兩個元組，只要他們的在集合 X 中的屬性相等，那么他們在集合 Y 中的屬性也相等。這里 X 稱為決定因素（Determinant）, Y 稱為被決定因素（Dependant）。

在現(xiàn)實應用中，F(xiàn)D 為數(shù)據(jù)庫明確約束，而且該約束在任何時候都需要保證成立。一般常使用以下兩種方法來確定某個數(shù)據(jù)庫的函數(shù)依賴：

1. 分析數(shù)據(jù)需求
2. 分析樣本數(shù)據(jù)

舉個例子：

對于以下的函數(shù)依賴：

• ABC → AB （√）
• A → B （√）
• ABC → D （×）
• E → ABCD （√）

阿姆斯特朗推理法則（Armstrong‘s Inference Rules）

反身法則（Reflexive rule）： XY → Y
增廣法則（Augmentation rule）： { X → Y } |= { XZ → YZ }
傳遞法則（Transitive rule）： { X → Y， Y → Z } |= { X → Z }
其中，公式 ∑ |= X → Y 表示函數(shù)依賴 X → Y 可以通過集合 ∑ 中的函數(shù)依賴推理得出。

在阿姆斯特朗推理法則的基礎上，我們進一步衍生出一些實用的法則：

• 合并律（Union rule）： { X → Y， X → Z } |= { X → YZ }
• 分解律（Decomposition rule）： { X → YZ } |= { X → Y， X → Z }

隱含的函數(shù)依賴

想要設計一個好的數(shù)據(jù)庫，我們需要考慮到所有的函數(shù)依賴，包括一些隱含的函數(shù)依賴。我們常用 ∑* 表示由函數(shù)依賴集合 ∑ 所隱含的所有可能的函數(shù)依賴。

我們規(guī)定：如果 ∑1* = ∑2，那么 ∑1 和 ∑2 是等價的。意思就是，∑1 和 ∑2 可以不相同，只要他們對應的 ∑ 是相等的，我們就可以認為這兩個函數(shù)依賴集合的等價的。

通過一個屬性 X 集合推理出來的所有屬性集合，稱之為該屬性 X 的閉包（Closure），記作 X+。所以我們可以這么表示：

Σ |= X → W 等價于 W ? X+

例如，一個數(shù)據(jù)庫 R = {A, B,C,D, E, F} 具有一下的函數(shù)依賴集合：Σ = { AC → B, B → CD,C → E, AF → B }。要判斷 Σ |= AC → DE 是否成立。我們首先需要找到屬性 AC 的閉包：

(AC)+   ? AC         初始化
        ? ACB        根據(jù)依賴 AC → B
        ? ACBD       根據(jù)依賴 B → CD
        ? ACBDE      根據(jù)依賴 C → E
        = ACBDE

其中，我們發(fā)現(xiàn) DE ? (AC)+，所以 Σ |= AC → DE 是成立的。

函數(shù)依賴的最小覆蓋（Minimal cover）

通過定義函數(shù)依賴的最小覆蓋，我們可以直接通過最小覆蓋推理出數(shù)據(jù)庫的所有函數(shù)依賴。一個函數(shù)依賴的最小覆蓋具有以下特點：

1. Σm 與 Σ 是等價的。其中 Σm 是最小覆蓋，Σ 是數(shù)據(jù)庫給定的函數(shù)依賴集合；
2. Dependant：最小覆蓋的每一條函數(shù)依賴，其右側(cè)只存在單個的屬性；
3. Determinant：最小覆蓋的每一條函數(shù)依賴，其左側(cè)可以存在多個屬性；
4. 任何冗余的函數(shù)依賴都會被移除。

通過 FD 尋找鍵

在一個數(shù)據(jù)庫中，一定存在這樣的函數(shù)依賴關系： K → R ， 其中 K 是超鍵，R 是該數(shù)據(jù)庫所有屬性的集合。

算法

輸入：數(shù)據(jù)庫 R 的 FD 集合 ∑。
輸出：數(shù)據(jù)庫 R 所有超鍵的集合。
步驟：
對于數(shù)據(jù)庫 R 的每一個屬性集合的子集 X，計算它的閉包 X+；
如果 X+ = R，那么 X 就是一個超鍵；
如果不存在 X 的真子集 Y 滿足 Y+ = R，那么 X 就是候選鍵（主鍵）。
在這個部分，我們把在候選鍵中出現(xiàn)的所有屬性稱為主要屬性（Prime attribute），其余的屬性則稱為非主要屬性（Non-prime attributes）。

在尋找候選鍵的過程中，有一些比較好用的小技巧：

• 如果一個屬性從來沒有出現(xiàn)在任何 FD 的右側(cè)，那么它肯定是候選鍵的一部分；
• 如果一個屬性從來沒有出現(xiàn)在任何 FD 的左側(cè)，但它出現(xiàn)在某個 FD 的右側(cè)，那么它肯定不是候選鍵的一部分；
• 如果某個集合 X 的真子集是候選鍵，那么 X 肯定不是一個候選鍵。