无损连接与函数依赖分解

Question

9

假设关系表R(K,L,M,N,P)，并且在R上存在以下函数依赖关系：

 - L  -> P
 - MP -> K
 - KM -> P
 - LM -> N

假设我们将其分解为以下3个关系：

 - R1(K, L, M)
 - R2(L, M, N)
 - R3(K, M, P)

我们如何确定这个分解是否是无损的？我使用了这个例子

R1 ∩ R2 = {L, M}, R2 ∩ R3 = {M}, R1 ∩ R3 = {K,M}。我们使用函数依赖关系，但在我看来，这不是无损的，但有点困惑。

- DjMix

那些不是唯一的FD，因为还有平凡的FD和根据Armstrong公理必须成立的FD。所以你可能被告知那是一个“覆盖”。如果你不知道它是一个覆盖，你就无法回答这个问题。 - philipxy

3个回答

0

上述算法是正确的，但计算错误了。
因为R1包含K、L、M而不是K、L、P。
所以在第二步中将使用LM-->N
这将使N1变为R1中的N
然后MP-->K将被使用，并且R1将包含R的所有属性
因此，算法将终止。

- Vivek Pandya

请将这个句子分成更小的块以提高可读性！ - stkent

0

当你有很多属性时，表方法并不那么酷，也不是一个有前途的方法。相反，我主张这种方法，

一般来说，如果R被分解为R1和R2，要么 R1交 R2 ->R1 要么 R1交 R2 ->R2 应该成立。

因此，当有R1、R2、R3..Rn时，首先检查它们中的任意两个是否满足上述条件，并借助给定的函数依赖将其缩减为R。检查 (Rn U Rn-1) 是否具有无损分解为 Rn-1 和 Rn，如果是，则用 (Rn U Rn-1) 替换 Rn-1，丢弃 Rn 并继续检查直到完成连接。

如果没有，则返回 False。

- user11370656

1

该测试仅适用于二进制分解。但是，有些分解具有超过2个组件，其中成对连接以进行重构是单独丢失的，但最终结果不会。 - philipxy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SáT · Accepted Answer

帮助我们将无损分解的概念简单化一些会很有帮助：它实际上只是意味着连接 R1、R2 和 R3 应该产生原始的 R。

你知道 the chase 测试，又称“表方法”吗？这是一个很酷的算法，用于测试无损性。它易于编程，并且实际上在推理数据一致性时被工业界使用。

我们从所谓的“分解表”开始，这是一个 n*m 矩阵，其中 n 是关系数，m 是属性数。对于每个字段，如果关系 n 包含属性 m，我们写入属性名称；否则，我们写入带有关系编号下标的属性名称。

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   n1  p1
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

现在，数据表将会被“追踪”（因此算法得名）。我们注意到第一行和第二行在它们的L和M值上是相同的。依赖关系LM->N意味着它们的N值也应该相同。让我们把第一行的n1改为第二行的N。

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   N   p1
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

现在第一行和第三行的K和M值相同。由于存在KM->P的依赖关系，因此它们应该也在P值上达成一致。

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   N   P
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

我们完成了！只要任何一行具有所有正确的属性（如第一行所示），算法就会终止并证明分解确实是无损的。

请注意，依赖关系的重复应用表示将共享键的关系连接起来。因此，我们所做的是在L和M上连接R1和R2（得到(K, L M, N)），然后将结果与R3在K和M上连接（得到R）。