关系代数与SQL查询优化的研究

1 引言

随着各个应用领域信息化程度日益提高，数据库中的数据量迅猛增长，导致数据库系统的查询性能下降。但是一个数据库应用系统的查询性能直接影响到系统的推广和应用，因此数据库系统性能和查询优化成为数据库应用领域备受关注的热点问题。

影响数据库系统性能的因素很多，包括数据库连接方式、应用系统架构、数据库设计、管理等。其中最本质又至关重要的是数据库管理系统本身的查询优化技术。在数据库系统开发中，用户业务逻辑必须转换成数据库查询语言执行，或将数据库查询语言嵌入在宿主语言程序中执行。通过分析关系代数表达式的等价变换准则及查询代价，于给定的SQL查询与关系代数表达式对应关系，研究并分析基于关系代数等价变换规则的SQL查询优化。

2 关系代数表达式的等价变换规则

数据库查询是指从数据库中提取数据的一系列活动，包括：将高级数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式，为优化查询进行各种转换，生成可供执行的查询计划。对于数据库的查询要求可通过关系代数的运算(操作)表达，而在SQL语言中通过SELECT语句实现查询要求。南于关系代数运算与SELECT语句描述之间存在着对应关系，凶此可将数据库查询转换成关系代数运算，并利用关系代数等价变换规则生成优化SOL的查询计划。

2．1 关系代数等价变换规则

设E、E1、E2和E3是关系代数表达式，A1,…，An和B1，…，Bm是属性名，且A1,…，An是B1，…，Bm的子集，F、F1、F2和F3是条件表达式。则有常用的等价变换规则如表1所示。

2．2 查询代价分析

从优化的角度考虑，规则1与规则2等价变换前后的中间结果规模几乎不发生变化，因此无需考虑优化问题。但规则3～规则10变换前后中间结果规模会发生变化，例如规则3若选取的条件F只与E1有关，那么先进行E1的条件选取，再与E2笛卡尔积的时间代价将大大减少，下面通过例子进行查询代价分析。

假设关系E1有106个元组，关系E2有103个元组。那么执行E1xE2，则有109个元组。若条件F只与E1有关，且满足F的选择性为0．1％，则意味着只有103个元组满足条件，而另外的1O9-103个元组都不满足条件。因此将σF(E1xE2)等价变换为σF(E1)xE2后，其中间结果σF (E1)的规模仅103元组。若1个物理块可允许存放100个E1元组，10个E2元组，而主存中可允许存放10块E1元组，1块E2元组，以下估计分析等价变换前后的查询代价。

2．2．1 等价变换前查询代价估计分析

等价变换前查询代价是指采用σF(E1)xE2方式所需花费的查询代价。下面分别从E1×E2和σF两个方面分析：

(1)E1×E2代价估计E1xE2代价估计主要是从磁盘读块和中间结果写盘的时间考虑，而对主存中数据的处理时间忽略不计。

E1xE2读块总数=E1的块数+E2的块数×读E2的遍数=104+100x103=110 000块。若每秒可以读50块，读块时间为2 200 s(约0．6 h)。连接后的元组数为109，若每块可存放10个元组，那么写中间结果需要的时间是108/50=2x1 06 s。故E1xE2花费的时间为2×106 s+2．2×103s≈556．2 h。

(2)σF代价估计 σF运算时需将E1xE2的中间结果依次读入内存进行运算，凶此需要108／50=2×106s；满足条件的103个元组，共需100个块写回磁盘，需2 s。故σF花费的时间为2x106s+2．2x103s≈556．2 h。

作者：王峥,王亚平 西安外事学院 来源：国外电子元器件