关系代数与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笛卡尔积的时间代价将大大减少，下面通过例子进行查询代价分析。