关系系统及其查询优化

关系系统及其查询优化第一页，共十五页，编辑于2023年，星期日4.1关系系统1.定义（1）支持关系数据库（关系数据结构）（2）支持选择、投影和（自然）连接运算，且不要求定义任何物理存取路径。2.分类根据关系模型的三个组成：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)的实现进行分类。分4类。第四章关系系统及其查询优化第二页，共十五页，编辑于2023年，星期日4.1关系系统3.全关系系统的基本准则（12条）

准则0RDBMS能完全通过它的关系能力管理数据库；

准则1信息准则；用基本表的值显式表示数据。准则2保证访问准则；不用选择路径。

准则3空值的系统化处理准则；支持空值。准则4动态联机数据字典准则；

准则5统一的数据子语言准则；准则6视图更新准则；允许理论上可更新的视图更新。

准则7高级的插入、修改和删除操作准则；允许选择存储路径。准则8数据物理独立性准则；存储和存储方法改变，应用不变。

准则9数据逻辑独立性准则；关系改变，应用不变。准则10数据完整性的独立性准则；定义在数据字典中。

准则11分布独立性准则；在引入和重新分布时，应用逻辑不变。第四章关系系统及其查询优化第三页，共十五页，编辑于2023年，星期日4.2查询优化1.实例用SQL语言查询选修了2号课程的学生姓名：SELECTStudent.SnameFROMStudent，SCWHEREStudent.Sno=SC.SnoANDSC.Cno=‘2’假定：数据库有1000个学生记录、10000个选课记录、选修2号课程的选课记录有50个。关系代数表达式表示为：第四章关系系统及其查询优化第四页，共十五页，编辑于2023年，星期日4.2查询优化2.分析

第四章关系系统及其查询优化数据项的数目：Student1000(5)×SC10000(3)=80,000,000选择后(最多)：50(5)×1(3)=400结果：50[80,000,450]数据项的数目：Student1000(5)×SC30(3)=240,000选择后(最多)：50(5)×1(3)=400结果：50[240,450]3/1000数据项的数目：Student50(5)×SC50(3)=20,0002/10000

选择后(最多)：50(5)×1(3)=400结果：50[20,450]

8/100第五页，共十五页，编辑于2023年，星期日4.2查询优化3.查询的代价

总代价＝I/O代价+CPU代价+内存代价4.查询优化的必要性

关系数据库系统能够取得巨大的成功，SQL语言能够得到广泛的应用，关键得益于查询优化技术的发展。

5.优化的步骤

（１）将查询转换为内部表示－－语法树；（２）根据等价变换规则把语法树优化；（３）选择底层的操作算法；（４）生成查询的执行方案。第四章关系系统及其查询优化第六页，共十五页，编辑于2023年，星期日4.2查询优化6.查询优化的一般准则

（１）选择运算尽可能先做；（２）执行连接前进行排序或索引；（３）投影运算和选择运算同时进行；（４）投影与前后的双目运算结合；（５）选择与笛卡尔积结合为连接；（６）提取公共子表达式。第四章关系系统及其查询优化第七页，共十五页，编辑于2023年，星期日4.2查询优化7.关系代数的等价变换规则

（１）连接、笛卡尔积的交换律E1×E2≡E2×E1E1∞E2≡E2∞E1E1∞E2≡E2∞E1

FF

（２）连接、笛卡尔积的结合律(E1×E2)×E3≡E1×(E2×E3)(E1∞E2)∞E3≡E1∞(E2

∞E3)(E1∞E2)∞E3≡E1∞(E2

∞E3)

F1F2

F1F2

第四章关系系统及其查询优化第八页，共十五页，编辑于2023年，星期日4.2查询优化7.关系代数的等价变换规则

（３）投影的串接定律ΠA1,A2,…,An(ΠB1,B2,…,Bm(E))≡ΠA1,A2,…,An(E)

（４）选择的串接定律σF1(σF2(E))≡σF1∧F2(E))

（５）选择与投影的交换律σF(ΠA1,A2,…,An(E))≡ΠA1,A2,…,An(σF(E))

（６）选择与并的交换律σF(E1∪E2)≡σF(E1)∪σF(E2)第四章关系系统及其查询优化第九页，共十五页，编辑于2023年，星期日4.2查询优化7.关系代数的等价变换规则

（７）选择与差的交换律σF(E1－E2)≡σF(E1)－σF(E2)

（８）选择与笛卡尔积的交换律σF(E1×E2)≡σF(E1)×E2σF(E1×E2)≡E1×σF(E2)σF(E1×E2)≡σF1(E1)×σF2(E2)σF(E1×E2)≡σF2(σF1(E1)×E2)第四章关系系统及其查询优化第十页，共十五页，编辑于2023年，星期日4.2查询优化7.关系代数的等价变换规则

（９）投影与笛卡尔积的交换律ΠA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡ΠA1,A2,…,An(E1)×ΠB1,B2,…,Bm(E2)

（１０）投影与并的交换律ΠA1,A2,…,An(E1∪E2)≡ΠA1,A2,…,An(E1)∪ΠA1,A2,…,An(E2)第四章关系系统及其查询优化第十一页，共十五页，编辑于2023年，星期日4.2查询优化8.关系代数表达式的优化算法

输入：表示关系代数表达式的语法树输出：计算该表达式的程序（１）分解选择运算－－规则４σF1(σF2(E))≡σF1∧F2(E))

（２）移到叶端－－σF(E1×E2)≡σF(E1)×E2

（３）分解投影并移到叶端－－ΠA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡ΠA1,A2,…,An(E1)×ΠB1,B2,…,Bm(E2)（４）合并投影和选择－－σF(ΠA1,A2,…,An(E))≡ΠA1,A2,…,An(σF(E))（５）合并选择和笛卡尔积为连接运算－－σF(E1×E2)≡E1∞E2

F’（６）生成优化后的关系代数表达式。第四章关系系统及其查询优化第十二页，共十五页，编辑于2023年，星期日4.2