无损连接和功能依赖性分解 [英] Lossless Join and Decomposition From Functional Dependencies

问题描述

假设关系R( K, L, M, N, P)和R所具有的功能依赖关系是:

Suppose the relation R( K, L, M, N, P), and the functional dependencies that hold on R are:

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

假设我们将其分解为3种关系，如下所示:

Suppose we decompose it into 3 relations as follows:

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

我们怎么知道这种分解是否是无损的? 我使用了这个示例

How can we tell whether this decomposition is lossless? I used this example

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

R1 ∩ R2 = {L, M}, R2 ∩ R3 = {M}, R1 ∩ R3 = {K,M} we use functional dependencies, and this is not lossless in my opinion, but a little bit confused.

推荐答案

如果我们对无损分解的概念进行一些神秘化，则将有所帮助:这实际上只是意味着将R1，R2和R3连接起来可以产生原始的R.

It helps if we demystify the concept of lossless decomposition a bit: it really just means that joining R1, R2 and R3 should yield the original R.

您知道追逐测试又称为表格方法"吗?这是测试无损性的一种很酷的算法.它易于编程，并且在推理数据一致性时实际上已在行业中使用.

Do you know the chase test a.k.a "the tableau method"? It's a cool algorithm to test for losslessness. It's easy to program, and it's actually used in the industry when reasoning about data consistency.

我们从所谓的分解图"开始，这是一个n * m矩阵，其中n是关系数，m是属性数.对于每个字段，如果关系n包含属性m，我们将写出属性名称.否则，我们将写上带有关系编号的属性名称.

We start with the so-called "tableau of the decomposition", an n*m matrix where n is the number of relations and m is the number of attributes. For every field, if the relation n contains attribute m we write the attribute name; otherwise we write the attribute name subscripted with the number of the relation.

   |  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:

Now the tableau will be "chased" (hence the name of the algorithm). We notice that the first and second rows agree on their L and M values. The dependency LM->N implies that their N values should agree too. Let's change the first row's n1 into the second row's 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值达成共识.

Now the first and third rows agree on their K and M values. We have a KM->P dependency, so they should agree on their P value also.

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

我们完成了！只要任何一行都具有所有适当的属性(就像第一行一样)，该算法就会终止并证明分解确实是无损的.

And we're done! As soon as any of the rows has all of the proper attributes (as the first row does), the algorithm terminates and proves the decomposition was indeed lossless.

请注意，依赖项的重复应用如何表示将关系共享到它们共享的键上.因此，我们要做的就是将L和M上的R1和R2连接起来(对我们(K，L M，N)进行网格划分)，然后将结果与K和M上的R3连接(产生R).

Note how the repeated applications of the dependencies represent joining the relations on the keys they share. So what we did was joining R1 and R2 on L and M (netting us (K, L M, N)), then joining the result with R3 on K and M (that yields R).

这篇关于无损连接和功能依赖性分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！