数据库系统概论—查询优化.ppt

数据库系统概论 关系系统及其查询优化 关系系统的定义（1） 关系系统与关系模型密切相关，支持关系模型的系统为关系系统。 关系模型 数据结构：关系 数据操作：关系代数中的并、交、差、广义笛卡尔积、选择、投影、连接、除等操作 数据完整性：实体完整性、参照完整性和用户定义的完整性 支持关系模型应该能支持上述概念 关系系统的定义（3） 几点解释 必须支持三种操作（选择、投影和连接）是因为他们是用户使用数据库的基本操作 支持这三种运算而不是全部运算是因为他们是最有用的运算功能，能解决大部分的实际问题。 要求运算不依赖存取路径是要保证数据的物理独立性 关系系统的分类 据E.F.Codd的思想，按照各类系统支持关系模型的程度进行分类（S、I、M） 表示系统：仅支持关系数据结构(S)，不能算是关系系统 最小关系系统：仅支持关系数据结构和三种关系操作（S、M) 关系完备的系统：支持关系数据结构和所有的关系操作 全关系系统：支持关系模型的所有特征 全关系系统的基本准则（1） 准则0：一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。 准则1：信息准则。关系型DBMS的所有信息都应在逻辑一级上用一种方法即表中的值显式的表示。 准则2：保证访问准则。依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项。 全关系系统的基本准则（2） 准则3：空值的系统化处理。 准则4：基于关系模型的动态的联机数据字典。 准则5：统一的数据子语言准则。 准则6：视图更新准则。 准则7：高级插入、修改和删除操作。 全关系系统的基本准则（3） 准则8：数据的物理独立性。 准则9：数据的逻辑独立性。 准则10：数据完整性的独立性。 准则11：分布独立性。 准则12：无破坏准则。 查询优化 关系系统的优点所在是：查询优化，它减轻了用户选择存取路径的负担。 查询优化的优点：系统可以比用户程序的“优化”做得更好，因为： 可以从数据字典中获取许多统计信息 如果信息发生变化，系统会自动对查询重新优化 可以考虑数百种不同的执行计划 包括了很多复杂的优化技术 查询优化的总目标 选择有效的策略，求得给定关系表达式的值 基于代价的优化算法 要求优化器充分考虑各种参数（如缓冲区大小等），通过某中代价模型计算出各种查询执行方案的的执行代价，然后选择代价最小的执行方案。 总代价=I/O代价+CPU代价 或 总代价=I/O代价+CPU代价+内存代价 引例 求选修了2号课程的学生姓名 SELECT Sname FROM student, SC WHERE student.Sno=SC.Sno and SC.Cno =‘2’ 假设有1000学生纪录，10000选课纪录，查询结果有50个。 可以将上式写成等价的关系代数表达式 引例—第一种情况 πSname (σCno=‘2’ ∧student.Sno=SC. Sno (Student × SC)) 读取的总块数及所用时间（每秒20块)： 写这些块用的时间(每块10个元组每秒20块） （读入）作选择操作需时间与写这些块的时间相同（选择结果不再写出） 做投影（在内存中的操作可忽略时间） 总时间： 引例——第二种情况 πSname (σCno=‘2’ (Student SC)) 读取的总块数以及所用的时间与第一种情况相同为105s 写这些块用的时间（元组个数为SC 中104个） 作选择操作需时间与写这些块的时间相同 做投影（在内存中的操作可忽略时间） 总时间： 引例——第三种情况 πSname (Student σCno=‘2’ (SC)) 做选择操作，读取SC的所用时间（每秒20块)： 50个 作连接操作需时间（读student的时间）： 做投影（在内存中的操作可忽略时间） 总时间： 总结 数据库系统的查询，即使是最简单的查询，也必须进行查询优化 优化工作不仅有逻辑方法的优化，也有物理方法的优化。（如存取路径、存取方法的优化） 当有选择和连接时，应先做选择，这样参加连接的元组就大大减少了。 查询优化的一般准则 选择运算应尽可能先做 在执行连接之前对关系适当的预处理，有两种方法：索引连接和排序合并 把投影运算和选择运算同时进行 把投影同其前后的双目运算结合起来 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接 找出公共子表达式 关系代数等价变换规则 关系代数表达式的等价是指：用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。 两个关系表达式等价可记为： 常用的等价变换规则（P162) 1．连接、笛卡尔积的交换律