第04章 关系系统及其查询优化

第四章 关系系统及其查询优化 4.1 关系系统 关系模型的三个基本要素：关系数据结构、关系的完整性、关系操作。 4.1.1 关系系统的定义

一、定义 满足以下两个条件的系统称为关系系统： ① 具有关系数据结构； ② 具有选择、投影、自然连接运算，且这些运算不依赖于物理存取路径。 二、解释 ① 为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影、连接运算呢？ 因为不支持这三种关系运算的系统，用户使用仍不方便，不能提高用户的生产率，而提高用户生产率正是关系系统主要目标之一。 ② 为什么要求这三种运算不能依赖于物理存取路径呢？ 因为依赖物理存取路径来实现关系运算就降低或丧失了数据的物理独立性。不依赖物理存取路径来实现关系运算就要求关系系统自动地选择路径。为此，系统要进行查询优化，以获得较好的性能。这正是关系系统实施的关键技术。 ③ 为什么要求关系系统支持这三种最主要的运算而不是关系代数的全部运算功能？ 因为它们是最有用的运算功能，能解决绝大部分的实际回题。 4.1.2 关系系统的分类 有了关系系统的定义，我们就可以根据它来区分哪些是真正的关系系统。 4.1.1定义的关系系统是关系系统的最小要求，许多实际系统，如Oracle、SQL Server、DB2、SyBase、Informix系统都不同程度地超过了这些要求。 按照E.F.Codd的思想，可以把关系系统分类如图4.1所示的四类系统。 图 4.1 关系系统的分类 说明： ① 图中的圆表示关系数据模型。每个圆分为三部分，分别表示关系模型的三个组成部分：数据结构S(Structure)，完整性I(Integrity)，数据操纵M(Manipulation)。 ② 图中阴影部分表示各类系统支持模型的程度。 一、表式系统 仅支持关系（即表）数据结构，不支持关系（即集合）操作。 二、（最小）关系系统 仅支持关系数据结构和三种关系搡作。即4.1.l中定义的关系系统。许多微机关系数据库系统如FoxBASE、FoxPro等就属于这一类。 三、关系完备的系统 这类系统支持关系数据结构和所有的关系代数操作（功能上与关系代数等价）。 四、全关系系统 这类系统支持关系模型的所有特征。即不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。目前，大多数关系系统已不同程度上接近或达到了这个目标。 4.1.3 全关系系统的十二条基本准则

关系模型的奠基人E.F.Codd博士具体地给出了全关系型的关系系统应遵循的十二条基本准则。从实际意义上看，这十二条准则可以作为评价或购买关系型产品的标准。从理论意义上看，它是对关系数据模型的具体而又深入的论述，是从理论和实际紧密结合的高度对关系型DBMS的评述。 准则0：一个关系型的DBMS必须能完全通过它的关系能力来管理数据库 准则0是下面十二条准则的基础。 准则0的第一个推论是：任何声称是关系型的DBMS必须在关系这个级别上支持数据的插入、修改和删除（即一次可以对多个记录进行操作)。不管一个系统是否还具有非关系的管理数据的能力，它必须满足准则0。任何不满足准则0的DBMS不配称为关系型DBMS。 准则0的第二个推论是：关系型DBMS必须遵循信息准则和保证访问(存取)准则。

准则1：信息准则——关系型DBMS的所有信息都应在逻辑一级上用一种方法（即表的值）显式地表示 表名、列名和域名等都用系统内部表（即数据字典表）中的值表示。数据字典本身是一个动态的用来描述元数据的关系数据库。 满足信息准则不仅为了提高用户的生产率，使得DBA维护数据库的工作更简单、更有效，而且也为了使软件开发商在开发应用软件时能够检索存储在数据字典中的信息，需要的话可以借助DBMS的操作把新的信息存入字典中，简便合理。 如：SQL Server对每一个用户数据库都建立了一个sysobjects表，表中保存了各类数据对象，如：数据表、视图、存储过程、关键字等。 图4.2 用数据表保存各类数据对象 又如：SQL Server对每一个用户数据库都建立了一个syscolumns表，表中保存了所有数据表的属性列定义。

图4.3 用数据表保存所有数据表的属性列定义 准则2：保证访问准则——依靠表名、主码和列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项 保证访问准则表明关系系统所采用的是关联寻址(association addressing)的访问模式，而不是那种面向机器的寻址方法。这是关系系统独有的方式。 准则3：空值的系统化处理

全关系型的DBMS应支持空值的概念，并用系统化的方式处理空值。 准则4：基于关系模型的动态的联机数据字典 数据库的描述在逻辑级上应该和普通数据采用同样的表示方式，使得授权用户可以使用查询一般数据所用的关系语言来查询数据库的描述信息。参见图4.2和图4.3。 准则5：统一的数据子语言准则 一个关系系统必须有一种语言，如SQL语言，它的语句可以表示为具有严格语法规定的字符串，并能全面地支持以下功能： · 数据定义、视图定义 · 数据操作(交互式或程序式) · 完整性约束 · 授权 · 事务处理功能(事务开始、提交、回滚) 准则6：视图更新准则 所有理论上可更新的视图也应该允许由系统更新。即：可以通过更新视图来达到更新相关的数据表。 理论上可更新的视图——指对此视图的更新要求，存在一个与时间无关的算法，该算法可以无二义性地把更新要求转换为对基本表的更新序列。 如：含有表达式列的视图，通过更新表达式的值，就不能更新基本表。该视图就是一个理论上不可更新的视图。 准则7：高级的插入、修改和删除操作 关系系统的操作对象是单一的关系。以关系为操作对象不仅简化了用户查询，提高了用户生产率，而且也为系统提供了很大的余地来进行查询优化，提高了系统的运行效率。它允许系统来选择存取路径，以便得到最有效的运行代码。 准则8：数据物理独立性 无论数据库的数据在存储表示或存取方法上作任何变化，应用程序和终端活动都保持逻辑上的不变性。即应用程序仅涉及逻辑方面。 准则9：数据逻辑独立性 当对基本关系进行理论上信息不受损害的任何变化时，应用程序和终端活动都保持逻辑上的不变性。 理论上保持信息不受损害的变化——举例说明：把一个基本表按行的内容或者按列名分解为两个表，若这两个表都保留原基本表的主码，则这种变换在理论上是保持信息不受损失的。如果删除了某个基本表的一个或多个属性列，就是受损害的变化。 为了尽可能提高数据逻辑独立性，DBMS必须能对理论上可更新的视图执行插入、修改和删除操作时，必须满足准则6。 准则10：数据完整性的独立性 关系数据库的完整性约束条件必须是用数据库语言定义并存储在数据字典中的，而不是在应用程序中加以定义的。如：SQL Server中的主键、外键、是否为空、缺省值、有效检查等。 准则11：分布独立性 指关系型DBMS具有这样的数据库语言，它使应用程序和终端活动无论在最初的数据还是以后的数据重新分布时都能在逻辑上保持不变。即应用程序不因数据库的体系结构是单机结构、客户/服务器结构或分布式结构的改变而改变。 准则12：无破坏准则 如果一个关系系统具有一个低级（指一次一个记录）语言，则这个低级语言不能违背或绕过完整性准则。 准则小结 十二条准则都是以准则0为基础的。但仅有准则0，若不支持信息准则（准则1）、不保证访问准则（准则2）、不支持空值准则（准则3）或没有数据字典准则（准则4），就不能保证数据库的完整性。即： 准则1～准则4使数据的管理和控制（授权和完整性控制）达到了更高的标准。 准则8～准则11要求全关系型DBMS具有四种独立性。 4.2 关系数据库系统的查询优化 查询优化在关系数据库系统中有着非常重要的地位。关系数据库系统和非过程化的SQL语言能够取得巨大的成功，关键是得益于查询优化技术的发展。关系查询优化是影响RDBMS性能的关键因素。 4.2.1 关系系统及其查询优化 关系系统的查询优化既是RDBMS实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。 一、查询优化的优点 用户不必考虑如何最好地表达查询以获得较好的效率，系统自身的优化器可以比用户程序的“优化”做得更好。其原因如下： ① 优化器可以从数据字典中获取许多统计信息。例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。 ② 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 ③ 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 ④ 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 二、查询优化的总目标 选择有效的策略，求得给定关系表达式的值。 三、查询优化的实现步骤 ① 将查询转换成某种内部表示，通常是语法树。 ② 根据一定的等价变换规则把语法树转换成标准（优化）形式。 ③ 选择低层的操作算法。即对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。 ④ 生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。 四、代价计算 在集中式数据库中： 总代价 = I/O代价 + CPU代价 在多用户环境下： 总代价 = I/O代价 + CPU代价 + 内存代价 本人认为，在多用户环境下： 总代价 = I/O代价 + CPU代价 + 网络代价 + 内存代价