一種交互式關系代數學習工具設計

王燕玲, 李廣倫, 張瑞玲

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

關系型數據庫中大量的查詢表達方式為SQL語言，而SQL語言的數學基礎為關系代數。關系代數包含了集合論、一階謂詞邏輯和關系。關系代數被認為是SQL操作的形式化描述。在關系代數中獲得的經驗是學生有效學習其他任何商業查詢語言的基礎。在以往的教學中發現，由于學生對查詢要求缺乏結構認識，即使通過大量的例題訓練，仍很難掌握關系代數表達式的書寫要領。即使學生書寫出關系代數表達式，也難判斷該關系代數表達式的正確性，尤其是面對較為復雜的查詢時，經常會出現各種運算的優先級混亂、表達式內括號的匹配錯誤等問題[1-6]。

目前，S. Sadiq等人開發了SQLator[1]系統，該系統是基于Web數據庫在線的學習平臺。其中實現了關系代數表達式在線輸入和判斷對錯功能，但是所用數據庫是該學習平臺的固定數據庫。WinRDBI[7]為使用Visual Basic而開發的Windows界面工具，它能夠實現輸入SQL語言或者關系代數表達式獲得運行結果。以上2個學習工具都未涉及關系代數表達式優化及其與SQL語言之間的轉換過程。

本文使用LALR(1)文法實現了一種關系代數交互學習工具：在交互界面中錄入或點擊相關控件生成關系代數表達式；判斷關系代數表達式正確與否；使用解析器對關系代數表達式進行2次解析，第一次解析生成文法樹，第二次解析生成SQL語言；使用SQL語言在數據庫中進行查詢。另外，在2次解析之間，列出等價的若干關系代數表達式。該學習工具的使用有助于學生理解關系代數表達式的結構，從而正確地寫出關系代數表達式。

1 關鍵技術

JCUP是一個第三方的詞法分析器，也是一個語法分析器，它本質上是LALR[8]分析器(超前查看LR(1)，look-ahead LR(1))：在LR(1)分析表中，合并除超前查看符號集合外其余部分都相同的2個狀態，從而得到的分析器變形。

1.1 JCUP基礎結構

JCUP[9-10]解析是以表格為主(table-based)，其結構如圖1所示，主要部分包括：輸入緩沖區、堆棧、狀態轉移表(goto table)和動作表(action table)。

圖1 Java CUP基本結構

具體含義為：

(1) 輸入緩沖區：儲存輸入的源代碼，將從第一個符號開始依序向后掃描。

(2) 堆棧：儲存過去的狀態與化簡中的符號。

(3) 狀態轉移表(goto table)：決定狀態的移轉規則。

(4) 動作表(action table)：決定目前的狀態碰到輸入符號時應采取的文法規則，輸入符號指的是終端符號(terminals)與非終端符號(non-terminals)。

1.2 JCUP主要算法

JCUP解析器的主要步驟為：

(1) 解析程序將結尾字符$與起始狀態0依序壓入空堆棧，隨后的狀態與符號會被壓入堆棧的頂端。

(2) 根據目前的狀態以及輸入的終端符號，到動作表中找到對應動作：

① 移位(shift)sn:將目前的終端符號由輸入緩沖區中移出并壓入堆棧，再將狀態n壓入堆棧并成為最新的狀態；

② 化簡(reduce)rm:考慮第m條文法規則，假設該文法的右邊(right-hand side)有X個符號，則將2X個元素從堆棧中彈出，此時過去的某個狀態會回到堆棧頂端，在狀態轉移表中查找此狀態遇到文法左邊(left-hand side)符號時的狀態轉移，將文法左邊的符號壓入堆棧，將查找到的新狀態壓入堆棧；

③ 接受：輸入字串解析完成；

④ 無對應動作：此情形即為文法錯誤。

重復步驟(2)直到輸入的字串被接受或偵測到文法錯誤。

2 關系代數表達式及其文法描述

關系代數是一種抽象的查詢語言，是關系數據庫查詢語言的理論基礎。關系代數包括并(∪)、交(∩)、差(-)、笛卡爾積(×)、選擇(σ)、投影(π)、連接(∞)和除法(÷)等運算[11]。這些運算經過有限次的組合后形成了關系代數表達式，從而解決了用戶提出的查詢請求。

本文所構建的關系代數學習工具包含并、交、差、除、選擇、投影和重命名等關系代數操作符的子集。其基本文法(G)描述如下：

::= SEMI;

::= | | | | | | | | RELATION | |

::= PROJECT [] ()

::= RENAME [] ()

::= ATTRIBUTE | , ATTRIBUTE

::= ( UNION )

::= ( MINUS )

::= ( INTERSECT )

::= ( JOIN )

::= ( TIMES )

::=( MINUS )

::= ( DIVIDE )

::= SELECT []()

::= |

AND

::=

::= ATTRIBUTE | STRING-CONST | NUMBER-CONST

::= < | <= | = | <> | > | >=

在上述文法描述中，需注意以下幾點：

(1) 關系代數的關鍵字。PROJECT(投影)、 RENAME(重命名)、UNION(并)、MINU S(差)、INTERSECT(交)、JOIN(自然連接)、TIMES(笛卡兒積)、SELECT(選擇)和DEVICE(除)；

(2) 雜項運算符。 (,),<,<=,=,<>,>,>=,;,and 逗號 (,)；

(3) 數據庫中對象。關系和屬性(不區分大小寫)；

(4) 字符串常量。單引號內的字符串和數字。

3 系統設計及實現

本文所構建的關系代數學習工具是使用Java和JCUP構建的，界面良好，易于初學者使用。其開發環境為eclipse+SQL server 2005，需要插件為JCUP。

3.1 系統總體設計

本系統的系統結構是采用MVC(model-view-controller)模式，即把一個應用的輸入、處理、輸出流程按照Model、View、Controller的方式進行分離，這樣一個應用被分成3個層次——模型層(Model)、視圖層(View)和控制層(Control)，如圖2所示。

圖2 系統總體結構框圖

(1) Model層。主要實現數據庫連接、解析器接口(Parser)、關系代數表達式解析器(Parser.RA)、sql語言解析器(Parser.SQL)、符號類(Sym)和掃描器(Scanner)。

(2) View層。主要包括數據庫連接顯示界面、主界面和結果界面。

(3) Control層。主要實現數據庫控制和交互接口。

本系統主要流程為：

(1) 選擇本地或遠程服務器、相關的數據庫，出現主界面；

(2) 用戶在主界面中使用各種控件編輯關系代數表達式；

(3) 掃描關系代數表達式，用不同的符號將用戶編寫關系代數表達式中的符號進行替換；

(4) 使用詞法分析器，判斷關系代數表達式的正誤；

(5) 若正確，使用Java CUP語法自動產生器按照語法形成語法樹，然后將語法樹從左到右，由下而上的對語法樹進行解析，然后拼裝形成對應的SQL語句，將形成的SQL語句顯示給用戶；

(6) 與SQL Server 2005數據庫系統連接，執行SQL語句查詢，將結果返回(選一個返回或顯示)給用戶。

用戶能夠直觀地了解到關系代數表達式與SQL語句的對應關系和關系代數表達式執行所產生的查詢結果。該系統的具體流程如圖3所示。

圖3 關系代數學習工具流程圖

3.2 詞法解析

從編輯框中獲取用戶編寫的關系代數字符串，調用scanner類對字符串進行逐行、逐個字符的掃描，將每個字符進行歸類，并分別用特定的符號表示，具體替換見表1。

表1 替換規則

表1(續)

舉例：使用表1替換規則，將關系代數π[k](f);逐個字符掃描之后，解析得到的表達式為

PROJECT LPAREN ATTRIBUTE RPAREN LBRACK TABLENAME RBRACK SEIM

3.3 文法解析

實現文法解析用到了JavaCUP語法產生器。

3.3.1 cup文件

首先定義cup文件，然后用JavaCUP語法產生器把cup文件轉化為Parser和Sym 2個Java類；通過這2個類以及JavaCUP對關系代數表達式進行語法解析。cup文件包括4個部分：預先聲明、終結符和非終結符的說明、終結符的優先級和終結符的結合性。

3.3.2 parser以及sym類

上文生成的Parser和Sym類，結合JavaCUP來進行具體的拼裝操作，使用LALR的解析方法來生成SQL語句。

例如：t1 union t2，轉換為SQL語句過程如下：

(1) 由3.2節詞法解析后變成TABLENAME UNION TABLENAME；

(2) Parser類解析，形成語法樹，同時將會有3個符號分別入棧；

(3) 解析UNION時，將TABLENAME符號出棧檢查相應的語法進行匹配；

(4) 進行SQL語句的拼裝，結果為Select * from t1 union Select * from t2。

在此過程中形成的語法樹如圖4所示。

圖4 語法樹示例圖

3.4 系統實現

系統界面分為選單(菜單)欄、工具欄、列表欄、編輯區域和顯示區域，其中工具欄包括常規工具和關系代數工具。

(1) 選單欄。方便用戶對已經編寫的關系代數表達式進行保存或者改變保存路徑，并且可以打開現有已經寫好的關系代數表達式。

(2) 工具欄。常規工具欄有新建查詢、保存、粘貼和剪切等按鈕。另外，為了減少用戶輸入錯誤，提供了關系代數常用符號按鈕。

(3) 列表欄。提供要查詢的列表名稱。

(4) 編輯區域。為了方便用戶對關系代數表達式的保存和使用，可以同時建立多個編輯區域。

(5) 顯示區域。顯示翻譯好的SQL語句和關系代數表達式優化結果。

總體的實現界面如圖5所示。

圖5 系統主界面圖

4 結束語

本文實現了一個界面良好的關系代數學習工具。該學習工具使用方便，能夠連接本地和遠程服務器，靈活選擇不同的數據庫，進行關系代數表達式的編輯工作；對于所編輯的關系代數表達式可以判斷對錯；如果正確可以返回關系代數表達式的正確結果。該關系代數學習工具在授課中的應用能很好地降低學生學習關系代數的難度，理解關系代數在關系數據庫中的核心地位，為學生學習SQL語言打下良好的基礎。該學習工具在信息技術學院2010、2011級數據庫系統教學中起到了良好的作用。

該關系代數學習工具目前僅能連接SQL SERVER 2005，下一步的工作要擴展該關系代數學習工具所連接數據庫管理系統的種類，如：Oracle、MySQL和SQL Server 2000等；對代碼進行優化，提高其運行效率。

[1] Sadiq S, Orlowska M, Sadiq W, et al. SQLator: an online SQL learning workbench[J]. ACM SIGCSE Bulletin, 2004,36(3):223-227.

[2] Appel A P, Silva E Q, Traina Jr C, et al. iDFQL:A query-based tool to help the teaching process of the relational algebra[G]. In Proceedings of World Congress on Engineering and Technology Education (WCETE2004), 2004 :429-433.

[3] Agrawal P, Benjelloun O, Sarma A D, et al. Trio:A system for data, uncertainty, and lineage[G]. In Proceedings of the 32nd international conference on Very large data bases, 2006: 1151-1154. VLDB Endowment.

[4] Relational Algebra[EB/OL].[2013-05-18].http://en.wikipedia.org/wiki/Relational algebra, March 2011.

[5] Soler J. An Automatic Correction Tool for Relational Algebra Queries. In M., Gervasi and M[G]. Gavrilova (Eds.) ICCSA 2007, LNCS, 2007.

[6] Agrawal P, Benjelloun O, Sarma A D, et al. Trio:A system for data, uncertainty, and lineage[C]//In Proceedings of the 32nd international conference on Very large data bases, 2006.

[7] RDBI.[EB/OL].[2013-05-15].http://rdbi.sourceforge.net/.

[8] Andrew W Appel.現代編譯原理C語言描述[M]. 趙克佳,等譯.北京:人民郵電出版社,2006:27-58.

[9] Hudson S. Cup User’s Manual[EB/OL].1999. http://www.cs.princeton.edu/-appel/modern/java/CUP/.

[10] Jang-Wu Jo, Byeong-Mo Chang. An uncaught exception analysis for Java [J]. Journal of Systems and Software: 2004,72(1): 59-69.

[11] Ramez Elmasri，Shamkant B Navathe.數據庫系統基礎[M].孫瑜,譯.4版.北京:中國電力出版社, 2006.