劉思培, 蔡一凡, 曹玲玲, 侯海婷, 鮑家坤, 袁 鴦

(1. 北方信息控制研究院集團(tuán)有限公司 總體部, 南京 211111； 2. 吉林大學(xué) 軟件學(xué)院,長(zhǎng)春 130012)

0 引 言

知識(shí)圖譜首先由Google提出, 主要由模式層和數(shù)據(jù)層組成[1]。在知識(shí)圖譜出現(xiàn)之前, 搜索引擎根據(jù)用戶關(guān)鍵詞搜索的結(jié)果以網(wǎng)頁(yè)鏈接列表形式呈現(xiàn), 然后根據(jù)用戶在網(wǎng)頁(yè)中點(diǎn)擊自己想要的鏈接, 才會(huì)瀏覽到相關(guān)的具體內(nèi)容。知識(shí)圖譜改善了搜索引擎的搜索模式, 將關(guān)鍵詞的搜索結(jié)果以一定的組織結(jié)構(gòu)呈現(xiàn), 比如三元組結(jié)構(gòu)的圖模式[2]。知識(shí)圖譜除了可以優(yōu)化搜索引擎外, 還被廣泛用于知識(shí)問(wèn)答系統(tǒng)中[3], 以幫助系統(tǒng)理解人類(lèi)語(yǔ)言并作出推理, 從而提升用戶體驗(yàn)。已有的知識(shí)圖譜有WikiData[4], Yago[5]和Freebase[6]等。

目前, 知識(shí)圖譜中的數(shù)據(jù)通常采用W3C(World Wide Web Comsortium)標(biāo)準(zhǔn)的RDF(Resource Description Framework)或OWL(Web Ontology Language)語(yǔ)言格式, 而用于查詢RDF或OWL數(shù)據(jù)的語(yǔ)言標(biāo)準(zhǔn)主要有SPARQL(SparQL Protocol and RDF Query Language)和RDQL(A Query Language for RDF)兩種。SPARQL專(zhuān)門(mén)用于訪問(wèn)和操作RDF數(shù)據(jù), 是一種主流的查詢語(yǔ)言[7], 因此筆者使用SPARQL作為知識(shí)圖譜的查詢語(yǔ)言進(jìn)行查詢重寫(xiě)研究。當(dāng)信息表示為RDF或OWL后, 出于查詢和推理的需要, 將這些數(shù)據(jù)相關(guān)的部分以一定形式存儲(chǔ), 而SPARQL可以通過(guò)圖模式匹配的方式從這些數(shù)據(jù)中獲得指定的部分。

筆者研究的目的是利用本體重寫(xiě)查詢語(yǔ)句, 發(fā)現(xiàn)隱含關(guān)聯(lián)模式。目前重寫(xiě)技術(shù)的研究主要分為基于相似度的重寫(xiě)[8]和基于本體規(guī)則的重寫(xiě)[9]。由于基于本體規(guī)則的重寫(xiě)結(jié)果更加準(zhǔn)確且可解釋, 因此筆者采用基于本體規(guī)則的重寫(xiě)。本體規(guī)則主要有RDFS(Resource Description Framework)和OWL兩種, 都是用于描述RDF數(shù)據(jù)的, 而OWL相比RDFS的表達(dá)能力更豐富, 推理能力更強(qiáng), 所以筆者采用基于OWL本體規(guī)則的查詢語(yǔ)句重寫(xiě)。

1 SPARQL查詢基礎(chǔ)知識(shí)

1.1 知識(shí)圖譜查詢語(yǔ)言SPARQL

SPARQL是由RDF Data Access Working Group開(kāi)發(fā)的本體查詢語(yǔ)言, 語(yǔ)法結(jié)構(gòu)類(lèi)似于SQL, 查詢包含三元組模型和實(shí)例[10]。SPARQL的部分關(guān)鍵詞有： SELECT指定要查詢的變量, WHERE指定要查詢的圖模式。以下是一個(gè)SPARQL查詢語(yǔ)句的實(shí)例。

SELECT ?X WHERE

{?X rdf:type ub:GraduateStudent.

?X ub:takesCourse http://www.Department0.University0.edu/GraduateCourse0}

在RDF數(shù)據(jù)模型中, 主體為頂點(diǎn), 主體與客體之間的邊為它們之間的屬性, 屬性包括主體自身的屬性和主體與客體之間的關(guān)系。SPARQL查詢語(yǔ)言和RDF三元組一樣, 同樣可以被表示為圖模式[2]。所以在RDF數(shù)據(jù)中查詢, 可以看作是SPARQL根據(jù)RDF的圖模式進(jìn)行匹配, 找出所有滿足條件的結(jié)果。例子中的?X rdf:type ub:GraduateStudent語(yǔ)句就是根據(jù)RDF的三元組模式找出所有滿足rdf:type是ub:GraduateStudent的實(shí)體, 其中?X為主體, ub:GraduateStudent為客體, rdf:type為這二者之間的屬性。

1.2 SPARQL與Prolog的轉(zhuǎn)換

在生成查詢重寫(xiě)語(yǔ)句前, 需要先將SPARQL查詢語(yǔ)句轉(zhuǎn)換為對(duì)應(yīng)的Prolog語(yǔ)句。Prolog是一種邏輯編程語(yǔ)言, 語(yǔ)法風(fēng)格與Horn邏輯子句[11]相似, 本質(zhì)上是對(duì)事實(shí)和規(guī)則的描述性語(yǔ)言。由于重寫(xiě)機(jī)制主要采用了歸結(jié)消解方法, 而Prolog就是基于歸結(jié)原理的一種邏輯程序語(yǔ)言, 因此將SPARQL語(yǔ)言轉(zhuǎn)換為Prolog語(yǔ)言, 方便用于查詢語(yǔ)句重寫(xiě)的實(shí)現(xiàn)。歸結(jié)會(huì)將原有查詢語(yǔ)言中不必要和多余的條件消解, 從而可得到更多的推理結(jié)果, 同時(shí)還可以提高查詢效率。最后將得到的Prolog語(yǔ)言的結(jié)果再轉(zhuǎn)換為SPARQL, 即得到了想要的重寫(xiě)后的SPARQL查詢語(yǔ)句。例如, 1.1節(jié)中的SPARQL查詢可以轉(zhuǎn)換為如下的Prolog語(yǔ)句：

?-GraduateStudent(X),takesCourse(X,http://www.Department0.University0.edu/GraduateCourse0).

2 查詢重寫(xiě)機(jī)制與方法

2.1 查詢重寫(xiě)機(jī)制

原本知識(shí)圖譜的知識(shí)庫(kù)包括事實(shí)集和規(guī)則集, 下面對(duì)規(guī)則集做出以下幾點(diǎn)限制： 1) 數(shù)據(jù)之間的關(guān)系只要求隱式的對(duì)稱(chēng), 比如研究生是學(xué)生, 但學(xué)生不一定是研究生, 也可以是本科生； 2) 在歸結(jié)中要替換的子句僅限于簡(jiǎn)單的事實(shí), 比如替換1.2節(jié)Prolog語(yǔ)句中的GraduateStudent(X), 而不替換takesCourse(X,teacherOf(X))中的teacherOf(X), 這是為了避免程序出現(xiàn)死循環(huán), 導(dǎo)致無(wú)法得出結(jié)果； 3) 歸結(jié)過(guò)程是子句單調(diào)減少的, 也就是說(shuō)重寫(xiě)的過(guò)程是有終止的, 當(dāng)所有滿足條件的子句都匹配完后, 即得到了重寫(xiě)后的結(jié)果。

圖1所示的推理模板中, 例如A(x)表示一個(gè)x是A的事實(shí),P(x,y)表示x和y存在某種關(guān)系,f(x)表示與x有關(guān)的實(shí)體。尋找可行的匹配得出新的子句, 并返回所有新子句的集合。如果無(wú)法在任一模板中得到匹配, 則返回空集。

圖1 推理模板Fig.1 Reasoning template

2.2 查詢語(yǔ)句重寫(xiě)方法

其輸入為一個(gè)合取查詢Q和一個(gè)本體TBoxT, 輸出為根據(jù)Q和T重寫(xiě)得出的若干條查詢。算法首先將Q和T轉(zhuǎn)換為一系列子句, 然后用將子句兩兩歸結(jié)得出新的子句, 算法如下。

輸入： 合取查詢Q, TBox本體T

R=Ξ(T)∪{Q};

repeat

for all clausesC1,C2 inRdo

R=R∪ resolve(C1,C2);

end

until無(wú)法歸結(jié)出新的子句

return{C|C∈unfold(ff(R)),andC的前件與Q相同}；

算法分為3步： 1) 子句化(clausification); 2) 飽和化(saturation); 3) 優(yōu)化。

第1步, 將Q和T轉(zhuǎn)換為一系列子句的集合Ξ(T)∪{Q}。Ξ(T)表示由T得到的子句的集合。TBox公理與邏輯子句的轉(zhuǎn)換如表1所示。

表1 公理T與子句集Ξ(T)的轉(zhuǎn)換

第2步, 算法反復(fù)對(duì)子句集中的子句進(jìn)行兩兩歸結(jié), 以期得出新的子句。歸結(jié)方法以兩個(gè)子句C1、C2為輸入, 通過(guò)在表1所示的推理模板中尋找可行的匹配得出新的子句, 并返回所有新子句的集合, 從而得到未優(yōu)化的重寫(xiě)語(yǔ)句。

當(dāng)所有子句都?xì)w結(jié)完成后, 對(duì)新的子句集進(jìn)行優(yōu)化。先將子句集中所有包含函數(shù)項(xiàng)的子句刪除, 然后將剩余所有不包含函數(shù)項(xiàng)的子句ff(Q,T)(Q為查詢語(yǔ)句,T為T(mén)BOX本體)在集合U上進(jìn)行擴(kuò)展, 其中子句集U中的子句包含以下形式： 1)A(x)←B(x); 2)A(x)←R(x,y); 3)A(x)←R(y,x); 4)R(x,y)←S(x,y); 5)R(x,y)←S(y,x)。例如：ff(Q,T)=P(x)←A(x),U中有A(x)←B(x), 設(shè)子句集R={ff(Q,T)}, 則R在U上擴(kuò)展后產(chǎn)生了新的子句P(x)←B(x), 擴(kuò)展后得到新的結(jié)果R∪{P(x)←B(x)}。最后, 將所有與查詢語(yǔ)句Q中的子句不匹配的子句刪除, 得到最終優(yōu)化后的重寫(xiě)語(yǔ)句結(jié)果。

2.3 查詢語(yǔ)句重寫(xiě)舉例

由于筆者是針對(duì)OWL規(guī)則集的推理, 即只輸入Ontology定義, 與本體實(shí)例數(shù)據(jù)無(wú)關(guān), 因此, 它只能處理不包含實(shí)例的查詢語(yǔ)句(類(lèi)似〈http://www.University0.edu〉的語(yǔ)句)。將LUBM提供的14條測(cè)試查詢語(yǔ)句[12]用SPARQL語(yǔ)句中不包含實(shí)例的第9條語(yǔ)句進(jìn)行重寫(xiě)。

先將SPARQL語(yǔ)句轉(zhuǎn)換為Prolog形式, 然后通過(guò)Requiem重寫(xiě), 第 9條語(yǔ)句只生成了一條新語(yǔ)句, 再將重寫(xiě)后的Prolog語(yǔ)句轉(zhuǎn)換回SPARQL語(yǔ)句。

原始的SPARQL語(yǔ)句：

PREFIX rdf:〈http:∥www.w3.org/1999/02/22-rdf-syntax-ns#〉

PREFIX ub:〈http:∥swat.cse.lehigh.edu/onto/univ-bench.owl#〉

SELECT?X,?Y,?Z

WHERE

{?X rdf:type ub:Student.

?Y rdf:type ub:Faculty.

?Z rdf:type ub:Course.

?X ub:advisor?Y.

?Y ub:teacherOf?Z.

?X ub:takesCouse?Z}.

在University0_0.owl數(shù)據(jù)集上的查詢結(jié)果：

重寫(xiě)后的SPARQL語(yǔ)句：

PREFIX rdf:〈http:∥www.w3.org/1999/02/22-rdf-syntax-ns#〉

PREFIX ub:〈http:∥swat.cse.lehigh.edu/onto/univ-bench.owl#〉

SELECT?X,?Y,?Z

WHERE

{?X ub:advisor?Y.

?X ub:takesCouse?Z.

?Y ub:teacherOf?Z.}

重寫(xiě)后的查詢結(jié)果為：

可以看到比原來(lái)多出了8條結(jié)果。原來(lái)的查詢語(yǔ)句翻譯為： 要找這樣的X,Y,Z, 學(xué)生X聽(tīng)老師Y教的課程Z。在數(shù)據(jù)集中, 只有UndergraduateStudent的type是學(xué)生, 而GraduateStudent的type是people, 其實(shí)際也是學(xué)生, 有屬性takesCourse, 所以重寫(xiě)后的語(yǔ)句簡(jiǎn)化了, 刪除了X,Y,Z的類(lèi)型約束, 輸出了更多結(jié)果。

這是由于查詢重寫(xiě)會(huì)根據(jù)本體定義對(duì)原本的查詢語(yǔ)句進(jìn)行優(yōu)化和擴(kuò)展, 會(huì)刪除其中冗余的限定條件, 因此重寫(xiě)后的語(yǔ)句復(fù)雜度總是低于原有的查詢語(yǔ)句, 從而在能獲得更多查詢結(jié)果的同時(shí)提高了查詢效率。

3 測(cè) 試

3.1 測(cè)試樣例

利用LUBM提供的數(shù)據(jù)生成器[12], 根據(jù)Ontology生成大量關(guān)于大學(xué)語(yǔ)義的數(shù)據(jù)。為便于隨后的測(cè)試, 分別生成了1、2、5、10所大學(xué)的數(shù)據(jù)。生成的數(shù)據(jù)是OWL格式, 1所大學(xué)對(duì)應(yīng)的OWL文件大約有10～20個(gè), 以1所大學(xué)為一個(gè)集合, 批量處理每所大學(xué)的數(shù)據(jù)。表2列出了各組數(shù)據(jù)的大小。

表2 大學(xué)數(shù)據(jù)集大小比較

筆者首先測(cè)試了1所大學(xué)的數(shù)據(jù), 將原語(yǔ)句和重寫(xiě)后的查詢語(yǔ)句得出的查詢結(jié)果作出了對(duì)比。例如, 對(duì)語(yǔ)句Query6[12]進(jìn)行重寫(xiě), 比較原始語(yǔ)句和重寫(xiě)后的結(jié)果。

原語(yǔ)句直接使用SPARQL語(yǔ)句查詢, 得到的結(jié)果為5 916, 即原語(yǔ)句查詢University0這所大學(xué)有5 916個(gè)學(xué)生。

下面對(duì)Query6查詢語(yǔ)句重寫(xiě), 重寫(xiě)后生成的Prolog語(yǔ)句包括：

?-Person(X),Course(Y),takesCourse(X,Y) .

?-ResearchAssistant(X),Course(Y),takesCourse(X,Y) .

?-TeachingAssistant(X),Course(Y),takesCourse(X,Y) .

?-Person(X),GraduateCourse(Y),takesCourse(X,Y).

?-ResearchAssistant(X),GraduateCourse(Y),takesCourse(X,Y).

?-TeachingAssistant(X),GraduateCourse(Y),takesCourse(X,Y).

?-GraduateStudent(X).

?-Student(X).

?-UnderGraduateStudent(X).

分別得到參加Course的Person有21 489個(gè), ResearchAssistant有1 099個(gè), TeachingAssistant有827個(gè), 參加GraduateCourse的Person有3 738個(gè), ResearchAssistant有1 099個(gè), TeachingAssistant有827個(gè), GraduateStudent有1 874個(gè), UndergraduateStudent有5 916個(gè), Student有5 916個(gè)。

綜合分析以上數(shù)據(jù), ResearchAssistant,TeachingAssistant都屬于Person, 參加Course的Person都可以稱(chēng)為Student, 而GraduateCourse屬于Course, GraduateStudent和UnderGraduateStudent都屬于Student, 且Student屬于Person, 因此Query6的重寫(xiě)語(yǔ)句的查詢結(jié)果為21 489個(gè)學(xué)生。

通過(guò)以上對(duì)比發(fā)現(xiàn), 1所大學(xué)對(duì)Query6語(yǔ)句的查詢, 原語(yǔ)句的查詢結(jié)果為5 916個(gè), 重寫(xiě)語(yǔ)句的查詢結(jié)果為21 489個(gè), 比原來(lái)多了15 573個(gè)結(jié)果, 挖掘出了更多的語(yǔ)義信息, 達(dá)到了預(yù)期。

3.2 查詢結(jié)果與比較

表3為原語(yǔ)句和重寫(xiě)語(yǔ)句查詢結(jié)果對(duì)比。從表3可以看出, 語(yǔ)句Query2和Query14沒(méi)有得出更多查詢結(jié)果, 這是由于Query2語(yǔ)句在去除了冗余條件的情況下, 限定條件依然很多, Query14語(yǔ)句請(qǐng)求查找UndergraduateStudent的實(shí)體, 但UndergraduateStudent這個(gè)條件已經(jīng)不包含子類(lèi)了, 所以這兩條語(yǔ)句都無(wú)法挖掘出更多信息, 原語(yǔ)句查詢已經(jīng)足夠。而其他語(yǔ)句都挖掘出了比原語(yǔ)句更多的信息, 重寫(xiě)Query6的查詢結(jié)果大約是原語(yǔ)句的4倍, Query9大約是原語(yǔ)句的2倍, 總體看重寫(xiě)后比原語(yǔ)句得到更多的語(yǔ)義信息。表4為原語(yǔ)句和重寫(xiě)語(yǔ)句的查詢時(shí)間對(duì)比。

表3 原語(yǔ)句和重寫(xiě)語(yǔ)句查詢結(jié)果對(duì)比Tab.3 The comparison of results between original and rewritten queries (ms)

表4為原語(yǔ)句和重寫(xiě)語(yǔ)句查詢時(shí)間對(duì)比結(jié)果。由表4可以看出, 除了語(yǔ)句Query9, 重寫(xiě)后的語(yǔ)句查詢時(shí)間總體上比原語(yǔ)句的查詢時(shí)間多, 但效率上沒(méi)有太明顯的差距, 因此筆者的重寫(xiě)實(shí)現(xiàn)是可行的。

表4 原語(yǔ)句和重寫(xiě)語(yǔ)句查詢時(shí)間對(duì)比Tab.4 The comparison of time consuming between original and rewitting queries (ms)

4 結(jié) 語(yǔ)

筆者實(shí)現(xiàn)了查詢結(jié)果與用戶查詢請(qǐng)求之間的語(yǔ)義級(jí)匹配, 滿足用戶的查詢需求。筆者的解決方案是在本體規(guī)則的基礎(chǔ)上, 利用Prolog邏輯程序?qū)PARQL查詢語(yǔ)句進(jìn)行重寫(xiě)。筆者提出的基于知識(shí)圖譜的重寫(xiě)查詢語(yǔ)句, 基于原有的查詢語(yǔ)句語(yǔ)義, 保證在不破壞原有語(yǔ)義的基礎(chǔ)上, 能挖掘出更多隱含的語(yǔ)義信息。在執(zhí)行效率方面, 重寫(xiě)后的查詢時(shí)間消耗代價(jià)是可接受的。從實(shí)測(cè)結(jié)果中可知： 對(duì)不明確的查詢語(yǔ)句, 重寫(xiě)后可以得出更多的查詢結(jié)果, 對(duì)明確的查詢語(yǔ)句不能得出更多結(jié)果, 但查詢效率更高。