估計自然連接的結果大小
我有以下表格
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 行。
教科書的解決方案是不正確的，還是我遺漏了什麼？
您最多有 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 in rows，其中 0 ≤ n ≤ 1000，其中n是 的值存在於 中的行數
R1：C實際上R2，當一行 的R1值C存在於 中時R2，您在結果中再次獲得單行。結合這兩種可能性，我們可以說 in 的行數
R1 ⨝ R2是一個值 n，其中 0 ≤ n ≤ 1000。現在考慮第二個連接。由於您在 中最多有 1000 行
R1 ⨝ R2，因此在這 1000 行中的每一行中，您都可以擁有一個值，E該值存在或不存在於 table 中R3。但是由於E是 中的主鍵R3，因此當您將這n行中的每一行加入時，R3您最多可以在 中找到一個對應的行R3。因此，您的結果將具有等於m的行數，即m ≤ n。將這些結果放在一起，我們知道對於m， 的行數
R1 ⨝ R2 ⨝ R2滿足以下條件：0 ≤ m ≤ 1000。添加
（基於@ypercubeᵀᴹ 的評論）。
請注意，結果很容易概括。如果您在k個表 R i , i = 1, …, k之間有自然連接或內等連接，並且您可以將連接重新排序為： R 1 ⨝ R 2 ⨝ … ⨝ R k，這樣R i ⨝ R i +1在 R i +1的主鍵（或唯一屬性）上，則結果的基數將始終小於或等於 R 1的基數。