关系代数 (数据库)

介绍

关系代数在1970年E.F. Codd发表数据的关系模型之前很少受到注意。Codd曾是皮尔士选集编辑者Arthur W. Burks的博士研究生。Codd提议这样一种代数作为数据库查询语言的基础。第一个基于Codd的代数的查询语言是ISBL，许多作者都认同这个先驱的工作展示了一个使Codd的想法成为有用语言的方式。商务系统12是追随ISBL先例的短命工业级实力的关系DBMS。在1998年Chris Date和Hugh Darwen提议了一种叫Tutorial D的语言，意图用于教学关系数据库理论，它的查询语言也吸取了ISBL的想法。Rel是Tutorial D的一个实现。即使SQL的查询语言也松散的基于了关系代数，尽管SQL中的操作数（表）不完全是关系，很多有用的关于关系代数的理论在SQL对应者中不成立。
因为关系被解释为某个谓词的外延，关系代数的每个运算在谓词演算中都有对应者。例如，自然连接是逻辑AND（）的对应者。如果关系R和S分别表示谓词p1和p2的外延，则R和S的自然连接（R  S）是表示谓词p1  p2的外延的关系。
认识到Codd的代数事实上关于一阶逻辑不完备是很重要的。实现它会引起不可逾越的特定计算困难。为了克服这些困难，他限制操作数为有限关系，并提议了对否定（NOT）和析取（OR）的有限支持。类似的限制在很多其他基于逻辑的计算机语言中也能见到。Codd定义术语关系完备性来称呼一个语言除了他提议的限制之外关于一阶逻辑是完备的。在实践中这些限制对他的关系代数用于数据库用途的适用性没有不利作用。

原始运算

如同任何代数，一些运算是原始的，而可以通过原始运算来定义的另一些运算是导出的。尽管逻辑中的AND, OR和NOT的选取，某种程度上是任意性的是众所周知的，Codd对他的代数作了类似的任意选取。
Codd的代数的六个原始运算是“选择”、“投影”、笛卡尔积（也叫做“叉积”或“交叉连接”）、并集、差集和“重命名”。（实际上，Codd忽略了重命名，而ISBL的发明者显式地包括了它）。这六个运算在省略其中任何一个都要损失表达能力的意义上是基本的。已经依据这六个原始运算定义了很多其他运算。其中最重要的是交集、除法和自然连接。事实上ISBL显著的用自然连接替代了笛卡尔积，它是笛卡尔积的退化情况。
总之，关系代数的运算有与域关系演算或元组关系演算同样的表达能力。但是出于前面介绍中给出的原因，关系代数有严格弱于没有函数符号的一阶谓词演算的表达能力。关系代数实际上对应于一阶逻辑的子集，即没有递归和否定的Horn子句。

投影 (π)

投影是写为的一元运算，这里的是属性名字的集合。这种投影的结果定义为当所有在中的元组被限制为集合的时候所获得的集合。

选择 (σ)

广义选择是写为的一元运算，这里的是由正常选择中所允许的原子和逻辑算子（与）、(或)和（非）构成的命题公式。这种选择选出中使成立的所有元组。

重命名(ρ)

重命名是写为的一元运算，这里的结果同一于，除了在所有元组中的字段被重命名为字段之外。它被简单的用来重命名关系的属性或关系自身。

外连接

尽管连接（或内连接）的结果是由组合两个操作数的匹配元组而形成的元组组成，外连接由这些元组加上通过向一个操作数的未匹配元组扩展上另一个操作数的每个属性的“填充”值而形成的元组组成。
本节定义的运算假定“空”值ω的存在性，我们不定义它并把它用做填充值。不应当假定它为数据库语言SQL所定义的NULL，也不应该假定ω为一个标号而非一个值，也不应该假定它介入了有争议的三值逻辑。
定义三个外连接：左外连接、右外连接和全外连接。（有时省略“外”字）

聚集运算

多数数据库包括五个聚集函数。这些运算是Sum、Count、Average、Maximum和Minimum。在关系代数中被写为Exp1,Exp2,Exp3...Gfunc1,func2,func3...（关系）。必须指定要用的函数，而表达式是可选的。假定有一个叫Account的表有两列，分别是Branch_Name和Balance，并希望找到有最高结余的分部的名字，我们可以写Branch_NameGMax(Balance)（Account）。要找到最高余额我们可以简单的写GMax(Balance)（Account）。

选择

关于选择运算的规则在查询优化中扮演了最重要的角色。选择是可非常有效的减少在它的操作数中的行数的运算，所以如果我们设法把在表达式树中选择向着叶子方向移动，（子表达式产生的）内部关系的大小将被缩小。