DBMS 中可能的超键数量

超键

在数据库管理系统中，用于唯一标识每一行的属性集合称为超级键。超级键是主键或候选键的超集。每个主键或候选键都是超级键，但每个超级键都不能称为候选键。

我们将通过理解下面讨论的各种示例来计算关系模型（表）中存在的超级键的数量。

注意

A 并集 B = A + B - (A 交集 B)

A 并集 B 并集 C = A + B + C - (A 交集 B) - (B 交集 C) - (C 交集 A) + (A 交集 B 交集 C)

示例 1

假设我们有一个关系模型，其属性为 {A, B, C, D}，A 是候选键，然后计算超级键的数量。

解决方案

我们知道候选键也是一个超级键，其任何子集都不是超级键，所以所有的超级键都将包含候选键。

所以超级键将是：{A, AB, AC, AD, ABC, ABD, ACD, ABCD}

因此，对于只有一个候选键的表，其通用公式是，如果 K 是属性的数量，则超级键总数 = 2^(K-1)。

注意：假设一个关系模型有 N 个属性，则超级键的最大数量为 2^N-1（当所有属性都是候选键时）。

示例 2

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1A2A3A4}，则超级键的数量是多少？

解决方案

超级键的总数为 2^(N-4)。

示例 3

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1, A2}，则超级键的数量是多少？

解决方案

超级键总数 = (A1 的超级键) 并集 (A2 的超级键)

超级键总数 = 2^(N-1) + 2^(N-1) - 2^(N-2)

示例 4

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1, A2A3}，则超级键的数量是多少？

解决方案

超级键总数 = (A1 的超级键) 并集 (A2A3 的超级键)

超级键总数 = 2^(N-1) + 2^(N-2) - 2^(N-3)

示例 5

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1A2, A3A4}，则超级键的数量是多少？

解决方案

超级键总数 = (A1A2 的超级键) 并集 (A3A4 的超级键)

超级键总数 = 2^(N-2) + 2^(N-2) - 2^(N-4)

示例 6

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1A2, A2A3}，则超级键的数量是多少？

解决方案

超级键总数 = (A1A2 的超级键) 并集 (A2A3 的超级键)

超级键总数 = 2^(N-2) + 2^(N-2) - 2^(N-3)

示例 7

如果一个关系模型有 N 个属性 {A1, A2...An}，候选键为 {A1, A2, A3}，则超级键的数量是多少？

解决方案

超级键总数 = (A1 的超级键) 并集 (A2 的超级键) 并集 (A3 的超级键)

超级键总数 = 2^(N-1) + 2^(N-1)+2^(N-1) - 2^(N-2) - 2^(N-2) - 2^(N-2)+ 2^(N-3)

示例 8

我们假设有一个属性集 R:{A, B, C, D, E, F, G, H} 和函数依赖集

A -> BC

B -> CFH

E -> A

F -> EG

CH -> G

解决方案

首先，我们将确定候选键，它们是：{AD, BD, ED, FD}

所以将得到超级键总数 = (AD 的超级键) 并集 (BD 的超级键) 并集 (ED 的超级键) 并集 (FD 的超级键)

对于单个 AD，我们有六个选项可以选择或不选择，所以是 2⁶。

两个超级键的组合，如 AD 交集 BD，将是 2⁵。

对于三个超级键的组合，总选项将是 2⁴。

对于四个超级键的组合，总选项将是 2³。

单个组合的数量 = 4

两个组合的数量 = 6

三个组合的数量 = 4

四个组合的数量 = 1

所以超级键总数为：4*2⁶ - 6*2⁵ + 4*2⁴ -1*2³ = 120

示例 9

如果一个关系模型有 N 个属性 {A1, A2...An}，并且有一个由 K 个属性组成的候选键。找到 K 的值，使得候选键的数量最多。

解决方案

从 N 中选择 K 个值是通过 ^NC_K 完成的。

^NC_K = (!N)/!(N-K)!k

对于上述值，K = N/2 以达到最大值。