王燕玲，李廣倫

(1.洛陽師范學(xué)院信息技術(shù)學(xué)院，河南洛陽471022；2.洛陽理工學(xué)院電氣工程與自動化系，河南洛陽471001)

0 引言

現(xiàn)在，絕大多數(shù)管理信息系統(tǒng)使用關(guān)系型數(shù)據(jù)庫管理系統(tǒng)（簡稱DBMS）完成信息的存儲和查詢.DBMS使用表和列來存儲數(shù)據(jù)，使用SQL語言進(jìn)行查詢.因?yàn)椴樵兘Y(jié)果須在用戶期望時(shí)間內(nèi)返回[1?3]，所以SQL語言在執(zhí)行前必須進(jìn)行查詢優(yōu)化.數(shù)學(xué)中的集合論、一階謂詞邏輯和關(guān)系的概念是SQL語言的基礎(chǔ)，也是SQL語言查詢優(yōu)化的基礎(chǔ)[4].

多年研究發(fā)現(xiàn)，數(shù)據(jù)庫從業(yè)人員難以掌握關(guān)系代數(shù)和查詢優(yōu)化等理論知識導(dǎo)致所開發(fā)的軟件后期維護(hù)成本較高[1,2,4,10,11,12].為了加強(qiáng)數(shù)據(jù)庫從業(yè)人員理論知識的學(xué)習(xí)，本文在介紹查詢處理過程的一般概念和關(guān)系代數(shù)查詢優(yōu)化之后，開發(fā)基于啟發(fā)式優(yōu)化的關(guān)系代數(shù)查詢優(yōu)化器.該工具包括兩個(gè)模塊：關(guān)系代數(shù)查詢優(yōu)化和關(guān)系代數(shù)轉(zhuǎn)化為等價(jià)SQL語句.

1 相關(guān)工作

雖然數(shù)據(jù)庫系統(tǒng)中的關(guān)系代數(shù)和查詢優(yōu)化非常重要，但是直觀展示這兩者的教學(xué)輔助工具相對較少.本節(jié)討論目前常見的關(guān)系代數(shù)輔助教學(xué)工具.

WinRDBI系統(tǒng)[5,6]中輸入關(guān)系代數(shù)查詢語句獲得實(shí)時(shí)查詢結(jié)果；工具Virtura[7,8]支持直接學(xué)習(xí)關(guān)系代數(shù)；McMaster[9]使用編程的方式實(shí)現(xiàn)關(guān)系代數(shù)和關(guān)系演算；EDDI[10]實(shí)現(xiàn)標(biāo)準(zhǔn)關(guān)系代數(shù)和SQL語言之間相互轉(zhuǎn)換；ACME[11]是基于互聯(lián)網(wǎng)的數(shù)據(jù)庫學(xué)習(xí)平臺，該平臺可以實(shí)現(xiàn)教師錄入關(guān)系代數(shù)問題，學(xué)生在線求解，最后由平臺自動對學(xué)生答案判斷對錯(cuò).這些工具主要的限制是數(shù)據(jù)庫只能是教師提供的，學(xué)生不能自由選擇.王燕玲[12]開發(fā)關(guān)系代數(shù)學(xué)習(xí)工具，學(xué)生可以自由變更數(shù)據(jù)庫.

盡管這些工具都可以實(shí)現(xiàn)直觀學(xué)習(xí)關(guān)系代數(shù)表達(dá)式和SQL語言，但是對于SQL語言的查詢優(yōu)化在DBMS中如何實(shí)現(xiàn)并沒有涉及.本文實(shí)現(xiàn)的關(guān)系代數(shù)查詢優(yōu)化器不僅包括關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為等價(jià)SQL語句和關(guān)系代數(shù)表達(dá)式對錯(cuò)的自動判斷，還實(shí)現(xiàn)基于啟發(fā)式的關(guān)系代數(shù)表達(dá)式查詢優(yōu)化功能.

2 關(guān)系代數(shù)表達(dá)式查詢優(yōu)化

2.1 查詢優(yōu)化

查詢優(yōu)化[13?17]主要是制定查詢計(jì)劃并選擇時(shí)間成本最小的查詢計(jì)劃進(jìn)行執(zhí)行.進(jìn)行查詢優(yōu)化的4種基本技術(shù)為：

1.基于開銷的優(yōu)化

該優(yōu)化器先根據(jù)等價(jià)規(guī)則為給定的查詢生成一系列的查詢評估計(jì)劃，然后再根據(jù)關(guān)于執(zhí)行這個(gè)查詢所需的關(guān)系和操作的性能指標(biāo)中選出一個(gè)開銷較小的計(jì)劃.商業(yè)軟件（SQL SERVER和ORACLE）使用該優(yōu)化策略.

2.啟發(fā)式優(yōu)化

為了消除不太高效的查詢，該優(yōu)化器先根據(jù)規(guī)則把查詢改寫為最優(yōu)的形式，其后生成和挑選執(zhí)行計(jì)劃.INGRES、Prairie中使用了該優(yōu)化策略.

3.語義優(yōu)化

根據(jù)查詢語句包含的語義和數(shù)據(jù)庫的實(shí)際情況（關(guān)系、索引等）來生成查詢執(zhí)行計(jì)劃.該優(yōu)化策略還未在系統(tǒng)中實(shí)現(xiàn).

4.參數(shù)優(yōu)化將基于開銷的優(yōu)化和啟發(fā)式優(yōu)化結(jié)合起來提出了參數(shù)優(yōu)化.該種優(yōu)化策略還未在DBMS系統(tǒng)中實(shí)現(xiàn).其中，基于開銷的優(yōu)化和參數(shù)優(yōu)化都需要記錄歷史查詢統(tǒng)計(jì)信息和索引，并使用動態(tài)編程算法來實(shí)現(xiàn)優(yōu)化策略的選擇過程.這些要求比較浪費(fèi)資源.語義優(yōu)化需要數(shù)據(jù)庫、關(guān)系和索引的語義定義完整.啟發(fā)式優(yōu)化主要是利用關(guān)系代數(shù)的等價(jià)規(guī)則來進(jìn)行優(yōu)化，對經(jīng)典關(guān)系代數(shù)查詢表達(dá)式優(yōu)化效果最好，而且資源浪費(fèi)較少.

2.2 啟發(fā)式優(yōu)化

關(guān)系代數(shù)包括并(∪)、交(∩)、差(-)、笛卡爾積(×)、選擇(σ)、投影(π)、連接(∞)、除法(÷)等運(yùn)算[12].這些運(yùn)算經(jīng)過有限次的組合后形成了關(guān)系代數(shù)表達(dá)式.啟發(fā)式優(yōu)化的目標(biāo)是應(yīng)用規(guī)則把關(guān)系代數(shù)表達(dá)式改寫為最優(yōu)的形式.主要啟發(fā)式規(guī)則有：

1.把包含“選擇（σ）-連接（∞）”、“投影（π）-連接（∞）”、“選擇（σ）-選擇（σ）”或“投影（π）-投影（π）”的子表達(dá)式分解.目的是求解單元最小化.

2.選擇（σ）盡可能早做.目的是盡量減少連接操作前的元組數(shù)，使得中間臨時(shí)關(guān)系盡量少（元組減少，連接得到的元組數(shù)就少），這樣減少IO和CPU的消耗，節(jié)約內(nèi)存時(shí)間.

3.投影（π）盡可能早做.目的是盡量減少連接操作前的列數(shù)，使得中間臨時(shí)關(guān)系盡量少，這樣雖然不能減少IO，但可以減少連接后中間關(guān)系的元組大小，節(jié)約內(nèi)存空間.

4.根據(jù)最左優(yōu)先策略判斷哪些選擇（σ）和連接（∞）會生成較小的中間結(jié)果集并先執(zhí)行.

5.盡可能使用連接（∞）代替笛卡爾積（×）.目的也是生成較小的中間結(jié)果集.

1-4條規(guī)則得到大家的認(rèn)同，但是第5條規(guī)則Lee[18]等人認(rèn)為某些條件下選擇（σ）和投影（π）的開銷比較大.本文中主要實(shí)現(xiàn)了1-4條規(guī)則.

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

3.1 系統(tǒng)總體設(shè)計(jì)

3.1.1 數(shù)據(jù)流圖

本系統(tǒng)使用JFlex進(jìn)行詞法解析，使用JCup進(jìn)行文法解析、文法優(yōu)化.解析的SQL語句和優(yōu)化后的SQL語句在Mysql數(shù)據(jù)庫管理系統(tǒng)中進(jìn)行查詢.

其具體步驟如下：

1.關(guān)系代數(shù)表達(dá)式字符串輸入到詞法分析器（例如JFlex）之中.JFlex掃描該字符串，將其分割為若干關(guān)系運(yùn)算符和操作數(shù)，并檢查是否與合法的關(guān)鍵詞匹配.若不合法則返回提示錯(cuò)誤信息，若合法則進(jìn)入第2步.

2.使用文法解析器（例如JCUP）檢查是否有文法錯(cuò)誤.如果有文法錯(cuò)誤則輸出提示錯(cuò)誤信息，若無則進(jìn)入第3步.

3.使用文法解析器（例如JCUP）將關(guān)系代數(shù)表達(dá)式進(jìn)行啟發(fā)式優(yōu)化.優(yōu)化后進(jìn)入第4步.

4.使用文法解析器（例如JCUP）將優(yōu)化前后的關(guān)系運(yùn)算符和操作數(shù)轉(zhuǎn)換為對應(yīng)的SQL語句.轉(zhuǎn)換后進(jìn)入第5步.

5.對應(yīng)合成的SQL語句在Mysql數(shù)據(jù)庫管理系統(tǒng)中進(jìn)行查詢，并在窗口界面中顯示結(jié)果和所用時(shí)間.系統(tǒng)數(shù)據(jù)流圖見圖1.

3.1.2 系統(tǒng)流程圖

根據(jù)分析，設(shè)計(jì)系統(tǒng)流程如圖2.

圖1 系統(tǒng)數(shù)據(jù)流圖

圖2 系統(tǒng)流程圖

首先連接mysql數(shù)據(jù)庫，失敗時(shí)給出提醒（重新連接），連接成功后將mysql服務(wù)器的所有數(shù)據(jù)庫名讀取到下拉列表框中.選擇一個(gè)數(shù)據(jù)庫，點(diǎn)擊數(shù)據(jù)表、字段和關(guān)系代數(shù)符號，組成關(guān)系代數(shù)表達(dá)式；之后優(yōu)化關(guān)系代數(shù)表達(dá)式，翻譯sql，執(zhí)行sql語句并顯示結(jié)果.

3.2 系統(tǒng)詳細(xì)設(shè)計(jì)

3.2.1 系統(tǒng)功能結(jié)構(gòu)設(shè)計(jì)

本系統(tǒng)分為兩個(gè)子系統(tǒng)：關(guān)系代數(shù)優(yōu)化子系統(tǒng)和關(guān)系代數(shù)翻譯為sql語句子系統(tǒng).兩個(gè)子系統(tǒng)集成在主界面中.

1.關(guān)系代數(shù)優(yōu)化子系統(tǒng)

主界面中關(guān)系代數(shù)文本作為輸入內(nèi)容，調(diào)用優(yōu)化子系統(tǒng)主類（ToolOptimize），通過該類完成一整套的關(guān)系代數(shù)優(yōu)化的詞法語法分析.該類調(diào)用RelationOptimizeScanner詞法分析器類實(shí)現(xiàn)詞法優(yōu)化，而該類調(diào)用RelationOptimizeParser類實(shí)現(xiàn)解析關(guān)系代數(shù)中各種終結(jié)符.關(guān)系代數(shù)優(yōu)化子系統(tǒng)類圖見圖3.

圖3 關(guān)系代數(shù)優(yōu)化子系統(tǒng)類圖

2.關(guān)系代數(shù)翻譯為sql子系統(tǒng)

主界面中關(guān)系代數(shù)文本作為輸入內(nèi)容，調(diào)用詞法分析器主類（ScannerMain），通過該類完成調(diào)用詞法分析器（RelationAlgebraScanner，解析關(guān)系代數(shù)中各種終結(jié)符的類型），進(jìn)而按照關(guān)系代數(shù)語法翻譯sql語句.關(guān)系代數(shù)翻譯為sql子系統(tǒng)見圖4.

圖4 關(guān)系代數(shù)翻譯為sql子系統(tǒng)類圖

3.2.2 系統(tǒng)界面設(shè)計(jì)

本系統(tǒng)所有與用戶交互內(nèi)容集成到一個(gè)界面中.該界面主要分為數(shù)據(jù)庫連接、關(guān)系代數(shù)表達(dá)式編輯、關(guān)系代數(shù)表達(dá)式優(yōu)化、關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為sql語句、sql語句查詢和顯示結(jié)果五個(gè)模塊.模塊詳細(xì)描述如下：

1.數(shù)據(jù)庫連接模塊

用戶輸入mysql數(shù)據(jù)庫系統(tǒng)的賬戶名和密碼進(jìn)入mysql數(shù)據(jù)庫系統(tǒng).默認(rèn)情況下，用root賬戶密碼為空登陸.無論成功和失敗，總會在右側(cè)提示信息.

2.關(guān)系代數(shù)編輯模塊

關(guān)系代數(shù)編輯模塊的操作界面見圖5.主要分為操作按鈕欄、工具按鈕和查詢編輯框三部分.

圖5 關(guān)系代數(shù)編輯模塊

圖6 關(guān)系代數(shù)優(yōu)化模塊

1）操作按鈕欄

操作按鈕欄分為兩部分.第一部分是數(shù)據(jù)庫中的表名和字段名，均以下拉列表框展示.當(dāng)點(diǎn)擊數(shù)據(jù)表時(shí)，表名插入關(guān)系代數(shù)表達(dá)式編輯區(qū)域，并且讀出該表的字段名到對應(yīng)的下拉列表框.同樣點(diǎn)擊字段名，字段名也插入到關(guān)系代數(shù)編輯區(qū)域.

第二部分是關(guān)系代數(shù)操作符.主要是把不容易用鍵盤輸入的關(guān)系代數(shù)操作符可以簡單地錄入到關(guān)系代數(shù)編輯區(qū)域.

2）工具按鈕

工具按鈕包括翻譯為sql語句、清空、優(yōu)化為關(guān)系代數(shù)語句和執(zhí)行sql語句的四個(gè)按鈕.點(diǎn)擊這些按鈕分別可以完成操作區(qū)域中關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為sql語句；清空操作區(qū)域；操作區(qū)域中關(guān)系代數(shù)表達(dá)式優(yōu)化和執(zhí)行操作區(qū)域中關(guān)系代數(shù)表達(dá)式的功能.

3）查詢編輯框

點(diǎn)擊執(zhí)行時(shí)，可以在結(jié)果欄的三個(gè)框里輪流顯示查詢結(jié)果，利用三個(gè)顯示框是為方便對比學(xué)習(xí)，例如左連接、除法.

3.關(guān)系代數(shù)表達(dá)式優(yōu)化模塊

本模塊利用關(guān)系代數(shù)表達(dá)式的啟發(fā)式優(yōu)化規(guī)則優(yōu)化關(guān)系代數(shù)運(yùn)算表達(dá)式并顯示在結(jié)果界面.界面見圖6.

4.關(guān)系代數(shù)轉(zhuǎn)換為sql模塊

本模塊可以將單條或多條關(guān)系代數(shù)表達(dá)式轉(zhuǎn)換為sql語句，結(jié)果顯示在窗口中.窗口界面見圖6.

4 查詢優(yōu)化器設(shè)計(jì)與實(shí)現(xiàn)

本文的關(guān)系代數(shù)表示式啟發(fā)式優(yōu)化實(shí)現(xiàn)時(shí)采用詞法優(yōu)化定義文件和語法優(yōu)化定義文件.兩個(gè)文件定義如下：

1.詞法優(yōu)化定義文件

optimize.flex是優(yōu)化的詞定義文件，部分代碼見下文.

”.” {

System.out.print(yytext());

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

isAttribute=true;

return symbol(Symbols.POINT);

}

這段代碼表示，當(dāng)遇到“.”時(shí)打開isAttribute開關(guān).

2.語法優(yōu)化定義文件

Optimize.cup是關(guān)系代數(shù)優(yōu)化語法定義文件.關(guān)系代數(shù)運(yùn)算表達(dá)式優(yōu)化對照如圖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 結(jié)論與展望

本文使用詞法分析和語法分析實(shí)現(xiàn)了關(guān)系代數(shù)表達(dá)式的啟發(fā)式優(yōu)化，并根據(jù)該原理實(shí)現(xiàn)了關(guān)系代數(shù)表達(dá)式遠(yuǎn)程錄入、優(yōu)化和轉(zhuǎn)換.該系統(tǒng)的推廣應(yīng)用有助于數(shù)據(jù)庫從業(yè)人員對數(shù)據(jù)庫知識的理解和使用，但還需進(jìn)一步探討語法方向的移進(jìn)和規(guī)約策略，從而可以實(shí)現(xiàn)更多的關(guān)系代數(shù)表達(dá)式啟發(fā)式優(yōu)化.