关系代数
关系代数（relational algebra）：一种过程化查询语言。包括一个运算的集合，集合中运算以一个或两个关系为输入，产生一个新的关系作为结果。
关系代数的基本运算包括：选择、投影、并、集合差、笛卡尔积、更名。
其他运算：集合交、自然连接、赋值，可用基本运算来定义。
关系运算的结果自身也是一个关系，可用一个关系运算表达式作为另一个关系运算的参数，因此可以把多个关系代数运算组合成一个关系代数表达式（relational-algebra expression）。
关系代数定义了一套在表上运算且输出结果也是表的代数运算。这些运算可以混合使用来得到表达所希望查询的表达式。关系代数定义了关系查询语言中使用的基本运算。
关系代数运算可分为：基本运算、附加的运算（可用基本运算表达）、扩展的运算（其中一些扩展了关系代数的表达能力）。
关系代数是一种简介的、形式化的语言，不适用于那些偶尔使用数据库系统的用户，因此商用数据库系统采用有更多“语法修饰”的语言。（SQL基于关系代数）
1. 基本运算
一元运算：对一个关系进行运算，包括选择、投影、更名运算。
二元运算：对两个关系进行运算，包括并、集合差、笛卡尔积运算。
选择（select）运算：选出满足给定谓词的元组，用小写sigma(σ)表示，下标为谓词，括号中为参数关系。
e.g. 找出关系instructor中属于物理系的所有教师
σdept_name=”Physics”(instructor)
e.g. 找出工资额大于90000美元的所有教师
σsalary>90000(instructor)
可用连词and(∧)、or(∨)、not(¬)将多个谓词合并为一个较大的谓词。
e.g. 找出属于物理系且工资大于90000美元的所有教师
σdept_name=”Physic”∧salary>90000(instructor)
选择谓词中可包括两个属性的比较。
e.g. 找出所有系名与楼名相同的系
σdept_name=building(department)
注意：关系代数中的属于select与SQL中的关键词select含义不同，关系代数中属于select对应SQL中的where。
投影（project）运算：返回作为参数的关系，但把某些属性排除在外，所有重复行均被去除。用大写pi(Π)表示，下标为在结果中出现的属性，括号中为参数关系。
e.g. 列出所有教师的ID、name和salary，而不关系dept_name。
ΠID, name, salary(instructor)
e.g. 找出物理系所有教师的名字
Πname(σdept_name=”Physics”(instructor))
并（union）运算： 可将两个集合并起来，找出出现在两个集合之一或同时出现在两个集合中的所有元组。用∪表示。
e.g. 找出开设在2009年秋季学期或者2010年春季学期或者这二者皆开的所有课程的集合。
Πcourse_id(σsemester=”Fall”∧year=2009(section))∪Πcourse_id(σsemester=”Spring”∧year=2010(section))
/*注意：结果中重复值只留下单个元组。*/
必须保证做并运算的关系是相容的，否则运算结果没有意义。要使并运算r∪s有意义（r和s可以是数据库关系或作为关系代数表达式结果的临时关系），要求以下两个条件同时成立：
a. 关系r和s必须是同元的（属性数目相同）。
b. 对所有的i，r的第i个属性的域必须和s的第i个属性的域相同。
集合差（set-difference）运算：表达式r-s包含所有在r中而不在s中的元组的关系。
e.g. 找出所有开设在2009年秋季学期但是在2010年春季学期不开的课程。
Πcourse_id(σsemester=”Fall”∧year=2009(section))-Πcourse_id(σsemester=”Spring”∧year=2010(section))
类似并运算，必须保证做集合叉运算的关系是相容的，否则运算结果没有意义。要使集合差运算r-s有意义，要求一下两个条件同时成立：
a. 关系r和s必须是同元的。
b. 对所有的i，r的第i个属性的域必须和s的第i个属性的域相同。
笛卡尔积（Cartesian-product）运算：将任意两个关系的信息组合在一起，结果中包含所有可能的元组对。关系r1和r2的笛卡尔积写作r1×r2，假如r1有n1个元组，r2有n2个元组，则可由n1×n2种方式选择元组对。
由于相同的属性名可能同时出现在r1和r2中，需要一个命名机制来区别这些属性。可采用把属性所来自的关系名称附加到该属性上的方法。
e.g. r = instructor×teaches的关系模式
(instructor.ID, instructor.name, instructor.dept_name, instructor.salary, teaches.ID, teaches.course_id, teaches.sec_id, teaches.semeser, teaches.year)
/*对于只在两个关系模式之一出现的属性，通常省略其关系名前缀。因此可将r的关系模式写作：*/
(instructor.ID, name, dept_name, salary, teaches.ID, course_id, sec_id, semester, year)
注意：该命名规则规定作为笛卡尔积运算参数的关系名称必须不同，因此当某个关系要与自身做笛卡尔积或在笛卡尔积中使用关系代数表达式结果时可能产生问题，可通过更名运算给关系一个名字以引用其属性来解决。
e.g. 找出物理系中的所有教师，以及他们所教授的所有课程。
/* σdept_name=”Physics”(instructor×teaches)只包含物理系的教师的元组，但course_id列可能包含并非这些教师所教授的课程；
σinstructor.ID=teaches.ID(σdept_name=”Physics”(instructor×teaches))包含物理系教师以及他们所教的课程的元组；
Πname, course_id(σinstructor.ID=teaches.ID(σdept_name=”Physics”(instructor×teaches)))投影得到需要的教师名字列和corse_id列。*/
Πname, course_id(σinstructor.ID=teaches.ID(σdept_name=”Physics”(instructor×teaches)))
/*用关系代数表达查询的方法并不唯一，也可采用如下等价查询：*/
Πname, course_id(σinstructor.ID=teaches.ID((σdept_name=”Physics”(instructor))×teaches))
更名（rename）运算：给关系代数表达式的结果赋上名字以供引用，用小写rho(ρ)表示。
表达式ρx(E)返回给定关系代数表达式E的结果并把名字x赋给它。更名运算也可用于关系，可得到具有新名字的一个相同的关系。
更名运算的另一形式：ρx(A1, A2, …, An)(E)。假设关系代数表达式E是n元的，运算返回表达式E的结果，并把名字x赋给它，同时将各属性更名为A1, A2, …, An。
e.g. 找出大学里的最高工资
/*步骤1：计算出一个由非最高工资组成的临时关系。
首先通过更名运算引用其中一个instructor关系以便计算笛卡尔积instructor×instructor，再构造选择运算比较任意两个出现在同一元组中的salary选择较低的元组。通过投影选取instructor.salary列得到非最高工资构成的临时关系*/
Πinstructor.salary (σinstructor.salary<d.salary(instructor×ρd(instructor)))
/*步骤2：计算关系Πsalary (instructor)和刚才计算出的非最高工资构成的临时关系的集合差，得到结果。*/
Πsalary (instructor)-Πinstructor.salary (σinstructor.salary<d.salary(instructor×ρd(instructor)))
更名运算不是必须的，因为可以用位置标记隐含地作为关系（或关系代数表达式运算的结果）的属性名，用$1、$2、…指代第一个属性、第二个属性…以此类推。
e.g. 用位置标记来计算大学里的非最高工资构成的临时关系
/*在笛卡尔积(instructor×instructor)中，$4代表第一个instructor的属性salary，$8代表第二个instructor的属性salary。*/
Π$4(σ$4<$8(instructor×instructor))
如果一个二元运算需要区分其运算对象的两个关系，也可使用为指标及作为关系的名称。E.g. $R1指代第一个作为运算对象的关系，$R2指代第二个关系。
2. 关系代数的形式化定义
关系代数中基本的表达式是以下二者之一：a. 数据库中的一个关系；b. 一个常数关系。
常数关系：可在{}内列出其元组来表示。
E.g. {(22222, Einstein, Physics, 95000), (76543, Singh, Finance, 80000)}
设E1和E2都是关系代数表达式，则以下这些都是关系代数表达式：
·E1∪E2
·E1-E2
·E1×E2
·σp(E1)，P为E1属性上的谓词。
·ΠS(E1)，S为E1上某些属性的列表。
·ρx(E1)，x为E1结果的新名字。
3. 附加的关系代数表达式
关系代数的基本运算足以表达任何关系代数查询。附加的关系代数运算不能增强关系代数的表达能力，但可以简化一些常用的查询。
集合交（intersection）运算 (∩)
e.g. 找出在2009年秋季和2010年春季都开设的课程
Πcourse_id(σsemester=”Fall”∧year=2009(section))∩Πcourse_id(σsemester=”Spring”∧year=2010(section))
任何使用了集合交的关系代数表达式都可以通过一对集合差运算替代重写：
r∩s=r-(r-s)
自然连接（natural join）运算 (⋈)：首先形成两个参数关系的笛卡尔积，然后基于两个关系模式中都出现的属性上的相等性进行选择（只考虑两个关系在所有相同属性有相同值的元组组成的元组对），最后去除重复属性（并不重复记录在两个关系模式中都出现的属性）。
自然连接的形式化定义：
设r(R)和s(S)（模式分别为R和S的两个关系），其自然连接的结果r ⋈ s是模式R∪S上的一个关系。
r ⋈ s = ΠR∪S(σr.A1=s.A1∧r.A2=s.A2∧…∧r.An=s.An(r×s))，其中R∩S={A1, A2, …, An}。
如果r和s不含有任何相同属性，即R∩S=∅，则r ⋈ s = r×s。
所列出的属性的顺序：两个关系模式的相同属性排在最前，只属于第一个关系模式的属性其次，只属于第二个关系模式的属性最后。
e.g. 找出所有教师的姓名，连同他们教的所有课程的course_id。
/*instructor和teaches自然连接的结果模式为(ID, name, dept_name, salary, course_id)，投影后得到模式为(name, course_id)的关系。*/
Πname, course_id(instructor ⋈ teaches)
考虑两个关系模式R和S，可将关系模式看作集合：用R∩S表示同时出现在R和S中的属性名，用R∪S表示出现在R中、S中或在二者中都出现的属性名，用R-S表示出现在R中而不出现在S中的属性名，用S-R表示出现在S中而不出现在R中的属性名。
自然连接时可结合的（associative）。
e.g. 找出计算机系的所有教师，以及他们教授的所有课程的名称。
/* 自然连接instructor ⋈ teaches ⋈ course的执行顺序可能为
(instructor ⋈ teaches) ⋈ course 或 instructor ⋈ (teaches ⋈ course)，二者是等价的。*/
Πname, title(σdept_name=”Comp.Sci.”(instructor ⋈ teaches ⋈ course))
theta连接（theta join）运算：是自然连接的扩展。
考虑关系r(R)和s(S)，θ是模式R∪S的属性上的谓词。r ⋈θ s = σθ(r×s)
赋值（assignment）运算 (←)：可用于给临时关系变量赋值，便于写关系代数表达式。
e.g. 自然连接运算r ⋈s的定义可写作
temp1←r×s
temp2←σr.A1=s.A1∧r.A2=s.A2∧…∧r.An=s.An(temp1)
result = ΠR∪S(temp2)
对关系代数查询而言，赋值必须是赋给一个临时关系变量。对永久关系的赋值形成了对数据库的修改。
外连接（outer-join）运算：连接运算的扩展，可处理缺失的信息（因为不满足自然连接条件而不能在自然连接结果中找到的元组），避免信息的丢失。
外连接运算与自然连接运算类似，不同之处在于外连接在连接计算结果中添加额外的带空值的元组，以此保留在连接中丢失的元组。
外连接运算有三种形式：
左外连接（left outer join）(⟕)：取出左侧关系中所有与右侧关系的任一元组都不匹配的元组，用空值填充所有来自右侧关系的属性，再把产生的元组加到自然连接的结果中。所有来自左侧关系的信息在左外连接结果中都得到保留。
右外连接（right outer join）(⟖)：与左外连接相对称，用空值填充来自右侧关系的所有与左侧关系任一元组都不匹配的元组，将结果加到自然连接的结果中。所有来自右侧关系的信息在右外连接中都得到保留。
全外链接（full outer join）(⟗)：既做左外连接又做右外连接，既填充左侧关系中与右侧关系的任一元组都不匹配的元组，又填充右侧关系中与左侧关系任一元组都不匹配的元组，并把结果都加到连接的结果中。
注意：外连接运算可用基本关系代数运算表示。E.g. 左外连接运算r⟕s可写作
/*其中常数关系{(null, …, null)}的模式为S-R。*/
(r ⋈ s)∪(r - ΠR(r ⋈ s)) × {(null, …, null)}
4. 扩展的关系代数运算
扩展的关系代数（extended relational-algebra）运算可实现一些不能用基本的关系代数运算来表达的查询。
广义投影（generalized-projection）：通过允许在投影列表使用算术运算和字符串函数等来对投影进行扩展。
运算形式：
ΠF1, F2, …, Fn(E)
其中E为任意关系代数表达式，F1, F2, …, Fn都是涉及常量以及E的模式中属性的算术表达式。
最基本情况下算术表达式可以仅仅是一个属性或常量，在表达式中可使用对数值属性或产生数值结果的表达式的+、-、*、/等代数运算。广义投影还允许其他数据类型上的运算（如字符串的串接）。
e.g. 查询每个教师的ID、name、dept_name以及每月的工资
ΠID, name, dept_name, salary/12(instructor)
聚集运算(?)
聚集函数（aggregate function）：输入值的一个汇集，将单一值作为结果返回。E.g. 聚集函数sum、avg、count、min、max。
e.g. 使用聚集查询所有教师的工资总和的关系代数表达式
? sum(salary)(instructor)
在计算聚集函数前如果想去除重复，可使用连字符将distinct附加在函数名后。
e.g. 找出在2010年春季学期教课的教师数（每名教师只应计算一次，而不管他教了几门课程。）
/*聚集函数count-distinct确保：即使某位教师授课多于一门，在结果中也只对他计数一次。*/
? count-distinct(ID)(σsemester=”Spring”∧year=2010(teaches) )
可对一组元组集合（而不是单个元组集合）执行聚集函数。
聚集运算的通常形式为：
G1, G2, …, Gn? F1(A1), F2(A2), …, Fm(Am)(E)
其中E为任意关系代数表达式，G1, G2, …, Gn是用于分组的一系列属性，每个Fi是一个聚集函数，每个Ai是一个属性名。表达式E的结果中的元组被分成若干组，各组用属性G1, G2, …, Gn上的值唯一标识。
属性列G1, G2, …, Gn可以为空，则唯一一组包含关系中所有的元组（相当于没有分组）。
e.g. 分别查询a. 每个系教师的平均工资 b. 所有教师的平均工资
/*先通过dept_name属性对关系instructor进行分组，再对每个分组执行指定查询。*/
dept_name ? average(salary)(instructor)
/*从运算符?左边去掉了属性dept_name，整个关系被当做单个组来执行聚集。*/
? average(salary)(instructor)
多重集（multiset）：使用聚集函数对其进行操作的汇集中，一个值可以出现多次，值出现的顺序是无关紧要的，这样的汇集称为多重集。集合（set）是多重集的特例，其中每个值都只出现一次。
多重集关系代数（multiset relational algebra）：SQL与关系代数不同，允许在输入关系以及查询结果汇总存在元组的多重拷贝。为了映射SQL的这种模式，我们定义了多重集关系代数来对多重集进行操作。
多重集关系代数基本运算的定义：
1. 如果在r1元组t1有c1份拷贝，并且t1满足选择σθ，那么在σθ(r1)中元组t1有c1份拷贝；
2. 对于r1中元组t1的每份拷贝，在ΠA(r1)中都有一个与之对应的ΠA(t1)，表示单个元组t1的投影。
3. 如果在r1中元组t1有c1份拷贝，在r2中元组t2有c2份拷贝，那么在r1×r2中就有元组t1t2的c1*c2份拷贝。
按照SQL中的相应含义，还可用相似方法定义多重集的并、交、集合差运算。（聚集运算在多重集定义下没有变化）
元组关系演算
不同于关系代数表达式，元组关系演算（tuple relational calculus）是非过程化的（nonprocedural）查询语言，只描述所需信息，而不给出获得该信息的具体过程。
元组关系演算中的查询表达为：{ t | P(t) }。含义：所有使谓词P为真的元组t的集合。
1. 查询示例
e.g. 找出工资大于80000美元的所有教师的ID
/*所有满足如下条件的元组t的集合：在关系instructor中存在元组s使t和s在属性ID上的值相等，且s在属性salary上的值大于80000美元。
因为ID属性是对t进行限制的条件所涉及的唯一属性，因此结果只得到ID列上的关系。*/
{ t| ∃s∈instructor( t[ID] = s[ID] ∧ s[salary] >80000 ) }
e.g. 找出位置在Watson楼的系中的所有教师姓名
/*元组变量u保证该系位于Watson楼，元组变量s被限制到与u的dept_name相同。结果得到name列上的关系。*/
{ t | ∃s∈instructor( t[name] = s[name]
∧∃u∈department( u[dept_name] = s[dept_name]
∧ u[building] = ‘Watson’ ) ) }
e.g. 找出在2009年秋季学期或2010年春季学期或这两个学期都开设的所有课程的course_id
/*给出至少满足下面两个条件之一的couse_id元组的集合：
·在关系section中满足semester=Fall且year=2009的某个元组包含该course_id；
·在关系section中满足semester=Spring且year=2010的某个元组包含该course_id。*/
{ t | ∃s∈section ( t[course_id] = s[course_id] )
∧s[semester] = “Fall”∧s[year] = 2009 )
∨∃u∈section (u[course_id] = t[course_id] )
∧u[semester] = “Spring”∧u[year] = 2010 )
e.g. 找出只在2009年秋季和2010年春季两个学期都开设的所有课程的course_id
{ t | ∃s∈section ( t[course_id] = s[course_id] )
∧s[semester] = “Fall”∧s[year] = 2009 )
∧∃u∈section (u[course_id] = t[course_id] )
∧u[semester] = “Spring”∧u[year] = 2010 )
e.g. 找出2009年秋季开设而2010年春季不开的所有课程的course_id
/*从2009年秋季开设的课程中去掉那些在2010年春季开设的课程*/
{ t | ∃s∈section ( t[course_id] = s[course_id] )
∧s[semester] = “Fall”∧s[year] = 2009 )
∧¬∃u∈section (u[course_id] = t[course_id] )
∧u[semester] = “Spring”∧u[year] = 2010 )
e.g. 找出所有那些选了生物系全部课程的学生
/*所有满足如下条件的ID列上的元组t的集合：
对关系course中所有元组u，如果u在dept_name属性上的值是’Biology’，那么在关系takes中一定存在一个包含该学生ID以及该课程course_id的元组。
注意：如果生物系没有开设任何课程，则所有学生ID都满足条件。该情况下，∃r∈student ( r[ID] = t[ID] )保证结果是关系student里的学生ID的值。*/
{ t | ∃r∈student ( r[ID] = t[ID] ) ∧
∀u∈course (u[dept_name] = “Biology”⇒
∃s∈takes ( t[ID] = s[ID]
∧s[course_id] = u[course_id] ) ) }
形式化定义
元组关系演算表达式的形式：{ t | P(t) }
P为一个公式，公式中可出现多个元组变量，如果元组变量不被∃或∀修饰则称为自由变量，否则称为受限变量。
公式由原子构成。原子可以为如下形式之一：
·s∈r，其中s为元组变量，r为关系；
·s[x] ? u[y]，其中s、u为元组变量，x为s所基于的关系模式中的一个属性，y为u所基于的关系模式中的一个属性，?为比较运算符(＜, ≤, ＝, ≠, ＞, ≥)（要求x和y所属域成员可用?比较）；
·s[x] ? c，其中s为元组变量，x为s所基于的关系模式中的一个属性，c是属性x所属域中的常量。
根据如下规则用原子构造公式：
·原子是公式；
·如果P1是公式，则¬P1和(P1)也都是公式；
·如果P1和P2是公式，则P1∨P2、P1∧P2和P1⇒P2也都是公式；
·如果P1(s)是包含自由元组变量s的公式，r为关系，则∃s∈r(P1(s))和∀s∈(P1(s))也都是公式。
元组关系演算中的等价性规则：
·P1∧P2等价¬(¬(P1)∨¬(P2))；
·∀t∈r(P1(t))等价¬∃t∈r(¬P1(t))；
·P1⇒P2等价¬(P1)∨P2。
元组关系演算表达式的安全性
为避免元组关系演算表达式产生一个无限的关系，需对元组关系演算进行限制。
域（domain）：元组关系公式P的域用dom(P)表示，是P所引用的所有值的集合。它既包括P自身用到的值，又包括P中所涉及的关系的元组中出现的所有值。（i.e. P中显式出现的值，以及名称出现在P中的那些关系的所有值的集合）。
如果出现在表达式{ t | P(t) }结果中的所有值均来自dom(P)，则表达式是安全的，安全的表达式一定包含有限的结果。
语言表达能力
限制在安全表达式范围内的元组关系演算和基本关系代数（不包括扩展的关系代数运算符）具有相同的表达能力。
因此:
对于每个只运用基本操作的关系代数表达式，都有与之等价的元组关系演算表达式；
对于每个元组关系演算表达式，也都有与之等价的关系代数表达式。
域关系演算
域关系演算（domain relational calculus）：关系演算的另一种形式，使用从属性域中取值的域变量，而不是整个元组的值。
1. 形式化定义
域关系演算中的表达式形式：
{ <x1, x2, …, xn> | P(x1, x2, …, xn) }
其中x1, x2, …, xn代表域变量，P代表由原子构成的公式。
原子可以为如下形式之一：
·<x1, x2, …, xn>∈r，其中r为n个属性上的关系，x1, x2, …, xn为域变量或域常量；
·x?y，其中x和y为域变量，?为比较运算符（要求属性x和y所属域可用?比较）；
·x?c，其中x为域变量，c是x作为域变量的那个属性域中的常量。
根据如下规则用原子构造公式：
·原子是公式；
·如果P1是公式，则¬P1和(P1)也都是公式；
·如果P1和P2是公式，则P1∨P2、P1∧P2和P1⇒P2也都是公式；
·如果P1(x)是包含自由域变量x的公式，则∃x(P1(x))和∀x(P1(x))也都是公式。
我们把∃a,b,c(P(a,b,c))作为a(∃b(∃c(P(a,b,c))))的简写。
2. 查询示例
e.g. 找出工资在80000美元以上的教师的ID、name、dept_name和salary。
{ <i, n, d, s> | <i, n, d, s>∈instructor∧s>80000 }
e.g. 找出工资大于80000美元的所有教师的姓名
{ < i > | ∃n, d, s (<i, n, d, s>∈instructor∧s>80000) }
e.g. 找出在物理系的所有教师的姓名，以及他们教授的所有课程的course_id。
{ <n, c> | ∃i, a, s, y (<I, c, a, s, y>∈teaches
∧∃d, s(<i, n, d, s>∈instructor∧d=”Physics”) ) }
e.g. 找出在2009年秋季学期或2010年春季学期或这两个学期都开设的所有课程的集合
{ < c > | ∃a, s, y, b, r, t(<c, a, s, y, b, r, t>∈section
∧s=”Fall”∧y=”2009”)
∨∃a, s, y, b, r, t(<c, a, s, y, b, r, t>∈section
∧s=”Spring”∧y=”2010”) }
e.g. 找出选了生物系开设的全部课程的所有学生
/*如果生物系没开设任何课程，结果将包含所有学生。*/
{ < i > | ∃n, d, tc(<i, n, d, tc>∈student) ∧
∀ci, ti, dn, cr(<ci, ti, dn, cr>∈course ∧ dn=“Biology” ⇒
∃si, se, y, g(<I, ci, si, se, y, g>∈takes) ) }
表达式的安全性
不安全的域关系演算表达式的结果中会出现不在表达式域中的值。
如果下列条件同时成立，则认为表达式{ <x1, x2, …, xn> | P(x1, x2, …, xn) }是安全的：
1. 表达式的元组中所有值均来自dom(P)；
2. 对每个形如∃x(P1(x))的子公式，子公式为真当且仅当dom(P1)中有某个值x使P1(x)为真；
3. 对每个形如∀x(P1(x))的子公式，子公式为真当且仅当P1(x)对dom(P1)中所有值x均为真。
语言表达能力
限制在安全表达式范围内的域关系演算和限制在安全表达范围内的元组关系演算具有相同的表达能力（因此也与基本关系代数的表达能力等价）。
注意：没有任何一个域关系演算等价于聚集运算，但它可以扩展以支持聚集。
元组关系演算和域关系演算是非过程化语言，代表了关系查询语言所需的基本能力。基本关系代数是一种过程化的语言，在能力上等价于被限制在安全表达式范围内的关系演算的这两种形式。
关系演算是简介的、形式化的语言，不适合于那些偶尔使用数据库系统的用户。（QBE和Datalog基于元祖关系演算和域关系演算）
