章节导航
顶部	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 成对出现。）