馬曉芳 楊衛(wèi)東

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 上海 201203)

0 引 言

隨著語義網(wǎng)、知識(shí)圖譜等技術(shù)的快速發(fā)展，結(jié)構(gòu)化語義數(shù)據(jù)的應(yīng)用越來越廣泛，這些數(shù)據(jù)通常使用資源描述框架(RDF)來表示。互聯(lián)網(wǎng)上出現(xiàn)了大量RDF形式的數(shù)據(jù)，如Dbpeida[1]、Yago[2]、Freebase[3]等。利用這些數(shù)據(jù)可以實(shí)現(xiàn)在用戶搜索時(shí)由一般文檔檢索轉(zhuǎn)換為知識(shí)檢索，提高返回結(jié)果與用戶搜索意圖的相關(guān)度，避免無關(guān)信息的展示。對(duì)于RDF數(shù)據(jù)中信息的檢索，可以通過W3C組織推薦的標(biāo)準(zhǔn)查詢語言SPARQL來實(shí)現(xiàn)。但是SPARQL語法非常復(fù)雜，且使用URI表示的數(shù)據(jù)資源可讀性較差，要準(zhǔn)確書寫SPARQL語句還需要用戶對(duì)原始數(shù)據(jù)圖的模式信息有一定的先驗(yàn)知識(shí)，這使得一般用戶從RDF數(shù)據(jù)中獲取所需信息是非常困難的，所以對(duì)于RDF數(shù)據(jù)的關(guān)鍵字查詢或者自然語言問句查詢的研究得到了越來越廣泛的關(guān)注，旨在方便普通用戶獲取RDF數(shù)據(jù)信息，實(shí)現(xiàn)語義檢索。相比于自然語言問句，RDF的關(guān)鍵字查詢更加接近于用戶的日常檢索習(xí)慣也更簡(jiǎn)潔易用，并且可以包含更多更廣泛的查詢信息。但是，由于關(guān)鍵字輸入中缺少語句中必要的依賴信息，使得對(duì)于用戶查詢意圖的理解相較于自然語言更加困難。

對(duì)于RDF數(shù)據(jù)基于關(guān)鍵字的信息檢索研究，主要可以分為兩大類[12]。一類是將關(guān)鍵字匹配到原始數(shù)據(jù)圖上的元素后，通過在整個(gè)數(shù)據(jù)圖上做檢索，獲得覆蓋全部匹配元素的最小子結(jié)構(gòu)，從而直接得到查詢結(jié)果[7，10-11]；第二類則是先將關(guān)鍵字查詢轉(zhuǎn)換為意圖匹配的結(jié)構(gòu)化查詢語句，之后再通過現(xiàn)有的查詢引擎執(zhí)行語句來獲得最終的結(jié)果[6，8-9]。文獻(xiàn)[11]通過劃分子圖對(duì)數(shù)據(jù)圖進(jìn)行索引，有效降低了搜索空間。文獻(xiàn)[8]通過在擴(kuò)展模式圖上進(jìn)行檢索確定查詢結(jié)構(gòu)，文獻(xiàn)[6]的查詢模式與文獻(xiàn)[8]類似，并且在結(jié)果排序時(shí)考慮了給定查詢中每個(gè)關(guān)鍵字對(duì)于其他關(guān)鍵字解釋的影響。

直接查詢和查詢轉(zhuǎn)換兩類方法都可以實(shí)現(xiàn)對(duì)于一般關(guān)鍵字查詢的支持，但是直接查詢方法只能返回圖中存在的元素作為查詢結(jié)果；查詢轉(zhuǎn)換方法也只能得到只包含查詢模式的查詢語句，無法充分利用SPARQL所支持的豐富查詢操作。上述相關(guān)研究的重點(diǎn)在于對(duì)圖進(jìn)行索引，以降低搜索空間，加快檢索效率，而忽略了對(duì)于統(tǒng)計(jì)信息的查詢。例如，對(duì)于查詢Q1={num, student, university0}表示“查詢university0中的學(xué)生數(shù)”，Q2={Article, max, volume}表示“查詢卷數(shù)最多的文章”，num/max所指示的查詢意圖無法被正確解析。同時(shí)，對(duì)于Q2中的關(guān)鍵字“max”可能指示MAX或TOP1類型的聚合操作，也可能匹配到名為“Max Robert”的人，對(duì)應(yīng)查詢意圖為“學(xué)者max所發(fā)表文章的卷數(shù)”，由于關(guān)鍵字是否匹配聚合查詢的不確定性，使得查詢意圖的確定更加困難。

統(tǒng)計(jì)查詢是常用的，但在當(dāng)前RDF關(guān)鍵字查詢研究中無法支持對(duì)其意圖的正確解析。在關(guān)系數(shù)據(jù)庫上已有算法對(duì)支持聚合關(guān)鍵字的查詢進(jìn)行了研究[4-5]。SQAK[4]通過限制num、max等特殊詞語一定匹配聚合操作，并使用保留關(guān)鍵字WITH確定查詢解釋，最終轉(zhuǎn)換為SQL的子集rSQL。PowerQ[5]則需要用戶交互信息進(jìn)行支持，得到注釋圖模式并轉(zhuǎn)換為SQL查詢。同時(shí)，RDF數(shù)據(jù)上的自然語言問句查詢也有研究對(duì)聚合查詢進(jìn)行處理，文獻(xiàn)[13]通過句子中的依存關(guān)系，確定用戶查詢意圖。TBSL[14]則通過問句的語義表征，確定所對(duì)應(yīng)的SPARQL模板，再將命名實(shí)體等加入插槽中。

由于數(shù)據(jù)結(jié)構(gòu)的不同以及語句依存關(guān)系的缺失，RDF上的聚合關(guān)鍵字查詢無法直接利用上述方法實(shí)現(xiàn)。此外，已有聚合關(guān)鍵詞的研究忽視了聚合操作關(guān)鍵字可能匹配到一般字面量的情況，而是將聚合關(guān)鍵字作為特殊的保留詞[4-5]，這會(huì)限制查詢的表達(dá)能力，錯(cuò)過可能的查詢解釋。為了使用戶可以利用簡(jiǎn)單的關(guān)鍵字進(jìn)行查詢，本文不對(duì)輸入內(nèi)容做限制，不強(qiáng)制用戶輸入指定的聚合關(guān)鍵字。對(duì)于可能指示聚合意圖的關(guān)鍵字，我們會(huì)在匹配階段計(jì)算其為聚合關(guān)鍵字的概率，從而確定可能的查詢解釋，再通過在模式圖上根據(jù)查詢解釋中的元素進(jìn)行擴(kuò)展，得到查詢意圖。

相比于關(guān)系數(shù)據(jù)，RDF數(shù)據(jù)還需要考慮聚合查詢對(duì)于查詢結(jié)構(gòu)圖連接方式的影響，例如對(duì)于查詢Q3= {AssistantProfessor, interest, sames as, fullprofessor1}，其對(duì)應(yīng)的查詢結(jié)構(gòu)圖如圖1所示，操作符“=”連接了兩個(gè)不同的節(jié)點(diǎn)，轉(zhuǎn)換后的SPARQL查詢語句如圖2所示，通過filter子句對(duì)查詢意圖進(jìn)行了準(zhǔn)確的描述。

圖1 查詢Q1對(duì)應(yīng)的查詢結(jié)構(gòu)圖

圖2 Q3對(duì)應(yīng)的SPARQL查詢

通過上述分析本文提出了包含聚合信息的關(guān)鍵字查詢轉(zhuǎn)換算法，將查詢統(tǒng)計(jì)信息的關(guān)鍵字轉(zhuǎn)換為帶聚合函數(shù)的SPARQL語句，實(shí)現(xiàn)對(duì)于MAX、AVG、MIN、COUNT、SUM及GROUP BY等操作的支持。本文主要貢獻(xiàn)如下：(1) 定義帶有聚合信息及查詢結(jié)構(gòu)圖的查詢意圖，給出具體的描述及含義；(2) 對(duì)聚合操作進(jìn)行分類，并構(gòu)造關(guān)鍵字與其匹配的字典，在關(guān)鍵字映射階段，同時(shí)獲得關(guān)鍵字元素及聚合信息；(3) 提出查詢意圖對(duì)應(yīng)分?jǐn)?shù)的計(jì)算方法，結(jié)合查詢結(jié)構(gòu)圖與聚合信息，獲得查詢意圖的匹配分?jǐn)?shù)；(4) 針對(duì)所提出的查詢意圖，設(shè)計(jì)模式圖上的查詢算法及SPARQL語句生成算法。

1 概述和定義

1.1 RDF數(shù)據(jù)

RDF數(shù)據(jù)的基本組成單元為三元組，也可表示為等價(jià)的屬性圖G=。其中，節(jié)點(diǎn)集合V可分為實(shí)體VE、類別VC或者是字面量VL；E中每一條邊e=連接左右兩個(gè)節(jié)點(diǎn)；L為所有可能的關(guān)系標(biāo)簽的集合。對(duì)于每一條邊，當(dāng)v1為一個(gè)實(shí)體或者空節(jié)點(diǎn)，v2為實(shí)體時(shí)，e表示的邊標(biāo)簽為L(zhǎng)R；當(dāng)v2為字面量時(shí)，e的邊標(biāo)簽則為L(zhǎng)A。圖3所示為L(zhǎng)UMB中描述學(xué)校、院系、學(xué)生信息的數(shù)據(jù)片段。

圖3 RDF數(shù)據(jù)圖示例

1.2 相關(guān)定義

為了支持將關(guān)鍵字查詢轉(zhuǎn)換為帶有聚合函數(shù)的標(biāo)準(zhǔn)查詢語句，實(shí)現(xiàn)查詢語義的擴(kuò)充，本文提出了特定的查詢意圖概念，并對(duì)相關(guān)定義描述如下。

定義1查詢意圖。關(guān)鍵字查詢可能對(duì)應(yīng)的查詢意圖定義為I=(G,A)，其中：G為查詢結(jié)構(gòu)圖，用于描述查詢內(nèi)容之間的語義關(guān)系；A則為聚合信息，當(dāng)查詢不含聚合意圖時(shí)，A為null。查詢圖與聚合信息的具體定義分別在定義2和定義3中給出。

定義2查詢圖。查詢結(jié)構(gòu)圖G=(V,E)是模式圖的一幅子圖，或者是由比較操作符連接的多個(gè)子圖，對(duì)于查詢中的每一個(gè)關(guān)鍵字，查詢圖中都包含與之對(duì)應(yīng)的關(guān)鍵元素。

定義3聚合信息。聚合信息的形式為A=(operation，ST，AT)，其中operation為查詢所屬聚合操作類型，ST為檢索對(duì)象，AT為聚合對(duì)象，限定ST與AT為查詢圖G所包含的元素，或?yàn)閚ull。

定義4查詢解釋。在關(guān)鍵字匹配階段獲得查詢解釋，根據(jù)查詢解釋進(jìn)行圖檢索可以得到查詢意圖。查詢解釋定義為E=(c,A)，其中c為一組關(guān)鍵元素，A則為對(duì)應(yīng)的聚合信息。

1.3 問題描述與算法結(jié)構(gòu)

包含聚合信息的關(guān)鍵字查詢轉(zhuǎn)換算法是將RDF數(shù)據(jù)上關(guān)鍵字查詢轉(zhuǎn)換為SPARQL查詢語句的研究，旨在理解用戶輸入關(guān)鍵字的查詢意圖，并支持轉(zhuǎn)換為復(fù)雜的聚合操作。對(duì)于給定的RDF數(shù)據(jù)圖G=(E,V,L)，我們定義用戶輸入的關(guān)鍵字查詢?yōu)橐唤M關(guān)鍵字的集合，即Q={k1,k2,…,kn}。每一個(gè)關(guān)鍵字ki，可能為指示聚合意圖的關(guān)鍵字或?yàn)橐话汴P(guān)鍵字，對(duì)于一般關(guān)鍵字則獲得RDF圖中與其匹配的元素集合Mi。確定查詢解釋后，在模式圖上根據(jù)所包含的關(guān)鍵元素進(jìn)行擴(kuò)展，并考慮聚合操作對(duì)于圖連接性的影響，獲得查詢結(jié)構(gòu)圖，再結(jié)合聚合信息得到對(duì)應(yīng)的查詢意圖。根據(jù)所提出的意圖分?jǐn)?shù)計(jì)算方法，選擇前k查詢意圖，將其轉(zhuǎn)換為對(duì)應(yīng)的SPARQL查詢語句。

所以，本文算法將關(guān)鍵字轉(zhuǎn)換為SPARQL查詢的主要步驟為：(1) 檢索關(guān)鍵字索引，與聚合操作詞典，獲得查詢解釋；(2) 提取RDF模式圖，并根據(jù)查詢解釋在圖上進(jìn)行檢索得到排序的候選查詢意圖；(3) 將查詢意圖一對(duì)一地轉(zhuǎn)換為SPARQL查詢語句。算法具體結(jié)構(gòu)如圖4所示，輸入為數(shù)據(jù)圖與關(guān)鍵字查詢，輸出則為符合查詢意圖的SPARQL語句。

圖4 RDF關(guān)鍵字查詢結(jié)構(gòu)圖

2 關(guān)鍵字查詢解釋

2.1 關(guān)鍵字映射

為了根據(jù)關(guān)鍵字獲得可能匹配的圖元素，我們?cè)O(shè)計(jì)了特定的圖元素存儲(chǔ)結(jié)構(gòu)，并構(gòu)建關(guān)鍵字-圖元素的映射表。我們認(rèn)為用戶查詢時(shí)會(huì)通過name、title等屬性所對(duì)應(yīng)的值來描述實(shí)體，所以我們考慮關(guān)鍵字匹配到屬性值節(jié)點(diǎn)，類別節(jié)點(diǎn)和關(guān)系標(biāo)簽三種情況，即?m∈Mi,m∈VL∪VC∪L。對(duì)于圖中的每一個(gè)元素，我們將其存儲(chǔ)在定義的數(shù)據(jù)結(jié)構(gòu)(class,property,value)中，其中,class為元素對(duì)應(yīng)的類別信息，property為邊標(biāo)簽，value則為屬性值。為了實(shí)現(xiàn)關(guān)鍵字的快速匹配，并且支持關(guān)鍵字與元素信息部分匹配的情況，我們構(gòu)建了關(guān)鍵字的倒排索引。

2.2 聚合操作與聚合信息

根據(jù)定義3可知，聚合信息的結(jié)構(gòu)為A=(operation,ST,AT)，ST所對(duì)應(yīng)變量出現(xiàn)在SELECT子句中，并可能被MAX、MIN等操作限制，同時(shí)也可能出現(xiàn)在group by子句中。當(dāng)AT不為空時(shí)，所對(duì)應(yīng)對(duì)象出現(xiàn)在order by、having或filter操作中。operation則為所屬的操作類型，聚合操作的分類及描述如表1所示。

表1 聚合操作分類

通過對(duì)SPARQL所支持聚合查詢的分析，我們對(duì)聚合操作進(jìn)行了分類，具體定義如表1所示。對(duì)于TOP1_G與TOPN_G類型的聚合操作，需要group by來實(shí)現(xiàn)查詢意圖，而其他聚合操作則不需要，這通過聚合信息是否為描述數(shù)值型字面量的關(guān)系標(biāo)簽來確定。例如“students with most classes”屬于TOP1_GF，而對(duì)于“students with highest score”則屬于TOP1_F，因?yàn)閟core匹配為關(guān)系標(biāo)簽，且其賓語為數(shù)值型對(duì)象。TOP1_G使用group by、order by、count與limit 1獲取排名最前的對(duì)象。>/<和EQU使用filter子句實(shí)現(xiàn)對(duì)于結(jié)果的過濾，并且該類型的聚合操作會(huì)影響查詢結(jié)構(gòu)圖的連接性，需要考慮操作函數(shù)連接子圖以獲得查詢結(jié)構(gòu)的情況。

TOPN使用group by、having、count對(duì)查詢對(duì)象分組，對(duì)聚合對(duì)象進(jìn)行計(jì)數(shù)。MAX、MIN、AVG、COUNT及SUM則為簡(jiǎn)單聚合查詢，查詢模塊中的AT為null，直接將聚合函數(shù)作用于ST。MAX與TOP1的區(qū)別在于MAX是直接對(duì)屬性值最查詢，而TOP1則查詢具有最值屬性的對(duì)象，注意：不是包含“max”就對(duì)應(yīng)MAX類別，也有可能是TOP1類型。

如果ki與聚合詞典中的key值相匹配，則為候選聚合關(guān)鍵字，如果不存在圖元素與ki相匹配，則ki為聚合關(guān)鍵字的概率P(op|ki)為1。當(dāng)存在圖元素與其匹配時(shí)，則計(jì)算ki匹配圖元素的距離倒數(shù)S：

(1)

(2)

綜上所述，不存在圖元素與ki匹配時(shí)P為1，否則ki與所匹配字面量編輯距離越小，P越??；ki對(duì)應(yīng)圖元素與其他圖元素的距離越小，P越小。當(dāng)P大于閾值時(shí)，認(rèn)為ki與聚合操作匹配。

2.3 查詢解釋確定

在查詢解釋確定階段，對(duì)于每一個(gè)ki，查看聚合詞典，如果ki是候選的聚合關(guān)鍵字則確定是否存在圖元素與其匹配，如果不存在，則確定ki為聚合關(guān)鍵字；如果存在，則得到匹配的元素Mi。然后計(jì)算Mi所有組合情況，得到元素集合C，對(duì)于每一個(gè)c屬于C，計(jì)算ci為聚合關(guān)鍵字的概率。

同時(shí)，由聚合操作的分類可知存在聚合操作由詞語的比較級(jí)或最高級(jí)指示，這些特殊的關(guān)鍵字除了指示聚合操作外，其原型形式還會(huì)與圖元素匹配提供信息。所以對(duì)于比較級(jí)/最高級(jí)形式的關(guān)鍵字，獲得對(duì)應(yīng)聚合類型后，將原型詞語加入到一般關(guān)鍵字集合中，用于圖元素匹配，查詢解釋獲取算法如算法1所示。

算法1查詢意圖解釋生成算法

輸入: 關(guān)鍵詞查詢Q={k1,k2,…,kn}。

輸出:一組查詢解釋。

1.forki in Qdo

2. Mi=map.get(ki)

//關(guān)鍵元素集合

3.ifkiin Operation map.keys()

//候選聚合關(guān)鍵字

4.ifMi==null

//確定為聚合關(guān)鍵字

5. aggType=Operation map.get(ki); aggPos=i

6.ifkiin CompSup_Map.Keys0then

7. archetype=CompSup_map.get(ki)

8. Mi=map.get(archetype)

9.elseMi.add(Operation map.get(ki))

10.elseMi=map.get(ki); aggPos=i

11.C=cartesianProduct(Mi)

12.ifaggType==null && aggPos!=null

//存在候選聚合

13.forc in C:

14.ifP(op|ci>threshold

15. ci=aggType=Operation_map.get(ki); aggPos=i

16. aggType: Operation_map.get(ki)

17. Element.add(getAgg(c, aggType, aggPos))

18.elseElement.add()

19.elseifaggType=nullthenreturn

20.elseElement=getAgg(C, aggType, aggPos)

21.returnElement

22.endif

其中，getAgg函數(shù)用于聚合信息的獲取，輸入關(guān)鍵元素組合，以及聚合操作出現(xiàn)的位置。對(duì)于每一組c屬于C，如果aggType為MAX/MIN，檢查聚合位置前是否為類別，如果存在類別，則將aggType對(duì)應(yīng)修改為TOP1類型；對(duì)于TOP1類型的，則根據(jù)聚合關(guān)鍵字之后的對(duì)象是否為數(shù)值型屬性，具體分為TOP1_G與TOP1。確定所屬聚合類別后，獲取查詢對(duì)象和聚合對(duì)象的信息：

(1) 聚合類型屬于{AVG, MAX, MIN, SUM}，聚合位置之后最接近的屬性標(biāo)簽為查詢對(duì)象，聚合對(duì)象為null。

(2) 當(dāng)聚合類型為COUNT，關(guān)鍵字元素中全部類別元素可能為查詢對(duì)象，分別對(duì)應(yīng)不同的聚合信息結(jié)果，聚合對(duì)象則為null。

(3) 聚合類型屬于{>, <, EQU}，查詢對(duì)象為聚合操作前的類別元素，聚合對(duì)象則描述為A-B的形式，其中A為對(duì)應(yīng)的聚合屬性元素或類別信息，B則為聚合操作后的字面量。例如，查詢Q1對(duì)應(yīng)的聚合信息為(EQU, AssistantProfessor, interest-fullprofessor1)。

(4) 當(dāng)聚合類型為TOP1時(shí)，如果聚合位置前不存在類別信息，則查詢對(duì)象ST為聚合位置后的類別節(jié)點(diǎn)，AT則為聚合位置對(duì)應(yīng)的屬性標(biāo)簽；否則查詢對(duì)象為聚合位置之前的類別元素，聚合對(duì)象為聚合位置之后的類別或?qū)傩詷?biāo)簽。

(5) 當(dāng)聚合類型為TOPN_G時(shí)，查詢對(duì)象ST為聚合位置之前的類別元素，聚合對(duì)象AT則為聚合位置后類別-聚合位置后字面量。

3 查詢意圖確定與轉(zhuǎn)換

3.1 模式圖提取

原始數(shù)據(jù)圖中通常含有大量的實(shí)體和關(guān)系，在查詢意圖確定時(shí)需要搜索的空間很大。對(duì)于本文中將關(guān)鍵字轉(zhuǎn)換為SPARQL查詢語句的任務(wù)，在圖檢索階段只需確定所匹配的關(guān)鍵元素之間的結(jié)構(gòu)關(guān)系，而無須遍歷完整的數(shù)據(jù)圖進(jìn)行精確的匹配。所以我們?cè)诎Y(jié)構(gòu)信息的模式圖上，實(shí)現(xiàn)對(duì)于查詢結(jié)構(gòu)的確定，進(jìn)而完成查詢轉(zhuǎn)換。

我們從數(shù)據(jù)圖中提取了包含類別實(shí)體和類別間關(guān)系的模式圖，同時(shí)本文在模式圖中考慮關(guān)系標(biāo)簽也為特殊的圖節(jié)點(diǎn)，在關(guān)鍵字匹配到數(shù)據(jù)圖中的關(guān)系標(biāo)簽時(shí)也能正確地得到對(duì)應(yīng)搜索意圖的關(guān)鍵元素查詢結(jié)構(gòu)。對(duì)于圖3中的RDF數(shù)據(jù)圖，對(duì)應(yīng)的模式圖如圖5所示。

圖5 示例模式圖

3.2 查詢意圖計(jì)算

在2.3節(jié)獲取查詢解釋后，利用查詢解釋中的元素在模式圖上進(jìn)行擴(kuò)展，并慮聚合操作對(duì)圖連接的影響，得到候選查詢意圖。查詢意圖獲取如算法2所示。

算法2查詢意圖獲取算法

輸入:意圖組件集合Element={},摘要圖Gs,最大距離max。

輸出:查詢意圖集合I={}。

1.forE in Elementdo

2.ifE.A.operation in {>, <, EQU}then

3. prop=E.A.info.split(-)[0]; value=E.A.Info.split(-)[1]

4.ifvalue not numberthen

5. pos=getpos(prop)

6. C1=cl, c2, …, cpos; C2=prop, cpos, …, cn

7. G1=Expand(C1, max); G2=Expand(C2, max)

8. G.E=G 1.E ∪G2.E

9. G:edge=Gl.edge ∪ G2.edgel∪E.A.operation("Literall","Literal2")

10.else

11. G1=Expand(Evalue, max); G.E=G1.E.add(value)

12. G.edge=G1.Edge.add(A.operation("Literal", value))

13.endif

14.elseG=Expand(E.C,max)endif

15.forg in Gdo

16.fornode in g.Edo

17.ifnode.property!=nullandnode.element!=nullthen

//字面量

18. g.E.add(node.element)

19. g.edge.add(node.property(node.classes,node.element))

20.endifendfor

21. I.G=g; I.A=E.A

22. Result.add(I)

23.endforendfor

24. Result.GetTopk()

25.returnResult

當(dāng)聚合類型屬于{>,<,EQU}，聚合操作會(huì)影響查詢結(jié)構(gòu)圖的連接性，將查詢分為兩個(gè)部分，分別進(jìn)行擴(kuò)展，并進(jìn)行連接。其中，Expand函數(shù)用于進(jìn)行摘要圖的擴(kuò)展，根據(jù)給定的關(guān)鍵元素集合以及最大查詢距離max，獲取包含全部元素的子圖。在圖的擴(kuò)展的過程中，采用反向搜索策略，由關(guān)鍵元素出發(fā)，按照模式圖中的結(jié)構(gòu)進(jìn)行擴(kuò)展，直到到達(dá)連接元素，獲得對(duì)應(yīng)查詢結(jié)構(gòu)圖。

3.3 意圖排序方法

由于本文定義的查詢意圖中包含了聚合信息，所以在對(duì)于意圖分?jǐn)?shù)進(jìn)行計(jì)算時(shí)，需要同時(shí)考慮查詢圖和聚合信息兩個(gè)部分。對(duì)于查詢意圖I=(G,A)，本文設(shè)計(jì)了新的度量策略來計(jì)算由關(guān)鍵字查詢獲得查詢意圖的對(duì)應(yīng)分?jǐn)?shù)，主要考慮以下三個(gè)指標(biāo)：

(1) 關(guān)鍵字匹配度。查詢圖中元素與所對(duì)應(yīng)關(guān)鍵字的匹配程度是衡量意圖是否準(zhǔn)確的重要指標(biāo)。同文獻(xiàn)[8]一樣，對(duì)于每一個(gè)關(guān)鍵元素，計(jì)算其與對(duì)應(yīng)關(guān)鍵字之間的編輯距離；對(duì)于非關(guān)鍵元素則認(rèn)為編輯距離為0，匹配度Sim(G)則為全部元素編輯距離之和的倒數(shù)。

(2) 查詢圖大小。與其他相關(guān)研究一樣，本文同樣認(rèn)為用戶查詢的是與給定元素鄰近的信息，所以越緊湊的查詢結(jié)構(gòu)圖，越可能符合用戶的查詢意圖。因此本文使用圖中節(jié)點(diǎn)數(shù)與邊數(shù)的總和來表示查詢結(jié)構(gòu)圖的大小SizeG。

(3) 聚合信息的置信度。聚合信息的匹配程度同樣是度量查詢意圖理解準(zhǔn)確性的重要指標(biāo)。對(duì)于聚合信息A=(operation,ST,AT)，當(dāng)A為null時(shí)，其對(duì)應(yīng)分?jǐn)?shù)為0；當(dāng)A屬于直接聚合和間接聚合兩類時(shí)，置信度的計(jì)算方法分別描述如式(3)、式(4)所示。

當(dāng)A為直接聚合時(shí)：

(3)

當(dāng)A為間接聚合時(shí)：

(4)

Path(AT→ST).length表示在查詢結(jié)構(gòu)圖中AT與ST所對(duì)應(yīng)元素之間路徑的長(zhǎng)度。根據(jù)上述三個(gè)方面影響，得到對(duì)于查詢意圖構(gòu)建代價(jià)的計(jì)算方法：

Score(I)=Score(G)+(1-α)Score(A)

(5)

式中：α為調(diào)和參數(shù)，一般取0.5；Score(G)為查詢結(jié)構(gòu)圖的分?jǐn)?shù)。

(6)

3.4 SPARQL查詢生成

獲得查詢意圖后，可以根據(jù)查詢結(jié)構(gòu)圖轉(zhuǎn)換得到與其對(duì)應(yīng)的查詢語句。對(duì)于每一個(gè)三元組，當(dāng)元素是類別class或“Literal”節(jié)點(diǎn)時(shí)，則將一個(gè)變量var與其綁定，并且在查詢語句中加入；如果元素是屬性邊，集合中加入三元組，其中，函數(shù)variable用來獲取綁定的變量；如果元素是連接兩個(gè)類別節(jié)點(diǎn)的關(guān)系邊，則加入三元組；如果邊標(biāo)簽為比較符號(hào)(>，<,=)，則加入filter語句對(duì)結(jié)果進(jìn)行過濾。

聚合信息同樣利用所包含的信息進(jìn)行轉(zhuǎn)化，對(duì)于TOP1類型的聚合操作，在WHERE子句之后使用group by修飾ST對(duì)應(yīng)變量，再加入order by desc/asc count(variable(AT))(只有TOP1_G類別需要使用count)，最后使用limit 1實(shí)現(xiàn)返回結(jié)果中排序第一的對(duì)象；對(duì)于TOPN類型的操作，則使用group by修飾ST對(duì)應(yīng)變量，再加入having(count(variable(AT)))對(duì)結(jié)果進(jìn)行篩選；而對(duì)于MAX/MIN等直接聚合的查詢，則通過在SELECT子語句中添加operation(ST)限制，類約束待返回的結(jié)果，表達(dá)對(duì)應(yīng)的查詢語義，例如SELECT MAX(?x)，可以返回?x位置所對(duì)應(yīng)的值最大的結(jié)果。

4 實(shí) 驗(yàn)

為了驗(yàn)證算法的正確性及有效性，本文使用Java語言和Jena框架來解析和處理RDF數(shù)據(jù)，并實(shí)現(xiàn)了上述算法(Power Keyword to SPARQL, PowerKTS)。

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

實(shí)驗(yàn)所用的環(huán)境為Windows 10操作系統(tǒng)，i5 CPU，8 GB內(nèi)存。實(shí)驗(yàn)數(shù)據(jù)為L(zhǎng)ehigh大學(xué)的開放基準(zhǔn)數(shù)據(jù)集LUBM和RDF形式的2005年DBLP數(shù)據(jù)，對(duì)于LUBM通過代碼生成了包含127萬條三元組的RDF數(shù)據(jù)，兩個(gè)數(shù)據(jù)集的具體信息表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息

本文給定10組關(guān)鍵字查詢進(jìn)行實(shí)驗(yàn)，所用具體查詢及對(duì)應(yīng)意圖如表3所示，L表示LUBM數(shù)據(jù)集上的查詢，而D則表示DBLP上的查詢，給定查詢關(guān)鍵字中包含一般查詢及聚合相關(guān)查詢。

表3 實(shí)驗(yàn)關(guān)鍵字查詢數(shù)據(jù)

4.2 查詢準(zhǔn)確性評(píng)估

對(duì)于查詢結(jié)果準(zhǔn)確性的評(píng)價(jià)，我們采用信息檢索領(lǐng)域常用的評(píng)價(jià)指標(biāo)MRR(Mean Reciprocal Rank)。

式中：n為正確答案在所返回結(jié)果中的排名。即當(dāng)排序中第一位為正確結(jié)果時(shí)MRR值最高，此時(shí)值為1；而當(dāng)結(jié)果中不包含正確意圖時(shí)，MRR值為0。

對(duì)于上述10組查詢，算法1中的閾值設(shè)置為1/3，則查詢結(jié)果對(duì)應(yīng)的MRR值如圖6所示，由實(shí)驗(yàn)結(jié)果可知PowerKTS可以正確實(shí)現(xiàn)對(duì)于查詢統(tǒng)計(jì)信息的關(guān)鍵字的處理，返回對(duì)應(yīng)的查詢意圖，而KAT則只是將聚合關(guān)鍵字與圖元素進(jìn)行匹配，無法正確解析查詢意圖。而對(duì)于一般查詢，PowerKTS也可以取得與KAT一樣的查詢準(zhǔn)確度。

圖6 查詢準(zhǔn)確性結(jié)果

4.3 索引空間分析

在倒排索引構(gòu)建時(shí)，將每一個(gè)圖元素看成是一個(gè)文檔，分別考慮關(guān)鍵字出現(xiàn)在類別節(jié)點(diǎn)、字面量節(jié)點(diǎn)以及邊標(biāo)簽中的情況，實(shí)現(xiàn)索引構(gòu)建。對(duì)于不同的數(shù)據(jù)集，獲得關(guān)鍵字索引文件的大小以及構(gòu)建時(shí)間如表4所示。

表4 關(guān)鍵字索引構(gòu)建效率

4.4 查詢效率

為了驗(yàn)證本文算法的查詢效率，對(duì)于給定的關(guān)鍵字查詢，實(shí)驗(yàn)記錄從輸入查詢到返回SPARQL查詢語句所需要的時(shí)間，并與KAT算法進(jìn)行比較。執(zhí)行時(shí)間結(jié)果如圖7所示。

圖7 查詢轉(zhuǎn)換時(shí)間結(jié)果

由于在轉(zhuǎn)換過程中需要對(duì)給定關(guān)鍵字查詢是否為聚合查詢進(jìn)行判斷，并獲取聚合信息，且模式圖的規(guī)模很少，兩種算法圖檢索所需時(shí)間都非常短，所以PowerKTS的執(zhí)行時(shí)間平均略高于KAT，但是兩者差距非常小，驗(yàn)證了算法的查詢效率。

5 結(jié) 語

本文針對(duì)RDF數(shù)據(jù)上的關(guān)鍵字檢索問題，在已有研究的基礎(chǔ)上，提出了一種將關(guān)鍵字轉(zhuǎn)換為SPARQL查詢的方法，并且支持聚合查詢的轉(zhuǎn)換。提出了包含聚合信息的查詢意圖，對(duì)聚合操作進(jìn)行分類，通過構(gòu)建聚合詞典以及關(guān)鍵字索引，實(shí)現(xiàn)對(duì)于查詢解釋的高效獲取，并且考慮候選聚合關(guān)鍵字可能對(duì)應(yīng)圖元素的情況，對(duì)查詢解釋包含聚合意圖的概率進(jìn)行計(jì)算。然后在模式圖上進(jìn)行圖擴(kuò)展，考慮聚合操作對(duì)于查詢結(jié)構(gòu)圖連接性的影響，獲取候選查詢意圖。本文還根據(jù)查詢意圖的組成信息，提出了對(duì)應(yīng)的評(píng)分策略，對(duì)候選意圖進(jìn)行排序。最后，利用查詢轉(zhuǎn)換算法，將查詢結(jié)構(gòu)轉(zhuǎn)換為結(jié)構(gòu)化查詢。實(shí)驗(yàn)驗(yàn)證本文算法可以將關(guān)鍵字轉(zhuǎn)換為符合查詢意圖的查詢語句，支持對(duì)于統(tǒng)計(jì)信息的查詢，并且具有較高的轉(zhuǎn)換效率。