^∗2.4 关系演算与查询优化

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

^∗2.4.1 关系演算概述

1.记录关系演算

记录关系演算（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）如果ϕ₁和ϕ₂是公式，则ϕ₁∧ϕ₂，ϕ₁∨ϕ₂，￢ϕ₁也是公式。其中，ϕ₁∧ϕ₂表示，只有ϕ₁和ϕ₂同时为真时ϕ₁∧ϕ₂为真，否则ϕ₁∧ϕ₂为假；ϕ₁∨ϕ₂表示只有ϕ₁和ϕ₂同时为假时ϕ₁∨ϕ₂为假，否则ϕ₁∨ϕ₂为真；￢ϕ₁表示，如果ϕ₁为真，则￢ϕ₁为假。

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]}

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₂，…，xk都域变量，ϕ是公式。该表达式的含义是：使ϕ为真的域变量x₁，x₂，…，x_k组成的记录集合。

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

【案例2-22】查询性别为男的所有售货员的编号和姓名。

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

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

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

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

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

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

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

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

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

E₁×E₂≡E₂×E₁

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

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

（E₁×E₂）×E₃≡E₁×（E₂×E₃）

（3）投影的串联

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

π_L1（π_L2（…（π_Ln（E）…））≡π_L1（E）

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

（4）选择的串联

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

σ_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₁和E₂是两个关系代数表达式，若F只涉及E₁的属性，则

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

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

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

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

σ_F（E₁×E₂）≡σ_F2（σ_F2（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₂的属性集，则

π_L1∪L2（E1×E₂）≡π_L1（E₁）×π_L2（E₂）

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

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

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

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

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

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

方法：

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

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

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

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

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

讨论思考：

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

2）记录关系演算和域关系演算有什么区别和联系？

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

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