数据库:笛卡儿积、连接、等值连接、自然连接、外连接、嵌套循环连接、排序合并连接、索引连接和哈希连接
写在前面
连接是数据库算法的一个重要内容,但数据库的知识有些忘了,最近刚好需要,就又看着笔记重新整理了一遍。
一、笛卡儿积
先来从笛卡儿积开始说起。笛卡儿积是集合的一种基本运算。假设有两个表 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 ∣tr∈R∧ts∈S}
简单点说,就是 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\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]\} R⋈AθBS={trts ∣tr∈R∧ts∈S∧tr[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]\} R⋈A=BS={trts ∣tr∈R∧ts∈S∧tr[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]\} R⋈S={trts [U−B]∣tr∈R∧ts∈S∧tr[B]=ts[B]}
其中, U U U是所有属性组, B B B是比较的属性组,要求两个表均有 B B B(即属性组同名且同域)。
简单点说,自然连接就是特殊的等值连接。它的特殊之处有两个:1.它不需要指定比较的属性,它会自动比较两个表的同名同域属性,只有这些属性对应的值均相等,元组才会被从两个表中选择出来进行连接。2.二是它能够删除连接结果中的重复属性列(就是 [ U − B ] [U-B] [U−B]的操作),这个是等值连接没有的。
- 一个例子如下, 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表同上:
注意,该方法效率较高,但是要求两个表均已排序。
八、索引连接
这也是一种连接的算法,并不影响连接的结果,它针对的是连接的过程。
简单点说,就是在较大表中建立对小表的索引,查找的时候不是顺序查找,而是通过索引来查找。
注意,该方法要求较大表中有对应属性的索引,且只能做等值连接。
九、哈希连接
这也是一种连接的算法,并不影响连接的结果,它针对的是连接的过程。
简单点说,是先用哈希函数将两个表分类后在遍历进行连接。此时遍历也不需要全表遍历,只需要在相同哈希值的元组中遍历即可。
注意,该方法要求较小的表能够全部放入内存(因为是遍历大表来在小表中查找相同哈希值的元组,所以小表及其对应哈希值应该要全部放入内存中),且只能做等值连接。
更多推荐
所有评论(0)