如何从函数依赖中找出候选键

函数依赖

函数依赖是两组属性 X 和 Y 之间的关系，使得如果 X -> Y，则所有相同的 X 值将具有相同的 Y 值，或者 Y 可以通过 X 值唯一标识。

候选键

在关系模型中，可用于唯一标识每行的属性集称为超键，并且可以有很多超键。那些没有作为任何超键的真子集的超键称为候选键。

例如，在关系模型中，我们有 {A, B, C} 三个属性，{AB} 可以标识一个完整的表，{A} 本身可以标识整个表，那么 AB 和 A 都将是超键，但 A 将是候选键。

闭包

属性的闭包可以标识为可以从它函数确定的属性集。

闭包将用于使用函数依赖找到候选键。

使用函数依赖找到关系表候选键的步骤

步骤 1

首先，我们将从给定的属性集中找出必需和非必需的属性集。那些依赖于其他属性的属性是非必需属性，它们的值可以使用必需属性找到。

因此，所有必需属性肯定会成为我们候选键的一部分。

步骤 2

我们将组合所有必需属性，如果它们能够确定所有属性（通过找到它们的闭包），那么它将是候选键。

步骤 3

如果必需属性的组合不是候选键，那么我们将尝试必需和非必需属性的不同组合，它们彼此不是子集，以找出所有候选键。

示例 1

假设我们有一个属性集 S：{A, B, C, D}，函数依赖是

A -> B

B -> C

C -> A

解决方案

在上面的示例中，我们有非必需属性 {A, B, C}，必需属性是 {D}。

所以，D 将是候选键的一部分。

D 的闭包：{D}

因此，必需属性的组合无法找到所有属性，所以我们将以不同方式添加非必需属性以找出候选键。

(AD) 的闭包 = {A, B, C, D} (使用 A->B 和 B->C)

所以，AD 将是候选键。

(BD) 的闭包 = {A, B, C, D} (使用 C->A 和 B->C)

所以，BD 将是候选键。

(CD) 的闭包 = {A, B, C, D} (使用 C->A 和 A->B)

所以，CD 将是候选键。

没有其他属性组合是不可能的，所以候选键是 {AD, BD, CD}

示例 2

假设我们有一个属性集 S：{A, B, C, D, E, F}，函数依赖是

AB -> C

B -> AE

C -> D

解决方案

在上面的示例中，我们有非必需属性 {A, C, D, E}，必需属性是 {B, F}。

所以，BF 将是候选键的一部分。

BF 的闭包：{B, A, E, C, D, F}

由于必需属性的组合能够找到所有属性，它将是一个候选键。所有其他必需和非必需属性的组合将不是最小的，因此只有一个候选键 {BF}。

示例 3

假设我们有一个属性集 S：{A, B, C, D, E}，函数依赖是

CE -> D

D -> B

C -> A

解决方案

在上面的示例中，我们有非必需属性 {A, B, D}，必需属性是 {C, E}。

所以，CE 将是候选键的一部分。

CE 的闭包：{C,E,D,B,A} (使用 CE->D, D->B 和 C->A)

由于必需属性的组合能够找到所有属性，它将是一个候选键。所有其他必需和非必需属性的组合将不是最小的，因此只有一个候选键 {CE}。

示例 4

假设我们有一个属性集 S：{W, X, Y, Z}，函数依赖是

Z -> W

Y -> XZ

XW -> Y

解决方案

在上面的示例中，我们有非必需属性 {W, X, Y, Z}，必需属性是 {}。

在这个示例中，我们将探索属性的每个组合以找出候选键，因为没有必需属性。

W 的闭包 = {W}

X 的闭包 = {X}

Y 的闭包 = {Y,X,Z,W} (使用 Y->XZ 和 Z->W)

Z 的闭包 = {Z}

由于 Y 能够找到所有属性，所以它将是候选键。Y 将不会是下一个组合的一部分。

XW 的闭包 = {X,W,Y,Z} (使用 XW->Y 和 Y->XZ)

ZW 的闭包 = {Z,W}

XZ 的闭包 = {X,W,Y,Z} (使用 Z->W 和 XW->Y)

所以 XW 和 XZ 将是下一个候选键，而下一个其他组合将不包含这些候选键之外的属性。

所以将有三个候选键 {Y, XW, XZ}

示例 5

假设我们有一个属性集 S：{A, B, C, D, E, F}，函数依赖是

AB -> C

C-> D

D -> BE

E -> F

F -> A

解决方案

在上面的示例中，我们有非必需属性 {A, B, C, D, E, F}，必需属性是 {}。

现在在这个示例中，我们将探索属性的每个组合以找出候选键，因为没有必需属性。

如果没有必需属性，那么每个非必需属性都可以是候选键，因此它增加了候选键的数量。

A 的闭包 = {A}

B 的闭包 = {B}

C 的闭包 = {C, D, B, E, F, A} (使用 C->D, D->BE, E->F, F->A)

D 的闭包 = {D, B, E, F, A, C} (使用 AB->C, D->BE, E->F, F->A)

E 的闭包 = {E,F,A} (使用 A->F, F->A)

F 的闭包 = {F,A} (使用 F->A)

由于 {C, D} 能够找到所有属性，所以它将是候选键集。{C, D} 将不会是下一个组合的一部分。

AB 的闭包 = { A, B, C, D, E, F}

AE 的闭包 = { A,E,F}

AF 的闭包 = { A,F}

BE 的闭包 = { A, B, C, D, E, F}

BF 的闭包 = { A, B, C, D, E, F}

EF 的闭包 = { A,E,F}

所以 AB, BE 和 BF 将是下一个候选键，而下一个其他组合将不包含这些候选键之外的属性。

所以将有五个候选键 {C, D, AB, BE, BF}

示例 6

假设我们有一个属性集 S：{A, B, C, D, E, F, G, H}，函数依赖是

A -> BC

E -> A

B -> CFH

CH -> G

F -> EG

解决方案

在上面的示例中，我们有非必需属性 {A, B, C, E, F, G, H}，必需属性是 {D}。

D 的闭包 = {D}

由于 D 是必需属性，它将是必需和非必需属性所有组合的一部分。

AD 的闭包 = {A, B, C, D, E, F, G, H} (使用 A->BC, B->CFH, F->EG)

BD 的闭包 = {A, B, C, D, E, F, G, H} (使用 B->CFH, F->EG, E->A)

CD 的闭包 = {C,D}

ED 的闭包 = {A, B, C, D, E, F, G, H} (使用 E->A, A->BC, B-> CFH, F->EG)

FD 的闭包 = {A, B, C, D, E, F, G, H} (使用 F->EG, E->A, A->BC)

GD 的闭包 = {D,G}

HD 的闭包 = {D,H}

由于 {AD, BD, ED, FD} 能够找到所有属性，所以有一个候选键集，并且 {A, B, E, F} 将不会是下一个组合的一部分。

CDG 的闭包 = {C, D, G}

CDH 的闭包 = {C, D, H, G}

CDGH 的闭包 = {C, D, G, H}

现在不可能有其他组合，因为下一个组合将包含来自预定候选键集的属性。那么它将是超键，而不是候选键。

所以，我们已经尝试了必需和非必需属性的所有组合，我们得到了四个候选键 {AD, BD, ED, FD}