*2.4 关系演算与查询优化

关系演算与关系运算不同，是以数理逻辑中的谓词演算为基础的一种运算。与关系代数相比较，关系演算是非过程化的。关系演算只需描述结果的信息，而不需给出获得信息的具体过程。按谓词变元的不同，关系演算可分为记录关系演算和域关系演算。记录关系演算以记录为变量，域关系演算以域为变量。

*2.4.1 关系演算概述

1．记录关系演算

记录关系演算（Tuple Relational Calculus）的形式化表达 为{ t|φ （ t ）}。其中， t 为记录变量，表示一个元数固定的记录； φ （ t ）是以记录变量 t 为基础的公式。该表达式的含义是使 φ （ t ）为真的记录 t 的组合。关系演算由原子公式和运算符组成。

原子公式有以下三类 。

1） R （ t ）。 R 是关系名， t 是记录变量， R （ t ）表示 t 是关系 R 的一个记录。

2） t [ i ]θ s [ j ]。其中， t 和 s 是记录变量，θ是算术比较运算符（如＞、＜、=、≥等）。 t [ i ]θ s [ 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）如果 ϕ ₁ 和 ϕ ₂ 是公式，则 ϕ ₁ ∧ ϕ ₂ 、 ϕ ₁ ∨ ϕ ₂ ， ϕ ₁ 也是公式。其中， ϕ ₁ ∧ ϕ ₂ 表示只有 ϕ ₁ 和 ϕ ₂ 同时为真时 ϕ ₁ ∧ ϕ ₂ 为真，否则 ϕ ₁ ∧ ϕ ₂ 为假； ϕ ₁ ∨ ϕ ₂ 表示只有 ϕ ₁ 和 ϕ ₂ 同时为假时 ϕ ₁ ∨ ϕ ₂ 为假，否则 ϕ ₁ ∨ ϕ ₂ 为真； ϕ ₁ 表示如果 ϕ ₁ 为真，则 ϕ ₁ 为假。3）如果 ϕ 为公式，则∃ t （ ϕ ）也是公式。其中，符号∃是存量词符号。∃ t （ ϕ ）表示若有一个 t 使 ϕ 为真，则∃ t （ ϕ ）为真，否则∃ t （ ϕ ）为假。

4）如果 ϕ 为公式，则∀ t （ ϕ ）也是公式。其中，∀是全称量词符号。∀ t （ ϕ ）表示如果对于所有 t ，都使 ϕ 为真，则∀ t （ ϕ ）为真，否则∀ t （ ϕ ）为假。

5）在记录演算公式中， 各种运算符的优先级 如下。

①算术比较运算符的优先级最高。

②量词次之，且∃的优先级高于∀的优先级。

③逻辑运算符最低，且 的优先级高于∧的优先级，∧的优先级高于∨的优先级。

④加括号时，括号中的运算符优先，同一括号内的运算符的优先级遵循①、②、③三项。

6）有限次地使用上述五条规则得到的公式是记录关系演算公式，其他公式不是记录关系演算公式。

关系代数的运算均可以用关系演算表达式来表示（反之亦然）。下面用关系演算表示 关系代数的五种运算 。

（1） 并运算

（2） 差运算

（3） 笛卡儿积

（4） 投影运算

（5） 选择运算

其中，关系 F′ 是 F 的等价条件。

下面给出一个关系演算的应用案例，供读者参考。

2．域关系演算

域关系演算与记录关系演算相似，记录关系演算中表达式使用的是记录变量，记录变量的变化范围是一个关系，域关系演算表达式中则以属性列为变量，即域变量。域变量的变化范围是上述的某值域。

域关系演算的原子公式 有两种形式。

1） R （ x ₁ ， x ₂ ，…， x _k ）。其中， R 是一个元数为 k 的关系， x _i 是一个常量或域变量。如果（ x ₁ ， x ₂ ，…， x _k ）是 R 的一个记录，则 R （ x ₁ ， x ₂ ，…， x _k ）为真。

2） x θ y 。其中， x 和 y 是常量或域常量，但至少有一个是域变量。θ是算术比较运算符。如果 x 和 y 满足关系θ，则 x θ y 为真。

域关系演算表达式 的 一般形式 为{ x ₁ ， x ₂ ，…， x _k |ϕ （ x ₁ ， x ₂ ，…， x _k ）}。

其中， x ₁ ， x ₂ ，…， x _k 都是域变量， ϕ 是公式。该表达式的含义是使 ϕ 为真的域变量 x ₁ ， x ₂ ，…， x _k 组成的记录集合。

下面是应用域关系演算对商品销售数据库进行查询的实例。

*2.4.2 查询优化常用规则与算法

查询是应用最广泛的操作，查询策略和方法至关重要。为了提高效率，可以先将查询语句转换为执行时间少的关系运算，并选取较优的存取路径，即查询优化。

1．关系代数等价变换规则

关系代数是各种数据库查询语言的基础，各种查询语言都能转换成关系代数表达式，所以关系代数表达式的优化是查询优化的基本方法。两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应的关系时，所得到的结果相同。

两个关系表达式 E ₁ 和 E ₂ 等价可表示为 E ₁ ≡ E ₂ 。

等价变换规则指出两种不同形式的表达式是等价的，可利用第二种形式的表达式代替第一种，或者用第一种形式的表达式代替第二种，主要原因是这两种表达式在任何有效的数据库中运行后将得到同样的结果。

常用的等价变换规则 如下。

（1）笛卡儿积和连接表达式的等价交换律

设 E ₁ 和 E ₂ 是两个关系代数表达式， F 是连接运算的条件，则：

（2）笛卡儿积和连接的结合律

设 E ₁ 、 E ₂ 和 E ₃ 是三个关系代数表达式， F ₁ 和 F ₂ 是两个连接运算的限制条件， F ₁ 只涉及 E ₁ 和 E ₂ 的属性， F ₂ 只涉及 E ₂ 和 E ₃ 的属性，则：

（3）投影的串联

设 E 是一个关系表达式， L ₁ ， L ₂ ，…， L _n 是属性名，则：

说明： 投影运算序列中，只有最后一个运算是需要的，其余可以省略。

（4）选择的串联

设 E 是一个关系表达式， F ₁ 和 F ₂ 是两个选择条件，则：

（5）选择和投影的交换

设 E 为一个关系代数表达式，选择条件 F 只涉及 L 中的属性，则：

π _L （ σ _F （ E ））≡ σ _F （ π _L （ E ））

若上式中的 F 还涉及不属于 L 的属性集 K ，则有：

π _L （ σ _F （ E ））≡ π _L （ σ _F （ π _{L ∧ U} （ E ）））

（6）选择对笛卡儿积的分配律

设 E ₁ 和 E ₂ 是两个关系代数表达式，若 F 只涉及 E ₁ 的属性，则：

σ _F （ E ₁ × E ₂ ）≡ σ _F （ E ₁ ）× E ₂

若 F = F ₁ ∧ F ₂ ，并且 F ₁ 只涉及了 E ₁ 中的属性， F ₂ 只涉及了 E ₂ 中的属性，则：

若 F ₁ 只涉及了 E ₁ 中的属性，而 F ₂ 涉及了 E ₁ 和 E ₂ 中的属性，则：

（7）选择对并的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

σ _F （ E ₁ ∪ E ₂ ）≡ σ _F （ E ₁ ）∪ σ _F （ E ₂ ）

（8）选择对差的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

σ _F （ E ₁ -E ₂ ）≡ σ _F （ E ₁ ） -σ _F （ E ₂ ）

（9）投影对并的分配律

设 E ₁ 和 E ₂ 有相同的属性名，或者 E ₁ 和 E ₂ 表达的关系的属性有对应性，则：

π _L （ E ₁ ∪ E ₂ ）≡ π _L （ E ₁ ）∪ π _L （ E ₂ ）

（10）投影对笛卡儿积的分配律

设 E ₁ 和 E ₂ 是两个关系代数表达式， L ₁ 是 E ₁ 的属性集， L ₂ 是 E ₂ 的属性集，则：

其他的等价关系变换规则请查阅相关文献，此处不一一列举。

2．关系表达式的优化算法

关系代数表达式的优化由DBMS的DML编译器完成。对于给定的查询，根据关系代数等价规则，得到与之等价的优化关系表达式序列，其中每个表达式序列执行的代价有所不同。对于优化器而言，存在选择查询最佳策略问题。

等价规则变换优化关系表达式的算法（关系代数表达式的优化）。

输入：一个待优化的关系表达式的语法树。

输出：计算表达式的一个优化序列。

方法：

1）利用等价变换规则（4）将 变换为 。

2）对每一个选择，利用等价变换（4）～（8），尽可能将它移动到树的叶端。

3）对每一个投影，利用等价变换规则（3）、（5）、（10）中的一般表达式，尽可能将它移动到树的叶端。

4）利用等价变换规则（3）～（5），将选择和投影的串接合并为单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。

5）将上述得到的语法树的内节点分组。每一个二元运算和它所有的直接祖先为一组。若其后代直到叶子全是一元运算，则也将它们并入该组，但当二元运算是广义笛卡儿积并且后面不是与它组成等值连接的选择时，则不能将选择与这个二元运算组成一组，而是将这些一元运算单独分为一组。

讨论思考：

1）什么是关系演算？在关系演算公式中，各运算符优先级是怎样的？

2）记录关系演算和域关系演算有何区别及联系？

3）进行查询优化的主要原因是什么？

4）试举例说明关系表达式优化的过程。 kJQC6aj89/q2nYzjd0VPnRSbcONvr4VpMCRqI/4N5kM2Wr5OPVr5dYDpHlw9uRk/