69.3. 关系数据模型中的操作
在上一节（关系数据模型的形式化定义 [原文引用目标缺失] [查看原文章节]）中，我们定义了关系模型的数学概念。现在我们知道如何用关系数据模型存储数据了，但还不知道对这些表做些什么才能从数据库中检索内容。例如有人可能询问销售零件'Screw'的所有供应商的名称。为此，人们定义了两种相当不同的用于表达关系上操作的记法：
关系代数，一种代数记法，查询通过将专门的操作符应用于关系来表达。
关系演算，一种逻辑记法，查询通过表述答案中的元组必须满足的某些逻辑限制来表达。
69.3.1. 关系代数
关系代数由 E. F. Codd 于 1972 年提出。它由一组关系上的操作组成：
SELECT（σ）：从关系中提取满足给定限制的元组。设
R是一张包含属性A的表。σA=a(R) = {t ∊ R ∣ t(A) = a} 其中t表示R的一个元组，而t(A)表示元组t的属性A的值。PROJECT（π）：从关系中提取指定的属性（列）。设
R是一个包含属性X的关系。πX(R) = {t(X) ∣ t ∊R}，其中t(X) 表示元组t的属性X的值。PRODUCT（×）：构建两个关系的笛卡尔积。设
R是元数为k1 的表，S是元数为k2 的表。R×S是所有这样的k1 +k2 元组的集合：其前k1 个分量构成R中的一个元组，后k2 个分量构成S中的一个元组。UNION（∪）：构建两个表的集合论并集。给定表
R和S（两者的元数必须相同），并集R∪S是属于R或S或两者的元组的集合。INTERSECT（∩）：构建两个表的集合论交集。给定表
R和S，R∩S是既属于R又属于S的元组的集合。我们同样要求R和S元数相同。DIFFERENCE（− 或 ∖）：构建两个表的集合差。设
R和S仍是两张元数相同的表。R-S是属于R但不属于S的元组的集合。JOIN（∏）：通过公共属性连接两张表。设
R是具有属性A、B和C的表，S是具有属性C、D和E的表。两个关系有一个公共属性，即属性C。R ∏ S = πR.A,R.B,R.C,S.D,S.E(σR.C=S.C(R × S)). 我们在这里做了什么？首先计算笛卡尔积R×S。然后选出公共属性C的值相等的那些元组（σR.C = S.C）。现在我们得到一张包含两次属性C的表，再通过投影去掉重复的列来纠正这一点。例 69.2. 一个内连接
让我们看一看执行连接所需的各个步骤所产生的表。给定下面两张表：
R: S: A | B | C C | D | E ---+---+--- ---+---+--- 1 | 2 | 3 3 | a | b 4 | 5 | 6 6 | c | d 7 | 8 | 9
首先计算笛卡尔积
R×S，得到：R x S: A | B | R.C | S.C | D | E ---+---+-----+-----+---+--- 1 | 2 | 3 | 3 | a | b 1 | 2 | 3 | 6 | c | d 4 | 5 | 6 | 3 | a | b 4 | 5 | 6 | 6 | c | d 7 | 8 | 9 | 3 | a | b 7 | 8 | 9 | 6 | c | d
经过选择 σR.C=S.C(R × S) 后，得到：
A | B | R.C | S.C | D | E ---+---+-----+-----+---+--- 1 | 2 | 3 | 3 | a | b 4 | 5 | 6 | 6 | c | d
为去掉重复的列
S.C，我们用下面的操作把它投影出去：πR.A,R.B,R.C,S.D,S.E(σR.C=S.C(R × S)) 并得到：A | B | C | D | E ---+---+---+---+--- 1 | 2 | 3 | a | b 4 | 5 | 6 | c | d
DIVIDE（÷）：设
R是具有属性 A、B、C、D 的表，S是具有属性 C 和 D 的表。除法定义为：R ÷ S = {t ∣ [forall] ts ∊ S ∃ tr ∊ R使得 tr(A,B)=t∧tr(C,D)=ts} 其中 tr(x,y) 表示表
R中仅由分量x和y组成的一个元组。注意元组t只由关系R的分量A和B组成。给定下面的表
R: S: A | B | C | D C | D ---+---+---+--- ---+--- a | b | c | d c | d a | b | e | f e | f b | c | e | f e | d | c | d e | d | e | f a | b | d | e
R ÷ S 的结果推导为
A | B ---+--- a | b e | d
关于关系代数更详细的描述和定义，参见 [ Ullman, 1988 ] 或 [ Date, 1994 ]。
例 69.3. 一个使用关系代数的查询
回想一下，我们阐述所有这些关系操作符，是为了能够从数据库中检索数据。让我们回到上一节（关系数据模型中的操作 [原文引用目标缺失] [查看原文章节]）中的例子：有人想知道销售零件 Screw 的所有供应商的名称。使用关系代数，这个问题可以用下面的操作来回答：
πSUPPLIER.SNAME(σPART.PNAME='Screw'(SUPPLIER ∏ SELLS ∏ PART))
我们把这样的操作称为查询。如果对示例表（供应商与零件数据库 [原文引用目标缺失] [查看原文章节]）求值上述查询，将得到以下结果：
SNAME
-------
Smith
Adams
69.3.2. 关系演算 #
关系演算基于一阶逻辑。关系演算有两种变体：
域关系演算（DRC），其中变量代表元组的分量（属性）。
元组关系演算（TRC），其中变量代表元组。
我们只想讨论元组关系演算，因为它是大多数关系语言的基石。关于 DRC（以及 TRC）的详细讨论，参见 Date, 1994 或 Ullman, 1988 。
69.3.3. 元组关系演算
TRC 中使用的查询具有如下形式：
x(A) ∣ F(x)
其中 x 是元组变量，A 是一个属性集合，F 是一个公式。结果关系由满足
F(t) 的所有元组 t(A) 组成。
如果我们想用 TRC 回答例子一个使用关系代数的查询 [原文引用目标缺失] [查看原文章节]中的问题，可以表述如下查询：
{x(SNAME) ∣ x ∊ SUPPLIER ∧
∃ y ∊ SELLS ∃ z ∊ PART (y(SNO)=x(SNO) ∧
z(PNO)=y(PNO) ∧
z(PNAME)='Screw')}
对供应商与零件数据库 [原文引用目标缺失] [查看原文章节]中的表求值该查询，得到的结果与一个使用关系代数的查询 [原文引用目标缺失] [查看原文章节]中的相同。
69.3.4. 关系代数与关系演算 #
关系代数和关系演算具有相同的表达能力；即所有能用关系代数表达的查询也都能用关系演算表达，反之亦然。这一点最早由 E. F. Codd 于 1972 年证明。该证明基于一个算法（"Codd 归约算法"），通过它可以把关系演算的任意表达式归约为语义等价的关系代数表达式。更详细的讨论参见 Date, 1994 和 Ullman, 1988 。
有时人们说，基于关系演算的语言比基于关系代数的语言"层次更高"或"更具声明性"，因为代数（部分地）指定了操作的顺序，而演算把确定最有效求值顺序的工作留给了编译器或解释器。