database - 候选人和超级密钥

Question

给定一个具有 n 个属性 R(A1, A2, ..., An) 的关系模式 R。R 的最大可能超级键数是多少？请证明你的回答。

给定一个具有 n 个属性 R(A1, A2, ..., An) 的关系模式 R。R 可能的候选键的最大数量是多少？请证明你的回答。

我仍然想知道如何回答这两个问题。我认为第一个问题的答案是 (2^n) - 1 因为不包括空集。

至于第二个问题。我的答案是 n 属性。

你们有什么感想？

Answer 1

与 n 个属性相关的最大超级键数将是所有可能的属性组合的数量。结果是 (2^n)-1。

这不过是采取

来自 n (nC1) 的 1 个属性 + 来自 n (nC2) 的 2 个属性 + ... + nCn = (2^n)-1

或者我们可以简单地认为它如下：我们将 n 个属性中的每一个都表示为一个位。当属性必须是超级键的一部分时，我们可以设置 1，否则设置为 0。所以这将是 (2^n)，因为对于 n 位/属性中的每一个，我们有两个选择（1 或 0）。我们减去 1 以避免全 0，即考虑将“无属性”作为超键。所以 (2^n)-1。

当所有属性都可以在功能上确定所有其他属性时，就会发生这种情况。当属性之间存在功能依赖循环时，就会发生这种情况。例如，如果存在关系 R(A,B,C,D)，则 FD 循环将是：

A->B
B->C
C->D
D->A

超级键是A,B,C,D,(AB),(AC),(AD),(BC),(BD),(CD),(ABC),(ACD),(ABD),(BCD),(ABCD)，总计 (2^4)-1=15

对于 nCr 最大的 size-r 键，候选键的最大可能数量将出现。或者换句话说，当所有 size-r 个属性组合都是候选键时，出现最大数量的候选键。

这可以从上面的例子中看出。以上A,B,C,D都是候选键，因此它们的超级键（例如（AB）或（BCD）或（ABCD））都不是候选键。类似地，如果在任何关系中 (AB) 是候选键，那么它的任何超键（比如 ABC 或 ABD）都不能是候选键。

一般来说，nCfloor(n/2) 是关于 n 个属性的关系的最大可能候选键数。

PS：这考虑了候选键是最小超键的定义（不能从中删除任何属性，同时仍使其能够唯一标识/在功能上确定所有其他属性）

Answer 2

具有 n 个属性的 R 的最大超级键数为 2^n，这是 R 属性的幂集的大小。当您意识到∅（空集）可能是候选键并且∅是每个属性集的子集时，这一点很明显。

候选键的最大数量由 nC(n/2)（二项式系数）给出。