功能依赖的无损连接和分解

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)

我们如何判断这种分解是否无损？ 我用过这个例子

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

Answer 1

如果我们稍微揭开无损分解的概念,它会有所帮助:它实际上只意味着连接R1,R2和R3应该产生原始的R.

你知道追逐测试又称"画面方法"吗？测试无损是一种很酷的算法.它易于编程,在推理数据一致性时,它实际上已在业界使用.

我们从所谓的"分解画面"开始,这是一个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,LM,N)),然后将结果与R3上的K和M(产生R)相连.