吳嬌嬌，何小衛(wèi)，趙 洋

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華 321004)

0 引 言

隨著計(jì)算機(jī)技術(shù)與應(yīng)用的快速發(fā)展，數(shù)據(jù)成為所有計(jì)算機(jī)應(yīng)用的操作對(duì)象。在進(jìn)行各種信息處理的過程中，數(shù)據(jù)占據(jù)著不可取代的地位[1]。由此可見，在計(jì)算機(jī)處理的背后，數(shù)據(jù)庫體系發(fā)揮著重大作用，對(duì)數(shù)據(jù)庫的學(xué)習(xí)也成為掌握計(jì)算機(jī)技能必不可少的條件。在數(shù)據(jù)庫的初級(jí)學(xué)習(xí)過程中，最重要的莫過于學(xué)習(xí)SQL(structured query language,結(jié)構(gòu)化查詢語言)。SQL語言結(jié)構(gòu)清晰，但是編碼有著多樣性及結(jié)果不易觀察的特點(diǎn)，使得代碼的評(píng)分標(biāo)準(zhǔn)變得界限模糊，人工評(píng)判工作愈加繁重[2]。為減輕人工評(píng)測負(fù)擔(dān)，構(gòu)建自動(dòng)評(píng)分模型及系統(tǒng)刻不容緩。而科學(xué)合理地評(píng)測SQL代碼，也成為構(gòu)建模型的一個(gè)重要問題。

目前，代碼的自動(dòng)評(píng)分技術(shù)主要分為動(dòng)態(tài)測試和靜態(tài)分析[3]。動(dòng)態(tài)測試是通過代碼執(zhí)行的結(jié)果判定代碼的正確性；而靜態(tài)分析主要是通過分析代碼的結(jié)構(gòu)特征及語義信息評(píng)判代碼。采用動(dòng)態(tài)測試的評(píng)分系統(tǒng)，主要用于檢測VB程序，如段漢周等[4]提出的自動(dòng)評(píng)分系統(tǒng)，以及檢測Java程序的BOSS系統(tǒng)[5]；采用靜態(tài)分析的評(píng)分系統(tǒng)發(fā)展得較為成熟，比如用系統(tǒng)依賴圖分析語義相似度的基于語義相似度比較的編程題自動(dòng)評(píng)分方法[6]和基于程序理解的編程題自動(dòng)評(píng)分方法[7]；當(dāng)然，也有結(jié)合了動(dòng)態(tài)測試和靜態(tài)分析的Course Master系統(tǒng)[8]。

文中借鑒程序代碼的自動(dòng)評(píng)判技術(shù)，針對(duì)SQL代碼的特殊性，采用靜態(tài)分析方法構(gòu)建自動(dòng)評(píng)分模型，并通過實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證。

1 自動(dòng)評(píng)分模型

自動(dòng)評(píng)分模型采用靜態(tài)分析的方法，總體流程如圖1所示。預(yù)處理刪除及處理了一些語句，使SQL語句表達(dá)統(tǒng)一化與規(guī)范化；對(duì)SQL代碼進(jìn)行詞法分析，對(duì)SQL代碼每一部分進(jìn)行分類，提取出特征結(jié)構(gòu)，并進(jìn)行分詞處理，獲得片段代碼；構(gòu)建同義庫，對(duì)SQL片段代碼的相似語句向操作符少的語句轉(zhuǎn)化；利用LCS算法對(duì)參考片段代碼與要測評(píng)的片段代碼進(jìn)行相似度比較，得到片段代碼的相似度；對(duì)代碼片段賦予相似度影響因子，計(jì)算出兩SQL代碼總的相似度；統(tǒng)計(jì)人工評(píng)審數(shù)據(jù)，用多項(xiàng)式擬合出相近數(shù)據(jù)，據(jù)此制定相應(yīng)的評(píng)分策略。

圖1 自動(dòng)評(píng)分模型總流程

1.1 預(yù)處理

由于書寫SQL語句時(shí)的不規(guī)范性和SQL語句表達(dá)的多樣性，為更好地識(shí)別SQL代碼，首先需要對(duì)SQL代碼進(jìn)行規(guī)范化預(yù)處理，預(yù)處理流程見圖2。

圖2 預(yù)處理流程

(1)刪除注釋以及與SQL代碼語義無關(guān)的內(nèi)容；SQL代碼中的注釋可以隨意敲入而不影響代碼結(jié)構(gòu)及語義，這對(duì)特征提取無用，因此，移除一切與語義無關(guān)的代碼。

(2)用空格代替SQL語句中的回車符，以及移除多余的空格[9]；在敲寫代碼的同時(shí)，可能無意地敲入一些空格、回車符等無義字符，使得代碼愈加繁瑣，需要移除，使得代碼簡潔明了。

(3)將SQL代碼全部變成小寫形式；統(tǒng)一規(guī)范大小寫，也可以全部轉(zhuǎn)化為大寫形式。

(4)對(duì)于表名加字段名的代碼，將表名移除，留下“.+字段名”。為體現(xiàn)代碼中帶有表名，保留“.”，但為了代碼的易于識(shí)別，移除會(huì)給相似度帶來較大誤差的表名。例如：“select table1.ename, table2.ename from emp table1, emp table2 where table1.mgr=table2.empno;”進(jìn)行處理后可轉(zhuǎn)化為“select .ename, .ename from emp table1, emp table2 where .mgr=.empno;”。

(5)對(duì)SQL代碼的各個(gè)關(guān)鍵詞之間的字段以及子句按ASCII值先后順序排序。其目的是保證相似語義的代碼片段相似度匹配時(shí)能獲得最大相似度[10]。例如：“select c1,a2,b3 from t1,t3,t2 where condi3=3 or condi1=1 order by o6,o2”進(jìn)行排序處理后，可以轉(zhuǎn)化為“select a2,b3,c1 from t1,t2,t3 where condi1=1 condi3=3 or order by o2,o6”。

1.2 特征提取

對(duì)SQL代碼的特征提取及分詞，首先對(duì)代碼進(jìn)行詞法分析，然后將代碼轉(zhuǎn)化為可識(shí)別的含結(jié)構(gòu)和語義信息的字符串序列。

由分析可知，SQL語句有其特有的語法規(guī)則以及明確的關(guān)鍵字，在評(píng)分時(shí)，關(guān)鍵詞占據(jù)較大的比重，先查詢到關(guān)鍵詞的正確率，才會(huì)逐步分析關(guān)鍵詞之后的字段差異。因此在提取結(jié)構(gòu)時(shí)，首先按照關(guān)鍵詞提取SQL的結(jié)構(gòu)特征。將SQL代碼進(jìn)行分類標(biāo)識(shí)，分為關(guān)鍵詞和關(guān)鍵詞之后的字段，并分別為此分配不同的類型，作標(biāo)記為：keyword，body?？蓪QL語句表述為：

SQL={ (Word1,C1) … (Wordi,Ci)|i∈N+}

(1)

其中，Wordi為SQL代碼的關(guān)鍵詞或關(guān)鍵詞之后的字段；Ci為標(biāo)記keyword或body。

給定如下SQL代碼：update emp set sal=newsal where eid=id;可轉(zhuǎn)化為(update,keyword)(emp,body)(set,keyword)(sal=newsal,body)(where,keyword)(eid=id,body)。

1.3 同義轉(zhuǎn)換

在評(píng)分過程中，兩段不同代碼實(shí)現(xiàn)的功能及得到的結(jié)果一致，就可以認(rèn)為這兩段代碼是相同的。SQL語句中存在一些相似句，雖然表現(xiàn)形式不一，但可以得出相同的結(jié)果，這些句子可稱之為相似句。判斷字段：sal between 3 000 and 5 000,它相當(dāng)于sal>=3 000 and sal<=5 000；sal in (3 000,5 000)相當(dāng)于sal=3 000 or sal=5 000，某些情況下的連接字段：from a1 left outer join a2 on a1.name=a2.name,和from a2 right outer join a1 on a1.name=a2.name。

相似度比較并不能很好地識(shí)別相似句，因此為提高匹配的精確度，對(duì)代碼進(jìn)行相似句轉(zhuǎn)化很有必要。為精簡轉(zhuǎn)化，對(duì)相似的語句建立語句同義庫，常用等價(jià)語句如表1所示。轉(zhuǎn)化的過程向同義庫規(guī)則靠攏。文中規(guī)定，將操作符多的向操作符少的轉(zhuǎn)化，如前段判斷字段所述，相同操作符的按ASCII值從大向小轉(zhuǎn)化。

表1 常用等價(jià)語句表

1.4 基于LCS的相似度比較

計(jì)算相似度本質(zhì)上是對(duì)要比較的字符串與標(biāo)準(zhǔn)字符串之間進(jìn)行字符串匹配。對(duì)于字符串匹配研究，現(xiàn)今已發(fā)展到較為成熟的水平，尤其在相似度檢測方面。字符串匹配算法大體上分為精確匹配與近似匹配，近似匹配就是在匹配時(shí)允許字符串出現(xiàn)一些誤差。精確匹配主要應(yīng)用于文本查找、網(wǎng)絡(luò)安全等方面，近似匹配的應(yīng)用域較為廣泛，包括信號(hào)處理、生物DNA信息檢測、語音識(shí)別、信息查詢、相識(shí)度檢測、查重等。字符串相似度匹配算法有簡單字符串匹配，基于字符距離的算法[11]，基于GST算法[12]或局部過濾的字符串比較。

經(jīng)過特征提取，抽取出了keyword以及body。由于對(duì)SQL進(jìn)行分詞過程相當(dāng)于對(duì)關(guān)鍵詞進(jìn)行抽取匹配，因此相似度比較只需比較關(guān)鍵詞之后的字段即body字段，也可稱之為body代碼片段。body代碼片段有其特有的規(guī)則和約束，有一定的規(guī)律和固定的表現(xiàn)形式。文中采用一種經(jīng)典的簡單字符串比較算法-最長公共子串算法進(jìn)行相似度比較。LCS的經(jīng)典算法有兩種：動(dòng)態(tài)編程(DP)或者后綴數(shù)組(suffix array)。文中采用DP求解最長公共子串。

針對(duì)該模型的最長公共子串問題可表述為：給定兩個(gè)代碼串，即參考代碼的body片段S1，評(píng)測代碼的body片段S2；求解S1，S2兩代碼串之間最長的相同字符串的長度。

定義1：

(1)兩個(gè)字符串：參考body代碼片段S1=[a1,a2,…,am],評(píng)測body代碼片段S2=[b1,b2,…,bn],m,n∈N+,a1,a2,…,am為body代碼片段S1中的每個(gè)字符，b1,b2,…,bn為body代碼片段S2中的每個(gè)字符；

(3)由SL[i][j]可得對(duì)應(yīng)的最長公共子串，標(biāo)記為：LCS(S1,S2);

(4)最長公共子串的長度為max(SL[i][j]),i∈{1,2,…,m},j∈{1,2,…,n}。

若S1[i+1]和S2[j+1]不同，那么SL[i+1,j+1]就應(yīng)該為0，因?yàn)槿魏我运鼈優(yōu)榻Y(jié)尾的子串都不可能完全相同；而如果S1[i+1]和S2[j+1]相同，那么只要在以S1[i]和S2[j]結(jié)尾的最長相同子串之后添上這個(gè)字符即可，這樣就可以讓SL增加一位；值得注意的是，若S1，S2中任何一個(gè)是空字符串，那么最長公共子串的長度SL就為0。這是一個(gè)遞歸問題的求解，為了更直觀形象地表述，可以得到狀態(tài)轉(zhuǎn)移方程：

(2)

通過SL[i][j]可以得到對(duì)應(yīng)的最長公共子串LCS。

定義2:參考和評(píng)測body代碼片段的相似度為：

(3)

其中，S1.length和S2.length分別為字符串S1和S2的長度。

定義了以上兩條，就可以對(duì)body代碼片段進(jìn)行相似度計(jì)算。編寫代碼，經(jīng)過整合，可以得到一個(gè)相似度集合，將該集合表達(dá)成一個(gè)向量，以便觀察。相似度集合表示為：

Similar=(sim1,sim2,…,simN),N∈N+

(4)

例1，現(xiàn)有兩個(gè)SQL代碼：S1={select count(ename), avg(sal), floor(sysdate-hiredate/365) from emp, info where ename='li' group by(deptno);}；S2={select count(ename),floor(sysdate-hiredate/365) from emp where ename='li' group by(deptno);}；根據(jù)定義1、定義2及式(4)，可得到相似度集合similar=(1,0.83,1,0.43,1,0.92,1,1)。

(2)金標(biāo)記BLI檢測。將光纖傳感器末端置于奶液中(200μL牛乳+50μL緩沖液+5μL金標(biāo)BSA)中平衡120 s;然后，將光纖傳感器末端沒入待測奶液(200μL待測牛乳+50μL緩沖液+5μL金標(biāo)氯霉素素單克隆抗體)中700 s。檢測牛乳中氯霉素殘留量。

1.5 相似度調(diào)整及評(píng)分策略

SQL評(píng)分時(shí)各個(gè)部分所占評(píng)分比重的不一致，使得對(duì)各個(gè)部分的相似度增加影響因子的處理很有必要[13-14]。又因?yàn)镾QL評(píng)分時(shí)關(guān)鍵詞對(duì)評(píng)分結(jié)果的影響較大，所以需賦予關(guān)鍵詞較大的影響因子。為了使自動(dòng)評(píng)分的結(jié)果更接近人工評(píng)審的結(jié)果，通過實(shí)驗(yàn)將影響因子定為：(α1,α2,…,αN),N為字段的個(gè)數(shù)，有以下約束關(guān)系：

(5)

賦予影響因子后的總相似度為：

SQLSim=sim1*α1+sim2*α2+…+simN*αN

(6)

從例1中可以得到總的相似度SQLSim=1*1/6+0.83*1/12+1*1/6+0.43*1/12+1*1/6+0.92*1/12+1*1/6+1*1/12=0.93。

為使自動(dòng)評(píng)分更貼近人工評(píng)審，根據(jù)人工評(píng)判結(jié)果制定了評(píng)分策略。據(jù)人工評(píng)判數(shù)據(jù)統(tǒng)計(jì)，得到相似度sim和分?jǐn)?shù)score的關(guān)系圖(見圖3)。由圖3可知，score和sim之間存在某種映射關(guān)系，通過多項(xiàng)式擬合，得到函數(shù)為：f(x)=-47.5x2+121.8x+21.8，波形如圖4所示。

最終得到分?jǐn)?shù)與相似度之間關(guān)系：score=-47.5 sim2+121.8sim+21.8，擬合誤差∑Δx2=251.08。

可以評(píng)定出例子1的分?jǐn)?shù)為94分。

圖3 人工評(píng)審得到的關(guān)系圖

圖4 擬合后的關(guān)系圖

2 實(shí)驗(yàn)結(jié)果與分析

從圖4可以看出，折線波動(dòng)較大，是由于人工評(píng)審時(shí)誤差較大，容易受到主觀因素的影響，存在誤判的概率。而對(duì)于自動(dòng)評(píng)判，客觀評(píng)分減小了誤判的概率。

2.1 人工評(píng)分和自動(dòng)評(píng)分?jǐn)?shù)據(jù)分析

由于評(píng)分策略采用人工數(shù)據(jù)擬合的方法，對(duì)于相似度已知的代碼，自動(dòng)評(píng)分已貼合人工評(píng)判給出的分?jǐn)?shù)。除去計(jì)算相似度之后的影響，整體評(píng)測人工評(píng)分和自動(dòng)評(píng)分的數(shù)據(jù)。

現(xiàn)有測試集：A班作業(yè)SQL代碼，共計(jì)200條數(shù)據(jù)。對(duì)該測試集進(jìn)行自動(dòng)評(píng)分測試，統(tǒng)計(jì)準(zhǔn)確率，如圖5所示。

圖5 樣本的準(zhǔn)確率

由圖5可看出，樣本的準(zhǔn)確率區(qū)間大體在[0.92,0.98]之間，零星散落部分點(diǎn)在其他準(zhǔn)確率較高和較低部分。據(jù)分析發(fā)現(xiàn)，較低部分的準(zhǔn)確率是作業(yè)中出現(xiàn)了將關(guān)鍵詞拼錯(cuò)，但是關(guān)鍵詞之后的字段出錯(cuò)地方較少的情況。因此，除去關(guān)鍵詞出錯(cuò)的情況，該自動(dòng)評(píng)分模型對(duì)SQL代碼的評(píng)分準(zhǔn)確率高且穩(wěn)定，總的來說可以達(dá)到較好的效果，因此可以定性地評(píng)判SQL代碼。

2.2 相似度參數(shù)數(shù)據(jù)分析

SQL評(píng)分時(shí)關(guān)鍵詞和body所占評(píng)分比重不同時(shí)，即影響因子不同，對(duì)評(píng)分準(zhǔn)確率的影響也有差別[15]。為確定最精確的影響因子，實(shí)驗(yàn)統(tǒng)計(jì)了兩個(gè)參數(shù)：關(guān)鍵詞所占整個(gè)SQL代碼的比重記為α，以及評(píng)分的準(zhǔn)確率accuracy_rate；調(diào)整參數(shù)α，統(tǒng)計(jì)準(zhǔn)確率。統(tǒng)計(jì)結(jié)果如圖6所示。

圖6 α與accuracy_rate關(guān)系圖

從圖6可以看出，關(guān)鍵詞的影響因子對(duì)評(píng)分的準(zhǔn)確率有一定影響。在到達(dá)臨界點(diǎn)之前，折線圖大體隨著α的增加而增加，臨界點(diǎn)之后，準(zhǔn)確率隨α的減少而劇烈下降。經(jīng)分析可知，這是由于SQL代碼的結(jié)構(gòu)性特點(diǎn)，評(píng)分時(shí)關(guān)鍵詞需要占據(jù)一定的比重，如果比重過低體現(xiàn)不出SQL代碼的結(jié)構(gòu)，如果比重過高，難以體現(xiàn)細(xì)節(jié)之處。經(jīng)過分析衡量，臨界點(diǎn)大約在0.62～0.69之間，為便于計(jì)算，將關(guān)鍵詞的影響因子定為總代碼的2/3。

經(jīng)過實(shí)驗(yàn)與數(shù)據(jù)統(tǒng)計(jì)，該模型可以對(duì)較長的SQL代碼進(jìn)行相似度匹配。采用同義庫以及最長公共子串的算法，有效提高了自動(dòng)評(píng)分的正確性。但是經(jīng)過分析發(fā)現(xiàn)，自動(dòng)評(píng)分也存在語義正確但是評(píng)分低的狀況，如關(guān)鍵詞錯(cuò)誤。因此，對(duì)于關(guān)鍵詞錯(cuò)誤的情況，應(yīng)該另行分析。

3 結(jié)束語

針對(duì)數(shù)據(jù)庫SQL代碼的評(píng)分，提出了新的SQL代碼的自動(dòng)評(píng)分模型。該模型借鑒了代碼的靜態(tài)分析方法，對(duì)相似語義構(gòu)建了SQL代碼的同義庫，運(yùn)用最長公共子串的算法對(duì)代碼片段進(jìn)行相似度匹配，又根據(jù)人工評(píng)判數(shù)據(jù)進(jìn)行多項(xiàng)式擬合，制定了貼合實(shí)際的評(píng)分策略，并為此開發(fā)了原型系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，該模型有效提高了SQL代碼的評(píng)分效率及正確率，因此可以定量地衡量SQL代碼的水平。但是，該模型存在一些問題，比如關(guān)鍵詞出錯(cuò)的處理，尚需進(jìn)一步深入，可作為未來工作的研究點(diǎn)。

參考文獻(xiàn)：

[1] 解 萍.《數(shù)據(jù)庫》課程在學(xué)生軟件能力培養(yǎng)中的作用分析[J].科技視界,2012(15):101-102.

[2] 楊鶴標(biāo),劉 玲,楊立凡.基于結(jié)構(gòu)相似匹配的SQL程序自動(dòng)評(píng)估模型研究[J].計(jì)算機(jī)工程與科學(xué),2010,32(11):92-96.

[3] 鄭燕娥.Java編程題自動(dòng)評(píng)分技術(shù)的研究與實(shí)現(xiàn)[D].泉州:華僑大學(xué),2013.

[4] 段漢周,凌 捷,鄭衍衡.VB程序設(shè)計(jì)考核自動(dòng)評(píng)閱系統(tǒng)中若干問題的研究[J].計(jì)算機(jī)工程,2001,27(4):167-168.

[6] 王甜甜.基于語義相似度的編程題自動(dòng)評(píng)分方法的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2005.

[7] 馬培軍,王甜甜,蘇小紅.基于程序理解的編程題自動(dòng)評(píng)分方法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(7):1136-1142.

[8] 牛永潔,張曉光.關(guān)于程序設(shè)計(jì)題自動(dòng)評(píng)分方法的研究[J].信息技術(shù),2010(11):155-156.

[9] CHEN Yaofei,CHEN Huantong.Research of automatic ma-rking on SQL server skill assessment based on XML[C]//International conference on web information systems and mining.Washington DC,USA:IEEE Computer Society,2010:8-12.

[10] HINKKA M,LEHTOAND T,HELJANKO K.Assessing big data SQL frameworks for analyzing event logs[C]//24th Euromicro international conference on parallel,distributed,and network-based processing.Washington DC,USA:IEEE Computer Society,2016:101-108.

[11] 王小鳳,周明全,耿國華,等.一種基于字符距離的特征字符串近似匹配算法[C]//圖像圖形技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議.北京:北京師范大學(xué)出版社,2008.

[12] 徐黎明.基于GST字符串近似匹配算法的研究[J].內(nèi)蒙古科技與經(jīng)濟(jì),2016(7):87-89.

[13] KLEINER C,TEBBE C,HEINE F.Automated grading and tutoring of SQL statements to improve student learning[C]//Proceedings of the 13th Koli calling international conference on computing education research.New York,NY,USA:ACM,2013:161-168.

[14] 馮君遠(yuǎn),賴明欽,李啟良.C語言源代碼抄襲識(shí)別的研究[J].福建電腦,2013,29(5):34-36.

[15] POHUBA D,DULIK T,JANKU P.Automatic evaluation of correctness and originality of source codes[C]//10th European workshop on microelectronics education.Washington DC,USA:IEEE Computer Society,2014:49-52.