第四章 关系系统及其查询优化 这一章包括两个内容，一是关系系统(关系数据库系统的简称)，二是关系系统的查询优化。第一部分讨论关系系统的定义和分类；第二部分讨论关系系统中查询优化的概念、查询优化的基本原理和技术。

第一节 关系系统 关系系统和关系模型是两个密切相关而又不同的概念。支持关系模型的数据库管理系统称为关系系统。这种说法很笼统，因为关系模型中并非每一部分都是同等重要的，所以并不苛求一个实际的关系数据库管理系统必须完全支持关系模型，也不苛求完全支持关系模型的系统才能称为关系系统。因此，可以给出一个关系系统的最小要求以及分类的定义。

一、关系系统的定义 一个系统可定义为关系系统，当且仅当它： (1)支持关系数据库(关系数据结构)。 从用户观点看，数据库由表构成，并且只有表这一种结构。 (2)支持选择、投影和(自然)连接运算，对这些运算不必要求定义任何物理存取路径。 一个系统仅支持关系数据库而没有选择、投影和连接运算功能的，不能称为关系系统。 一个系统虽然支持这三种运算，但要求定义物理存取路径，如要求用户建立索引才能按索引字段检索记录，也不能称为关系系统。

对关系系统的定义做几点解释： （1）为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影、连接运算昵?因为不支持这三种关系运算的系统，用户使用仍不方便，不能提高用户的生产率，而提高用户生产率正是关系系统的主要目标之一。 (2)为什么要求这三种运算不能依赖于物理存取路径呢?因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。不依赖物理存取路径来实现关系运算就要求关系系统自动地选择路径。为此，系统要进行查询优化，以获得较好的性能。这正是关系系统实施的关键技术。 (3)要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能，是因为它们是最有用的运算功能，能解决绝大部分的实际问题。

二、关系系统的分类 有了关系系统的定义，就可以根据它来区分哪些系统是贴了“关系型”标签的非关系系统，哪些是关系系统。当前，许多产品如DB2，Oracle，Sybase，Informix，Ingres是关系系统。我国自主开发的Pbase和Easybase(中国人民大学)、Cobase(北京大学、中国人民大学与中国软件总公司)、OPENBASE(东大阿尔派)、DM2(华中理工大学)等数据库管理系统是关系系统

按照E．F．Codd的思想，可以把关系系统分类 图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：结构S(Structure)、完整性I(Integrity)、数据操纵M(Manipulation)。图中阴影部分表示各类系统支持模型的程度。

1．表式系统:这类系统仅支持关系(即表)数据结构，不支持集合级的操作。表式系统不能算关系系统。倒排表列(Inverted List)系统就属于这一类。 2．(最小)关系系统: 在前面文中定义的关系系统，它们仅支持关系数据结构和三种关系操作。许多微机关系数据库系统如FoxBASE，FoxPro等 3．关系完备的系统: 这类系统支持关系数据结构和所有的关系代数操作(功能上与关系代数等价)。20世纪90年代初的许多关系数据库管理系统属于这一类。 4．全关系系统: 这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数关系系统已不同程度上接近或达到了这个目标。

*三、全关系系统的十二条基本准则 全关系型的系统应该完全地支持关系模型的所有特征，这是个原则。关系模型的奠基人E．F．Codd具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据模型的具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMS的评述。

准则0一个关系型的DBMS必须能完全通过它的关系能力来管理数据库。 准则2保证访问准则。依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项(分量值)。 准则3空值的系统化处理。全关系型的DBMS应支持空值的概念，并用系统化的方式处理空值。 准则4基于关系模型的动态的联机数据字典。数据库的描述在逻辑级上应该和普通数据采用同样的表示方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。

准则5统一的数据子语言准则。一个关系系统可以具有几种语言和多种终端使用方式(如表格填空方式、命令方式等)。 准则6视图更新准则。所有理论上可更新的视图也应该允许由系统更新。 准则7高级的插入、修改和删除操作。关系系统的操作对象是单一的关系。以关系为操作对象不仅简化了用户查询，提高了用户生产率，而且也为系统提供了很大的余地来进行查询优化，提高了系统的运行效率。它允许系统来选择存取路径，以便得到最有效的运行代码。

准则8数据物理独立性。无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。 准则9数据逻辑独立性。当对基本关系进行理论上信息不受损害的任何改变时，应用程序和终端活动都保持逻辑上的不变性。 准则10数据完整性的独立性。关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。

准则11分布独立性。关系型DBMS具有分布独立性。 准则12无破坏准则。如果一个关系系统具有一个低级(指一次一个记录)语言，则这个低级语言不能违背或绕过完整性准则。 在关系方法中，为获得数据完整性的独立性(准则10)就要让完整性约束条件和数据的逻辑结构相独立。用准则12就很容易帮助识别那些贴着“关系”标签的非关系系统。因为这一系统已经在关系接口之下有一个应用接口，因此很难满足准则12。这时DBA不能控制他们的数据库，不能保证数据库的完整性状态。

以上是E．F．Codd给出的衡量一个全关系型DBMS的十二条准则。这十二条准则都以准则0为基础。但仅有准则O是不够的。不支持信息准则，不保证访问准则，不支持空值准则和数据字典准则就不能保证数据库的完整性。和早期的DBMS相比，这四条准则使数据的管理和控制(授权和完整性控制)达到了更高的标准。准则8～1 l要求全关系型DBMS具有四种独立性。其中数据的物理独立性和逻辑独立性已为大家所熟知，而数据完整性的独立性和分布独立性也已为大家重视。准则lO、准则11已变得和准则8、准则9同等重要。

第二节 关系数据库系统的 查询优化 查询优化在关系数据库系统中有着非常重要的地位。关系数据库系统和非过程化的SQL语言能够取得巨大的成功，关键是得益于查询优化技术的发展。关系查询优化是影响RDBMS性能的关键因素。 优化对关系系统来说既是挑战又是机遇。所谓挑战是指关系系统为了达到用户可接受的性能必须进行查询优化。由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。这就为关系系统在性能上接近甚至超过非关系系统提供了机遇。

一、关系系统及其查询优化 关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。对比一下非关系系统中的情况，用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户而不是由系统来决定的。因此用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。如果用户做了愚蠢的选择，系统是无能为力对此加以改进的。这就要求用户有较高的数据库技术和程序设计水平。 查询优让的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。

(1)优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 (2)如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 (3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 （4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值。 实际系统对查询优化的具体实现不尽相同，但一般来说．可以归纳为四个步骤： ①将查询转换成某种内部表示，通常是语法树。 ②根据一定的等价变换规则把语法树转换成标准(优化)形式。 ③选择低层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 ④生成查询计划。查询计划是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。

二、一个实例 看一个简单的例子，说明为什么要进行查询优化。 例 求选修了2号课程的学生姓名。用SQL语言表达： SELECT Student．Sname FROM Student,SC WHERE Student.Sno=SC．Sno AND SC．Cno='2'; 假定学生－课程数据库中有1000个学生记录，10000个选课记录，其中选修2号课程的选课记录为50个。 系统可以用多种等价的关系代数表达式来完成这一查询

将看到由于查询执行的策略不同，查询时间相差很大。

(一)、第一种情况 1．计算广义笛卡尔积 把Student和SC的每个元组连接起来。一般连接的做法是：在内存中尽可能多地装入某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的Student元组连接，直到SC表处理完。这时再一次读入若干块Student元组，读入一块SC元组，重复上述处理过程，直到把Student表处理完。 设一个块能装10个Student元组或100个SC元组，在内存中存放5块Student元组和l块SC元组，则读取总块数为：2100块,其中读Student表100块。读SC表20遍，每遍100块。若每秒读写20块，则总计要花105 s。连接后的元组数为10 3 X 104=107。设每块能装10个元组，则写出这些块要用106／20=5*104 s。

2．作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录。假定内存处理时间忽略。这一步读取中间文件花费的时间(同写中间文件一样)需5×104 s。满足条件的元组假设仅50个,均可放在内存。 3．作投影 把第2步的结果在Sname上作投影输出，得到最终结果。 因此第一种情况下执行查询的总时间=105+2×5×104=105 s。这里，所有内存处理时间均忽略不计。

(二)、第二种情况 l.计算自然连接 为了执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2 100块花费105s。但自然连接的结果比第一种情况大大减少，为104个。因此写出这些元组时间为104／10／20=50 s，仅为第一种情况的千分之一。 2．读取中间文件块，执行选择运算，花费时间也为50 s。 3．把第2步结果投影输出。 第二种情况总的执行时间≈105+50+50=205 s。

(三)、第三种情况 1．先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为5 s，因为满足条件的元组仅50个，不必使用中间文件。 2．读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块花费时间为5 s。 3．把连接结果投影输出。 第三种情况总的执行时间。5+5=10 s。

假如SC表的Cno字段上有索引，第l步就不必读取所有的SC元组而只需读取Cno='2'的那些元组(50个)。存取的索引块和SC中满足条件的数据块大约总共3～4块。若Student表在Sno上也有索引，则第2步也不必读取所有的Student元组，因为满足条件的SC记录仅50个，涉及最多50个Student记录，因此读取Student表的块数也可大大减少。总的存取时间将进一步减少到数秒。 这个简单的例子充分说明了查询优化的必要性，同时也给出一些查询优化方法的初步概念。如当有选择和连接操作时，应当先做选择操作，这样参加连接的元组就可以大大减少。

三、 查询优化的一般准则 下面的优化策略一般能提高查询效率，但不一定是所有策略中最优的。其实“优化”一词并不确切，也许“改进”或“改善”更恰当些。 1．选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时间降低几个数量级，因为选择运算一般使计算的中间结果大大变小。 2．在执行连接前对关系适当地预处理。预处理方法主要有两种，在连接属性上建立索引和对关系排序，然后执行连接。第一种称为索引连接方法；第二种称为排序合并(SORT-MERGE)连接方法。

四、关系代数等价变换规则 上面的优化策略大部分都涉及到代数表达式的变换。在第二、三章中介绍了各种查询语言，这些语言都可以转换成关系代数表达式。因此关系代数表达式的优化是查询优化的基本课题。而研究关系代数表达式的优化最好从研究关系代数表达式的等价变换规则开始。所谓关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。 两个关系表达式E1和E2是等价的，可记为E1=E2。

常用的等价变换规则有 1、连接、笛卡尔积交换律 2、连接、笛卡尔积的结合律 3、投影的串接定律 4、选择的串接定律 5、选择与投影的交换律 6、选择与笛卡尔积的交换律 7、选择与并的交换律 8、选择与差运算的交换 9、投影与笛卡尔积的交换 10、投影与并的交换

五、关系代数表达式的优化办法 算法：关系表达式的优化。 输入：一个关系表达式的语法树。 输出：计算该表达式的程序。 方法：详见P164

六、优化的一般步骤 各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下： 1、把查询转换成某种内部表示； 2、把语法树转换成标准（优化）形式； 3、选择低层的存取路径； 4、生成查询计划，选择代价最小的。 注意：对某一查询可以有很多不同的查询计划。不可能生成所有的查询计划。因为对这些查询计划进行代价估计本身要花费一定的代价，弄不好就会得不偿失。

查询处理是数据库管理系统的核心，而查询优化技术又是查询处理的关键技术。查询优化一般可分为代数优化和物理优化。代数优化是指关系代数表达式的优化；物理优化则是指存取路径和低层操作算法的选择。