远程关系代数查询优化器设计及实现∗

王燕玲，李广伦

(1.洛阳师范学院信息技术学院，河南洛阳471022；2.洛阳理工学院电气工程与自动化系，河南洛阳471001)

0 引言

现在，绝大多数管理信息系统使用关系型数据库管理系统（简称DBMS）完成信息的存储和查询.DBMS使用表和列来存储数据，使用SQL语言进行查询.因为查询结果须在用户期望时间内返回[1−3]，所以SQL语言在执行前必须进行查询优化.数学中的集合论、一阶谓词逻辑和关系的概念是SQL语言的基础，也是SQL语言查询优化的基础[4].

多年研究发现，数据库从业人员难以掌握关系代数和查询优化等理论知识导致所开发的软件后期维护成本较高[1,2,4,10,11,12].为了加强数据库从业人员理论知识的学习，本文在介绍查询处理过程的一般概念和关系代数查询优化之后，开发基于启发式优化的关系代数查询优化器.该工具包括两个模块：关系代数查询优化和关系代数转化为等价SQL语句.

1 相关工作

虽然数据库系统中的关系代数和查询优化非常重要，但是直观展示这两者的教学辅助工具相对较少.本节讨论目前常见的关系代数辅助教学工具.

WinRDBI系统[5,6]中输入关系代数查询语句获得实时查询结果；工具Virtura[7,8]支持直接学习关系代数；McMaster[9]使用编程的方式实现关系代数和关系演算；EDDI[10]实现标准关系代数和SQL语言之间相互转换；ACME[11]是基于互联网的数据库学习平台，该平台可以实现教师录入关系代数问题，学生在线求解，最后由平台自动对学生答案判断对错.这些工具主要的限制是数据库只能是教师提供的，学生不能自由选择.王燕玲[12]开发关系代数学习工具，学生可以自由变更数据库.

尽管这些工具都可以实现直观学习关系代数表达式和SQL语言，但是对于SQL语言的查询优化在DBMS中如何实现并没有涉及.本文实现的关系代数查询优化器不仅包括关系代数表达式转换为等价SQL语句和关系代数表达式对错的自动判断，还实现基于启发式的关系代数表达式查询优化功能.

2 关系代数表达式查询优化

2.1 查询优化

查询优化[13−17]主要是制定查询计划并选择时间成本最小的查询计划进行执行.进行查询优化的4种基本技术为：

1.基于开销的优化

该优化器先根据等价规则为给定的查询生成一系列的查询评估计划，然后再根据关于执行这个查询所需的关系和操作的性能指标中选出一个开销较小的计划.商业软件（SQL SERVER和ORACLE）使用该优化策略.

2.启发式优化

为了消除不太高效的查询，该优化器先根据规则把查询改写为最优的形式，其后生成和挑选执行计划.INGRES、Prairie中使用了该优化策略.

3.语义优化

根据查询语句包含的语义和数据库的实际情况（关系、索引等）来生成查询执行计划.该优化策略还未在系统中实现.

4.参数优化将基于开销的优化和启发式优化结合起来提出了参数优化.该种优化策略还未在DBMS系统中实现.其中，基于开销的优化和参数优化都需要记录历史查询统计信息和索引，并使用动态编程算法来实现优化策略的选择过程.这些要求比较浪费资源.语义优化需要数据库、关系和索引的语义定义完整.启发式优化主要是利用关系代数的等价规则来进行优化，对经典关系代数查询表达式优化效果最好，而且资源浪费较少.

2.2 启发式优化

关系代数包括并(∪)、交(∩)、差(-)、笛卡尔积(×)、选择(σ)、投影(π)、连接(∞)、除法(÷)等运算[12].这些运算经过有限次的组合后形成了关系代数表达式.启发式优化的目标是应用规则把关系代数表达式改写为最优的形式.主要启发式规则有：

1.把包含“选择（σ）-连接（∞）”、“投影（π）-连接（∞）”、“选择（σ）-选择（σ）”或“投影（π）-投影（π）”的子表达式分解.目的是求解单元最小化.

2.选择（σ）尽可能早做.目的是尽量减少连接操作前的元组数，使得中间临时关系尽量少（元组减少，连接得到的元组数就少），这样减少IO和CPU的消耗，节约内存时间.

3.投影（π）尽可能早做.目的是尽量减少连接操作前的列数，使得中间临时关系尽量少，这样虽然不能减少IO，但可以减少连接后中间关系的元组大小，节约内存空间.

4.根据最左优先策略判断哪些选择（σ）和连接（∞）会生成较小的中间结果集并先执行.

5.尽可能使用连接（∞）代替笛卡尔积（×）.目的也是生成较小的中间结果集.

1-4条规则得到大家的认同，但是第5条规则Lee[18]等人认为某些条件下选择（σ）和投影（π）的开销比较大.本文中主要实现了1-4条规则.

3 系统设计与实现

3.1 系统总体设计

3.1.1 数据流图

本系统使用JFlex进行词法解析，使用JCup进行文法解析、文法优化.解析的SQL语句和优化后的SQL语句在Mysql数据库管理系统中进行查询.

其具体步骤如下：

1.关系代数表达式字符串输入到词法分析器（例如JFlex）之中.JFlex扫描该字符串，将其分割为若干关系运算符和操作数，并检查是否与合法的关键词匹配.若不合法则返回提示错误信息，若合法则进入第2步.

2.使用文法解析器（例如JCUP）检查是否有文法错误.如果有文法错误则输出提示错误信息，若无则进入第3步.

3.使用文法解析器（例如JCUP）将关系代数表达式进行启发式优化.优化后进入第4步.

4.使用文法解析器（例如JCUP）将优化前后的关系运算符和操作数转换为对应的SQL语句.转换后进入第5步.

5.对应合成的SQL语句在Mysql数据库管理系统中进行查询，并在窗口界面中显示结果和所用时间.系统数据流图见图1.

3.1.2 系统流程图

根据分析，设计系统流程如图2.

图1 系统数据流图

图2 系统流程图

首先连接mysql数据库，失败时给出提醒（重新连接），连接成功后将mysql服务器的所有数据库名读取到下拉列表框中.选择一个数据库，点击数据表、字段和关系代数符号，组成关系代数表达式；之后优化关系代数表达式，翻译sql，执行sql语句并显示结果.

3.2 系统详细设计

3.2.1 系统功能结构设计

本系统分为两个子系统：关系代数优化子系统和关系代数翻译为sql语句子系统.两个子系统集成在主界面中.

1.关系代数优化子系统

主界面中关系代数文本作为输入内容，调用优化子系统主类（ToolOptimize），通过该类完成一整套的关系代数优化的词法语法分析.该类调用RelationOptimizeScanner词法分析器类实现词法优化，而该类调用RelationOptimizeParser类实现解析关系代数中各种终结符.关系代数优化子系统类图见图3.

图3 关系代数优化子系统类图

2.关系代数翻译为sql子系统

主界面中关系代数文本作为输入内容，调用词法分析器主类（ScannerMain），通过该类完成调用词法分析器（RelationAlgebraScanner，解析关系代数中各种终结符的类型），进而按照关系代数语法翻译sql语句.关系代数翻译为sql子系统见图4.

图4 关系代数翻译为sql子系统类图

3.2.2 系统界面设计

本系统所有与用户交互内容集成到一个界面中.该界面主要分为数据库连接、关系代数表达式编辑、关系代数表达式优化、关系代数表达式转换为sql语句、sql语句查询和显示结果五个模块.模块详细描述如下：

1.数据库连接模块

用户输入mysql数据库系统的账户名和密码进入mysql数据库系统.默认情况下，用root账户密码为空登陆.无论成功和失败，总会在右侧提示信息.

2.关系代数编辑模块

关系代数编辑模块的操作界面见图5.主要分为操作按钮栏、工具按钮和查询编辑框三部分.

图5 关系代数编辑模块

图6 关系代数优化模块

1）操作按钮栏

操作按钮栏分为两部分.第一部分是数据库中的表名和字段名，均以下拉列表框展示.当点击数据表时，表名插入关系代数表达式编辑区域，并且读出该表的字段名到对应的下拉列表框.同样点击字段名，字段名也插入到关系代数编辑区域.

第二部分是关系代数操作符.主要是把不容易用键盘输入的关系代数操作符可以简单地录入到关系代数编辑区域.

2）工具按钮

工具按钮包括翻译为sql语句、清空、优化为关系代数语句和执行sql语句的四个按钮.点击这些按钮分别可以完成操作区域中关系代数表达式转换为sql语句；清空操作区域；操作区域中关系代数表达式优化和执行操作区域中关系代数表达式的功能.

3）查询编辑框

点击执行时，可以在结果栏的三个框里轮流显示查询结果，利用三个显示框是为方便对比学习，例如左连接、除法.

3.关系代数表达式优化模块

本模块利用关系代数表达式的启发式优化规则优化关系代数运算表达式并显示在结果界面.界面见图6.

4.关系代数转换为sql模块

本模块可以将单条或多条关系代数表达式转换为sql语句，结果显示在窗口中.窗口界面见图6.

4 查询优化器设计与实现

本文的关系代数表示式启发式优化实现时采用词法优化定义文件和语法优化定义文件.两个文件定义如下：

1.词法优化定义文件

optimize.flex是优化的词定义文件，部分代码见下文.

”.” {

System.out.print(yytext());

//make the word that follow it is translated into an ATTRIBUTE

isAttribute=true;

return symbol(Symbols.POINT);

}

这段代码表示，当遇到“.”时打开isAttribute开关.

2.语法优化定义文件

Optimize.cup是关系代数优化语法定义文件.关系代数运算表达式优化对照如图6.OptimizeExpression::=

PROJECT LEFTBRACKET TABLENAME:tableName1 POINT ATTRIBUTE:attribute1 RIGHTBRACKET LEFTPARENTHESIS

SELECT LEFTBRACKET TABLENAME:tableName2 POINT ATTRIBUTE:attribute2 COMPARISON

STRING:string1 RIGHTBRACKET SELECT LEFTBRACKET TABLENAME:tableName3 POINT

ATTRIBUTE:attribute3 COMPARISON TABLENAME:tableName4 POINT ATTRIBUTE:attribute4

RIGHTBRACKET LEFTPARENTHESIS

LEFTPARENTHESIS TABLENAME:tableName5 TIMES TABLENAME:tableName6 RIGHTPARENTHESIS

RIGHTPARENTHESIS

RIGHTPARENTHESIS{:

/*πσ×*/

RESULT= ”π[”+tableName1+”.”+attribute1+”]( ”

+” ”+tableName5+”∞[”+tableName3+”.”+attribute3+”=”+tableName4+”.”+attribute4+”]( ”

+ ” ”+”σ[”+tableName2+”.”+attribute2+”=’”+string1+”’]”

+ ”(”+tableName6+”) ) ”

+”) ”;

:};

5 结论与展望

本文使用词法分析和语法分析实现了关系代数表达式的启发式优化，并根据该原理实现了关系代数表达式远程录入、优化和转换.该系统的推广应用有助于数据库从业人员对数据库知识的理解和使用，但还需进一步探讨语法方向的移进和规约策略，从而可以实现更多的关系代数表达式启发式优化.