join - 函数依赖的无损连接和分解

Question

假设关系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)

我们如何判断这种分解是否是无损的？
I used this example

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

Answer 1

如果我们稍微揭开无损分解的概念的神秘面纱会有所帮助:它实际上只是意味着加入 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)连接起来)，然后在 K 和 M 上将结果与 R3 连接(产生 R)。