写在前面

连接是数据库算法的一个重要内容，但数据库的知识有些忘了，最近刚好需要，就又看着笔记重新整理了一遍。

一、笛卡儿积

先来从笛卡儿积开始说起。笛卡儿积是集合的一种基本运算。假设有两个表$R$和$S$，则笛卡儿积的定义如下：

R × S = { t r t s ^ ∣ t r ∈ R ∧ t s ∈ S } R\times S=\{\widehat{t_{r}t_{s}}|t_r\in R \wedge t_s\in S \} R×S={tr​ts​ ​∣tr​∈R∧ts​∈S}

简单点说，就是$R$表中每一行（即一个元组$t_r$）和$S$表中每一行（即一个元组$t_s$）进行两两组合，并把组合的结果作为一个新的大表。

• 一个例子如下：假设给定的$R$表（3个元组）和$S$表（4个元组）为：

• 则$R\times S$的结果为（3*4=12个元组）：

二、连接

连接的定义式如下：

R ⋈ A θ B S = { t r t s ^ ∣ t r ∈ R ∧ t s ∈ S ∧ t r [ A ] θ t s [ B ] } R\bowtie_{A\theta B} S=\{\widehat{t_{r}t_{s}}|t_r\in R \wedge t_s\in S \wedge t_r[A] \theta t_s[B]\} R⋈AθB​S={tr​ts​ ​∣tr​∈R∧ts​∈S∧tr​[A]θts​[B]}

其中，$\theta$是一个运算符，可以是$>$，$\ge$，$<$，$\le$，$\ne$等；$A$和$B$是列数相等且同域的属性组。

简单点说，连接实际上是从笛卡儿积的结果中选择某些元组作为一个新表。

• 一个例子如下，$R$表和$S$表同上：

三、等值连接

等值连接的定义如下：

R ⋈ A = B S = { t r t s ^ ∣ t r ∈ R ∧ t s ∈ S ∧ t r [ A ] = t s [ B ] } R\bowtie_{A= B} S=\{\widehat{t_{r}t_{s}}|t_r\in R \wedge t_s\in S \wedge t_r[A] = t_s[B]\} R⋈A=B​S={tr​ts​ ​∣tr​∈R∧ts​∈S∧tr​[A]=ts​[B]}

简单点说，等值连接是特殊的连接，特殊就特殊在它把原来的任意$\theta$运算符固定为$=$，这也是它之所以被叫做等值连接的原因。

• 一个例子如下，$R$表和$S$表同上：

四、自然连接

自然连接的定义式如下：

R ⋈ S = { t r t s ^ [ U − B ] ∣ t r ∈ R ∧ t s ∈ S ∧ t r [ B ] = t s [ B ] } R\bowtie S=\{\widehat{t_{r}t_{s}}[U-B]|t_r\in R \wedge t_s\in S \wedge t_r[B] = t_s[B]\} R⋈S={tr​ts​ ​[U−B]∣tr​∈R∧ts​∈S∧tr​[B]=ts​[B]}

其中，$U$是所有属性组，$B$是比较的属性组，要求两个表均有$B$（即属性组同名且同域）。

简单点说，自然连接就是特殊的等值连接。它的特殊之处有两个：1.它不需要指定比较的属性，它会自动比较两个表的同名同域属性，只有这些属性对应的值均相等，元组才会被从两个表中选择出来进行连接。2.二是它能够删除连接结果中的重复属性列（就是$[U-B]$的操作），这个是等值连接没有的。

• 一个例子如下，$R$表和$S$表同上：

五、外连接

外连接是针对自然连接而言的。因为自然连接会丢失原表的信息，所以用外连接来选择保留原表中没有连接的元组（即悬浮元组）。但实际上，这种思路也可以用在普通的连接上。上面提到的连接、等值连接和自然连接均可视为内连接，因为它们均没有保留悬浮元组。外连接的方式有三种：

• 全外连接：两边的悬浮元组都保留，其他属性填空值。
  

• 左外连接：左边的悬浮元组保留。
  

• 右外连接：右边的悬浮元组保留。
  

六、嵌套循环连接

这是一种连接的算法，并不影响连接的结果，它针对的是连接的过程。

简单点说，就是用两个（如果是多表连接就是多个）循环，依次顺序比较两个（或者多个）表的每个元组，看它们是否满足连接条件。如果满足，就提取出来连接并组成结果。

时间复杂度是$O(N_r\times N_s)$。

• 一个例子如下，$R$表和$S$表同上：
  

注意，该方法对任意表均适用，但效率最低。另外，通常用小表作为外表。

七、排序合并连接

这也是一种连接的算法，并不影响连接的结果，它针对的是连接的过程。

两个表均排序好，扫描的时候均从上往下扫描，但对外层表的每一个元组，内层表并不是从头开始扫描，而是接着上次扫描终止的地方开始扫描，相当于交替扫描遍历。

时间复杂度是$O(N_r+N_s)$。

• 一个例子如下，$R$表和$S$表同上：

注意，该方法效率较高，但是要求两个表均已排序。

八、索引连接

这也是一种连接的算法，并不影响连接的结果，它针对的是连接的过程。

简单点说，就是在较大表中建立对小表的索引，查找的时候不是顺序查找，而是通过索引来查找。

注意，该方法要求较大表中有对应属性的索引，且只能做等值连接。

九、哈希连接

这也是一种连接的算法，并不影响连接的结果，它针对的是连接的过程。

简单点说，是先用哈希函数将两个表分类后在遍历进行连接。此时遍历也不需要全表遍历，只需要在相同哈希值的元组中遍历即可。

注意，该方法要求较小的表能够全部放入内存（因为是遍历大表来在小表中查找相同哈希值的元组，所以小表及其对应哈希值应该要全部放入内存中），且只能做等值连接。