本文共 2829 字,大约阅读时间需要 9 分钟。
本文简单介绍了数据库系统实现中查询优化的关系代数基础,包括优化所基于的关系代数等价规则等.
查询优化的主要目标是把表达式树变换成等价的表达式树,使得在树中的子表达式生成的关系的平均大小比优化前更小。次要目标是在一个单一查询中,或在要同时求值多于一个查询的时候的所有这些查询中,尽可能形成公共子表达式。一个关系表达式可以表示成多种形式,前提是这些形式是等价的。如何把一个表达式变换为其他形式的表达式,遵循哪些关系代数规则,下面作一简要描述。
幂等性
选择是幂等性的,也就是说多次执行同一个选择运算,跟只执行一次效果一样: σ F (R)=σ F σ F σ F (R)满足交换律
σ F1 σ F2 (R)=σ F2 σ F1 (R)可分解
σ F1∧F2 (R)=σ F1 (σ F2 (R))=σ F2 (σ F1 (R)) σ F1∨F2 (R)=σ F1 (R)∪σ F2 (R)选择下推
笛卡尔积耗费的资源巨大,在应用笛卡尔积之前最大可能减少两个关系的大小,把选择下推至参与运算的关系中。 σ F (R × S),假设F可以分解为F1、F2、F3,即σ F1 σ F2 σ F3 ,F2只与R有关,F3只与S有关,F1与R和S均有关系,那么: σ F (R × S)=σ F1 (σ F2 (R) × σ F3 (S))选择和θ连接
σ θ (R × S)= R ⋈ θ S 这其实是θ连接的定义. 另外,选择运算在下面两个条件下对θ连接运算具有分配律: 当选择条件θ 中的所有属性只涉及参与连接运算的表达式之一时: σ θ (R 1 ⋈ θ R 2 ) = (σ θ (R 1 )) ⋈ θ R 2 当选择条件θ 1 只涉及R1的属性,θ 2 只涉及R2的属性时: σ θ 1 ∧ θ 2 (R 1 ⋈ θ R 2 ) =(σ θ 1 (R 1 )) ⋈ θ (σ θ 2 (R 2 ))选择和集合运算
选择在差、交和并运算上均有分配性: σ F (R ∪ S) = σ F (R) ∪ σ F (S) σ F (R ∩ S) = σ F (R) ∩ σ F (S) σ F (R - S) = σ F (R) - σ F (S)选择和投影
选择与投影具有交换性(要求选择中的列是投影字段的子集): π a 1 ,a 2 ,... (σ F (R))=σ F (π a 1 ,a 2 ,... (R))级联
一系列投影运算中只有最后一个运算是必需的,其他的可省略: π a 1 ,a n ,... (π a 1 ,a 2 ,... (π a 1 ,a 2 ,... (R)))=π a 1 ,a n ,... (R)投影和连接
令L 1 和L 2 分别代表R1和R2的属性,假设连接条件θ只涉及L 1 ∪L 2 的属性,则投影在θ连接上具有分配律: π L 1 ∪L 2 (R 1 ⋈ θ R 2 ) = π L 1 (R 1 ) ⋈ θ π L 2 (R 2 )投影和集合运算
投影在差、交和并运算上均有分配性: π a 1 ,a 2 ,... (R ∪ S) = π a 1 ,a 2 ,... (R) ∪ π a 1 ,a 2 ,... (S) π a 1 ,a 2 ,... (R ∩ S) = π a 1 ,a 2 ,... (R) ∩ π a 1 ,a 2 ,... (S) π a 1 ,a 2 ,... (R - S) = π a 1 ,a 2 ,... (R) - π a 1 ,a 2 ,... (S)θ(自然)连接满足交换律
R ⋈ θ S = S ⋈ θ Rθ连接满足结合律
R 1 ⋈ θ 1 (R 2 ⋈ θ 2 ∧ θ 3 R 3 )=R 1 ⋈ θ 1 ∧ θ 3 (R 2 ⋈ θ 2 R 3 ) 其中θ 2 只涉及R2和R3的属性.自然连接满足结合律
R 1 ⋈ (R 2 ⋈ R 3 )=(R 1 ⋈ R 2 ) ⋈ R 3集合并和交满足交换律
R 1 ∪ R 2 = R 2 ∪ R 1 R 1 ∩ R 2 = R 2 ∩ R 1集合并和交满足结合律
(R 1 ∪ R 2 ) ∪ R 3 = R 1 ∪ (R 2 ∪ R 3 ) (R 1 ∩ R 2 ) ∩ R 2 = R 1 ∩ (R 2 ∩ R 3 )尽可能早地执行选择操作,尽可能在叶子节点完成选择运算;
尽可能早地执行投影操作,尽可能在叶子节点完成投影运算; 避免笛卡儿积运算,尽可能把笛卡儿积之前和之后的选择和投影运算合并一起完成。现有以下三个关系:
1、单位信息T_DWXX(以下简称DW)DWMC | DWBH | DWDZ |
---|---|---|
X有限公司 | 1001 | 广东省广州市荔湾区 |
Y有限公司 | 1002 | 北京市海淀区 |
Z有限公司 | 1003 | 广西南宁市五象区 |
2、个人信息T_GRXX(以下简称GR)
DWBH | GRBH | XM | NL |
---|---|---|---|
1001 | 901 | 张三 | 23 |
1002 | 902 | 李四 | 33 |
1002 | 903 | 王五 | 43 |
3、个人缴费信息T_JFXX(以下简称JF)
GRBH | NY | JE |
---|---|---|
901 | 201801 | 401.30 |
901 | 201802 | 401.30 |
901 | 201803 | 401.30 |
902 | 201801 | 513.10 |
902 | 201802 | 513.10 |
902 | 201804 | 513.10 |
903 | 201801 | 372.22 |
903 | 201804 | 372.22 |
现要求列出单位编号为1001和1002的个人编号、姓名和缴费金额.
初始结果表达式为(纯粹为了演示需要,把单位信息加入到连接中,实际并不需要): π GRBH,XM,JE (σ (DWBH=1001∨ DWBH=1002)∧ (DW.DWBH=GR.DWBH)∧(GR.GRBH=JF.GRBH) (DW × GR × JF)) 转换为语法树:1、等价规则:关系代数表达式可以遵循等价规则进行转换;
2、优化:表达式通过等价规则可以改写为更优的等价表达式。维基百科
《数据库系统概念》来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/6906/viewspace-2374899/,如需转载,请注明出处,否则将追究法律责任。
转载于:http://blog.itpub.net/6906/viewspace-2374899/