写在前面

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

一、笛卡儿积

先来从笛卡儿积开始说起。笛卡儿积是集合的一种基本运算。假设有两个表 R R R S S 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={trts trRtsS}

简单点说,就是 R R R表中每一行(即一个元组 t r t_r tr)和 S S S表中每一行(即一个元组 t s t_s ts)进行两两组合,并把组合的结果作为一个新的大表。

  • 一个例子如下:假设给定的 R R R表(3个元组)和 S S S表(4个元组)为:

R表和S表

  • R × S R\times S R×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]\} RAθBS={trts trRtsStr[A]θts[B]}

其中, θ \theta θ是一个运算符,可以是 > \gt > ≥ \ge < \lt < ≤ \le ≠ \ne =等; A A A B B B是列数相等且同域的属性组。

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

  • 一个例子如下, R R R表和 S S 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]\} RA=BS={trts trRtsStr[A]=ts[B]}

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

  • 一个例子如下, R R R表和 S S 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]\} RS={trts [UB]trRtsStr[B]=ts[B]}

其中, U U U是所有属性组, B B B是比较的属性组,要求两个表均有 B B B(即属性组同名且同域)。

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

  • 一个例子如下, R R R表和 S S S表同上:

自然连接

五、外连接

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

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

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

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

六、嵌套循环连接

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

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

时间复杂度是 O ( N r × N s ) O(N_r\times N_s) O(Nr×Ns)

  • 一个例子如下, R R R表和 S S S表同上:
    嵌套循环连接

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

七、排序合并连接

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

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

时间复杂度是 O ( N r + N s ) O(N_r + N_s) O(Nr+Ns)

  • 一个例子如下, R R R表和 S S S表同上:

排序合并连接

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

八、索引连接

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

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

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

九、哈希连接

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

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

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

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐