大規(guī)模知識(shí)圖譜的多查詢優(yōu)化問題研究

郭欣彤, 高 宏

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

0 引 言

知識(shí)圖譜將客觀世界中的海量信息以結(jié)構(gòu)化的形式描述，提供了強(qiáng)大的組織、管理和理解互聯(lián)網(wǎng)海量信息的能力。知識(shí)圖譜不僅給搜索引擎帶來了新的活力，同時(shí)也在智能決策中顯示出強(qiáng)大威力，是人工智能的重要基石。隨著知識(shí)圖譜被廣泛應(yīng)用于各個(gè)領(lǐng)域，在真實(shí)SPARQL查詢歷史中發(fā)現(xiàn)很多相似查詢。如果一定時(shí)間段內(nèi)的相似查詢可以一起處理，就能減少冗余計(jì)算，從而大大降低查詢響應(yīng)時(shí)間，提高吞吐量。因此，本文研究在知識(shí)圖譜上的多查詢優(yōu)化問題。

關(guān)系數(shù)據(jù)庫上的多查詢優(yōu)化問題是NP-hard，由于SQL與SPARQL二者之間有等價(jià)關(guān)系，因此RDF/SPARQL上的多查詢優(yōu)化問題也是NP-hard。MQO是關(guān)系數(shù)據(jù)和半結(jié)構(gòu)化數(shù)據(jù)上的一個(gè)經(jīng)典問題，有很多方法取得了很好的效果。一個(gè)很直觀的想法是把已有方法推廣到RDF數(shù)據(jù)上，但現(xiàn)有的方法并不能無縫的集成在已有的RDF查詢引擎上，主要原因有：

(1)關(guān)系數(shù)據(jù)上的SQL查詢通常可以轉(zhuǎn)換成一棵抽象語法樹，在樹上檢測同構(gòu)的子樹較為簡單，而SPARQL查詢通常表示成圖結(jié)構(gòu)，因此公共子結(jié)構(gòu)檢測更難；

(2)RDF的物理存儲(chǔ)和索引并沒有固定的模式，每個(gè)系統(tǒng)選用的方法都不同，例如 RDF-3X中使用全索引結(jié)構(gòu)[1]，Jena使用屬性表[2]，還有最近很多系統(tǒng)采用的垂直劃分方法，這些多樣的存儲(chǔ)模式和索引選擇，使得代價(jià)估算不準(zhǔn)確，某些情形下優(yōu)化后的響應(yīng)時(shí)間并不總是小于未優(yōu)化的；

(3)真實(shí)世界中的 SPARQL查詢遠(yuǎn)比關(guān)系數(shù)據(jù)庫上的SQL語句復(fù)雜，連接更多，這可以通過比較 TPC 測試集和一些RDF測試集得出結(jié)論。隨著連接個(gè)數(shù)的增加，代價(jià)估計(jì)的準(zhǔn)確性大幅下降。在查詢處理時(shí)，代價(jià)估計(jì)是非常重要的，錯(cuò)誤的代價(jià)估計(jì)有時(shí)反而會(huì)使查詢效率下降[3]。

從圖的角度也有很多針對多查詢優(yōu)化的解法，大多數(shù)都需要找出最大公共子圖(Maximum Common Subgraph, MCS)。由于MCS檢索是NP-complete 問題，很多查詢同時(shí)到達(dá)時(shí)，時(shí)間開銷難以承受。

除了多查詢優(yōu)化問題本身的復(fù)雜度，隨著知識(shí)圖譜數(shù)據(jù)集規(guī)模的不斷增大，RDF查詢引擎的可擴(kuò)展性變得尤為重要，需要一個(gè)分布式的RDF查詢引擎提高查詢處理時(shí)的并行性，從而減少響應(yīng)時(shí)間，此時(shí)數(shù)據(jù)劃分變得尤為重要。眾所周知，圖劃分問題是NP-complete的，現(xiàn)有系統(tǒng)大多都基于啟發(fā)式方法，一些系統(tǒng)使用簡單的哈希方法，但這種方法導(dǎo)致很少查詢能夠無通信的并行計(jì)算；一些系統(tǒng)使用了較為復(fù)雜的劃分算法，這類方法局限于很高的預(yù)處理代價(jià)和較高的復(fù)制系數(shù)。

為了解決現(xiàn)有方法不足，本文提出了一個(gè)新的分布式，基于內(nèi)存的RDF查詢引擎Leon，能夠解決多查詢優(yōu)化問題。Leon使用一個(gè)基于特征集合的平衡劃分算法，具有時(shí)間復(fù)雜度低，有利于星型查詢等特點(diǎn)。對之后的多查詢優(yōu)化也有很多好處，本文提出了一個(gè)新穎的多查詢優(yōu)化算法。首先，利用特征集合快速過濾沒有優(yōu)化前景的查詢；其次，利用 triplet 進(jìn)一步過濾，只保留十分相似的查詢；最后，在剩下來的查詢中精確、高效地查找公共子結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，在多查詢負(fù)載下，時(shí)間是無優(yōu)化時(shí)的1/10。

1 算法框架

1.1 特征集合

RDF圖中的主體都有一系列謂詞，同一實(shí)體類型的主體擁有的謂詞也十分相似。真實(shí)世界中的RDF數(shù)據(jù)集即使包含的三元組個(gè)數(shù)很多，謂詞集合也很少。例 如，對于一個(gè)擁有超過8億三元組的UniProt數(shù)據(jù)集來說，謂詞集合只有 615個(gè)；DBLP數(shù)據(jù)集包含176.63M條元組，謂詞集合只有95個(gè)。許多其它數(shù)據(jù)集也觀察到這種現(xiàn)象，例如：YAGO、LibraryThings、Barton等。Neumann和Moerkott由此提出了特征集合的概念[4]。

給定一個(gè)RDF數(shù)據(jù)圖G(V,E,L)，s是一個(gè)主體，s的特征集合S(s)定義為式(1)：

S(s)={p|?o:∈G}

(1)

圖G中所有特征集合可以表示為式(2)：

S(G)={S(s)|?p,o:∈G}

(2)

基于以上兩個(gè)定義，定義特征集合塊，特征集合為Si的主體對應(yīng)的所有三元組，形成了一個(gè)特征集合塊Bi，式(3)：

Bi={|S(s)=Si}

(3)

圖中所有特征集合塊可以表示為式(4)：

B(G)={Bi|Si∈S(G)}

(4)

顯然，B(G)是RDF數(shù)據(jù)圖以主體為中心的一個(gè)劃分，特征集合Si和特征集合塊Bi之間是一一對應(yīng)的。

將RDF圖中的三元組根據(jù)特征集合編碼，使用基于特征集合的平衡劃分算法將特征集合塊發(fā)送到從節(jié)點(diǎn)中。為了使各個(gè)節(jié)點(diǎn)上的工作量較為平均，保持每臺(tái)機(jī)器上的三元組個(gè)數(shù)接近。假設(shè)劃分計(jì)劃表示為P={P1,P2,…,Pk}。將|E|條三元組平均分配到k個(gè)節(jié)點(diǎn)上，那么每臺(tái)機(jī)器上的數(shù)量應(yīng)為|E|/k個(gè)。根據(jù)每個(gè)特征集合塊內(nèi)三元組數(shù)量從大到小排序，將排序后的特征集合塊貪心地放入剩余容量最多的節(jié)點(diǎn)。

1.2 公共子結(jié)構(gòu)檢測

多查詢優(yōu)化算法的核心是公共子結(jié)構(gòu)檢測，主要分為3個(gè)步驟:

(1)將SPARQL查詢根據(jù)特征集合進(jìn)行分解，根據(jù)包含的特征集合，將查詢劃分成幾個(gè)粗粒度的聚類；

(2)使用triplet進(jìn)一步精細(xì)聚類，只保留非常相似的查詢進(jìn)行優(yōu)化；

(3)找出查詢間準(zhǔn)確的公共子結(jié)構(gòu)。

到達(dá)的SPARQL查詢會(huì)被分解成一系列不相交的星型的子查詢，稱為fork。fork中的三元組模式有相同的主體連接變量，根據(jù)謂詞每個(gè)fork都能映射到0個(gè)或多個(gè)特征集合，相應(yīng)的特征集合塊一定含有這個(gè)fork的結(jié)果。

要篩選出哪些查詢可以一起優(yōu)化，因此使用k-means聚類算法粗粒度地對查詢集合聚類。k-means聚類算法使用基于特征集合的Jaccard系數(shù)作為度量，使用特征集合對查詢粗聚類是高效且準(zhǔn)確的，特征集合中不僅包含了查詢的謂詞信息，也反映了結(jié)構(gòu)信息。如果兩個(gè)查詢包含的特征集合都相同，那么其有很大可能結(jié)構(gòu)也相似，相比已有方法只使用謂詞進(jìn)行聚類更加準(zhǔn)確。

粗聚類后，在每個(gè)簇上進(jìn)一步篩選可以共同優(yōu)化的查詢。將每個(gè)查詢q分解成一系列triplet，所謂triplet就是相連的兩條邊組成的三元組。表1就是圖1的triplet分解結(jié)果。

圖1 一組查詢

表1 Triplets

如果兩個(gè)查詢有很多公共的 triplet，那么其很可能有很大的公共子結(jié)構(gòu)，計(jì)算兩兩查詢的親密度，式(5)：

(5)

親密度越高，說明兩個(gè)查詢公共子結(jié)構(gòu)越大。只有當(dāng)兩個(gè)查詢之間的親密度高于一個(gè)閾值β時(shí)，才會(huì)被考慮一起優(yōu)化。將不相似查詢過濾出去后，在剩下的查詢上運(yùn)行最大公共子結(jié)構(gòu)發(fā)現(xiàn)算法，找到的公共子結(jié)構(gòu)如圖2所示。

圖2 查詢的公共子結(jié)構(gòu)

1.3 查詢重寫

給定一組查詢Q={q1,q2,…,qn}，假設(shè)qc是其公共子結(jié)構(gòu)，將每個(gè)查詢改寫如式(6)和式(7)：

(6)

(7)

為QOPT生成查詢計(jì)劃，進(jìn)行查詢處理。

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

使用兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。LUBM是一個(gè)廣為人知的 RDF測試基準(zhǔn)，其優(yōu)點(diǎn)是數(shù)據(jù)集中的度量值隨著數(shù)據(jù)集大小線性增長，結(jié)構(gòu)簡單的數(shù)據(jù)集，只含有11個(gè)特征集合，本文使用 LUBM 數(shù)據(jù)生成器生成LUBM1k 數(shù)據(jù)集；WatDiv也是一個(gè)人工數(shù)據(jù)集，其可以測試不同查詢負(fù)載情況下RDF 系統(tǒng)的性能，本文生成了一個(gè)超過10億條三元組的WatDiv1B數(shù)據(jù)集。將Leon與目前最先進(jìn)的AdPart[5]系統(tǒng)進(jìn)行對比，AdPart使用主體上哈希的劃分算法，并能根據(jù)負(fù)載進(jìn)行數(shù)據(jù)復(fù)制。

為LUBM1k和WatDiv1B數(shù)據(jù)集分別生成包含10k個(gè)查詢的查詢負(fù)載，比較4個(gè)算法AdPart-random、AdPart-seq、Leon和Leon-non(無優(yōu)化)，其中“AdPart-seq”表明相似的查詢同時(shí)到達(dá)，“AdPart-random”代表相似查詢隨機(jī)到達(dá)，做這樣的區(qū)分是因?yàn)锳dPart是通過一段時(shí)間內(nèi)重復(fù)出現(xiàn)的查詢進(jìn)行復(fù)制的。

圖3給出了LUBM1k負(fù)載上的查詢表現(xiàn)，橫軸代表查詢個(gè)數(shù)，縱軸代表累積處理時(shí)間。對于AdPart-random，由于相似查詢隨機(jī)到達(dá)，并沒有檢測到很多公共子結(jié)構(gòu)，因此累積處理時(shí)間迅速增長；而AdPart-seq識(shí)別到了連續(xù)到來的相似查詢，并將公共子查詢的結(jié)果在集群中復(fù)制，因此時(shí)間遠(yuǎn)遠(yuǎn)小于AdPart-random。相比之下，Leon將所有查詢看成一個(gè)整體，對不同的查詢聚簇分別優(yōu)化，運(yùn)行時(shí)間比AdPart-seq減少了大約40%，這是因?yàn)樽畲蟪潭鹊墓蚕砹斯膊糠值挠?jì)算，而且選擇了正確的公共子結(jié)構(gòu)進(jìn)行重寫；Leon-non比AdPart-random花費(fèi)時(shí)間少大約32%，這是因?yàn)榛谔卣骷系膭澐址椒p少了查詢處理時(shí)間。Leon的運(yùn)行時(shí)間大約是Leon-non的1/10，說明引入多查詢優(yōu)化可以大大提高查詢響應(yīng)時(shí)間。

圖3 LUBM負(fù)載表現(xiàn)

圖4表明在WatDiv負(fù)載上各個(gè)系統(tǒng)的查詢表現(xiàn)也有相同的變化趨勢。由于WatDiv的查詢模板更復(fù)雜，因此特征集合的剪枝能力發(fā)揮了巨大的作用。此外，基于特征集合的基數(shù)估計(jì)更準(zhǔn)確，使得生成的查詢計(jì)劃更優(yōu)。Leon比AdPart-seq節(jié)約了 25% 的時(shí)間，Leon比Leon-non節(jié)約了91%的時(shí)間。

圖4 WatDiv1B負(fù)載表現(xiàn)

3 結(jié)束語

本文探討大規(guī)模知識(shí)圖譜上的多查詢優(yōu)化問題，提出了一個(gè)基于內(nèi)存的，分布式RDF處理引擎Leon。Leon基于特征集合對RDF數(shù)據(jù)進(jìn)行劃分，大大減少了連接個(gè)數(shù)，從而減少了計(jì)算時(shí)間。同時(shí)本文也提出了一個(gè)高效的提取公共子結(jié)構(gòu)的算法，利用特征集合和triplet兩次篩選，逐漸縮小搜索空間。實(shí)驗(yàn)證明,Leon 在單查詢性能上與目前最好的RDF查詢引擎相當(dāng)；在多查詢優(yōu)化上，響應(yīng)時(shí)間是無優(yōu)化的版本的1/10。