估计自然连接的结果大小

Question

我有以下表格

R1( A , B, C) 有 1.000 行

R2( C , D, E) 有 1.500 行

R3( E , F) 750 行

其中粗体字母表示主键。

我需要估计自然连接 R1 |x| 的行数 R2 |x| R3。

我的教科书提出了以下解决方案

无论我们以哪种方式连接 R1、R2 和 R3，它们的自然连接都是相同的（连接既是关联又是可交换的）。可以使用先加入 R1 和 R2，然后将结果与 R3 连接的策略来估计大小。将 R1 与 R2 连接将产生最多 1.000 行的表，因为 C 是 R2 的键。同样，将该结果与 R3 连接将产生最多 1.000 行的表，因为 E 是 R3 的键。因此，最终关系最多有 1.000 行！

我原以为最终关系最多有 750 行，因为 R3 只有 750 行。

教科书的解决方案不正确，还是我遗漏了什么？

Answer 1

您最多有1000行从自然连接的R1，并R2因为有两种可能：要么1）所有的值 R1.C存在于R2.C（即R1.C是一个“外键”的R2），或者，2）有值R1.C不存在在R2.C。

在第一种情况下，你必须精确地1000行的加入，因为对于每行R1有只有一行在R2与相同的值C，因为C是一个关键R2，并为一定值C，只有一个排它，因此您可以将一行R1与 中的一行连接起来R2，结果正好有 1000 行。

在第二种情况下，结果中有n行，而 0 ? ň？1000，其中n是R1其值C存在于R2中的行数：实际上，当 的行R1具有C存在于 中的值时R2，您将再次获得结果中的单行。

结合这两种可能性，我们可以说中的行数R1 ? R2是一个值 n，其中 0 ? ň？1000。

现在考虑第二个连接。由于您最多有 1000 行R1 ? R2，因此在这 1000 行中的每一行中，您都可以拥有一个值E是否存在于表中R3。但由于E是在一个主键R3，当你加入每个那些ň与行R3，你可以找到对应的行最大的一个中R3。所以你的结果将有许多行等于m，这样m ? 名词。

将这些结果放在一起，我们知道对于m， 的行数 R1 ? R2 ? R2，包含以下内容： 0 ? 米？1000。

添加

（基于@ypercube 的评论？？）。

请注意，结果可以很容易地推广。如果您在k 个表 R _i , i = 1, ..., k之间有自然连接或内部等值连接，并且您可以将连接重新排序为：R ₁ ? [R ₂ ？……？R _k，使得 R _i ? ř_我1是R的主键（或唯一的属性）_我1，则结果的基数将总是小于或等于R的基数₁。