第六章 关系系统及其查询优化
6.1 关系系统
关系模型的三个部分是,
★ 数据结构,
★ 关系操作,
★ 数据完整性,
关系系统和关系关系模型是两个密切相关而又不同的概念,支
持关系模型的系统成为关系系统,
6.1.1 关系系统的定义
一、关系系统的定义
一个系统可定义为关系系统,当且仅当它支持,
1,关系数据库。
2,支持选择、投影和（自然）连接运算。对这些运算不必要
求定义任何物理存取路径。
二、对 关系系统的定义的几点解释
6.1.2 关系系统的分类
1,表式系统
2,(最小 )关系系统
3.关系上完备的系统
4,全关系系统
6.1.3 全关系系统的十二条基本准则
准则 0,一个关系型的 DBMS必须能完全通过它的关系能力来管
理数据库,
准则 1,信息准则,
准则 2,保证访问准则,
准则 3,空值的系统化处理,
准则 4,基于关系模型的动态的联机数据字典,
准则 5,统一的数据子语言准则,
准则 6,视图更新准则,
准则 7,高级的插入、修改和删除操作,
准则 8,数据物理独立性,
准则 9,数据逻辑独立性,
准则 10,数据完整性的独立性,
准则 11,分布独立性,
准则 12,无破坏准则,
6.2 关系系统的查询优化
6.2.1 查询优化概述
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以
获得较好的效率,而且在于系统可以比用户程序的“优化”做得更好,
查询优化的总目标是,选择有效的策略,求得给定的关系表达式
的值,
6.2.2 一个实例
例,求选修了课程 C2的学生姓名,用 SQL语言表达为,
SELECT DISTINCT S.SN
FROM S,SC
WHERE S.S# =SC.S# AND SC.C# =‘C2’;
假定学生 —— 课程数据库中有 1000个学生记录,10000个选课记
录,其中选修 C2课程的选课记录为 50个,
系统可以用多种等价的关系代数表达式来完成这一查询
Q1 = πSN( σS.S# =SC.S#∧ SC.C# =’C2’(S× SC))
Q2 = πSN( σSC.C# =’C2’(S∞SC))
Q3 = πSN( S∞σSC.C# =’C2’(SC))
分析这三种情况,得出查询执行的策略不同,查询时间的差异有多大,
第 1种情况需约, 100000秒 (27.7778小时 ).
第 2种情况需约, 205秒 (3.416分钟 ),
第 3种情况需约, 10秒,
从上述的分析可以充分说明查询优化的必要性,
注意时间
6.2.3 优化的一般策略
1,选择运算应尽可能先做,
2,在执行连接前对文件适当地预处理,
3,把投影运算和选择运算同时进行,
4,把投影和其前或后的双目运算结合起来,
5,把某些选择同在它前面要执行的笛卡尔积结合起来成为一
个连接运算,
6,找出公共子表达式,
6.2.4 关系代数等价变换规则
两个关系表达式 E1和 E2是等价的,可记为, E1 ≡ E2
常用的等价变换规则有,
1,连接、笛卡尔积的交换律
设 E1和 E2是关系代数表达式,F是连接运算的条件，则有：
E1× E2≡E2× E1
E1∞E2≡E2∞E1
E1∞E2≡E2∞E1F F
2,连接、笛卡尔积的结合律
设 E1,E2和 E3是关系代数表达式,F1和 F2是连接运算的条件，
则有：
(E1× E2) × E3 ≡E1× (E2 × E3)
(E1∞E2) ∞E3 ≡E1∞(E2 ∞E3)
(E1∞E2) ∞E3≡E1∞(E2 ∞E3)
F1 F2 F1 F2
3,投影的串接定律
πA1,A2,……,An (πB1,B2,……,Bm (E))≡πA1,A2,……,An (E)
4.选择的串接定律
σF1(σF2 (E)) ≡ σF1∧ F2 (E)
5,选择和投影的交换律
σF (πA1,A2,……,An (E)) ≡πA1,A2,……,An (σF (E))
6.选择与笛卡尔积的交换
如果 F中涉及的属性都是 E1中定属性,则
σF (E1× E2) ≡σF (E1) × E2
如果 F=F1∧ F2,并且 F1只涉及 E1中的属性,F2只涉及 E2中的属
性,则由上面的 1,4,6可推出,
σF (E1× E2) ≡σF1 (E1) × σF2 (E2)
如果 F1只涉及 E1中的属性,F2涉及 E1和 E2两者的属性,则仍有,
σF (E1× E2) ≡σF2 (σF1 (E1) × E2)
8,选择与差运算的交换
若 E1,E2有相同的属性名,则
σF (E1－ E2) ≡σF (E1)－ σF (E2)
7,选择与并的交换
设 E=E1∪ E2,E1,E2有相同的属性名,则
σF (E1∪ E2) ≡σF (E1)∪ σF (E2)
9,投影与笛卡尔积的交换
设 E1和 E2是两个关系表达式,A1,A2,…,An 是 E1的属性,B1,B2,…,Bm
是 E2的属性,则
πA1,A2,……,An,B1,B2,…,Bm ≡π A1,A2,……,An (E1)× πB1,B2,……,Bm (E2)
10,投影与并的交换
设 E1,E2有相同的属性名,则
πA1,A2,……,An (E1∪ E2) ≡ πA1,A2,…,An (E1)∪ πA1,A2,…,An (E2)
6.2.5 关系代数表达式的优化算法
我们可以应用上面的变换法则来优化关系表达式,使优化后的
表达式能遵循 6.2.3中的一般原则,如把选择和投影尽可能地早做,关
系表达式的优化算法如下,
算法, 关系表达式的优化,
输入, 一个关系表达式的语法树,
输出, 计算该表达式的程序,
方法,
1,利用规则 (4)把形如,σ
F1∧ F2 … ∧ Fn (E)变换为 σF2 (σF2 (… ( σFn (E))…))
2,对每一个选择,利用规则 (4)~(8)尽可能把它移到树的叶端,
3,对每一个投影,利用规则 (3),(9),(10),(5)中的一般形式尽可能
把它移到树的叶端,
4,利用法则 (3)~(5)把选择和投影的串接合并成单个选择、单个
投影或一个选择后跟一个投影。
5,把上述得到的语法树的内结点分组,每一双目运算和它所有的
直接祖先为一组,
6,生成一个程序,每组结点的计算是程序中的一步,各步的顺序
是任意的,只要保证任何一组的计算不会在它的后代组之前计算,
6.2.6 优化的一般步骤
1,把查询转换成某种内部表示
结果
project(SN)
restrict(SC.C# =‘C2’)
join(S.S# =SC.S#)
S SC
图 6-3
π SN
σ SC.C# =‘C2’
σ S.S# =SC.S#
×
S SC
图 6-4
πSN
σ S.S# =SC.S#
×
S σ SC.C# =‘C2’
SC图 5-6
2,把语法树转换成标准 (优化 )形式
3.选择底层的存取路径
4,生成查询计划,选择代价最小的
第六章结束
6.1 关系系统
关系模型的三个部分是,
★ 数据结构,
★ 关系操作,
★ 数据完整性,
关系系统和关系关系模型是两个密切相关而又不同的概念,支
持关系模型的系统成为关系系统,
6.1.1 关系系统的定义
一、关系系统的定义
一个系统可定义为关系系统,当且仅当它支持,
1,关系数据库。
2,支持选择、投影和（自然）连接运算。对这些运算不必要
求定义任何物理存取路径。
二、对 关系系统的定义的几点解释
6.1.2 关系系统的分类
1,表式系统
2,(最小 )关系系统
3.关系上完备的系统
4,全关系系统
6.1.3 全关系系统的十二条基本准则
准则 0,一个关系型的 DBMS必须能完全通过它的关系能力来管
理数据库,
准则 1,信息准则,
准则 2,保证访问准则,
准则 3,空值的系统化处理,
准则 4,基于关系模型的动态的联机数据字典,
准则 5,统一的数据子语言准则,
准则 6,视图更新准则,
准则 7,高级的插入、修改和删除操作,
准则 8,数据物理独立性,
准则 9,数据逻辑独立性,
准则 10,数据完整性的独立性,
准则 11,分布独立性,
准则 12,无破坏准则,
6.2 关系系统的查询优化
6.2.1 查询优化概述
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以
获得较好的效率,而且在于系统可以比用户程序的“优化”做得更好,
查询优化的总目标是,选择有效的策略,求得给定的关系表达式
的值,
6.2.2 一个实例
例,求选修了课程 C2的学生姓名,用 SQL语言表达为,
SELECT DISTINCT S.SN
FROM S,SC
WHERE S.S# =SC.S# AND SC.C# =‘C2’;
假定学生 —— 课程数据库中有 1000个学生记录,10000个选课记
录,其中选修 C2课程的选课记录为 50个,
系统可以用多种等价的关系代数表达式来完成这一查询
Q1 = πSN( σS.S# =SC.S#∧ SC.C# =’C2’(S× SC))
Q2 = πSN( σSC.C# =’C2’(S∞SC))
Q3 = πSN( S∞σSC.C# =’C2’(SC))
分析这三种情况,得出查询执行的策略不同,查询时间的差异有多大,
第 1种情况需约, 100000秒 (27.7778小时 ).
第 2种情况需约, 205秒 (3.416分钟 ),
第 3种情况需约, 10秒,
从上述的分析可以充分说明查询优化的必要性,
注意时间
6.2.3 优化的一般策略
1,选择运算应尽可能先做,
2,在执行连接前对文件适当地预处理,
3,把投影运算和选择运算同时进行,
4,把投影和其前或后的双目运算结合起来,
5,把某些选择同在它前面要执行的笛卡尔积结合起来成为一
个连接运算,
6,找出公共子表达式,
6.2.4 关系代数等价变换规则
两个关系表达式 E1和 E2是等价的,可记为, E1 ≡ E2
常用的等价变换规则有,
1,连接、笛卡尔积的交换律
设 E1和 E2是关系代数表达式,F是连接运算的条件，则有：
E1× E2≡E2× E1
E1∞E2≡E2∞E1
E1∞E2≡E2∞E1F F
2,连接、笛卡尔积的结合律
设 E1,E2和 E3是关系代数表达式,F1和 F2是连接运算的条件，
则有：
(E1× E2) × E3 ≡E1× (E2 × E3)
(E1∞E2) ∞E3 ≡E1∞(E2 ∞E3)
(E1∞E2) ∞E3≡E1∞(E2 ∞E3)
F1 F2 F1 F2
3,投影的串接定律
πA1,A2,……,An (πB1,B2,……,Bm (E))≡πA1,A2,……,An (E)
4.选择的串接定律
σF1(σF2 (E)) ≡ σF1∧ F2 (E)
5,选择和投影的交换律
σF (πA1,A2,……,An (E)) ≡πA1,A2,……,An (σF (E))
6.选择与笛卡尔积的交换
如果 F中涉及的属性都是 E1中定属性,则
σF (E1× E2) ≡σF (E1) × E2
如果 F=F1∧ F2,并且 F1只涉及 E1中的属性,F2只涉及 E2中的属
性,则由上面的 1,4,6可推出,
σF (E1× E2) ≡σF1 (E1) × σF2 (E2)
如果 F1只涉及 E1中的属性,F2涉及 E1和 E2两者的属性,则仍有,
σF (E1× E2) ≡σF2 (σF1 (E1) × E2)
8,选择与差运算的交换
若 E1,E2有相同的属性名,则
σF (E1－ E2) ≡σF (E1)－ σF (E2)
7,选择与并的交换
设 E=E1∪ E2,E1,E2有相同的属性名,则
σF (E1∪ E2) ≡σF (E1)∪ σF (E2)
9,投影与笛卡尔积的交换
设 E1和 E2是两个关系表达式,A1,A2,…,An 是 E1的属性,B1,B2,…,Bm
是 E2的属性,则
πA1,A2,……,An,B1,B2,…,Bm ≡π A1,A2,……,An (E1)× πB1,B2,……,Bm (E2)
10,投影与并的交换
设 E1,E2有相同的属性名,则
πA1,A2,……,An (E1∪ E2) ≡ πA1,A2,…,An (E1)∪ πA1,A2,…,An (E2)
6.2.5 关系代数表达式的优化算法
我们可以应用上面的变换法则来优化关系表达式,使优化后的
表达式能遵循 6.2.3中的一般原则,如把选择和投影尽可能地早做,关
系表达式的优化算法如下,
算法, 关系表达式的优化,
输入, 一个关系表达式的语法树,
输出, 计算该表达式的程序,
方法,
1,利用规则 (4)把形如,σ
F1∧ F2 … ∧ Fn (E)变换为 σF2 (σF2 (… ( σFn (E))…))
2,对每一个选择,利用规则 (4)~(8)尽可能把它移到树的叶端,
3,对每一个投影,利用规则 (3),(9),(10),(5)中的一般形式尽可能
把它移到树的叶端,
4,利用法则 (3)~(5)把选择和投影的串接合并成单个选择、单个
投影或一个选择后跟一个投影。
5,把上述得到的语法树的内结点分组,每一双目运算和它所有的
直接祖先为一组,
6,生成一个程序,每组结点的计算是程序中的一步,各步的顺序
是任意的,只要保证任何一组的计算不会在它的后代组之前计算,
6.2.6 优化的一般步骤
1,把查询转换成某种内部表示
结果
project(SN)
restrict(SC.C# =‘C2’)
join(S.S# =SC.S#)
S SC
图 6-3
π SN
σ SC.C# =‘C2’
σ S.S# =SC.S#
×
S SC
图 6-4
πSN
σ S.S# =SC.S#
×
S σ SC.C# =‘C2’
SC图 5-6
2,把语法树转换成标准 (优化 )形式
3.选择底层的存取路径
4,生成查询计划,选择代价最小的
第六章结束
