下载掌阅APP，畅读海量书库
立即打开
关系演算不同于关系运算，是以数理逻辑中的谓词演算为基础的一种运算。与关系代数相比较，关系演算是非过程化的。关系演算只需描述结果的信息，而无须给出获得信息的具体过程。按谓词变元的不同，关系演算可分为记录关系演算和域关系演算。记录关系演算以记录为变量，域关系演算以域为变量。
记录关系演算（Tuple Relational Calculus）中，其形式化表达为
{t|ϕ(t)}
其中，t为记录变量，表示一个元数固定的记录，ϕ（t）是以元组变量t为基础的公式。该表达式的含义是使ϕ（t）为真的记录t的组合。关系演算由原子公式和运算符组成。
原子公式有以下3类。
1）R（t）。R是关系名，t是记录变量，R（t）表示t是关系R的一个记录。
2）t[i]θt[j]。其中t和s是记录变量，θ是算术比较运算符（如>、<、=、≥等）。t[i]θt[j]表示记录t的第i个分量与记录s的第j个分量满足θ关系。例如，t[3]≥s[5]表示t第3个分量大于等于s的第5个分量。
3）t[i]θC或Cθt[i]。其中C表示一个常量，t是记录变量，θ是算术比较运算符。t[i]θC表示t的第i个分量与常量C满足关系θ。例如，t[2]>5表示t的第2个分量大于5。
公式可递归定义如下。
1）每个原子公式是公式。
2）如果ϕ 1 和ϕ 2 是公式，则ϕ 1 ∧ϕ 2 ，ϕ 1 ∨ϕ 2 ，﹁ϕ 1 也是公式。其中，ϕ 1 ∧ϕ 2 表示，只有ϕ 1 和ϕ 2 同时为真时ϕ 1 ∧ϕ 2 为真，否则ϕ 1 ∧ϕ 2 为假；ϕ 1 ∨ϕ 2 表示只有ϕ 1 和ϕ 2 同时为假时ϕ 1 ∨ϕ 2 为假，否则ϕ 1 ∨ϕ 2 为真；﹁ϕ 1 表示，如果ϕ 1 为真，则﹁ϕ 1 为假。
3）如果ϕ为公式，则∃t（ϕ）也是公式。其中符号∃是存量词符号，∃t（ϕ）表示，若有一个t使ϕ为真，则∃t（ϕ）为真，否则∃t（ϕ）为假。
4）如果ϕ为公式，则∀t（ϕ）也是公式。其中∀是全称量词符号，∀t（ϕ）表示，如果对所有t，都使ϕ为真，则∀t（ϕ）为真，否则∀t（ϕ）为假。
5）在记录演算公式中，各种运算符的优先级如下。
①算术比较运算符最高。
②量词次之，且∃的优先级高于∀的优先级。
③逻辑运算符最低，且﹁的优先级高于∧的优先级，∧的优先级高于∨的优先级。
④加括号时，括号中运算符优先，同一括号内的运算符之优先级遵循①、②、③。
6）有限次地使用上述5条规则得到的公式是记录关系演算公式，其他公式不是记录关系演算公式。
关系代数的运算均可以用关系演算表达式来表示（反之亦然）。下面用关系演算来表示关系代数的5种运算。
（1）并运算
R∪S={t|R（t）∨S（t）}
（2）差
R-S={t|R（t）∧﹁S（t）}
（3）笛卡儿积
（4）投影
（5）选择
σ F （R）={t|R（t）∧F′}
其中，关系F′是F的等价条件。
下面给出一个关系演算的应用案例，供读者参考。
【案例2-21】
查询商品表中所有产品的价格大于500元的商品，{t|商品（t）∧t[4]>500}；查询性别为女的所有售货员的编号和姓名，{t|（
）（售货员（u）∧u[3]='女'∧t[1]=u[1]∧t[2]=u[2]}
域关系演算与记录关系演算相似，记录关系演算中表达式使用的是记录变量，记录变量的变化范围是一个关系，域关系演算表达式中以属性列为变量，即域变量，域变量的变化范围是上述的某值域。
域关系演算的原子公式有两种形式。
1）R（x 1 ，x 2 ，…，x k ）。其中，R是一个元数为k的关系，x i 是一个常量或域变量。如果（x 1 ，x 2 ，…，x k ）是R的一个记录，则R（x 1 ，x 2 ，…，x k ）为真。
2）xθy。其中，x和y是常量或域常量，但至少有一个是域变量。θ是算术比较运算符。如果x和y满足关系θ，则xθy为真。
域关系演算表达式的 一般形式 为：{x 1 ，x 2 ，…，x k |ϕ（x 1 ，x 2 ，…，x k ）}
其中，x 1 ，x 2 ，…，xk都域变量，ϕ是公式。该表达式的含义是：使ϕ为真的域变量x 1 ，x 2 ，…，x k 组成的记录集合。
下面应用域的关系演算对商品销售数据库进行查询。
【案例2-22】 查询性别为男的所有售货员的编号和姓名。
查询是应用最广泛的操作，查询策略和方法至关重要。为了提高效率，可以先将查询语句转换为执行时间少的关系运算，并选择较优的存取路径，即查询优化。
关系代数是各种数据库查询语言的基础，各种查询语言都能转换成关系代数表达式，所以关系代数表达式的优化是查询优化的基本方法。两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应的关系时，所得到的结果相同。
两个关系表达式E 1 和E 2 等价可表示为E 1 ≡E 2 。
等价变换规则指出两种不同形式的表达式是等价的，可利用第二种形式的表达式代替第一种，或者用第一种形式的表达式代替第二种，主要原因是这两种表达式在任何有效的数据库中运行后将得到同样的结果。
常用的等价变换规则如下。
（1）笛卡儿积和连接表达式的等价交换律
设E 1 和E 2 是两个关系代数表达式，F是连接运算的条件，则
E 1 ×E 2 ≡E 2 ×E 1
（2）笛卡儿积和连接的结合律
设E 1 、E 2 和E 3 是3个关系代数表达式，F 1 和F 2 是两个连接运算的限制条件，F 1 只涉及E 1 和E 2 的属性，F 2 只涉及E 2 和E 3 的属性，则
（E 1 ×E 2 ）×E 3 ≡E 1 ×（E 2 ×E 3 ）
（3）投影的串联
设E是一个关系表达式，L 1 ，L 2 ，…，L n 是属性名，则
π L1 （π L2 （…（π Ln （E）…））≡π L1 （E）
说明：
投影运算序列中，只有最后一个运算是需要的，其余可以省略。
（4）选择的串联
设E是一个关系表达式，F 1 和F 2 是两个选择条件，则
σ F1 （σ F2 （E））≡σ F1∧F2 （E）
（5）选择和投影的交换
设E为一个关系代数表达式，选择条件F只涉及L中的属性，则
π L （σ F （E））≡σ F （π L （E））
若上式中F还涉及不属于L的属性集K，则有
π L （σ F （E））≡π L （σ F （π L∧U （E）））
（6）选择对笛卡儿积的分配律
设E 1 和E 2 是两个关系代数表达式，若F只涉及E 1 的属性，则
σ F （E 1 ×E 2 ）≡σ F （E 1 ）×E 2
若F=F 1 ∧F 2 ，并且F 1 只涉及了E 1 中的属性，并且F 2 只涉及了E 2 中的属性，则
σ F （E 1 ×E 2 ）≡σ F1 （E 1 ）×σ F2 （E 2 ）
若F 1 只涉及了E 1 中的属性，而F 2 只涉及了E 1 和E 2 中的属性，则
σ F （E 1 ×E 2 ）≡σ F2 （σ F2 （E 1 ）×E 2 ）
（7）选择对并的分配律
设E 1 和E 2 有相同的属性名，或者E 1 和E 2 表达的关系的属性有对应性，则
σ F （E 1 ∪E 2 ）≡σ F （E 1 ）∪σ F （E 2 ）
（8）选择对差的分配律
设E 1 和E 2 有相同的属性名，或者E 1 和E 2 表达的关系的属性有对应性，则
σ F （E 1 -E 2 ）≡σ F （E 1 ）-σ F （E 2 ）
（9）投影对并的分配律
设E 1 和E 2 有相同的属性名，或者E 1 和E 2 表达的关系的属性有对应性，则
π L （E 1 ∪E 2 ）≡π L （E 1 ）∪π L （E 2 ）
（10）投影对笛卡儿积的分配律
设E 1 和E 2 是两个关系代数表达式，L 1 是E 1 的属性集，L 2 是E 2 的属性集，则
π L1∪L2 （E1×E 2 ）≡π L1 （E 1 ）×π L2 （E 2 ）
其他的等价关系变换规则请查阅相关文献，此处不再一一列举。
关系代数表达式的优化是由DBMS的DML编译器完成的。对于给定的查询，根据关系代数等价规则，得到与之等价的优化关系表达式序列，其中每个表达式序列执行的代价有所不同。对于优化器而言，存在选择查询最佳策略问题。
等价规则变换优化关系表达式的算法（关系代数表达式的优化）如下。
输入：一个待优化的关系表达式的语法树。
输出：计算表达式的一个优化序列。
方法：
1）利用等价变换规则（4）将形如
变换为
。
2）对每一个选择，利用等价变换规则（4）～规则（8）尽可能将它移动到叶端。
3）对每一个投影利用等价变换规则（3）、规则（5）、规则（10）中的一般表达式尽可能将它移动到树的叶端。
4）利用等价变换规则（3）～规则（5）将选择和投影的串接合并为单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。
5）将上述得到的语法树的内结点分组，每一个二元运算和它所有的直接祖先为一组。若其后代直到叶子全是一元运算，则也将它们并入该组，但当二元运算是广义笛卡儿积并且后面不是与它组成等值连接的选择时，则不能将选择与这个二元运算组成同一组，而是将这些一元运算单独分为一组。
讨论思考：
1）什么是关系演算？在关系演算公式中，各种运算符的优先级是什么？
2）记录关系演算和域关系演算有什么区别和联系？
3）进行查询优化的原因是什么？
4）试举例说明关系表达式优化的过程。