database - 函数依赖的数量

Question

找出具有 n 个属性的关系中函数依赖的数量？

首先想到，我发现左侧可以有 N+1 种可能性(null 也可以存在。)同样地，右侧有 N+1 种可能性。
因此FD的总数应该是
(n+1)*(n+1) - 1

但是给出的答案是 2^(n+1) 。

在分析答案时，我们可以看到它们不包括 ABC -> A 等琐碎的问题。

那么正确的答案应该是什么？？？

Answer 1

LHS 上有 2^n 个可能的属性集，RHS 上有 2^n 个可能的属性集。两个计数都包括空集。

它们之间可能的不同对的数量是 2^n * 2^n。

虽然在技术上是正确的，但这个答案也意味着还考虑了诸如 {AB} -> {} 之类的 FD。其中有多少？对于 LHS 的每个基数 l，有 2^l 个可能的子集，如果出现在 RHS 上，每个子集都会给出一个平凡的 FD。所以平凡的 FD 的数量是 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1。总共留下 2^(2*n) + 1 - 2^(n+1).

但现在我们只排除了 {AB} -> {A} 等，而不是 {AB} -> {AC}。如果我们希望 RHS 仅提及 LHS 上未提及的属性，则对于 LHS 的每个基数 l，RHS 上有 2^(n-l)-1 个可能的子集(额外的需要减一，因为必须排除空集)。总和为 2^0 - 1 + 2^1 - 1 + 2^2 - 1 + ... + 2^n - 1 = 2^(n+1) - 1 - (n + 1)。

还是和给出的答案不一样。无论如何，这个问题的表述非常糟糕。这个问题没有说明要排除琐碎的 FD。这个问题没有说明要排除“部分微不足道的”FD。

顺便说一句，让我们把答案带到测试中。选择一个度数为 1 的关系，{A}。有四种可能的 FD:

{} -> {} 简单，LHS 的 RHS 子集
{} -> {A}
{A} -> {} 平凡，LHS 的 RHS 子集
{A} -> {A} 平凡，LHS 的 RHS 子集。

如果要排除琐碎的 FD，正确答案是“一”。你的教科书说它是“四”。