＊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]θ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）如果ϕ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）笛卡儿积
R×S={tn+m|(∃un)(∃vm)(R(u)∧S(v)∧t[1]=u[1]∧…∧t[n]=u[n]∧t[n+1]
=v[1]∧…∧t[n+m]=v[m]}
（4）投影
πi1,i2,…,ik(R)={t(k)|(∃u)(R(u)∧t[1]=u[i1]∧…∧t[k]=u[ik])}
（5）选择
σF(R)={t|R(t)∧F′}
其中，关系F′是F的等价条件。
下现给出一个关系演算的案例，供读者参考。
【案例2-21】查询商品表中所有产品的价格大于500元的商品，{t|商品（t）∧t[4]＞500}；查询性别为“女”的所有售货员的编号和姓名，{t|（∃u）（售货员（u）∧u[3]='女'∧t[1]=u[1]∧t[2]=u[2]）}。
2．域关系演算
域关系演算与元组关系演算相似，元组关系演算中表达式使用的是元组变量，元组变量的变化范围是一个关系，域关系演算表达式中以属性列为变量，即域变量，域变量的变化范围是某上属的值域。
域关系演算的原子公式有两种形式。
1）R（x1,x2,…,xk）。其中，R是一个元数为k的关系，xi是一个常量或域变量。如果（x1,x2,…,xk）是R的一个元组，则R（x1,x2,…,xk）为真。
2）xθy。其中，x和y是常量或域常量，但至少有一个是域变量。θ是算术比较运算符。如果x和y满足关系θ，则xθy为真。
域关系演算表达式的一般形式为
{x1,x2,…,xk|ϕ(x1,x2,…,xk)}
其中，x1,x2,…,xk是域变量，ϕ是公式。该表达式的含义是：使ϕ为真的域变量x1,x2,…,xk组成的元组集合。
下面试用域关系演算实现对商品销售数据库进行查询。
【案例2-22】查询性别为“男”的所有售货员的编号和姓名。
{x1x2|（∃u1）（∃u2）（∃u3）（∃u4）售货员（u1u2u3u4）∧u3=′男′∧x1=u1∧x2=u2}
*2.4.2 查询优化常用的规则与算法
在实际项目中，查询是应用非常多的操作，并且大多数应用系统随着数据量的增加，查询效率和速度经常是困扰用户和应用系统开发人员的一大难题，因此查询优化至关重要。
对于给定的查询，通常有多种处理策略和方法，也可以写出多种等价的关系代数，不同的代数表达式具有不同的执行代价。为了提高效率，减少运行时间，可以在查询语言处理程序执行查询操作之前，先由数据库系统对用户的查询语句进行转换，将其转变为一串需要执行时间较少的关系运算，并为这些运算选择较优的存取路径，实现查询时间的减少和查询效率的提高，这就是关系数据库的查询优化。大多数商用的关系数据系统都提供SQL语言的预编译功能，在执行语句前对语句进行优化，提高查询的效率。
1．关系代数等价变换规则
关系代数是各种数据库查询语言的基础，各种查询语言都能转换成关系代数表达式，所以关系代数表达式的优化是查询优化的基本方法。两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应的关系时，所得到的结果相同。
两个关系表达式E1和E2等价可表示为E1≡E2。
等价变换规则指出两种不同形式的表达式是等价的，可利用第二种形式的表达式代替第一种，或者用第一种形式的表达式代替第二种，主要原因是这两种表达式在任何有效的数据库中运行后将得到同样的结果。
常用的等价变换规则如下。
（1）笛卡儿积和连接表达式的等价交换律
设E1和E2是两个关系代数表达式，F是连接运算的条件，则
（2）笛卡儿积和连接的结合律
设E1、E2和E3是3个关系代数表达式，F1和F2是2个连接运算的限制条件，F1只涉及E1和E2的属性，F2只涉及E2和E3的属性，则
（3）投影的串联
设E是一个关系表达式，L1，L2，…，Ln是属性名，则
说明：在投影运算序列中，只有最后一个运算是需要的，其余可以省略。
（4）选择的串联
设E是一个关系表达式，F1和F2是两个选择条件，则
（5）选择和投影的交换
设E为一个关系代数表达式，选择条件F只涉及L中的属性，则
πL(σF(E))≡σF(πL(E))
若上式中F还涉及不属于L的属性集K，则有
πL(σF(E))≡πL(σF(πL∪K(E)))
（6）选择对笛卡儿积的分配律
设E1和E2是两个关系代数表达式，若F只涉及E1的属性，则
σF(E1×E2)≡σF(E1)×E2
若F=F1∧F2,并且F1只涉及了E1中的属性，并且F2只涉及了E2中的属性，则
σF(E1×E2)≡σF1(E1)×σF2E2
若F1只涉及了E1中的属性，而F2只涉及了E1和E2中的属性，则
σF(E1×E2)≡σF2(σF2(E1)×E2)
（7）选择对并的分配律
设E1和E2有相同的属性名，或者E1和E2表达的关系的属性有对应性，则
σF(E1∪E2)≡σF(E1)∪σF(E2)
（8）选择对差的分配律
设E1和E2有相同的属性名，或者E1和E2表达的关系的属性有对应性，则
σF(E1-E2)≡σF(E1)-σF(E2)
（9）投影对并的分配律
设E1和E2有相同的属性名，或者E1和E2表达的关系的属性有对应性，则
πL(E1∪E2)≡πL(E1)∪πL(E2)
（10）投影对笛卡儿积的分配律
设E1和E2是两个关系代数表达式，L1是E1的属性集，L2是E2的属性集，则
πL1∪L2(E1×E2)≡πL1(E1)×πL2(E2)
其他的等价关系变换规则请查阅相关文献，在此不一一列举。
2．关系表达式的优化算法
关系代数表达式的优化是由DBMS的DML编译器完成的。对于给定的查询，根据关系代数等价规则，得到与之等价的优化关系表达式序列，其中每个表达式序列执行的代价有所不同。对于优化器而言，存在选择查询最佳策略问题。
下面列出应用等价规则变换优化关系表达式的算法。
算法：关系代数表达式的优化。
输入：一个待优化的关系表达式的语法树。
输出：计算表达式的一个优化序列。
方法如下。
1）利用等价变换规则（4）将形如σF1∧F2…∧Fn(E)变换为σF1(σF2(…σFn(E)…))。
2）对每一个选择，利用等价变换规则（4）～规则（8）尽可能地将它移动到叶端。
3）对每一个投影利用等价变换规则（3）、规则（5）和规则（10）中的一般表达式尽可能地将它移动到树的叶端。
4）利用等价变换规则（3）～规则（5）将选择和投影的串接合并为单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。
5）将上述得到的语法树的内结点分组。每一个二元运算和它所有的直接的祖先为一组。若其后代直到叶子全是一元运算，则也将它们并入该组，但当二元运算是广义笛卡儿积并且后面不是与它组成等值连接的选择时，则不能将选择与这个二元运算组成同一组，而是将这些一元运算单独分为一组。
讨论思考：
1）什么是关系演算？在关系演算公式中，各种运算符的优先级次序是什么？
2）元组关系演算和域关系演算有什么区别和联系？
3）进行查询优化的原因是什么？
4）什么是等价变换规则？
5）试举例说明关系表达式优化的过程。