基于結構和語義相似度的SQL程序評分模型①

陳潔

(中華女子學院 計算機系,北京 100101)

基于結構和語義相似度的SQL程序評分模型①

陳潔

(中華女子學院 計算機系,北京 100101)

針對SQL查詢程序實現多樣性的問題,提出一種用于精確評估SQL程序的評分模型.首先基于通用標準的SQL語法規范標識符和命令子句,基于同義詞鏈和抽象語法樹規范表達式,將SQL程序轉換成統一的中間形式,充分消除SQL程序句法和語義表達多樣性帶來的差異;然后,模擬人工評分思想,對標準化后的程序按評分點組成評估單元序列,采用改進的最長公共子序列算法評估代碼相似度,按評分點權重計算成績,并給出錯誤定位;最后,通過樣例測試和分析說明了評分模型的有效性.

SQL查詢;程序標準化;抽象語法樹;最長公共子序列;自動評分

SQL查詢設計是數據庫技術的一個重要應用,其設計方法靈活,表達方式多樣化,為實現同一要求,可以使用不同的命令式子;而在同一個命令式子中,同一個數據項可以有不同的表示形式,同一個表達式也可以有多種表示方式.這種多樣性給機器的自動評閱帶來了很大困難,成為影響評閱精度的重要因素.

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

為此,針對SQL程序語義表達多樣性的問題,首先采用多維度的語義消歧方法,對命令子句、標識符、計算表達式和邏輯表達式進行標準化處理;然后將基于動態規劃方法的最長公共子序列算法(Longest Common Subsequence,LCS)[9,10]應用于SQL程序相似匹配中,并考慮不同評分點的分值權重,計算學生程序和模板程序的相似度,使評分過程更加客觀公正,評分結果更加準確.

1 設計思想

基于結構和語義相似度的SQL程序評分模型如圖1所示,分為標準化處理和相似度評估兩個部分.

圖1 SQL程序評分模型

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

標準化處理后,再模擬人工評分的思想,從程序結構和設計內容兩方面進行考查,分別將SQL代碼中的命令關鍵字、標識符、表達式、子查詢設置為評分點,在詞法分析時,以評分點為單元抽取相應的標記,組成一個評估單元(token)序列.同時,還考慮到不同的評估單元在信息體現的重要性上的差別,通過賦予不同的權重,對得到的最長公共子序列進行加權處理,計算模板代碼和學生代碼的相似度,使評分過程更加客觀公正.

一題多解的情況在SQL程序設計中很常見,為此需要建立多個SQL模板程序,并用每個模板代碼依次評估學生代碼,該題的最終得分即為每個結果中的最大值,這也體現了評分過程的完備性.

2 SQL代碼的標準化

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

2.1 命令子句和標識符的標準化

2.1.1 命令子句的標準化[11]

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

2.1.2 標識符的標準化

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

① 別名處理:由于表的別名和字段別名不影響代碼執行結果,所以可以忽略字段別名,表的別名統一用表名表示.

② 更新標識符:將所有字段名均表示為“表名.字段名”的形式.若輸出列中使用了“*”號,則將“*”擴展為基表中的所有字段.排序項為列的別名或序號時,均用標準化后的輸出列標識符表示,沒有指定排序方向的默認加asc關鍵字.

③ 重排標識符順序:Select子句中輸出列的順序和From子句中表的排列順序不影響查詢結果,可以統一為排序后的順序.對連接條件中的同名字段,也統一為排序后的順序.

2.2 表達式的標準化

語義等價的表達式可以有多種表達方式,表達式的標準化處理基于同義詞鏈和抽象語法樹.

2.2.1 同義詞替換

語義等價的表達式采用不同的實現方法.如, left(學號,2)和substring(學號,1,2)語義等價.對此,可以建立同義詞鏈,進行同義詞替換.同義鏈的形式為“目標表達式:備選表達式1|備選表達式2|…”,如,“left(學號,2):substring(學號,1,2)”,統一表示為left(學號,2).

2.2.2 運算符轉換

語義等價的表達式中采用不同的運算符.如,“in”與“or”運算符語義等價,“between…and”與“>=…and…<=”語義等價.將包含in或between…and運算符的表達式轉換為邏輯表達式或關系表達式.

2.2.3 表達式中運算符和運算對象位置的標準化

針對運算符的優先級、結合性及所滿足的運算律方面的不同而導致的表達多樣性,可以按一定的語法語義規則將表達式轉換成中間形式,從而達到標準化的效果.

(1)算術表達式的標準化

文獻[12]中介紹了31條算術表達式轉換規則和22條布爾表達式轉換規則對表達式進行標準化處理.本文根據SQL查詢程序中表達式的應用情況,基于后綴式和抽象語法樹,對表達式進行標準化處理.

第一步,將中綴式轉換為后綴式,統一表達式中不同優先級運算符的順序.后綴式也稱為逆波蘭式[13],是一種表達式中間代碼形式,它將運算符寫在運算對象的后面,其形式化表示為“arg1 arg2 op”,這種表示方式除去了原表達式中的括號,且運算符的順序與表達式的實際運算次序相同.

文獻[14]中介紹了中綴式轉換為后綴式的算法.

第二步,建立抽象語法樹,規范同級運算符和運算對象的順序.本文規定,同級運算符的排列優先級為:+、-運算符按先“+”后“-”的順序,*、/、%(取模)運算符按“*”、“/”、“%”的順序.按以下方法調整運算符節點(op)和運算對象節點在樹中的位置:

① 依次交換左右子節點、分解右子樹、交換左側上下子節點和右側上下子節點,使排序優先級高的op節點位于樹的左下方,排序優先級低的op節點位于樹的右上方.

② 重復上述過程,直到沒有一項操作要做為止.

③ 運算對象按字符串的排序規則排序,值小的放在運算符的左邊.先比較每個op節點下的2個葉子節點;再比較每個op節點下的2個非葉子節點(或1個葉子節點和1個非葉子節點),對非葉子節點比較其左葉子節點的值;最后比較2個或多個相鄰且同名的op節點下的子節點.

例如,“d*c-a+b”的后綴式為“dc*a-b+”,依此建立的樹結構,按同級運算符排列優先級調整的結果以及對運算對象排序后的結果如圖2所示,最后的標準式為“bcd*+a-”.

圖2 同級運算符和運算對象的標準化過程

(2)邏輯表達式的標準化

對于邏輯表達式,首先分離出其中的算術表達式成分,然后再對邏輯表達式進行處理,方法與算術表達式的處理類似.表達式中包含Not運算符且運算對象是關系表達式時,先執行取反操作,再將表達式轉換為后綴式.例如,“y>30 and x not between 20 and 50”的標準式為“x<20 x>50 or y>30 and”.

3 基于LCS算法的程序相似度評估

評分模型針對SQL語言本身所具有的特征,模擬人工評分的思路,劃分評分點,并采用LCS算法,評估學生程序和模板程序的相似度,同時按評分點的難易度計算分值,充分體現評分過程的公正性和合理性.

3.1 最長公共子序列

SQL程序本質上就是一個句子,本文采用LCS算法,并根據SQL程序的結構特征進行適當改進后,用于SQL程序的相似度評估.

最長公共子序列的長度即為c[n],依據該數組回溯,便可找出最長公共子序列.對SQL語句相似度評估時,序列中的每一項對應一個評估單元,最長公共子序列即代表學生程序中正確的部分.

本文的評分模型要同時從結構和語義兩方面評估代碼相似度,為適合本文的問題域,對式(1)做適當修正,將2個數據項相同的概念定義為“值相等并且來自同一個命令子句”,因此遞歸式中的條件修改為:

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

不同的評估單元在信息體現的重要性上是有差別的,因此各評估點的分值是不同的,評分模型中通過將每個評估單元劃分為不同的單元類型,并賦予不同的權重,來體現這種差別.單元類型分為關鍵字、表達式、標識符、子查詢標識符四種,其中,關鍵字是指用來描述程序結構的命令關鍵字,如select、from、where等;表達式包括算術表達式和關系表達式,邏輯表達式拆分為關系表達式和邏輯運算符,以兼顧評估粒度的大小和信息表達的完整性;標識符包括表名、字段名、邏輯運算符和程序中的其他關鍵字(如distinct、asc、desc等);子查詢標識符代表子查詢在父查詢中的占位符,用“[?]”表示,子查詢從父查詢中分離出來單獨評估.每個類型的權重分別為w1、w2、w3和0.

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

其中,ni和Ni分別表示最長公共子序列和模板程序的token序列中各單元類型的數量(計算相似度時,子查詢和父查詢的結果合并在一起),w為對應的權重.

對于2個給定的字符序列,最長公共子序列的個數可能有多個,當基于權重計算相似度時就會導致不同的結果.但在本文設計的評分模型中,相似度值是唯一的.select、from、where等子句中的各項在標準化之后都是按順序排列的,如果group by和order by子句中包含多個數據項,因數據項未按順序排列,這2個子句中的匹配結果可能有多組,但匹配個數是相同的,且這2個子句中的評估單元都可以視作標識符類型,因此最終得到的相似度值只有一個.

最長公共子序列評估了學生程序中正確的部分,當學生程序中包含多余子句時,應該酌情扣除這部分結構性錯誤的分值.因此,每題最后的得分s,可通過式(3)計算:

其中S表示題目的總分值,△n為學生程序中多余子句的數量,w’表示扣分權重.

3.2 SQL程序相似度評估

基于LCS算法的評估步驟為:

① 對模板程序進行詞法分析,按語句的自然順序和句法規定的分隔符劃分每個評估單元,組成一個token序列X,并統計X中各單元類型的數量N1,N2,N3.

② 對學生程序進行詞法分析,組成評估序列Y,并統計關鍵字類型的數量n1’.

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

④ 統計Z中各單元類型的數量n1,n2,n3,通過式(2)計算學生程序的相似度值sim.

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

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

⑦ 若是一題多解,有多個模板程序,則重復執行

假設標準化后的模板程序:select s.name,s.sno from s where s.dept=’CS’order by s.sno asc,學生程序: 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.

對于包含子查詢的SQL程序,分別計算父查詢和子查詢的最長公共子序列,并將統計的各單元類型數量合并后計算出整個SQL代碼的相似度.

4 樣例測試和分析

為了驗證評估模型的實際效果,選取不同類型的SQL程序樣例進行測試和分析.其中,x、y分別表示模板程序和學生程序,X、Y分別表示2個程序標準化之后的中間形式,sim表示X和Y的相似度值.測試結果如表1所示.

表1 測試分析

(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對應的token序列包括父查詢和子查詢2個:

有如下2個學生程序:

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

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

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

有如下學生程序:

y:select職工號,sum(金額)as總金額 from 職工,訂購單,倉庫 where職工.職工號=訂購單.經手人 and職工.倉庫號=倉庫.倉庫號 and(城市='北京'and供貨方='S4'or year(訂購日期)='2016')and sum(金額)> 100000

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

從測試結果中可以看出,SQL程序經過標準化處理后提高了評估結果的準確性;基于結構和語義的評分方式也充分體現了評分過程的合理性,如學生程序存在結構性錯誤時評估的相似度較低,符合人工評分思想.

5 結語

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

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

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

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

4楊鶴標,劉玲,楊立凡.基于結構相似匹配的SQL程序自動評估模型研究.計算機工程與科學,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馬培軍,王甜甜,蘇小紅.基于程序理解的編程題自動評分方法.計算機研究與發展,2009,46(7):1136–1142.

7段利國,陳俊杰.綜合句法結構及語義相似度的問題推薦技術.計算機科學,2012,39(1):203–206.

8屠方博,楊志強.基于語法樹和JavaCC的程序題自動評分系統.計算機技術與發展,2012,22(1):126–128.

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

10王紅梅.算法設計與分析.北京:清華大學出版社,2006: 126–128.

11李海龍,張偉明,肖衛東等.通用標準SQL語法分析模型.小型微型計算機系統,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張素琴,呂映芝,蔣維杜等.編譯原理.北京:清華大學出版社,2005.

14陳慧南.數據結構——C語言描述.西安:西安電子科技大學出版社,2009.

15周松松,馬建紅.基于URL相似度的會話識別方法.計算機系統應用,2014,23(12):191–196.

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

17曾波,潘少彬,陸璐.改進的LCS方法在測試腳本序列比對中的應用.計算機工程與應用,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

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

2016-08-13;收到修改稿時間:2016-09-27

10.15888/j.cnki.csa.005750