章節導航
頂部	E/R 理論 - 規範化 - 資料查詢 - 整合 SQL 和程式語言

函式依賴 (FD)

FD 簡介

gene_id	name	annotation
...	...	...
g23	hsp39	XX 蛋白
g24	hsp39	XX 蛋白

函式依賴：如果兩個元組在 X 上一致，則它們在 Y 上也一致，則 X->Y。例如“gene_id -> name”和“gid-> annotation”是 FD，但“name->gene_id”和“name->annotation”不是 FD。

鍵和 FD 之間的關係

一組屬性 {A₁, A₂, ...A_t} 是關係 R 的鍵，如果

(1) {A₁, A₂, ...A_t} 函式確定所有其他屬性；

(2) 當 {A₁, A₂, ...A_t} 的任何真子集都不能函式確定所有其他屬性時，它被稱為超鍵（或候選鍵？）。

FD 規則

觀察

        Correct: 
               X->Y, A->B:   XA->BY;   
               X->AY:   X->A, X->Y;
               X->Y, A->Y: XA->Y;
        Incorrect:
               XY->A: X->A, Y->A;

函式依賴的形式推理規則

        Armstrong’s axioms:
               1. Reflexivity: If Y ⊆ X then X -> Y (called trivial FD);
               2. Transitivity: If X -> Y and Y -> Z then X -> Z;
               3. Augmentation: If X -> Y then XZ -> YZ where Z is a set of attributes.

FD 來自哪裡？

檢視

              (1) Domain Knowledge (the meaning of the attributes); 
              (2) the data;

a	b	c
1	2	3
4	2	6

b->a 不是 FD，但 a->b 是一個有效的 FD。

BCNF

分解表的正式方法

基因	name	annotation	實驗 ID	實驗描述	實驗級別
...	...	...	...	...	...

⇒

         R1 (gid, name, annotation);    gid->name annotation;
         R2 (exp id, exp desc);         exp id -> exp desc;
         R3 (gid, expid, exp level);   gid, expid -> exp level;

$OriginalRelation->find\ \ a\ FD\ X->Y\left\{{\begin{array}{ll}{X,Y},&{\hbox{gid, name, annotation;}}\\{everything\ \ exceptY},&{\hbox{gid, exp id, exp desc, exp level;}}\end{array}}\right.$

$gid,expid,expdesc,explevel\left\{{\begin{array}{ll}{expid,expdesc},&{\hbox{;}}\\{gid,\ expid,\ explevel},&{\hbox{;}}\end{array}}\right.$

如果對於所有依賴關係 X -> Y，以下至少一個成立，則關係 R 處於 BCNF 中

• X -> Y 是一個平凡的 FD (Y ⊆ X)

• X 是 R 的超鍵

3NF

正式定義：如果對於 F+ 中的所有依賴關係 X® Y，以下至少一個成立，則關係 R 處於 3NF 中

• X -> Y 是一個平凡的 FD (Y ⊆ X)

• X 是 R 的超鍵

• Y ⊂ R 的候選鍵

BCNF 和 3NF 的比較

	移除冗餘	保留 FD	無損分解
BCNF	是	否	是
3NF	否	是	是

有損分解

假設我們有一個類似於以下表的表。

a	b	c
1	2	3
4	2	6

分解成以下“規範化”表

a	b
1	2
4	2

b	c
2	3
2	6

這意味著我們遵循

b → a 或

b → c

作為我們分解原始表的 FD。（記住，BCNF 將 X → Y 分解為集合 {X, Y} 和 {除了 Y 的所有內容}）。但是，請注意，列 b 具有非唯一值（兩個數字 2）。當我們透過連線重新組合這兩個表時，我們最終得到了一個表，其中原始關係丟失了

a	b	c
1	2	3
1	2	6
4	2	3
4	2	6

我們將其宣告為 **有損分解**，因為分解表假設的 FD 不成立（b → a 和 b → c 均為假）。因此，BCNF 無法消除所有形式的冗餘。我們需要使用另一種模型，多值依賴 (MD)，來幫助我們正確分解表以進行規範化。

多值依賴 (MD)

讓我們探索一個具體的場景。我們想代表富裕學生的財產。我們建立了 **多值依賴 (MD)**

SID →→ car

讀作，“給定的學生 ID 可以擁有多輛汽車”。

將其與類似於 FD 的內容進行比較

SID → name

我們將其讀作，“給定的 SID 最多可以有一個姓名”。

假設我們還有以下 MD

SID →→ clothes

我們可以得到以下表格

SID	car	clothes
1	本田	牛仔褲
1	豐田	卡其褲
1	豐田	牛仔褲
1	本田	卡其褲
…	…	…

也許我們想進一步分解這個表。我們沿著 MD 分解

SID →→ car

這將留下 {SID, clothes}，留下以下表格

SID →→ car

{SID, clothes}

SID	car
1	本田
1	豐田
…	…

sid	clothes
1	牛仔褲
1	卡其褲
…	…

我們無法 *真正* 執行此操作，因為這些 *不是* FD！SID →→ car 或 SID →→ clothes 都沒有超鍵。鍵必須是所有三個屬性。我們需要新的規則來分解 MD。

MD 規則

識別平凡MD

如果 $X \cup Y = {所有屬性}$ ，則我們稱 MD $X \to\to Y$ 在 $R$ 中是平凡的。

例如，考慮以下關係 $R 1$ ，其中我們有 MD $a \to\to b$

a	b
$R 1$
1	2
1	3
2	2
…	…

因為每個 $a$ 可以有多個 $b$ ，所以我們無法生成資料來違反 MD。

現在考慮以下關係 $R 2$

a	b	c
$R 3$
1	2	6
1	3	7
2	2	6
…	…	…

在這種情況下， $a \to\to b$ 是非平凡的，因為關係是三向的。

非平凡MD成對出現

事實上， $a \to\to b$ 有一個也是非平凡的夥伴 MD： $a \to\to c$

以下是 $R 2$ 中所有非平凡 MD 對的列表

a \to\to b

a \to\to c

b \to\to a

b \to\to c

c \to\to a

c \to\to b

將此與 $R 2$ 中平凡 MD 的示例進行比較

a \to\to bc

ab \to\to c

b \to\to ac

bc \to\to a

c \to\to ab

ca \to\to b

…

FD的蘊涵對MD不成立

在 FD 中，我們知道 $X\rightarrow YZ\iff {\begin{array}{c}X\rightarrow Y\\{\mbox{and}}\\X\rightarrow Z\end{array}}$

然而，同樣的蘊涵對 MD 不存在。也就是說， $X\rightarrow \rightarrow YZ\nLeftrightarrow {\begin{array}{c}X\rightarrow \rightarrow Y\\{\mbox{and}}\\X\rightarrow \rightarrow Z\end{array}}$

MD實際上是關於獨立性

給定MD

a \to\to b

以及

a \to\to c

我們知道，對於每個 $a$

可以有多個 $a$
可以有多個 $a$
並且， $b$ 與 $c$ 相對於 $a$ 是獨立的，我們用符號表示為 $b\perp c|a$ [注意：實際的第一個二元關係符號應該是\Perp而不是\perp，但此符號不受Mediawiki支援。]

每個FD都是一個MD

根據定義， $X \to Y \Rightarrow X \to\to Y$ 。如果 $X$ 最多有一個 $Y$ ，則它滿足有多個 $Y$ 的條件。

例如，給定以下關係

a	b
…	…

以及 $a \to b$ 的 FD，那麼我們也有 $a \to\to b$ 的平凡 MD。

現在，考慮 FD $a \to b$ 與以下關係

a	b	c	d
…	…	…	…

在這種情況下，我們實際上有兩個非平凡的 MD

a \to\to b

a \to\to cd

（記住，非平凡的 MD 成對出現。）