分解无损连接算法

Question

我得到了以下关于无损连接的解释。请有人解释变量'r‘是什么，以及它如何出现在算法/方程/公式的两边？

“如果关系R被分解为关系R1，R2，使得对于每一个法律实例r. R=πR1(r)⋈πR2 (r) ...then分解本身被称为无损连接分解。“

注: R1和R2为下标。

Answer 1

r应该代表模式R的任何关系值/实例(即无损可分解)。但是，即使一个关系值是无损可分解的，我们也必须注意我们分解成哪些属性。

更重要的问题是:什么是R1，R2？

你的引文可能是基于维基百科文章或者其中的一个链接--这似乎是完全的垃圾；比维基百科在关系模型主题上的通常标准要糟糕得多。(例如，它显示了一个笛卡尔乘积来重新组合投影-而无损join通常需要一个连接: bowtie操作符，如您所示。)

算子π是关系代数投影。π通常以属性名称(或者更恰当地说是一组属性名称)进行订阅。这些通常由X, Y或类似的符号来表示。那么R1，R2应该是属性名的集合，而不是关系。他们当然不能兼而有之。(我所能想象的是，R1, R2意在代表这两个关系的模式/属性集。)

此外，对于无损连接分解，我们要求两个投影一起包含R的所有属性。(通常还有一些共同的属性，这样连接就可以匹配在一起了。)

所以我们应该

r1 = πX(r)             -- r1 is the value of R1 corresponding to r
r2 = πY(r)             -- ditto for R2
attributes of R = X ∪ Y   -- intersection of X, Y not necessarily empty
r = r1 ⋈ r2

一个明显的例子是R具有属性{A, B, C}和{A}是关键。然后我们可以分解为X = {A, B}, Y = {A, C}。