第4章 第章关系系统及其查询优化 4.1关糸糸统 关系系统的定义 关系系统的分类 全关系系统12条准则 4.2头糸条统的查询优化 查询优化概述 查询优化的一般准则 关系代数等价变换规则 关系代数表达式的优化算法 优化的一般步骤
4.1 关系系统 ▪ 关系系统的定义 ▪ 关系系统的分类 ▪ 全关系系统12条准则 4.2 关系系统的查询优化 ▪ 查询优化概述 ▪ 查询优化的一般准则 ▪ 关系代数等价变换规则 ▪ 关系代数表达式的优化算法 ▪ 优化的一般步骤 第4章 关系系统及其查询优化 第4章
4.1关系系统 「关系系统定义 支持关系模型的关系数据库管理系统简称关系系统 下述关系的DBMS不能称为关系系统 1)不支持关系数据结构的系统 2)支持关系数据结构,但无δ、π、D算功能的系统 3)支持关系数据结构,有δ、π、运算,但要求定义物理存 取路径的系统 可称为关系系统的DBMS,当且仅当 1)支持关系数据结构(关系数据库) 2)支持δ、π、D运算,且不要求用户定义任何物理存取路径
4.1 关 系 系 统 关系系统定义 支持关系模型的关系数据库管理系统简称关系系统。 1．下述关系的DBMS不能称为关系系统 1）不支持关系数据结构的系统 2）支持关系数据结构，但无δ、π、 运算功能的系统 3）支持关系数据结构，有δ、π、 运算，但要求定义物理存 取路径的系统 可称为关系系统的DBMS，当且仅当 1）支持关系数据结构（关系数据库） 2）支持δ、π、 运算，且不要求用户定义任何物理存取路径
4.1关系系统 「关系系统分类 1.表式系统 仅支持关系数据结构,不支持关系操作。 2.(最小)关系系统: 支持关系数据结构,支持δ、π、∞运算,且不定义物理路径。 3.关系完备系统: 支持关系数据结构和所有关系代数操作(或功能上与关系代数等价) DBⅡ, ORACLE, SYBASE,属于这一类 4.全关系系统: 支持关系模型的所有特征。在关系完备系统的基础上,进一步支 持实体完整性和参照完整性等。 DBI, ORACLE, SYBASE,…已接近这个目标。目前尚无全关系系统
4.1 关 系 系 统 关系系统分类 4．全关系系统： 支持关系模型的所有特征。在关系完备系统的基础上，进一步支 持实体完整性和参照完整性等。 DBⅡ,ORACLE,SYBASE, …已接近这个目标。目前尚无全关系系统。 1．表式系统： 仅支持关系数据结构，不支持关系操作。 2．（最小）关系系统： 支持关系数据结构，支持δ、π、 ∞ 运算，且不定义物理路径。 3．关系完备系统： 支持关系数据结构和所有关系代数操作（或功能上与关系代数等价）。 DBⅡ,ORACLE,SYBASE,…属于这一类
4.1关系系统 「关系系统分类 数据结构数据操作完整性约束 表式系统 表 × × (最小)关系系统 表择投影 × 连接 关系完备的系统表 × 全关系系统
4.1 关 系 系 统 关系系统分类 数据结构 数据操作 完整性约束 表式系统 表 × × (最小)关系系统 表 选择、投影、 连接 × 关系完备的系统 表 √ × 全关系系统 √ √ √
4.1关系系统 全关系系统12条准则 0.一个关系型的DBMS必须能完全通过它的关系能力来管理数据库 准则1:信息准则。关系型DBMS的所有信息都应在逻辑一级上用一种 方法即表中的值显式地表示 准则2:保证访间准则。依表名、主码、列名的组合,保证能以逻辑 方式访问关系数据库中的每个数据项。(独立于物理结构) 准则3:空值的系统化处理。支持NULL的概念 准则4:基于关系模型的动态的联机数据字典。(以关系的形式存储 元数据) 准则5:统一的数据子语言准则。一体化的统一的数据子语言
4.1 关 系 系 统 全关系系统12条准则 0. 一个关系型的DBMS必须能完全通过它的关系能力来管理数据库 • 准则1：信息准则。关系型DBMS的所有信息都应在逻辑一级上用一种 方法即表中的值显式地表示 • 准则2：保证访问准则。依表名、主码、列名的组合，保证能以逻辑 方式访问关系数据库中的每个数据项。（独立于物理结构） • 准则3：空值的系统化处理。支持NULL的概念 • 准则4：基于关系模型的动态的联机数据字典。（以关系的形式存储 元数据） • 准则5：统一的数据子语言准则。一体化的统一的数据子语言
41关系系统 全关系系统12条准则 准则6:视图准则。所有理论上可更新的视图也应该允许由系统更新。 准则7:高级的插入、修改、删除操作。以关系为对象进行操作 准则8:数据物理独立性 准则9:数据逻辑独立性 准则10:数据完整性的独立性。用DDL定义并存储在数据字典中,独立 于应用程序 准则11:分布独立性 准则12:无破坏准则
4.1 关 系 系 统 全关系系统12条准则 • 准则6：视图准则。所有理论上可更新的视图也应该允许由系统更新。 • 准则7：高级的插入、修改、删除操作。以关系为对象进行操作 • 准则8：数据物理独立性 • 准则9：数据逻辑独立性 • 准则10：数据完整性的独立性。用DDL定义并存储在数据字典中，独立 于应用程序 • 准则11：分布独立性 • 准则12：无破坏准则
42关系系统的查询优化 查询优化概述 ●查询处理的过程 查询语句 语法分析与 关系代数表达式 翻译 优化器 查询输出 执行引擎 执行计划 数据 有关数据的统计 信息
4.2 关系系统的查询优化 查 询 优 化 概 述 ● 查询处理的过程 查询语句 查询输出 关系代数表达式 执行计划 语法分析与 翻译 执行引擎 优化器 数据 有关数据的统计 信息
42关系系统的查询优化 查询优化概述 ●实际系统的查询优化步骤 1.将查询转换成某种内部表示,通常是语法树 2.根据一定的等价变换规则把语法树转换成标准(优化)形式 3.选择低层的操作算法 对于语法树中的每一个操作 ■根据存取路径、数据的尺寸、数据的存储分布、存储数据 的聚簇等信息来计算各种执行算法的执行代价 选择代价小的执行算法 4.生成查询计划(查询执行方案)
4.2 关系系统的查询优化 查 询 优 化 概 述 ● 实际系统的查询优化步骤 1. 将查询转换成某种内部表示，通常是语法树 2. 根据一定的等价变换规则把语法树转换成标准（优化）形式 3. 选择低层的操作算法 • 对于语法树中的每一个操作 ▪ 根据存取路径、数据的尺寸、数据的存储分布、存储数据 的聚簇等信息来计算各种执行算法的执行代价 ▪ 选择代价小的执行算法 4. 生成查询计划(查询执行方案)
42关系系统的查询优化 查询优化概述 常用查询优化技术 用启发式规则来缩减查询计划的搜索空间 利用统计信息估算执行代价 基于代价 代价模型 集中式数据库 单用户系统:总代价=ⅣO代价+CPU代价 多用户系统:总代价=ⅣO代价+CPU代价+内存代价 分布式数据库 总代价=ⅣO代价+CPU代价+内存代价]+通信代价
4.2 关系系统的查询优化 查 询 优 化 概 述 ● 常用查询优化技术 ▪ 用启发式规则来缩减查询计划的搜索空间 ▪ 利用统计信息估算执行代价 ▪ 基于代价 ● 代价模型 ▪ 集中式数据库 • 单用户系统：总代价= I/O代价 + CPU代价 • 多用户系统：总代价= I/O代价 + CPU代价+ 内存代价 ▪ 分布式数据库 总代价= I/O代价 + CPU代价 [+ 内存代价] + 通信代价
42关系系统的查询优化 SELECT SNAME FROM Student, SC 查询优化概述 WHERE Student Sno=SC Sno 个实例:求选C2课程的学生名 AND Cno=C2’; 假设 外存 Student:1000条,SC:100.条,选修2号课程50条 个内存块装元组: 10个 Student,或100个SC,内存中一次可以存放:5块 Student元组, 1块SC元组和若干块连接结果元组 读写速度:20块秒 连接方法:基于数据块的嵌套循环法
4.2 关系系统的查询优化 查 询 优 化 概 述 ● 一个实例:求选C2课程的学生名 SELECT SNAME FROM Student，SC WHERE Student.Sno=SC.Sno AND Cno=‘C2’； ▪ 外存： Student:1000条, SC:10000条, 选修2号课程:50条 ▪ 一个内存块装元组: 10个Student , 或100个SC , 内存中一次可以存放: 5块Student元组, 1块SC元组和若干块连接结果元组 ▪ 读写速度：20块/秒 ▪ 连接方法：基于数据块的嵌套循环法 假设