基于結(jié)構(gòu)和語(yǔ)義相似度的SQL程序評(píng)分模型①

陳潔

(中華女子學(xué)院 計(jì)算機(jī)系,北京 100101)

基于結(jié)構(gòu)和語(yǔ)義相似度的SQL程序評(píng)分模型①

陳潔

(中華女子學(xué)院 計(jì)算機(jī)系,北京 100101)

針對(duì)SQL查詢程序?qū)崿F(xiàn)多樣性的問題,提出一種用于精確評(píng)估SQL程序的評(píng)分模型.首先基于通用標(biāo)準(zhǔn)的SQL語(yǔ)法規(guī)范標(biāo)識(shí)符和命令子句,基于同義詞鏈和抽象語(yǔ)法樹規(guī)范表達(dá)式,將SQL程序轉(zhuǎn)換成統(tǒng)一的中間形式,充分消除SQL程序句法和語(yǔ)義表達(dá)多樣性帶來(lái)的差異;然后,模擬人工評(píng)分思想,對(duì)標(biāo)準(zhǔn)化后的程序按評(píng)分點(diǎn)組成評(píng)估單元序列,采用改進(jìn)的最長(zhǎng)公共子序列算法評(píng)估代碼相似度,按評(píng)分點(diǎn)權(quán)重計(jì)算成績(jī),并給出錯(cuò)誤定位;最后,通過樣例測(cè)試和分析說(shuō)明了評(píng)分模型的有效性.

SQL查詢;程序標(biāo)準(zhǔn)化;抽象語(yǔ)法樹;最長(zhǎng)公共子序列;自動(dòng)評(píng)分

SQL查詢?cè)O(shè)計(jì)是數(shù)據(jù)庫(kù)技術(shù)的一個(gè)重要應(yīng)用,其設(shè)計(jì)方法靈活,表達(dá)方式多樣化,為實(shí)現(xiàn)同一要求,可以使用不同的命令式子;而在同一個(gè)命令式子中,同一個(gè)數(shù)據(jù)項(xiàng)可以有不同的表示形式,同一個(gè)表達(dá)式也可以有多種表示方式.這種多樣性給機(jī)器的自動(dòng)評(píng)閱帶來(lái)了很大困難,成為影響評(píng)閱精度的重要因素.

字符串的相似度查詢和語(yǔ)句相似度計(jì)算已成為研究熱點(diǎn)[1-3].文獻(xiàn)[4]給出了一個(gè)基于結(jié)構(gòu)相似匹配的評(píng)估模型,該模型借鑒 Petro vskiy[5]提出的通過提取SQL查詢語(yǔ)句框架進(jìn)行異常檢測(cè)的方法,重點(diǎn)評(píng)估SQL查詢程序的結(jié)構(gòu),即命令關(guān)鍵字和運(yùn)算符,對(duì)標(biāo)識(shí)符(如字段名、表名等)和表達(dá)式則不做檢測(cè).但在實(shí)際應(yīng)用中,標(biāo)識(shí)符和表達(dá)式具有靈活的設(shè)置方法和多樣化的表達(dá)方式,可變性范圍很大.為了更全面和準(zhǔn)確地考查學(xué)習(xí)者對(duì)SQL查詢程序的設(shè)計(jì)能力,本文借鑒文獻(xiàn)[6-8]中提出的綜合句法結(jié)構(gòu)及語(yǔ)義相似度的評(píng)估模型,根據(jù)句法和語(yǔ)義兩個(gè)層次來(lái)評(píng)估學(xué)生程序的正確程度.

為此,針對(duì)SQL程序語(yǔ)義表達(dá)多樣性的問題,首先采用多維度的語(yǔ)義消歧方法,對(duì)命令子句、標(biāo)識(shí)符、計(jì)算表達(dá)式和邏輯表達(dá)式進(jìn)行標(biāo)準(zhǔn)化處理;然后將基于動(dòng)態(tài)規(guī)劃方法的最長(zhǎng)公共子序列算法(Longest Common Subsequence,LCS)[9,10]應(yīng)用于SQL程序相似匹配中,并考慮不同評(píng)分點(diǎn)的分值權(quán)重,計(jì)算學(xué)生程序和模板程序的相似度,使評(píng)分過程更加客觀公正,評(píng)分結(jié)果更加準(zhǔn)確.

1 設(shè)計(jì)思想

基于結(jié)構(gòu)和語(yǔ)義相似度的SQL程序評(píng)分模型如圖1所示,分為標(biāo)準(zhǔn)化處理和相似度評(píng)估兩個(gè)部分.

圖1 SQL程序評(píng)分模型

在SQL代碼中,除語(yǔ)法規(guī)定的關(guān)鍵字,其他的標(biāo)識(shí)符和表達(dá)式具有很大的可變性,且有多種符合語(yǔ)義的書寫方式,必須進(jìn)行標(biāo)準(zhǔn)化處理.通過采用格式規(guī)范化、同義詞鏈和基于后綴式的抽象語(yǔ)法樹等方法,將代碼中的標(biāo)識(shí)符、表達(dá)式和命令子句按一定的語(yǔ)法語(yǔ)義規(guī)則轉(zhuǎn)換成統(tǒng)一的中間形式,以提高詞法分析階段輸出的標(biāo)記串(token)的標(biāo)準(zhǔn)化程度,從而提高評(píng)估結(jié)果的準(zhǔn)確性.

標(biāo)準(zhǔn)化處理后,再模擬人工評(píng)分的思想,從程序結(jié)構(gòu)和設(shè)計(jì)內(nèi)容兩方面進(jìn)行考查,分別將SQL代碼中的命令關(guān)鍵字、標(biāo)識(shí)符、表達(dá)式、子查詢?cè)O(shè)置為評(píng)分點(diǎn),在詞法分析時(shí),以評(píng)分點(diǎn)為單元抽取相應(yīng)的標(biāo)記,組成一個(gè)評(píng)估單元(token)序列.同時(shí),還考慮到不同的評(píng)估單元在信息體現(xiàn)的重要性上的差別,通過賦予不同的權(quán)重,對(duì)得到的最長(zhǎng)公共子序列進(jìn)行加權(quán)處理,計(jì)算模板代碼和學(xué)生代碼的相似度,使評(píng)分過程更加客觀公正.

一題多解的情況在SQL程序設(shè)計(jì)中很常見,為此需要建立多個(gè)SQL模板程序,并用每個(gè)模板代碼依次評(píng)估學(xué)生代碼,該題的最終得分即為每個(gè)結(jié)果中的最大值,這也體現(xiàn)了評(píng)分過程的完備性.

2 SQL代碼的標(biāo)準(zhǔn)化

在基本的代碼格式標(biāo)準(zhǔn)化(如將大寫字母轉(zhuǎn)化為小寫等)基礎(chǔ)上,通過運(yùn)用符合語(yǔ)法語(yǔ)義的標(biāo)準(zhǔn)化規(guī)則,可以消除SQL代碼語(yǔ)義表達(dá)的多樣性,提高學(xué)生程序和模板程序之間相似度匹配的準(zhǔn)確率,同時(shí)也能有效地減少模板程序的數(shù)量.

2.1 命令子句和標(biāo)識(shí)符的標(biāo)準(zhǔn)化

2.1.1 命令子句的標(biāo)準(zhǔn)化[11]

對(duì)多表的連接查詢,將Where子句中的連接條件移入From子句,Where中只保留篩選條件.From子句可形式化表示為“from,,… on .=.,…”.

2.1.2 標(biāo)識(shí)符的標(biāo)準(zhǔn)化

基于查詢使用的基表,通過分析From子句,可以得到表名、表的別名、連接條件等信息.

① 別名處理:由于表的別名和字段別名不影響代碼執(zhí)行結(jié)果,所以可以忽略字段別名,表的別名統(tǒng)一用表名表示.

② 更新標(biāo)識(shí)符:將所有字段名均表示為“表名.字段名”的形式.若輸出列中使用了“*”號(hào),則將“*”擴(kuò)展為基表中的所有字段.排序項(xiàng)為列的別名或序號(hào)時(shí),均用標(biāo)準(zhǔn)化后的輸出列標(biāo)識(shí)符表示,沒有指定排序方向的默認(rèn)加asc關(guān)鍵字.

③ 重排標(biāo)識(shí)符順序:Select子句中輸出列的順序和From子句中表的排列順序不影響查詢結(jié)果,可以統(tǒng)一為排序后的順序.對(duì)連接條件中的同名字段,也統(tǒng)一為排序后的順序.

2.2 表達(dá)式的標(biāo)準(zhǔn)化

語(yǔ)義等價(jià)的表達(dá)式可以有多種表達(dá)方式,表達(dá)式的標(biāo)準(zhǔn)化處理基于同義詞鏈和抽象語(yǔ)法樹.

2.2.1 同義詞替換

語(yǔ)義等價(jià)的表達(dá)式采用不同的實(shí)現(xiàn)方法.如, left(學(xué)號(hào),2)和substring(學(xué)號(hào),1,2)語(yǔ)義等價(jià).對(duì)此,可以建立同義詞鏈,進(jìn)行同義詞替換.同義鏈的形式為“目標(biāo)表達(dá)式:備選表達(dá)式1|備選表達(dá)式2|…”,如,“l(fā)eft(學(xué)號(hào),2):substring(學(xué)號(hào),1,2)”,統(tǒng)一表示為left(學(xué)號(hào),2).

2.2.2 運(yùn)算符轉(zhuǎn)換

語(yǔ)義等價(jià)的表達(dá)式中采用不同的運(yùn)算符.如,“in”與“or”運(yùn)算符語(yǔ)義等價(jià),“between…and”與“>=…and…<=”語(yǔ)義等價(jià).將包含in或between…and運(yùn)算符的表達(dá)式轉(zhuǎn)換為邏輯表達(dá)式或關(guān)系表達(dá)式.

2.2.3 表達(dá)式中運(yùn)算符和運(yùn)算對(duì)象位置的標(biāo)準(zhǔn)化

針對(duì)運(yùn)算符的優(yōu)先級(jí)、結(jié)合性及所滿足的運(yùn)算律方面的不同而導(dǎo)致的表達(dá)多樣性,可以按一定的語(yǔ)法語(yǔ)義規(guī)則將表達(dá)式轉(zhuǎn)換成中間形式,從而達(dá)到標(biāo)準(zhǔn)化的效果.

(1)算術(shù)表達(dá)式的標(biāo)準(zhǔn)化

文獻(xiàn)[12]中介紹了31條算術(shù)表達(dá)式轉(zhuǎn)換規(guī)則和22條布爾表達(dá)式轉(zhuǎn)換規(guī)則對(duì)表達(dá)式進(jìn)行標(biāo)準(zhǔn)化處理.本文根據(jù)SQL查詢程序中表達(dá)式的應(yīng)用情況,基于后綴式和抽象語(yǔ)法樹,對(duì)表達(dá)式進(jìn)行標(biāo)準(zhǔn)化處理.

第一步,將中綴式轉(zhuǎn)換為后綴式,統(tǒng)一表達(dá)式中不同優(yōu)先級(jí)運(yùn)算符的順序.后綴式也稱為逆波蘭式[13],是一種表達(dá)式中間代碼形式,它將運(yùn)算符寫在運(yùn)算對(duì)象的后面,其形式化表示為“arg1 arg2 op”,這種表示方式除去了原表達(dá)式中的括號(hào),且運(yùn)算符的順序與表達(dá)式的實(shí)際運(yùn)算次序相同.

文獻(xiàn)[14]中介紹了中綴式轉(zhuǎn)換為后綴式的算法.

第二步,建立抽象語(yǔ)法樹,規(guī)范同級(jí)運(yùn)算符和運(yùn)算對(duì)象的順序.本文規(guī)定,同級(jí)運(yùn)算符的排列優(yōu)先級(jí)為:+、-運(yùn)算符按先“+”后“-”的順序,*、/、%(取模)運(yùn)算符按“*”、“/”、“%”的順序.按以下方法調(diào)整運(yùn)算符節(jié)點(diǎn)(op)和運(yùn)算對(duì)象節(jié)點(diǎn)在樹中的位置:

① 依次交換左右子節(jié)點(diǎn)、分解右子樹、交換左側(cè)上下子節(jié)點(diǎn)和右側(cè)上下子節(jié)點(diǎn),使排序優(yōu)先級(jí)高的op節(jié)點(diǎn)位于樹的左下方,排序優(yōu)先級(jí)低的op節(jié)點(diǎn)位于樹的右上方.

② 重復(fù)上述過程,直到?jīng)]有一項(xiàng)操作要做為止.

③ 運(yùn)算對(duì)象按字符串的排序規(guī)則排序,值小的放在運(yùn)算符的左邊.先比較每個(gè)op節(jié)點(diǎn)下的2個(gè)葉子節(jié)點(diǎn);再比較每個(gè)op節(jié)點(diǎn)下的2個(gè)非葉子節(jié)點(diǎn)(或1個(gè)葉子節(jié)點(diǎn)和1個(gè)非葉子節(jié)點(diǎn)),對(duì)非葉子節(jié)點(diǎn)比較其左葉子節(jié)點(diǎn)的值;最后比較2個(gè)或多個(gè)相鄰且同名的op節(jié)點(diǎn)下的子節(jié)點(diǎn).

例如,“d*c-a+b”的后綴式為“dc*a-b+”,依此建立的樹結(jié)構(gòu),按同級(jí)運(yùn)算符排列優(yōu)先級(jí)調(diào)整的結(jié)果以及對(duì)運(yùn)算對(duì)象排序后的結(jié)果如圖2所示,最后的標(biāo)準(zhǔn)式為“bcd*+a-”.

圖2 同級(jí)運(yùn)算符和運(yùn)算對(duì)象的標(biāo)準(zhǔn)化過程

(2)邏輯表達(dá)式的標(biāo)準(zhǔn)化

對(duì)于邏輯表達(dá)式,首先分離出其中的算術(shù)表達(dá)式成分,然后再對(duì)邏輯表達(dá)式進(jìn)行處理,方法與算術(shù)表達(dá)式的處理類似.表達(dá)式中包含Not運(yùn)算符且運(yùn)算對(duì)象是關(guān)系表達(dá)式時(shí),先執(zhí)行取反操作,再將表達(dá)式轉(zhuǎn)換為后綴式.例如,“y>30 and x not between 20 and 50”的標(biāo)準(zhǔn)式為“x<20 x>50 or y>30 and”.

3 基于LCS算法的程序相似度評(píng)估

評(píng)分模型針對(duì)SQL語(yǔ)言本身所具有的特征,模擬人工評(píng)分的思路,劃分評(píng)分點(diǎn),并采用LCS算法,評(píng)估學(xué)生程序和模板程序的相似度,同時(shí)按評(píng)分點(diǎn)的難易度計(jì)算分值,充分體現(xiàn)評(píng)分過程的公正性和合理性.

3.1 最長(zhǎng)公共子序列

SQL程序本質(zhì)上就是一個(gè)句子,本文采用LCS算法,并根據(jù)SQL程序的結(jié)構(gòu)特征進(jìn)行適當(dāng)改進(jìn)后,用于SQL程序的相似度評(píng)估.

最長(zhǎng)公共子序列的長(zhǎng)度即為c[n],依據(jù)該數(shù)組回溯,便可找出最長(zhǎng)公共子序列.對(duì)SQL語(yǔ)句相似度評(píng)估時(shí),序列中的每一項(xiàng)對(duì)應(yīng)一個(gè)評(píng)估單元,最長(zhǎng)公共子序列即代表學(xué)生程序中正確的部分.

本文的評(píng)分模型要同時(shí)從結(jié)構(gòu)和語(yǔ)義兩方面評(píng)估代碼相似度,為適合本文的問題域,對(duì)式(1)做適當(dāng)修正,將2個(gè)數(shù)據(jù)項(xiàng)相同的概念定義為“值相等并且來(lái)自同一個(gè)命令子句”,因此遞歸式中的條件修改為:

當(dāng) i,j>0且 xi=yj時(shí),如果xi,yj來(lái)自同一個(gè)命令子句,則c[i]=c[i-1][j-1]+1;如果是來(lái)自不同的命令子句,則c[i]=max(c[i][j-1],c[i-1]).

不同的評(píng)估單元在信息體現(xiàn)的重要性上是有差別的,因此各評(píng)估點(diǎn)的分值是不同的,評(píng)分模型中通過將每個(gè)評(píng)估單元?jiǎng)澐譃椴煌膯卧愋?并賦予不同的權(quán)重,來(lái)體現(xiàn)這種差別.單元類型分為關(guān)鍵字、表達(dá)式、標(biāo)識(shí)符、子查詢標(biāo)識(shí)符四種,其中,關(guān)鍵字是指用來(lái)描述程序結(jié)構(gòu)的命令關(guān)鍵字,如select、from、where等;表達(dá)式包括算術(shù)表達(dá)式和關(guān)系表達(dá)式,邏輯表達(dá)式拆分為關(guān)系表達(dá)式和邏輯運(yùn)算符,以兼顧評(píng)估粒度的大小和信息表達(dá)的完整性;標(biāo)識(shí)符包括表名、字段名、邏輯運(yùn)算符和程序中的其他關(guān)鍵字(如distinct、asc、desc等);子查詢標(biāo)識(shí)符代表子查詢?cè)诟覆樵冎械恼嘉环?用“[?]”表示,子查詢從父查詢中分離出來(lái)單獨(dú)評(píng)估.每個(gè)類型的權(quán)重分別為w1、w2、w3和0.

基于權(quán)重的X和Y兩個(gè)序列的相似度sim(X,Y),可通過式(2)計(jì)算得到.

其中,ni和Ni分別表示最長(zhǎng)公共子序列和模板程序的token序列中各單元類型的數(shù)量(計(jì)算相似度時(shí),子查詢和父查詢的結(jié)果合并在一起),w為對(duì)應(yīng)的權(quán)重.

對(duì)于2個(gè)給定的字符序列,最長(zhǎng)公共子序列的個(gè)數(shù)可能有多個(gè),當(dāng)基于權(quán)重計(jì)算相似度時(shí)就會(huì)導(dǎo)致不同的結(jié)果.但在本文設(shè)計(jì)的評(píng)分模型中,相似度值是唯一的.select、from、where等子句中的各項(xiàng)在標(biāo)準(zhǔn)化之后都是按順序排列的,如果group by和order by子句中包含多個(gè)數(shù)據(jù)項(xiàng),因數(shù)據(jù)項(xiàng)未按順序排列,這2個(gè)子句中的匹配結(jié)果可能有多組,但匹配個(gè)數(shù)是相同的,且這2個(gè)子句中的評(píng)估單元都可以視作標(biāo)識(shí)符類型,因此最終得到的相似度值只有一個(gè).

最長(zhǎng)公共子序列評(píng)估了學(xué)生程序中正確的部分,當(dāng)學(xué)生程序中包含多余子句時(shí),應(yīng)該酌情扣除這部分結(jié)構(gòu)性錯(cuò)誤的分值.因此,每題最后的得分s,可通過式(3)計(jì)算:

其中S表示題目的總分值,△n為學(xué)生程序中多余子句的數(shù)量,w’表示扣分權(quán)重.

3.2 SQL程序相似度評(píng)估

基于LCS算法的評(píng)估步驟為:

① 對(duì)模板程序進(jìn)行詞法分析,按語(yǔ)句的自然順序和句法規(guī)定的分隔符劃分每個(gè)評(píng)估單元,組成一個(gè)token序列X,并統(tǒng)計(jì)X中各單元類型的數(shù)量N1,N2,N3.

② 對(duì)學(xué)生程序進(jìn)行詞法分析,組成評(píng)估序列Y,并統(tǒng)計(jì)關(guān)鍵字類型的數(shù)量n1’.

③ 使用修正后的式(1)計(jì)算X和Y的最長(zhǎng)公共子序列Z.

④ 統(tǒng)計(jì)Z中各單元類型的數(shù)量n1,n2,n3,通過式(2)計(jì)算學(xué)生程序的相似度值sim.

⑤計(jì)算學(xué)生程序中多余的子句數(shù)量△n=n1’-n1(n1’>n1).

⑥ 通過式(3)計(jì)算該題的得分s.

⑦ 若是一題多解,有多個(gè)模板程序,則重復(fù)執(zhí)行

假設(shè)標(biāo)準(zhǔn)化后的模板程序:select s.name,s.sno from s where s.dept=’CS’order by s.sno asc,學(xué)生程序: select s.sno from s where s.dept=’CS’order by s.dept asc,則 X=(select,s.name,s.sno,from,s,where,s.dept=’CS’, orderby,s.sno,asc),Y=(select,s.sno,from,s,where, s.dept=’CS’,orderby,s.dept,as),Z=(select,s.sno,from,s, where,s.dept=’CS’,orderby,asc).若 w1=2,w2=2, w3=1,S=15,則 s=13.

對(duì)于包含子查詢的SQL程序,分別計(jì)算父查詢和子查詢的最長(zhǎng)公共子序列,并將統(tǒng)計(jì)的各單元類型數(shù)量合并后計(jì)算出整個(gè)SQL代碼的相似度.

4 樣例測(cè)試和分析

為了驗(yàn)證評(píng)估模型的實(shí)際效果,選取不同類型的SQL程序樣例進(jìn)行測(cè)試和分析.其中,x、y分別表示模板程序和學(xué)生程序,X、Y分別表示2個(gè)程序標(biāo)準(zhǔn)化之后的中間形式,sim表示X和Y的相似度值.測(cè)試結(jié)果如表1所示.

表1 測(cè)試分析

(1)例1:一題多解的SQL.

連接查詢x1:select sno,grade from c inner join sc on c.cno=sc.cno where cname=’java’,X1:select sc. grade,sc.sno from c,sc on c.cno=sc.cno where c.cname =’java’

子查詢 x2:select sno,grade from sc where cno=(select cno from c where cname=’java’),X2:select sc.grade,sc.sno from sc where sc.cno=(select c.cno from c where c.cname=’java’)

X2對(duì)應(yīng)的token序列包括父查詢和子查詢2個(gè):

有如下2個(gè)學(xué)生程序:

(2)例2:帶有連接和嵌套的復(fù)雜SQL.

x:select職工號(hào),sum(金額)as銷售總金額 from職工 e join訂購(gòu)單 o on e.職工號(hào)=o.經(jīng)手人 join倉(cāng)庫(kù) w on e.倉(cāng)庫(kù)號(hào)=w.倉(cāng)庫(kù)號(hào) where year(訂購(gòu)日期)= year(GETDATE())or(城市='北京'and供貨方 is not null and經(jīng)手人not in(select distinct經(jīng)手人from 訂購(gòu)單 where供貨方<>'S4'))group by職工號(hào) having sum(金額)>100000

預(yù)處理后,外層查詢語(yǔ)句中忽略列別名“銷售總金額”,from子句規(guī)范為“倉(cāng)庫(kù),訂購(gòu),職工”,on子句規(guī)范為“訂購(gòu)單.經(jīng)手人=職工.職工號(hào),倉(cāng)庫(kù).倉(cāng)庫(kù)號(hào)=職工.倉(cāng)庫(kù)號(hào)”,where子句規(guī)范為“year(getdate())=year(訂單.訂購(gòu)日期)倉(cāng)庫(kù).城市='北京'訂購(gòu)單.供貨方_is_not_null and訂購(gòu)單.經(jīng)手人 in(?)not and or”.

有如下學(xué)生程序:

y:select職工號(hào),sum(金額)as總金額 from 職工,訂購(gòu)單,倉(cāng)庫(kù) where職工.職工號(hào)=訂購(gòu)單.經(jīng)手人 and職工.倉(cāng)庫(kù)號(hào)=倉(cāng)庫(kù).倉(cāng)庫(kù)號(hào) and(城市='北京'and供貨方='S4'or year(訂購(gòu)日期)='2016')and sum(金額)> 100000

預(yù)處理后,y中的where子句規(guī)范為“倉(cāng)庫(kù).城市='北京'訂購(gòu)單.供貨方='S4'and year(訂單.訂貨日期)='2016'or sum(訂購(gòu)單.金額)>100000 and”.

從測(cè)試結(jié)果中可以看出,SQL程序經(jīng)過標(biāo)準(zhǔn)化處理后提高了評(píng)估結(jié)果的準(zhǔn)確性;基于結(jié)構(gòu)和語(yǔ)義的評(píng)分方式也充分體現(xiàn)了評(píng)分過程的合理性,如學(xué)生程序存在結(jié)構(gòu)性錯(cuò)誤時(shí)評(píng)估的相似度較低,符合人工評(píng)分思想.

5 結(jié)語(yǔ)

本文按照一定的語(yǔ)法語(yǔ)義規(guī)則,并結(jié)合抽象語(yǔ)法樹對(duì)SQL程序中的命令子句、標(biāo)識(shí)符和表達(dá)式進(jìn)行標(biāo)準(zhǔn)化處理,消除句法和語(yǔ)義的多樣性,減少模板程序的數(shù)量;采用改進(jìn)的LCS算法,考查模板程序和學(xué)生程序的匹配度,其中標(biāo)準(zhǔn)化處理是提高評(píng)估效率的關(guān)鍵.該模型能夠有效地評(píng)估多表查詢、子查詢、含有復(fù)雜條件的查詢,以及一題多解的情況,貼合人工評(píng)分結(jié)果,已在教學(xué)中得到實(shí)際應(yīng)用.

1林學(xué)民,王煒.集合和字符串的相似度查詢.計(jì)算機(jī)學(xué)報(bào), 2011,34(10):1853–1860.

2呂強(qiáng),鄧薇,宋玲.句子語(yǔ)義相似度計(jì)算.計(jì)算機(jī)工程與應(yīng)用, 2010,46(36):150–152,229.

3劉運(yùn)通,梁燕軍.基于分段語(yǔ)義比較的語(yǔ)句相似度計(jì)算方法.計(jì)算機(jī)工程與設(shè)計(jì),2013,34(7):2637–2641.

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

5 Petrovskiy M.A data mining approach to learning probabilistic user behavior models from database access log.Proc.of Portuguese ConfonArtificial Intelligence,2003.

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

7段利國(guó),陳俊杰.綜合句法結(jié)構(gòu)及語(yǔ)義相似度的問題推薦技術(shù).計(jì)算機(jī)科學(xué),2012,39(1):203–206.

8屠方博,楊志強(qiáng).基于語(yǔ)法樹和JavaCC的程序題自動(dòng)評(píng)分系統(tǒng).計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(1):126–128.

9 Hirschberg DS.Algorithmsforthelongestcommon subsequence problem.ACM,1977,24(4):664–675.

10王紅梅.算法設(shè)計(jì)與分析.北京:清華大學(xué)出版社,2006: 126–128.

11李海龍,張偉明,肖衛(wèi)東等.通用標(biāo)準(zhǔn)SQL語(yǔ)法分析模型.小型微型計(jì)算機(jī)系統(tǒng),2003,24(11):1969–1972.

12 Wang TT,Su XiH,Wang YY,etal.Semantic similarity-based grading of student programs.Information and Software Technolgy,2007,49(2):99–107.

13張素琴,呂映芝,蔣維杜等.編譯原理.北京:清華大學(xué)出版社,2005.

14陳慧南.數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言描述.西安:西安電子科技大學(xué)出版社,2009.

15周松松,馬建紅.基于URL相似度的會(huì)話識(shí)別方法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(12):191–196.

16于海英.程序代碼相似度度量的研究與實(shí)現(xiàn).計(jì)算機(jī)工程,2010,36(4):45–46,49.

17曾波,潘少彬,陸璐.改進(jìn)的LCS方法在測(cè)試腳本序列比對(duì)中的應(yīng)用.計(jì)算機(jī)工程與應(yīng)用,2011,47(35):71–76.

SQLProgram Grading Model Based on Structure and Semantic Similarity

CHEN Jie

(Department of Computer Science,China Women’s University,Beijing 100101,China)

In view of the diversity of SQL query program,an accurate scoring model is presented.First,based on the common standard SQL syntax specification identifier,command clause,the synonym chain and the abstract syntax tree, SQL program is converted into a kind of unified intermediate form,fully eliminating the SQL program syntax and semantic differences.Then,referring to the artificial grading thought,the standardized code is transformed into the token sequence according to grading points,and the improved algorithm for Longest Common Subsequence(LCS)is used to grade the program similarity.The scores are calculated according to the weight of the scoring points,and the error location is given as well.Finally,samples are tested and anglicized to illustrate the effectiveness of the grading model.

SQLquery;program standardization;abstract syntax tree;LCS;auto-grading

中華女子學(xué)院科研基金(KY2016-03011)

2016-08-13;收到修改稿時(shí)間:2016-09-27

10.15888/j.cnki.csa.005750