文档介绍：关系系统及查询优化
关系系统
查询优化概述
查询优化的一般策略
关系代数表达式的等价变换规则
关系代数表达式的优化算法
1. 关系系统
关系模型的三个组成部分:
关系数据结构、关系操作集合、完整性约束
关系系统
——支持关系模型的系统
定义
一个系统可以定义为关系系统,当且仅当它支持:
1)关系数据库,即从用户观点看,数据库由二维表构成且只有表结构;
2)支持选择、投影和(自然)连接运算,且对它们不必要求定义任何物理存取路径。
关系系统的分类
关系模型的三个部分:
S —关系数据结构、M—关系操作、I—完整性约束
按支持模型的程度分类关系系统:
√
×
√
√
√
√
√
√
×
×
×
2. 关系系统的查询优化
必要性
——关系系统为了达到较好的性能(即用户可接受的性能)必须进行查询优化。
可能性
——关系系统从关系表达式中分析查询语义,自动选取存取路径,为执行查询优化提供了可能性。
关系系统的查询优化既是系统实现的关键技术又是关系系统的优点所在。
查询优化的总目标:
选择有效的策略,求得给定的关系表达式的值。
为什么要进行查询优化?
查询时间
T1: 105
T2: 205
T3: 10(秒)
实例:查找选修C2课程的学生姓名。
SELECT
FROM S,SC
WHERE = AND o=‘C2’
几个等价的关系代数表达式:
T1=ΠSN( =∧ o=‘C2’(S X SC))
T2= Π SN(σ o=‘C2’(S SC))
T3=Π SN(S o=‘C2’(SC))
查询优化的一般策略
一般策略——可提高查询效率,并非最优策略
1. 选择运算尽量先做;
2. 连接前对关系先做预处理;
——预处理方法:文件排序、在连接属性上建立索引
3. 投影运算和选择运算同时进行;
4. 投影与其前后的双目运算同时进行;
5. 把某些选择同它前面的笛卡尔积合并为连接运算;
——即用自然连接替代笛卡尔积
6. 存储公共子表达式。——权衡考虑
3. 关系代数表达式的等价变换规则
关系代数表达式的等价
——若用相同关系替代两个表达式中相应的关系所得到的结果关系相同,则称这两个表达式等价,两个关系表达式E1和E2是等价的,记为E1≡E2。
关系代数中最基本的五种运算是:
∪、-、×、σ、∏
常用的等价变换规则
连接、笛卡尔积的交换律
E1 E2 ≡ E2 E1
E1 X E2 ≡ E2 X E1
连接、笛卡尔积的结合律
(E1E2)E3 ≡ E1(E2 E3)
(E1XE2)XE3 ≡ E1X(E2 XE3)
等价变换规则(续1)
(3) 投影的串接定律
A1,A2,…,Am (B1,B2,…,Bn(E)) ≡A1,A2,…,Am(E)
其中属性名A1,A2,…,Am是B1,B2,…,Bn的子集
如: SN (Sno,SN(S)) ≡SN(S)
(4) 选择的串接定律
F1(F2(E)) ≡F1 F2(E)
等价变换规则(续2)
(5) 选择与投影的交换律
F (A1,A2,…,Am (E)) A1,A2,…,Am(F(E))
其中F只涉及A1,A2,…,Am属性
A1,A2,…,Am (F (E))
A1,A2,…,Am(F(A1,A2,…,Am,B1,B2,…,Bn (E)))
其中F 涉及A1, A2,…, Am以外的属性B1, B2,…, Bn