假设关系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}我们使用函数依赖,这在我看来并非无损,但有点混淆。
如果我们稍微揭开无损分解的概念,它会有所帮助:它实际上只意味着连接R1,R2和R3应该产生原始的R.
你知道the chase测试a.k.a“画面方法”吗?测试无损是一种很酷的算法。它易于编程,在推理数据一致性时,它实际上在业界使用。
我们从所谓的“分解画面”开始,这是一个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)),然后将结果与R和K连接(产生R)。
上面提到的算法是正确的,但计算错误 因为R1含有K,L,M而不是K,L,P 所以这里的第二步LM - > N将被使用 并且它将使R1中的N1到N. 然后使用MP - > K,R1将包含R的所有属性 算法将终止。
当你有很多属性时,画面方法并不那么酷,也不是很有前途的方法。相反,我声称这种方法,
通常,如果R被分解为R1和R2,则R1相交R2 - > R1或R1相交R2 - > R2应该为真。
因此,当它是R1,R2,R3 .. Rn时,首先检查它们中的任何两个是否相同,并在给定的功能依赖性的帮助下将其减少为R.检查(Rn U Rn-1)是否对Rn-1和Rn进行无损分解,如果是,则将Rn-1替换为(Rn U Rn-1),丢弃Rn并继续检查直到完成加入。
如果不是,则返回False。