1-3:关系代数

关系代数

是一种过程化查询语言。
包括一个运算的集合。
这些运算以一个或两个关系为输入，产生一个新的关系为结果。
关系代数基本运算有：选择，投影，并，集合差，笛卡尔积和更名
基本运算外，还有集合交，自然连接，赋值。［可用基本运算来定义］

基本运算

选择，投影，更名为一元运算，它们对一个关系进行运算。
并，集合差，笛卡尔积对两个关系进行运算。

选择运算

选择运算选出满足给定谓词的元组。
用σ来表示选择，将谓词写作σ的下标，参数关系在σ后的括号中。

	// 选择关系instructor中属于Physics系的元组
	σ_{dept_name="Physics"}(instructor)

通常，允许在选择谓词中比较。
使用

	=/≠/</≤/>/≥

可以用

	and(∧)/or(∨)/not(¬)

将多个谓词合并为一个较大的谓词

	// 找到物理系中工资额大于90000美元的教师
	σ_{dept_name="Physics" ∧ salary>90000}(instructor)

选择谓词可包含两个属性的比较

	// 找出系名与楼名相同的系
	σ_{dept_name=building}(department)

// 关系代数中select类似SQL中的where

投影运算

投影运算是一元运算，返回作为参数的关系，但把某些属性排除在外。
关系是一个集合，所以重复行被去除。
用π表示，希望出现属性作为π下标，关系跟随在π后括号中。

	// 列出所有教师的ID,name,salary
	π_{ID,name,salary}(instructor)

关系运算的组合

关系运算的结果自身也是一个关系。

	// 找出物理系的所有教师的名字
	π_{name}(σ_{dept_name="Physics"}(instructor))

一般地说，
关系代数运算的结果同其输入的类型一样，
仍为关系。
可把多个关系代数运算组合成一个关系代数表达式。
将关系代数运算组合成关系代数表达式如同将算术运算组合成算术表达式一样。

并运算

要使并运算rUs有意义
- 关系r和s必须是同元的，即它们的属性数目必须相同
- 对所有的i，r的第i个属性的域必须和s的第i个属性的域相同

集合差运算

用-表示集合差，
找出在一个关系中而不在另一个关系中的那些元组
r-s为一个包含在r但不在s中所有元组构成的关系

	// 所有开设在2009，秋季学期，且在2010，春季不开的课程
	π_{course_id}(σ_{semester="Fall" ∧ year=2009}(section)) - π_{course_id}(σ_{semester="Spring" ∧ year=2010}(section))

要使并运算r-s有意义
- 关系r和s必须是同元的，即它们的属性数目必须相同
- 对所有的i，r的第i个属性的域必须和s的第i个属性的域相同

笛卡尔积运算

用×表示，使我们可将任意两个关系的信息组合在一起。
将关系r1和r2的笛卡尔积写作r1×r2
由于相同的属性名可能同时出现在r1和r2中，
需提出一个命名机制来区别这些属性。
这里采用的方式是找到属性所来自的关系，
把关系名称附加到该属性上。
对只在两个关系模式之一中出现的属性，通常省略其关系名前缀。
这个命名规则规定作为笛卡尔积运算参数的关系名字必须不同。
关系与自身进行笛卡尔积需借助更名

一般地说，如果有关系r1(R1)和r2(R2)，
则关系r1×r2的模式是R1和R2串接而成的。
关系R中包含所有满足以下条件的元组t:
r1中存在元组t1
且r2中存在元组t2
使得t[R1]=t1[R1]且t[R2]=t2[R2]

	π_{name,course_id}(σ_{instructor.ID=teaches.ID}(σ_{dept_name="Physics"}(instructor×teaches)))

	// 一个等价形式
	π_{name,course_id}(σ_{instructor.ID=teaches.ID}((σ_{dept_name="Physics"}(instructor))×teaches))

更名运算

关系代数表达式的结果没有可供我们引用的名字，可用更名运算给其一个可供引用的名字
ρ表示更名运算。
对给定关系代数表达式E，
ρ_{x}(E)返回表达式E的结果，并把名字x赋给了它。
对一个关系ｒ来说，
它自身被认为是一个【平凡的】关系代数表达式。
故可将更名运算运用于关系r，
这样可得到具有新名字的一个相同的关系。

更名运算的另一形式如下：
设关系代数表达式E是n元的，
则表达式
ρ_{x(A1,A2,...,An)}(E)返回表达式E的结果，并赋给它名字x，同时将各属性更名为A1,A2,...,An
	

用$1,$2,...指代第一个，第二个属性，...
位置标记也适用于关系代数表达式运算的结果

	// 获取非最高工资
	π_{$4}(σ_{$4<$8}(instructor×instructor))

笛卡尔积把两个关系的属性串接起来
在笛卡尔积中$4代表第一个instructor的属性salary
$8代表第二个instructor的属性salary

$R1可指代第一个作为运算对象的关系
$R2可指代第二个关系

关系代数的形式化定义

关系代数中基本的表达式是如下二者之一：
- 数据库中的一个关系
- 一个常数关系
常数关系可在{}内列出它的元组来表示
如
{(222,Ein,Phy,950), (765,Sing,Fina,800)}
关系代数中一般的表达式是由更小的子表达式构成的
设E1和E2是关系代数表达式，则以下这些都是关系代数表达式
- E1 U E2
- E1 - E2
- E1 × E2
- σ_{P}(E1)，其中P是E1的属性上的谓词
- π_{s}(E1)，其中S是E1中某些属性的列表
- ρ_{x}(E1)，其中x是E1结果的新名字

附加的关系代数运算

对每个新运算，均可以基本运算写出一个等价形式

集合交运算

∩
任何使用了集合交的关系代数表达式，可通过用一对集合差运算替代集合交

	r ∩ s = r - (r - s)

自然连接运算

对笛卡尔积选择，大多数情况下会要求进行笛卡尔积的两个关系在所有相同属性上值一致。
⋈
自然连接运算首先形成它的两个参数的笛卡尔积，
然后基于两个关系模式中都出现的属性上的相等性进行选择
最后去除重复属性

排在最前面的是两个关系模式的相同属性
其次是只属于第一个关系模式的属性
最后是只属于第二个关系模式的属性


设r(R)和s(S)是两个关系，
r和s的自然连接表示为r⋈s，是模式R U S 上的一个关系
其形式化定义如下

	r⋈s=π_{RUS}(σ_{r.A1=s.A1 ∧ r.A2=s.A2 ∧ ... ∧ r.An=s.An}(r×s))
	其中R ∩ S = {A1,...,An}
	如R ∩ S　＝　∅，则r⋈s＝r×s

theta连接是自然连接的扩展，
它使得我们可把一个选择运算和一个笛卡尔积运算合并为单独的一个运算
考虑关系r(R)和s(S)
设θ是模式R U S　的属性上的谓词，则theta连接运算 r ⋈_{θ} s = σ_{θ}(r×s)

赋值运算

←

	// 可把r⋈s写作
	temp1←R×S
	temp2←σ_{r.A1=s.A1 ∧ r.A2=s.A2 ∧ ... ∧ r.An=s.An}(temp1)
	result=π_{RUS}(temp2)

使用赋值运算，可把查询表达为一个顺序程序
该程序由一系列赋值加上一个其值被作为查询结果显示的表达式组成
对关系代数查询而言，赋值必须赋给一个临时关系变量
对永久关系的赋值形成了对数据库的修改

外连接运算

- 左外连接
取出左侧关系中所有与右侧关系的任一元组都不匹配的元组
用空值填充所有来自右侧关系的属性
再把产生的元组加到自然连接的结果中
保证所有来自左侧关系的信息在左外连接结果中都得到保留
- 右外连接
用空值填充来自右侧关系的所有与左侧关系的任一元组都不匹配的元组
将结果加到自然连接的结果中
保证所有来自右侧关系的信息在右外连接结果中都得到保留
- 全外连接
既填充左侧关系中与右侧关系的任一元组都不匹配的元组
又填充右侧关系中与左侧关系的任一元组都不匹配的元组
把结果都加到连接的结果中

	// 外连接运算可用基本关系代数运算表示
	r 左连接　s　可写成
	(r⋈s)U[(r-π_{R}(r⋈s)) × {(null,...,null)}]
	其中常数关系{(null,...,null)}的模式是　S-R

扩展的关系代数运算

它们可实现一些不能用基本关系代数运算来表达的查询。称为扩展的关系代数运算。

广义投影

允许在投影列表中使用算术运算和字符串函数等来对投影进行扩展。
π_{F1,F2,...,Fn}(E)
E是任意关系代数表达式
F1,F2,...,Fn中的每一个都涉及常量及E的模式中属性的算术表达式。
最基本情况下，算术表达式可仅仅是一个属性或常量
在表达式中可使用对数值属性或产生数值结果的表达式的+,-,*,/等代数运算。
广义投影还允许其他数据类型上的运算，如字符串的串接
π_{ID, name, dept_name, salary/12}(instructor)

聚集

可用来对值的集合使用
sum
avg
count
min
max
使用聚集函数对其进行操作的汇集中，
一个值可出现多次，
称这样的汇集为多重集。
集合是多重集的特例，每个值只出现一次。

	// 结果所一个单一属性的关系，只包含单独的一行，表示所有教师工资总和
	// 所有教师工资总和
	G_{sum(salary)}(instructor)

有时在计算聚集函数前，必须去除重复值．
用distinct加在函数名后

	// 找出2010,春季教课的教师数
	G_{count_distinct(ID)}(σ_{semester="Spring" ∧ year=2010}(teaches))

有时希望对一组元组集合而非单个元组集合执行聚集函数

	// 先对关系执行分组
	// 对每个分组使用聚集
	// 求出每个系的平均工资
	dept_name_G_{average(salary)}(instructor)

聚集运算G通常形式
{G1,G2,...,Gn}_G_{F1(A1),...,Fm(Am)}(E)
E是任意关系代数表达式
G1,G2,...,Gn是用于分组的一系列属性
每个Fi是一个聚集函数，每个Ai是一个属性名．
运算的含义如下：
表达式E的结果中元组以如下方式被分成若干组
- 同一组中所有元组在G1,G2,...,Gn上的值相同
- 不同组元组在G1,G2,...,Gn上的值不同
故，各组可用属性G1,...,Gn上的值来唯一标识
对每个组
(g1,g2,...,gn)来说
结果中有一个元组
(g1,...,gn,a1,...,am),其中对每个i，ai是将聚集函数Fi作用于该组的属性Ai上的多重值得到的结果．
G1,G2,...,Gn为空时，相当于没有分组．


SQL与关系代数
典型的SQL查询如下：
select A1,A2,...,An
from r1,r2,...,rm
where P
每个Ai表示一个属性，
每个ri代表一个关系
P表示一个谓词
等价于多重集关系代数表达式
π_{A1,A2,...,An}(σ_{P}(r1 x r2 x ... x rm))
如省略掉where，则P就是true

select A1, A2, sum(A3)
from r1,...,rm
where P
group by A1,A2
等价于
{A1,A2}_G_{sum(A3)}(π_{A1,A2,...,An}(σ_{P}(r1 x r2 x ... x rm)))