关系代数

参考文献

• 关系代数的基本运算
• SQL 与关系代数

关系代数

关系代数的运算符

集合运算符

运算符	含义	英文
$\cup$	并	Union
$−$	差	Difference
$\cap$	交	Intersection
$\times$	笛卡尔积	Cartesian Product

比较运算符

运算符	含义
>	大于
≥	大于等于
<	小于
≤	小于等于
=	等于
≠	不等于

专门的关系运算符

运算符	含义	英文
$\sigma$	选择	Selection
$\prod$	投影	Projection
$\Join$	链接	Join
$\div$	除	Division

逻辑运算符

运算符	含义
$\wedge$	与
$\vee$	或
$\neg$	非

五种基本的关系代数运算

并(Union)

• 关系R与S具有相同的关系模式,即R与S的结构相同,R与S的并属于R或属于S的元组构成的集合,记作$R\cup S$,定义如下

  $$R\cup S = \{t|t\in R \vee t\in S \}$$

差(Difference)

• 关系R与S具有相同的关系模式,关系R与S的差是属于R但不属于S的元组构成的集合记作$R-S$,定义如下

  $$R-S = \{t|t\in R \vee \notin S\}$$

广义笛卡尔积(Extended Cartesian Product)

• 两个数分别为 n 目和 m 目的关系 R 和 S 的 笛卡尔积是一个 (n+m) 列的元组的集合。组的前 n 列是关系 R 的一个元组，后 m 列是关系 S 的一个元组，记作$R\times S$，定义如下

  $$R \times S =\{t|t\eqslantless (\stackrel\frown{t n},\stackrel\frown{t m})| \stackrel\frown{t n}\in R \wedge \stackrel\frown{t m}\in S \}$$

  • $(\stackrel\frown{t n},\stackrel\frown{t m})$称为元组的连接(concatenation)

投影（Projection）

• 投影运算是从关系垂直方向进行运算,在关系R中选出若干属性列A组成新的关系,记作$\pi A(R)$,其形式:

  $$\prod_{A} (R)=\{ t[A]|t\in R\}$$

选择(Selection)

• 选择运算是从关系的水平方向进行运算，是从关系 R 中选择满足给定条件的元组，记作 $σ_F(R)$，其形式如下：

  $$σ_F(R)=\{t|t∈R∧F(t)=True\}$$

扩展的关系代数运算

交（Intersection）

• 关系 R 和 S 具有相同的关系模式，交是由属于 R 同时双属于 S 的元组构成的集合，记作 $R\cap S$，形式如下

  $$R\cap S=\{t|t\in R \wedge t\in S\}$$

连接(Join)

• 从 R 与 S的笛卡尔积中选取属性间满足一定条件的元组，可由基本的关系运算笛卡尔积和选取运算导出，表示为

  $$R\Join_{X\theta Y } S = \sigma_{X\theta Y}(R\times S)$$

  • 连接与笛卡尔积的区别在于笛卡尔积包含两个关系的所有元组的组合，而连接只包含那些满足连接条件的元组的组合。如果没有连接条件，即无条件连接，则连接变成笛卡尔积

等值连接

• 当$\theta$ 为$=$时,称之为等值连接,记为$R\Join_{X=Y}S$

自然连接

• 自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是 相同的属性组，并且在结果集中将 重复的属性列 去掉.

除(Division)

• 关系的除运算是同时从关系的水平方向和垂直方向上进行的运算。假设关系R（X,Y）和S（Y,Z），X、Y、Z为属性组。$R\div S$应当满足元组在X上的分量值X的像集YX包含关系S在属性组Y上投影的集合。其形式定义为：

  $$R\div S=\{t_{n}[X]|t_{n}\in R \wedge \prod_{Y}(S)\subseteq Y_{X} \}$$

  • R与S的除运算得到一个新的关系P（X），P是R中满足下列条件的元组在X属性列上的投影：
    • 关系R（X，Y）和S（Y，Z），其中X，Y，Z为属性组（R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集）;元组在X上的分量值X 的像集YX包含S在Y上的投影。
    • 元组在X上的分量值X 的像集YX包含S在Y上的投影。

更名运算

• $\rho_{x}(A1,A2,A3....A_{n})(E)$表示的是将关系E更名为X，Ai表示的是给E的第i个字段指定别名

关系代数操作与SQL的关系

投影

• 他的作用和SQL中的SELECT基本相同

  SELECT id FROM user;

• 用关系代数来写,就可以写成$\prod_{id}(user)$,多列则是这样$\prod_{id,name}(user)$

选择

• 由于一些历史原因，关系代数中的选择和 SQL 中的 SELECT 不是一个意思，而是更接近 WHERE, 我们可以通过选择运算选择关系中符合指定条件的部分。

  SELECT * FROM user WHERE id = 1;

  • 等价于$\sigma_{id=1}(user)$
  • 选择运算中可以使用谓词包括:=,≠,<,⩽,>,⩾同时还可以使用连词 and($\wedge$),or($\vee$),not($\neg$)将多个谓词合并为一个较大的连词。

投影和选择结合

SELECT id,name FROM user WHERE id = 1;

• 等价于$\prod_{id,name}(\sigma_{id=1}(user))$

并运算

SELECT id FROM user UNION SELECT id FROM address;

• 等价于$\prod_{id}(user) \cup \prod_{id}(address)$
• 几点需要额外注意的：
  • 此处的并运算是集合运算，所以结果是去重的，结果集中不存在重复的元组（而在SQL语句中，指定UNION ALL是可以保留重复的）
  • 关系r与关系s必须是同元的，即它们的属性的数目要求必须相同（这就和SQL语句中UNION使用的时候要求上下两个语句的字段数相同是一样的意思）
  • 关系r和关系s对应位置的属性域应该是类型兼容的（同样和SQL中UNION使用时，每个对应位置字段类型兼容是一样的意思）

差运算

SELECT id FROM user EXCEPT SELECT id FROM address;

• 等价于$\prod_{id}(user)-\prod_{id}(address)$
• 差运算对不同关系的要求和并运算是相同的。

笛卡尔积

SELECT * FROM user CROSS JOIN address;

• 等价于$user \times address$