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

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

0 引 言

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

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

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

1 自動評分模型

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

圖1 自動評分模型總流程

1.1 預(yù)處理

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

圖2 預(yù)處理流程

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

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

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

(4)對于表名加字段名的代碼，將表名移除，留下“.+字段名”。為體現(xiàn)代碼中帶有表名，保留“.”，但為了代碼的易于識別，移除會給相似度帶來較大誤差的表名。例如：“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)對SQL代碼的各個關(guān)鍵詞之間的字段以及子句按ASCII值先后順序排序。其目的是保證相似語義的代碼片段相似度匹配時能獲得最大相似度[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 特征提取

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

由分析可知，SQL語句有其特有的語法規(guī)則以及明確的關(guān)鍵字，在評分時，關(guān)鍵詞占據(jù)較大的比重，先查詢到關(guān)鍵詞的正確率，才會逐步分析關(guān)鍵詞之后的字段差異。因此在提取結(jié)構(gòu)時，首先按照關(guān)鍵詞提取SQL的結(jié)構(gòu)特征。將SQL代碼進(jìn)行分類標(biāo)識，分為關(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)換

在評分過程中，兩段不同代碼實(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。

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

表1 常用等價語句表

1.4 基于LCS的相似度比較

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

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

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

定義1：

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

(3)由SL[i][j]可得對應(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é)尾的最長相同子串之后添上這個字符即可，這樣就可以讓SL增加一位；值得注意的是，若S1，S2中任何一個是空字符串，那么最長公共子串的長度SL就為0。這是一個遞歸問題的求解，為了更直觀形象地表述，可以得到狀態(tài)轉(zhuǎn)移方程：

(2)

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

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

(3)

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

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

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

(4)

例1，現(xiàn)有兩個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)整及評分策略

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

為使自動評分更貼近人工評審，根據(jù)人工評判結(jié)果制定了評分策略。據(jù)人工評判數(shù)據(jù)統(tǒng)計，得到相似度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。

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

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

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

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

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

2.1 人工評分和自動評分?jǐn)?shù)據(jù)分析

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

現(xiàn)有測試集：A班作業(yè)SQL代碼，共計200條數(shù)據(jù)。對該測試集進(jìn)行自動評分測試，統(tǒng)計準(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)鍵詞拼錯，但是關(guān)鍵詞之后的字段出錯地方較少的情況。因此，除去關(guān)鍵詞出錯的情況，該自動評分模型對SQL代碼的評分準(zhǔn)確率高且穩(wěn)定，總的來說可以達(dá)到較好的效果，因此可以定性地評判SQL代碼。

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

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

[8] 牛永潔,張曉光.關(guān)于程序設(shè)計題自動評分方法的研究[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ù)會議.北京:北京師范大學(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語言源代碼抄襲識別的研究[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.