数据库系统概论【系统篇】

一、关系查询处理和查询优化

关系数据库系统的查询处理

        查询处理的步骤分为4个阶段：查询分析、查询检查、查询优化和查询执行。

            查询语句（由此语句进行查询）

1、查询分析

     首先对查询语句进行扫描、词法分析和语法分析。对sql关键字、属性名和关系名等，进行语法检查和语法分析 ，即判断查询语句是否符合sql语法规则。

2、查询检查

     对合法的查询语句进行语义检查，即根据数据字典中有关的模式定义检查语句的数据库对象，如关系名、属性名是否存在和有效。

3、查询优化

    查询优化和分为代数优化和物理优化：代数优化是指按照一定的规则，通过对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效；

                                                                 物理优化则是指存取路径和底层操作算法的选择。选择的依据可以是基于规则的，也可以是基于代价的，也可以是基于语义的。

4、查询执行

    依据优化器得到的执行策略生成查询执行计划，有代码生成器（code generator）生成执行这个查询计划的代码，然后加以执行，回送查询结果；

实现查询操作的实例：(数据库优化的最终操作：尽量减少io的块数)

       1、选择操作的实现

           （1）、简单的全表扫描算法(table scan)（全扫：io代价：总的块数m block + o_(n)元组代价）

           （2）、索引扫描算法（index scan） 

                        通过索引先找到满足条件的元组指针，再通过元组指针在查询的基本表中找到数组；

        2、连接操作的实现：（连接操作是查询处理中最常用也是最耗时的操作之一。）

           （1）、嵌套循环算法（nested loop join）:在实际实现中数据存取是按照数据块读入内存，而不是按照元组进行i/o的。

           （2）、排序-合并算法（sort-merge join或merge join）：1、如果参与连接的表没有排好序，首先对表按连接属性排序 。2、在取表中的连接属性，把它们表中的属性连接起来。

           （3）、索引连接（index join）算法：（b+树   索引+基地址的方式）

           （4）、hash join算法：以数组的方式：基地址+偏移（快）；

关系数据库系统的查询优化

       查询优化的优点不仅在于用户不必考虑如何最好的表达查询以获得较高的效率，而且在于系统可以比用户程序的“优化”做的更好，这是因为：（1）、优化器可以从数据字典中获取许多统计信息 （2）、如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。（3）、优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。

（4）、优化器中包括了许多复杂的优化技术，这些技术往往只有最好的程序员才能掌握。

 

                                        总代价=i/o代价 +cpu代价 +内存代价+通信代价（数据结构：内存地址    ； 数据库：硬盘的逻辑地址）

代数优化

       代数优化策略是通过对关系代数表达式的等价变换来提高查询效率。

        1、连接，笛卡尔积的交换律

        2、连接、笛卡尔积的结合律

        3、投影的串接定律

        4、选择的串接定律

        5、选择与投影操作的交换律

        6、选择与笛卡尔积的交换律

        7、选择与并的分配律

        8、选择与差运算的分配律

        9、选择对自然连接的分配律

       10、投影与笛卡尔积的分配律

        11、投影与并的分配律

  查询树的启发式优化

      （1）、选择运算应尽可能先做

      （2）、把投影运算和选择运算同时进行

      （3）、把投影同其前或其后的双目运算结合起来

      （4）、把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。

      （5）、找出公共子表达式。

物理优化

        代数优化改变查询语句中操作的次序和组合，但不涉及底层的存取路径。物理优化就是要选择高效合理的操作算法或存取路径。

        选择的方法可以是：

        （1）、基于规则的启发式优化

        （2）、基于代价估算的优化

        （3）、两者结合的优化方法

二、数据库恢复技术