基于結(jié)構(gòu)分解的分布式RDF圖模式匹配優(yōu)化算法

孫云浩 邢維康 李冠宇 韓 冰 李逢雨

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

如今，由于知識(shí)圖譜的興起，越來越多的數(shù)據(jù)集采用資源描述框架(Resource Description Framework，RDF)的格式發(fā)布和維護(hù)數(shù)據(jù)，它將一個(gè)數(shù)據(jù)集表示為一組三元組，這些三元組構(gòu)成一個(gè)有向標(biāo)簽圖。例如Google的知識(shí)圖[1]和一些公共知識(shí)庫DBpedia[2]、Bio2RDF[3]等。Google和Bing等一些商業(yè)網(wǎng)站也通過SPARQL向這些數(shù)據(jù)集提供在線查詢服務(wù)。

早期的RDF存儲(chǔ)，如RDF-3X[4]、SW-Store[5]、HexaStore[6]，通常使用集中式設(shè)計(jì)。隨著RDF數(shù)據(jù)集規(guī)模和查詢規(guī)模增加，保證查詢的低延遲性成為了一項(xiàng)挑戰(zhàn)。作為回應(yīng)，很多研究致力于開發(fā)可擴(kuò)展和高性能的系統(tǒng)來索引RDF數(shù)據(jù)和處理SPARQL查詢。如StarMR[7]、TriAD[8]、Trinity.RDF[9]、Wukong[10]和Stylus[11]等通過使用分布式存儲(chǔ)，來應(yīng)對不斷增長的數(shù)據(jù)量。

雖然RDF數(shù)據(jù)集能夠以三元組的形式作為元素存儲(chǔ)在關(guān)系表中(即三元組存儲(chǔ))[4,8,12-13]，但RDF數(shù)據(jù)集本質(zhì)上是一個(gè)帶標(biāo)簽的有向多邊圖，所以也能夠以原生圖形(即圖形存儲(chǔ))的形式進(jìn)行存儲(chǔ)管理[9,11,14,25]。文獻(xiàn)[10-11]也表明，使用三元組存儲(chǔ)雖然可以方便地繼承很多關(guān)系數(shù)據(jù)庫上成熟的查詢優(yōu)化技術(shù)，但查詢處理過度依賴于大表索引所產(chǎn)生中間結(jié)果的連接操作，這通常會(huì)產(chǎn)生大量無用的中間數(shù)據(jù)。此外，使用關(guān)系表來存儲(chǔ)三元組可能會(huì)限制通用性，很難支持RDF數(shù)據(jù)上的其他圖形分析，如可達(dá)性分析、最短路徑和社區(qū)檢測等。

本文遵從基于圖形的設(shè)計(jì)，使用基于內(nèi)存的分布式架構(gòu)，將RDF數(shù)據(jù)集存儲(chǔ)為原生圖形式，并利用圖探索策略來處理查詢。由于處理圖探索問題的復(fù)雜性，而將查詢圖Q的節(jié)點(diǎn)分解為核心(Core)、路徑(Path)、邊際(Marginal)節(jié)點(diǎn)三部分，并依據(jù)分解結(jié)構(gòu)提出了一種查詢圖的生成樹模型Tq。使得圖探索過程轉(zhuǎn)化為沿著Q的生成樹Tq迭代地?cái)U(kuò)展從Q到數(shù)據(jù)圖D的嵌入(embedding)，同時(shí)檢查與Tq中新擴(kuò)展的節(jié)點(diǎn)相鄰的非樹邊。最后，根據(jù)各部分結(jié)構(gòu)的特征，通過在分布式并行計(jì)算中分割匹配過程及推遲笛卡爾乘積操作，來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度以降低查詢延遲。

本文的主要貢獻(xiàn)如下：(1) 根據(jù)查詢圖中各部分結(jié)構(gòu)在分布式環(huán)境中的匹配特點(diǎn)，提出了查詢圖的CMP節(jié)點(diǎn)分解模型。針對RDF數(shù)據(jù)圖節(jié)點(diǎn)為語義實(shí)體的特點(diǎn)，提出了基于類型的統(tǒng)計(jì)概要圖，并利用統(tǒng)計(jì)信息對節(jié)點(diǎn)分解結(jié)構(gòu)進(jìn)行加權(quán)計(jì)算。(2) 在加權(quán)的查詢圖上，提出了以節(jié)點(diǎn)為核心的代價(jià)模型并結(jié)合最小生成樹思想將復(fù)雜的圖探索問題轉(zhuǎn)化為查詢執(zhí)行樹，得到了更高效的查詢執(zhí)行序列。(3) 為進(jìn)一步提高算法性能，提出了兩種優(yōu)化策略：一是通過推遲笛卡爾積操作，大量壓縮了核心結(jié)構(gòu)匹配時(shí)包含全歷史信息的路徑數(shù)目；二是通過結(jié)構(gòu)分解將匹配過程分割，使得路徑結(jié)構(gòu)匹配可以無冗余計(jì)算地高速并行執(zhí)行。(4) 在基準(zhǔn)合成數(shù)據(jù)集LUBM[26]和真實(shí)數(shù)據(jù)集YAGO2[27]上進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了算法的有效性、高效性；針對不同數(shù)據(jù)集規(guī)模及集群節(jié)點(diǎn)數(shù)目的變化進(jìn)行了實(shí)驗(yàn)分析，驗(yàn)證了算法的可擴(kuò)展性。

1 預(yù)備知識(shí)及相關(guān)工作

1.1 RDF圖及SPARQL查詢

定義1RDF數(shù)據(jù)圖。RDF數(shù)據(jù)圖D(V,E,L,φ)是一個(gè)有向標(biāo)簽圖，其中V表示節(jié)點(diǎn)集；E是連接V中節(jié)點(diǎn)的有向邊集；E:(v,v′)是一個(gè)有向函數(shù)，表示從v到v′的一條有向邊，其中v,v′∈V；L表示邊和節(jié)點(diǎn)標(biāo)簽集；φ:V∪E→(L∪var)表示一個(gè)將節(jié)點(diǎn)或邊映射到對應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。

圖1是從LUBM[26]數(shù)據(jù)集中摘取的RDF圖示例。為了更簡潔地表述，對節(jié)點(diǎn)URI進(jìn)行了壓縮表示，沒有涉及RDF標(biāo)準(zhǔn)定義中的空節(jié)點(diǎn)(Blank Node)，空節(jié)點(diǎn)問題與本文內(nèi)容是正交的。

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

SPARQL是W3C推薦的RDF數(shù)據(jù)集的標(biāo)準(zhǔn)查詢語言。最常見的SPARQL查詢類型定義如下：

Q:SELECTRDWHERETP

其中：RD是對結(jié)果的描述，TP是一組三元組模式。每個(gè)三元組模式的形式為(簡寫為),其中每一個(gè)主語、謂語和賓語都可以表示為一個(gè)變量或者常數(shù)。給定RDF數(shù)據(jù)圖D，三元組模式TP在D上搜索D的一組子圖，每個(gè)子圖都通過將TP中的模式變量映射到D中的值(節(jié)點(diǎn)或邊)形成綁定，來匹配TP所定義的圖形模式，結(jié)果描述RD包含圖形模式中的變量子集。

定義2RDF查詢圖。RDF查詢圖Q是SPARQL查詢類型的圖形化表示。SPARQL中的每一個(gè)三元組模式TP可以被看作RDF查詢圖中的一條帶節(jié)點(diǎn)和邊標(biāo)簽的有向邊，與數(shù)據(jù)圖不同的是，查詢圖中的節(jié)點(diǎn)可以是變量指代。所有的三元組模式構(gòu)成的完整圖形即為RDF查詢圖Q(∧1≤i≤nTPi)。

定義3模式匹配。給定一個(gè)RDF圖D和SPARQL查詢Q(∧1≤i≤nTPi)，模式匹配Q(D)定義為：

(1) 設(shè)f是從Q到D的一個(gè)映射；

如圖2(a)所示，SPARQL查找選修了由其指導(dǎo)教授所講授課程的學(xué)生及對應(yīng)的選修課程組合。查詢可以圖形化來表示,如圖2(b)所示。圖2(c)中顯示了該查詢在圖1所示的示例RDF圖中的模式匹配結(jié)果Q(D)，即結(jié)果描述RD為{?X→Person_B,?Y→Person_A}。

(a) SPARQL原語 (b) 查詢圖表示Q (c) 結(jié)果描述RD圖2 示例RDF圖上的SPARQL查詢示例

1.2 現(xiàn)有的解決方案

本節(jié)介紹最先進(jìn)的RDF系統(tǒng)中所采用的幾種代表性方法。

1) 關(guān)系方法(scan-join)。大多數(shù)RDF系統(tǒng)將RDF數(shù)據(jù)作為關(guān)系數(shù)據(jù)庫中的一組三元組表進(jìn)行存儲(chǔ)和索引。如Abadi等[5]提出的SW-store將RDF三元組垂直分區(qū)到多個(gè)屬性表。RDF-3X[4]和Hexastore[6]通過直接在B+-tree中冗余地存儲(chǔ)三元組SPO的多種排列(如PSO、POS)來實(shí)現(xiàn)基于索引的查詢方案，這可能導(dǎo)致多達(dá)15個(gè)這樣的B+-tree[15]。Peng等[16]給出了一種能夠根據(jù)查詢負(fù)載優(yōu)化圖劃分和存儲(chǔ)的RDF圖存儲(chǔ)方案，查詢處理通常包括掃描(scan)和連接(join)兩個(gè)階段。在掃描階段，查詢引擎將SPARQL查詢分解為一組三元組模式。例如，對于圖2所示查詢，三重模式TP包含{?X advisor ?Y}、{?X takesCourse ?Z}、{?Y teachOf ?Z}三個(gè)三元組模式。對于每個(gè)三元組模式，通過掃描索引或表來生成符合每個(gè)模式的中間結(jié)果綁定。在連接階段，將掃描階段的中間結(jié)果綁定依照連接計(jì)劃(例如左深連接或者平面連接)進(jìn)行連接，以產(chǎn)生查詢的最終答案。

2) 基于MapReduce的方法。分布式系統(tǒng)H-RDF-3X[17]和SHARD[18]在多個(gè)計(jì)算節(jié)點(diǎn)上水平劃分RDF數(shù)據(jù)，并將Hadoop作為跨節(jié)點(diǎn)查詢的通信層。H-RDF-3X通過最小邊割方法METIS[19]將RDF圖分割成指定分區(qū)數(shù)。然后，在每個(gè)分區(qū)上利用1-hop或者2-hop復(fù)制來擴(kuò)展分區(qū)邊界以保證小直徑查詢可以在分區(qū)內(nèi)部獲取完整答案。兩個(gè)系統(tǒng)的查詢處理都使用迭代的Reduce-side連接，其中Map階段進(jìn)行選擇，Reduce階段執(zhí)行實(shí)際連接[20]。但是對于復(fù)雜查詢，Map階段掃描大量的RDF元組和迭代運(yùn)行MapReduce作業(yè)的開銷十分昂貴。Lai等[21]提出了基于TwinTwig結(jié)構(gòu)分解的MapReduce分布式高效子圖枚舉算法,但該算法僅用于無向無標(biāo)簽圖。S2RDF將SPARQL查詢轉(zhuǎn)換為Spark分布式計(jì)算框架上的RDD操作,其離線建立了大量索引,用于加速在線查詢,但對于大規(guī)模知識(shí)圖譜,索引構(gòu)建時(shí)間開銷可能很高[22]。TriAD[8]中的工作表明，如果分布式查詢過程中需要交互，應(yīng)該避免通過Hadoop進(jìn)行連接。

3) 原生圖方法。最近許多以原生圖格式存儲(chǔ)RDF數(shù)據(jù)的方法被提出。這些方法通常使用鄰接表作為存儲(chǔ)和處理RDF數(shù)據(jù)的基本結(jié)構(gòu)。此外，這些方法通過使用復(fù)雜的索引，如TripleBit[13]、BitMat[14]和gStore[23]，或者使用圖形探索(graph-exploration)，如Trinity.RDF[9]和Wukong[10]，在進(jìn)行最后的連接操作之前剪枝許多無望形成結(jié)果的三元組。原生圖方法能更有效地支持更多類型的圖形查詢，例如可達(dá)性、社區(qū)檢測、最短路徑及隨機(jī)游走(部分已經(jīng)包含在SPARQL1.1標(biāo)準(zhǔn)中)，這也是RDF-S樣式推斷所必須的。Trinity.RDF中只采用一步剪枝的圖探索策略雖然避免了指數(shù)級(jí)路徑結(jié)果的保存，但最終需要利用一臺(tái)機(jī)器來聚合所有片段結(jié)果以對結(jié)果進(jìn)行最終連接。文獻(xiàn)[8，10]中的研究發(fā)現(xiàn)，最終的連接很容易成為查詢的瓶頸，因?yàn)樗薪Y(jié)果都需要聚合到一臺(tái)機(jī)器中進(jìn)行連接，Wukong在LUBM[26]上的實(shí)驗(yàn)表明，一些查詢在最終連接上花費(fèi)了90%以上的執(zhí)行時(shí)間。Wukong采用全歷史剪枝的策略來避免最終連接，但其只是借鑒關(guān)系方法中基于謂詞連接的代價(jià)模型來指導(dǎo)查詢執(zhí)行，沒有針對圖探索策略及復(fù)雜查詢結(jié)構(gòu)來進(jìn)行執(zhí)行序列優(yōu)化，也沒有壓縮基于全歷史剪枝策略的中間結(jié)果，造成冗余驗(yàn)證及不必要的網(wǎng)絡(luò)傳輸。

針對上述問題，本文提出了一種新型的查詢分解模型并以此優(yōu)化查詢執(zhí)行序列，并根據(jù)各部分結(jié)構(gòu)的特征，分割匹配過程及推遲笛卡爾乘積操作，來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度來降低查詢延遲。

2 基于結(jié)構(gòu)分解的圖模式匹配

本節(jié)提出一種基于圖探索模式的新的RDF并行計(jì)算模型，旨在盡早地對匹配過程中的結(jié)果路徑進(jìn)行剪枝并延緩笛卡爾乘積過程。

2.1 CPM查詢圖分解模型

為了更好地支持圖探索模式和復(fù)雜查詢，將查詢圖Q中的節(jié)點(diǎn)進(jìn)行分解，根據(jù)查詢圖各部分結(jié)構(gòu)的特征，來盡可能縮減查詢的中間結(jié)果數(shù)及增大查詢并行度以降低查詢延遲。

定義4無向查詢圖Qud。對于給定的查詢圖Q，將圖中的每一條邊都替換為無向邊，所構(gòu)成的無向圖定義為無向查詢圖(記為Qud)。

為了方便后續(xù)表述，如圖3所示，將無向圖Q中的查詢節(jié)點(diǎn)標(biāo)示為圓形，并采用類樹形的結(jié)構(gòu)劃分層次。轉(zhuǎn)換成無向圖，是為了泛化原查詢圖中邊關(guān)系的指向，Qud中各層次之間的邊所對應(yīng)的原始邊既可以由低層次指向高層次，也可以由高層次指向低層次。

圖3 查詢圖Q及其無向查詢圖Qud

定義5核心節(jié)點(diǎn)集VC。給定查詢圖Qud，對于能完整遍歷Qud中所有節(jié)點(diǎn)的任意生成樹Tq，核心節(jié)點(diǎn)集VC={u|u∈Qud，?(p∈Pre(u)，Tq←Qud)，p是Tq的非樹邊}，其中Pre(u)表示與節(jié)點(diǎn)u關(guān)聯(lián)的謂詞邊，即對于核心節(jié)點(diǎn)中的每一個(gè)節(jié)點(diǎn)，都存在一條邊在某棵生成樹中為非樹邊。

如圖4所示，對于由Qud中節(jié)點(diǎn)?C、?FP、?S構(gòu)成的環(huán)形結(jié)構(gòu)，對于不同的查詢圖生成樹Tq，謂詞邊TO、TC、Adv都可能作為非樹邊出現(xiàn)，與非樹邊相關(guān)聯(lián)的?C、?FP、?S節(jié)點(diǎn)均為核心節(jié)點(diǎn)。

圖4 核心節(jié)點(diǎn)集結(jié)構(gòu)

一個(gè)良好的匹配序列需要盡早進(jìn)行非樹邊的驗(yàn)證，一方面這將修剪大量無法形成最終結(jié)果的路徑綁定(即中間結(jié)果)，另一方面也減少了非樹邊緣檢查的總數(shù)。因此，算法將VC中的節(jié)點(diǎn)作為匹配序列的起始部分，這對高效的子圖匹配至關(guān)重要[24]。

定義6路徑節(jié)點(diǎn)集VP。給定Qud，路徑節(jié)點(diǎn)集VP={u|d(u)≥2，?(至多一個(gè)u′∈Qud.Adj(u)，u′∈VC)}，其中d(u)表示節(jié)點(diǎn)的度，Qud.Adj(u)表示節(jié)點(diǎn)u的鄰接節(jié)點(diǎn)集，即路徑節(jié)點(diǎn)集包括所有的節(jié)點(diǎn)度大于等于2且至多只與一個(gè)核心節(jié)點(diǎn)相連的節(jié)點(diǎn)。

如圖5所示，對于無向查詢圖Qud，?R、?D、?P均為路徑節(jié)點(diǎn)，VP中節(jié)點(diǎn)在任何生成樹Tq中都不與非樹邊相連，所以在進(jìn)行節(jié)點(diǎn)驗(yàn)證時(shí)并不需要利用到歷史信息，可以減少通信代價(jià)且可以并行化操作。路徑節(jié)點(diǎn)的匹配緊跟在核心節(jié)點(diǎn)之后并行執(zhí)行。

圖5 路徑節(jié)點(diǎn)集結(jié)構(gòu)

定義7邊際節(jié)點(diǎn)集VM。給定無向查詢圖Qud，邊際節(jié)點(diǎn)集VM={u|u∈Qud，d(u)=1}，即邊際節(jié)點(diǎn)集包括Qud中的所有度為1的節(jié)點(diǎn)。

如圖6所示，對于無向查詢圖Qud、?RA、?U、?X、?TA均為邊際節(jié)點(diǎn)。在本文的存儲(chǔ)模型中，由于邊際節(jié)點(diǎn)只存在一條謂詞邊約束，所以完全可以在其鄰接節(jié)點(diǎn)上進(jìn)行節(jié)點(diǎn)的匹配驗(yàn)證，而無須將中間結(jié)果傳遞到邊際節(jié)點(diǎn)。邊際節(jié)點(diǎn)的候選集也不會(huì)對后續(xù)的匹配有所幫助，所以作為整個(gè)結(jié)果的笛卡爾積部分，應(yīng)將其放在匹配的最后進(jìn)行處理。

圖6 邊緣節(jié)點(diǎn)集結(jié)構(gòu)

2.2 核心節(jié)點(diǎn)匹配序列

根節(jié)點(diǎn)是匹配順序中的第一個(gè)節(jié)點(diǎn)，所以要從核心節(jié)點(diǎn)集VC中選擇根節(jié)點(diǎn)。本節(jié)中，優(yōu)化器結(jié)合對數(shù)據(jù)圖預(yù)處理而生成的RDF特有的統(tǒng)計(jì)概要，對匹配中間結(jié)果進(jìn)行更加準(zhǔn)確的估計(jì)，制定更加合理的匹配序列(seq)。

直觀來講，傾向于選擇具有較少的局部匹配結(jié)果，以及較大的度(只統(tǒng)計(jì)核心節(jié)點(diǎn)內(nèi)部的度)的節(jié)點(diǎn)作為初始節(jié)點(diǎn)。較少的匹配結(jié)果意味著更低的網(wǎng)絡(luò)傳輸代價(jià)；較大的度意味著有更多的機(jī)會(huì)在匹配早期階段修剪綁定路徑。類似于文獻(xiàn)[24]，本文選擇根節(jié)點(diǎn)：

(1)

式中：d(u)是u關(guān)聯(lián)到核心節(jié)點(diǎn)內(nèi)部的度；cost(u)是對核心查詢節(jié)點(diǎn)u的預(yù)估局部匹配結(jié)果數(shù)。得到cost(u)有不同的策略，不同的策略會(huì)有不同的代價(jià)。本文使用預(yù)處理階段生成的RDF特有的統(tǒng)計(jì)概要來對進(jìn)行估計(jì)。接下來將討論統(tǒng)計(jì)概要的獲取過程。

W3C提供了一組詞匯表(作為RDF標(biāo)準(zhǔn)的一部分)來編碼RDF圖豐富的語義信息，例如類型謂詞(rdfs：type)提供了將RDF圖的節(jié)點(diǎn)分組成不同類別的功能。與一般標(biāo)簽圖不同，RDF圖節(jié)點(diǎn)標(biāo)識(shí)的是實(shí)體/文本信息，實(shí)體的語義特性導(dǎo)致了相同類型的節(jié)點(diǎn)通常具有類似的謂詞組合，便于統(tǒng)計(jì)。

對于每一個(gè)type類型，C(type)表示對應(yīng)數(shù)據(jù)類型的節(jié)點(diǎn)在數(shù)據(jù)圖中的基數(shù)。

圖7 RDF摘要統(tǒng)計(jì)示例

對于RDF圖G上的查詢Q，用Pre(u)表示查詢節(jié)點(diǎn)u具有的屬性(也就是謂詞)集合，Pre(u)={pi|?∈Qud}。根據(jù)u′所屬節(jié)點(diǎn)類型集，劃分Pre(u)=P(u)∪P′(u)，其中:

P(u)={pi|?(u′∈VC且(u,pi,u′)∈Qud)}P′(u)={pi|?(u′?VC且(u,pi,u′)∈Qud)}

進(jìn)一步地，根據(jù)查詢圖Q中謂詞p與u的出入邊關(guān)系，劃分P(u)=P-in(u)∪P-out(u),形式化為：

P-out(u)={pi|?(u′∈VC且(u,pi,u′)∈Q)}P-in(u)={pi|?(u′∈VC且(u′,pi,u)∈Q)}

同樣可得，P′(u)=P′-in(u)∪P′-out(u)。

基于上述討論，得出了起始節(jié)點(diǎn)的局部匹配數(shù)cost(u)的估算公式：

cost(u)=C(u.type)×des(u)×cut(u)

(2)

(3)

(4)

通過式(1)-式(2)，具有最小代價(jià)的節(jié)點(diǎn)被選為根節(jié)點(diǎn)。例如圖7中示例，核心節(jié)點(diǎn)集VC={u1,u2,u3}中三個(gè)節(jié)點(diǎn)所對應(yīng)d(u)均為2。通過計(jì)算，cost(u1)為1 952，cost(u2)為3 489，cost(u3)為39 124。因此，選取u1節(jié)點(diǎn)為核心節(jié)點(diǎn)中查詢搜索的起始節(jié)點(diǎn)。

定義8核心結(jié)構(gòu)權(quán)重圖Gw(VC)。給定核心節(jié)點(diǎn)集VC，核心結(jié)構(gòu)圖Gw(VC)中的權(quán)重w計(jì)算為：

(1) 對于模式Tp=，其中u,u′∈VC。

式中：Tpcut(u)為核心結(jié)構(gòu)中所有內(nèi)部模式(邊)的選擇度的乘積，權(quán)重值w表示核心節(jié)點(diǎn)在指定邊的預(yù)估計(jì)中間結(jié)果數(shù)。

對于圖7所示查詢圖及概要統(tǒng)計(jì)圖，計(jì)算得到的核心結(jié)構(gòu)權(quán)重圖如圖8所示。給定起始節(jié)點(diǎn)r，在Gw(VC)上結(jié)合最小生成樹思想得出最低代價(jià)的核心節(jié)點(diǎn)匹配序列，并依次記錄節(jié)點(diǎn)的樹邊與非樹邊。

圖8 查詢圖的核心結(jié)構(gòu)權(quán)重圖示例

如算法1所示，算法1-4行將每個(gè)節(jié)點(diǎn)的最低連接代價(jià)key值設(shè)置為∞，然后初始化匹配序列，并將根節(jié)點(diǎn)r的key值設(shè)置為0，以便在循環(huán)中第一個(gè)執(zhí)行；算法5-17行借鑒Prim算法思想尋找以r為起始點(diǎn)的，核心結(jié)構(gòu)權(quán)重圖Gw(VC)上的最小代價(jià)生成樹(即匹配序列)。當(dāng)以一個(gè)二叉最小堆來記錄u.key時(shí)，1-4行的時(shí)間成本為O(|VC|)；While循環(huán)一共要執(zhí)行|VC|次，其中Extract_Min(Q)操作選擇出隊(duì)列Q中具有最小key值的節(jié)點(diǎn)u并將其移出隊(duì)列，單次操作的時(shí)間成本為O(lg|VC|)，所以函數(shù)總的時(shí)間代價(jià)為O(|VC|lg|VC|)；算法8-16行的for循環(huán)執(zhí)行的總次數(shù)為O(E)，通過對節(jié)點(diǎn)設(shè)置標(biāo)志位可以在O(1)內(nèi)實(shí)現(xiàn)對v∈QorVnt的判斷，算法11行中賦值操作對應(yīng)的堆操作時(shí)間成本為O(lg|VC|)。所以，用E表示Gw(VC)中邊的數(shù)量，總的時(shí)間代價(jià)為O(|VC|lg|VC|+Elg|VC|)=O(Elg|VC|)。

算法1核心節(jié)點(diǎn)匹配序列(MatchingOrder)

輸入：核心節(jié)點(diǎn)集VC，匹配根節(jié)點(diǎn)r，核心結(jié)構(gòu)權(quán)重圖Gw(VC)。

輸出：核心節(jié)點(diǎn)的匹配順序seq。

1.for each查詢節(jié)點(diǎn)u∈VCdo

2.u.key←∞；

3.seq←?；r.key←0；

4.Q←VC；Vnt←?；

5.whileQ≠? do

6.u←Extract_Min(Q);

7.seq←seq∪u；

8.for eachv∈Gw(VC).Adj(u) do

9.ifv∈Q

10.ifw(u,v)

11.v.key←w(u,v)；

12.ifv∈Vnt

13.u.nt←u.nt∪e(u,v)；

14.else

15.u.t←u.t∪e(u,v)；

16.Vnt←Vnt∪v；

17.MatchingEdgeOrder(u,u.nt,u.t);

18.returnseq

2.3 將查詢圖轉(zhuǎn)化為查詢計(jì)劃樹

查詢序列確定后，可以將無向查詢圖重構(gòu)為一棵查詢樹(記為Tq)?；趫D探索的RDF存儲(chǔ)結(jié)構(gòu)保證了對同一節(jié)點(diǎn)的鄰接關(guān)系都存儲(chǔ)在與之相同的機(jī)器上。節(jié)點(diǎn)驗(yàn)證及查詢路由(Query Routing)與查詢圖的BFS過程類似，完整的查詢圖只需要在Tq中補(bǔ)全缺失的非樹邊。

如圖9所示，若查詢圖中核心節(jié)點(diǎn)部分所構(gòu)成的圖形如圖9(a)所示，經(jīng)過計(jì)算選取u1為起始節(jié)點(diǎn)，且查詢執(zhí)行序列為seq=，則對應(yīng)的Tq如圖9(b)所示(虛線表示非樹邊驗(yàn)證)。對于Tq中每一個(gè)查詢節(jié)點(diǎn)ui的候選節(jié)點(diǎn)，其邊緣的驗(yàn)證順序?yàn)椋悍菢溥?樹邊，多條非樹邊內(nèi)部的順序與多條樹邊內(nèi)部的順序，由根據(jù)統(tǒng)計(jì)概要計(jì)算得出的模式選擇度大小α(Tp)(即定義8中(2)所示)決定，最終得到完整的查詢執(zhí)行計(jì)劃。

(a) (b)圖9 核心節(jié)點(diǎn)圖G(VC)及查詢計(jì)劃樹Tq

節(jié)點(diǎn)邊緣匹配順序算法流程如算法2所示。

算法2節(jié)點(diǎn)邊緣匹配順序(MatchingEdgeOrder)

輸入：查詢節(jié)點(diǎn)u，節(jié)點(diǎn)的非樹邊集u.nt，節(jié)點(diǎn)的樹邊集u.t。

輸出：u上的邊緣匹配序列u.order。

1.u.order←?；

2.for eachv∈VP.Adj(u) orv∈VM.Adj(u) do

3.u.t←u.t∪e(u,v)；

4.Whileu.nt≠? do

6.u.order←u.order∪p；

7.u.nt←u.nt-{p}；

8.Whileu.t≠? do

10.u.order←u.order∪p；

11.u.t←u.t-{p}；

14.returnu.order

圖10 全歷史剪枝下各中間路徑驗(yàn)證匹配過程

對于u2的候選節(jié)點(diǎn)，u2.nt表示Tq中與u2相連的未匹配非樹邊集合，即邊p4；u2.t表示與u2相連的未匹配樹邊集合，即邊p3。當(dāng)查詢路徑執(zhí)行到u2節(jié)點(diǎn)時(shí)，由于u2.nt不為空，固先匹配非樹邊p4，再匹配樹邊p3。圖10中實(shí)線箭頭所示過程為非樹邊驗(yàn)證，虛線箭頭所示部分為樹邊匹配過程。按照核心節(jié)點(diǎn)執(zhí)行序列依次執(zhí)行各節(jié)點(diǎn)，直到所有節(jié)點(diǎn)都完成路徑匹配。

圖11顯示了數(shù)據(jù)圖上依據(jù)v-id進(jìn)行hash分區(qū)的一個(gè)示例，其中虛線節(jié)點(diǎn)代表謂詞或類型所對應(yīng)的虛擬節(jié)點(diǎn)。類似于文獻(xiàn)[10-11]，鍵值存儲(chǔ)創(chuàng)建了一個(gè)RDF的圖模型，每個(gè)RDF實(shí)體被表示為具有唯一id的圖節(jié)點(diǎn)，節(jié)點(diǎn)id與謂詞id及出入度關(guān)系組成的三元組結(jié)構(gòu)實(shí)現(xiàn)了細(xì)粒度的key值表示，Value表示對應(yīng)索引的候選集合，如圖12所示。這十分便于獲取各查詢節(jié)點(diǎn)的候選集合。

圖11 數(shù)據(jù)圖分區(qū)示例

圖12 字典編碼與索引結(jié)構(gòu)

算法將查詢計(jì)劃傳遞到每一個(gè)計(jì)算節(jié)點(diǎn)。對于變量節(jié)點(diǎn)，根據(jù)不同情況，計(jì)算節(jié)點(diǎn)利用類型或者謂詞對應(yīng)的倒排索引(Idx-t,Idx-p)查詢到本地全部的初始根節(jié)點(diǎn)r的候選，在所有計(jì)算節(jié)點(diǎn)上開始匹配任務(wù)。

2.4 高并發(fā)的子路徑匹配連接算法

在先前的圖探索方法Trinity.RDF和Wukong中，查詢序列的生成借鑒了關(guān)系方法中的成熟模型，其類似于關(guān)系方法中join階段的連接計(jì)劃確定(例如左深連接計(jì)劃樹)，以謂詞關(guān)系的連接順序主導(dǎo)來確定節(jié)點(diǎn)匹配序列。但是，RDF本質(zhì)上是一個(gè)帶標(biāo)簽的有向多邊圖，關(guān)系模型無法充分利用查詢圖的結(jié)構(gòu)特征(例如環(huán)形或者星形結(jié)構(gòu))來指導(dǎo)查詢，無法充分發(fā)揮圖探索策略的優(yōu)勢(即與關(guān)系方法相比，隨著探索的進(jìn)行，在匹配早期修剪大量無望的中間結(jié)果)。

例如，在圖7(a)所示結(jié)構(gòu)中，若關(guān)系主導(dǎo)的匹配序列為seq=，經(jīng)過謂詞Adv、TO的探索，中間結(jié)果包含由?Student、?FB、?Course候選結(jié)果形成的部分組合，在這些組合當(dāng)中，由于沒有進(jìn)行TC關(guān)系的驗(yàn)證，存在大量假陽性的學(xué)生、課程組合實(shí)際并不存在選課關(guān)系，導(dǎo)致謂詞PA的探索在許多假陽性的Student節(jié)點(diǎn)上進(jìn)行，降低了查詢效率。

另一方面，圖探索策略中關(guān)系主導(dǎo)的匹配序列在分布式環(huán)境下可能導(dǎo)致中間結(jié)果在計(jì)算節(jié)點(diǎn)間的往復(fù)傳遞。與關(guān)系方法中的join連接不同，join連接是將scan階段所有收集到的中間結(jié)果匯總到同一節(jié)點(diǎn)進(jìn)行連接工作，join階段類似于單機(jī)環(huán)境。圖探索策略由于數(shù)據(jù)的分布存儲(chǔ)，不同實(shí)體節(jié)點(diǎn)可能被劃分到不同的計(jì)算節(jié)點(diǎn)，如圖11所示。同一實(shí)體節(jié)點(diǎn)在查詢圖中具有的謂詞關(guān)系可能還未完全驗(yàn)證，匹配序列即要求將匹配的中間結(jié)果傳遞到其他節(jié)點(diǎn)，進(jìn)行后續(xù)謂詞關(guān)系的驗(yàn)證，而后又再次返回原節(jié)點(diǎn)，進(jìn)行剩余謂詞關(guān)系的探索。

例如，在圖7(a)所示結(jié)構(gòu)中，關(guān)系主導(dǎo)的匹配序列仍為seq=，如果查詢從u1節(jié)點(diǎn)的候選出發(fā)，通過謂詞Adv的探索，中間結(jié)果包含由?Student、?FB候選結(jié)果形成的部分組合。而后，各子查詢被發(fā)送到各u2候選結(jié)果所在計(jì)算節(jié)點(diǎn)，進(jìn)行后續(xù)TO謂詞探索，由于u1節(jié)點(diǎn)的謂詞PA關(guān)系并未驗(yàn)證，中間結(jié)果需要再次被發(fā)送到u1候選結(jié)果所在計(jì)算節(jié)點(diǎn)，造成了額外的網(wǎng)絡(luò)傳輸與查詢延遲。

由于關(guān)系主導(dǎo)的匹配序列的一系列問題，本文提出了一種結(jié)構(gòu)主導(dǎo)的分布式子圖匹配算法SDSM，基于各部分結(jié)構(gòu)在分布式環(huán)境中的匹配特點(diǎn)，利用CPM分解模型進(jìn)行查詢圖的結(jié)構(gòu)分解，以結(jié)構(gòu)信息指導(dǎo)匹配序列，盡可能地縮減查詢的中間結(jié)果數(shù)，提高查詢效率。

在2.2節(jié)與2.3節(jié)中，為了降低中間結(jié)果數(shù)量，制定了以結(jié)構(gòu)為主導(dǎo)的嚴(yán)格的匹配序列，并完成了核心部分節(jié)點(diǎn)結(jié)果的匹配(記為MC)。各中間結(jié)果路徑在核心節(jié)點(diǎn)部分都得到了唯一(各不相同)的路徑綁定，而匹配過程中與核心節(jié)點(diǎn)相連的路徑節(jié)點(diǎn)或者邊際節(jié)點(diǎn)則以候選集的形式保存，如圖13所示。

圖13 中間結(jié)果綁定

路徑節(jié)點(diǎn)由于不存在非樹邊，所以無須用到歷史信息剪枝，沒有必要攜帶完整的歷史信息來造成網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān)。對于核心節(jié)點(diǎn)遍歷獲得的中間結(jié)果，如果采用文獻(xiàn)[10]中的全部中間結(jié)果獨(dú)立計(jì)算策略，且攜帶完整的歷史信息直到整個(gè)查詢結(jié)束，不僅會(huì)增大網(wǎng)絡(luò)負(fù)擔(dān)，同時(shí)也造成了節(jié)點(diǎn)的重復(fù)計(jì)算。

圖14 不同中間結(jié)果映射到相同的路徑節(jié)點(diǎn)

SDSM算法通過分割核心節(jié)點(diǎn)匹配與路徑節(jié)點(diǎn)匹配兩個(gè)過程來實(shí)現(xiàn)高并發(fā)的子路徑匹配連接，如算法3所示。各路徑分支以MC中產(chǎn)生的路徑節(jié)點(diǎn)候選作為起始，執(zhí)行一個(gè)個(gè)獨(dú)立的子路徑查詢，路徑匹配過程可以無冗余地并行化執(zhí)行，提高了查詢的并發(fā)度。各路徑匹配結(jié)果MP最終在主機(jī)節(jié)點(diǎn)上執(zhí)行輕量級(jí)的連接形成最終匹配結(jié)果M。

算法3結(jié)構(gòu)主導(dǎo)的分布式子圖匹配算法SDSM

輸入：查詢圖Q，索引Idx。

輸出：SPARQL查詢匹配結(jié)果M。

master

1.無向查詢圖Qud←Q；

2.(VC,VP,VM)←頂點(diǎn)分解算法Decomposed(Qud)；

3.計(jì)算初始節(jié)點(diǎn)r；

4.計(jì)算核心結(jié)構(gòu)權(quán)重圖Gw(VC)；

5.sed←MatchingOrder(VC,r,Gw(VC))；

6.sendseqto all Slave；

7.匹配結(jié)果集M←?；

8.receiveMc、Mpfrom slave；

9.for each核心節(jié)點(diǎn)綁定Mcdo

10.for each路徑節(jié)點(diǎn)綁定Mpdo

11.M←M∪{MC×MP}；

12.展開M中邊際節(jié)點(diǎn)VM的笛卡爾積部分；

13.returnM；

Slave

14.receiveseqfrom master；

15.Mc←MatchCoreEdge(seq,Idx)；

16.sendMcto master；

17.for each路徑節(jié)點(diǎn)候選ui.c∈Mc.set(VP) do

18.If has visited do

19.continue；

20.else

21.MP←MatchPathEdge(ui.c,Idx)

22.sendMPto master.

首先，算法將查詢圖轉(zhuǎn)化為無向查詢圖Qud，并依據(jù)結(jié)構(gòu)對節(jié)點(diǎn)進(jìn)行分解。在Decompose(Qud)操作中，首先將度數(shù)為1的節(jié)點(diǎn)全部加入VM并從Qud中刪除；然后迭代地將新生成的度數(shù)為1的節(jié)點(diǎn)加入VP集合并去除，直到?jīng)]有新的度數(shù)為1的節(jié)點(diǎn)生成；VC即為剩余節(jié)點(diǎn)。算法3-6行依據(jù)2.2節(jié)的相關(guān)討論及算法1進(jìn)行計(jì)算，隨后將查詢計(jì)劃seq發(fā)送給所有計(jì)算節(jié)點(diǎn)。算法14-22行中，依據(jù)2.3節(jié)及本節(jié)相關(guān)討論，在各計(jì)算節(jié)點(diǎn)依照查詢結(jié)構(gòu)執(zhí)行不同匹配策略，最終得到核心匹配結(jié)果Mc、路徑匹配結(jié)果MP并返回給主機(jī)節(jié)點(diǎn)。算法8-13行中，主機(jī)節(jié)點(diǎn)對匹配的中間結(jié)果執(zhí)行輕量級(jí)的join連接，并展開相應(yīng)笛卡爾乘積結(jié)果，返回最終答案集M。

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

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文所有實(shí)驗(yàn)均在包括6個(gè)相同計(jì)算節(jié)點(diǎn)的分布式集群上進(jìn)行，每個(gè)計(jì)算節(jié)點(diǎn)采用Intel(R) Core(TM) i7-7700@3.60 GHz八核處理器，物理內(nèi)存為16 GB，硬盤大小為1 TB。節(jié)點(diǎn)間通信使用1 000 Mbit/s以太網(wǎng)。

實(shí)驗(yàn)分別使用了合成數(shù)據(jù)集LUBM(Lehigh University BenchMark)[26]的4個(gè)生成規(guī)模和真實(shí)數(shù)據(jù)集YAGO2(Yet Another Great Ontology 2)[27]。相關(guān)信息如表1所示，其中#T、#S、#O、#P分別表示三元組數(shù)、主語節(jié)點(diǎn)數(shù)、賓語節(jié)點(diǎn)數(shù)以及不同謂詞數(shù)目。

合成數(shù)據(jù)集LUBM是由利哈伊大學(xué)開發(fā)的，關(guān)于大學(xué)本體的一種標(biāo)準(zhǔn)且系統(tǒng)的語義Web存儲(chǔ)庫評價(jià)基準(zhǔn)。該基準(zhǔn)旨在評估單個(gè)現(xiàn)實(shí)本體在大型數(shù)據(jù)集上的擴(kuò)展查詢。本文使用數(shù)據(jù)生成器UBA1.7生成了4個(gè)不同規(guī)模的數(shù)據(jù)集，以便進(jìn)行可擴(kuò)展性測試。

YAGO2是一個(gè)鏈接數(shù)據(jù)知識(shí)庫，主要集成了Wikipedia、WordNet和GeoNames三個(gè)來源的數(shù)據(jù)，包含1.2億條三元組，擁有超過1 000萬個(gè)實(shí)體(如個(gè)人、組織、城市等)的知識(shí)。

表1 數(shù)據(jù)集詳細(xì)信息

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

將SDSM算法的查詢性能與TriAD、Wukong，StarMR做對比，相關(guān)測試代碼及設(shè)置來源于文獻(xiàn)[7-8,10]。首先，比較了LUBM-2560數(shù)據(jù)集在6個(gè)計(jì)算節(jié)點(diǎn)(包括一個(gè)主節(jié)點(diǎn))上的查詢性能。對于查詢，本文使用了Atre等發(fā)表的基準(zhǔn)查詢[15]，它被許多分布式RDF系統(tǒng)所使用[9-11,14,25]。

如圖15所示，在6個(gè)查詢中，SDSM算法比最快的Wukong分別提高了1.4～3.6倍。將實(shí)驗(yàn)分成2組，其中第一組L1、L2、L3(分別對應(yīng)文獻(xiàn)[14]中的Q1、Q3、Q7查詢)，特別地，因?yàn)長2的最終結(jié)果為空，源于基準(zhǔn)查詢中某謂詞關(guān)系雖然在數(shù)據(jù)圖中大量存在，但在其所對應(yīng)的實(shí)體上基數(shù)為0。SDSM中基于類型的摘要統(tǒng)計(jì)在制定查詢計(jì)劃時(shí)很容易發(fā)現(xiàn)了這一點(diǎn)，而Wukong及TriAD卻需要遍歷大量中間結(jié)果；L1跟L3分別構(gòu)成了較少及較多的最終結(jié)果(約為初始候選三元組的1/65 000及1/1 000)，圖探索的方式比基于關(guān)系的模式擁有近1個(gè)數(shù)量級(jí)的速度提升，基于MapReduce的StarMR算法由于其平臺(tái)計(jì)算的局限性，在每個(gè)查詢上都落后于其他算法1～2個(gè)數(shù)量級(jí)，SDSM依據(jù)摘要統(tǒng)計(jì)在核心結(jié)構(gòu)上得到了比Wukong更合理的查詢節(jié)點(diǎn)匹配，并依據(jù)非樹邊的優(yōu)先匹配更快地剪枝了中間結(jié)果，所以得到了更大的性能提升。

圖15 LUBM-2560上不同算法的平均查詢響應(yīng)時(shí)間

對于第二組更復(fù)雜(擁有較多模式)的查詢L4、L5、L6(分別對文獻(xiàn)[14]中的Q2、Q1、Q7進(jìn)行了擴(kuò)展)，L4中的查詢模式具有很低的選擇性，并且由于不存在環(huán)結(jié)構(gòu)，極大地降低了借助結(jié)構(gòu)分解及全歷史剪枝策略帶來的剪枝效果，導(dǎo)致圖探索策略與關(guān)系方法TriAD相比性能提升較少，SDSM較Wukong的性能提升來源于推遲笛卡爾乘積部分連接的操作帶來的收益。查詢L5、L6中的環(huán)結(jié)構(gòu)分別具有較少及較多核心結(jié)構(gòu)匹配結(jié)果，但即使是對于具有較多核心結(jié)構(gòu)匹配結(jié)果的查詢，核心結(jié)構(gòu)的剪枝力度仍然是最大的，之后在路徑節(jié)點(diǎn)上無重復(fù)的高速并行驗(yàn)證進(jìn)一步加速了查詢。

對于YAGO2數(shù)據(jù)集上的查詢，本文從文獻(xiàn)[11-12]收集所需的查詢集，查詢涵蓋了輕量查詢和復(fù)雜查詢。對于YAGO2上的復(fù)雜查詢Y4、Y5、Y6，實(shí)驗(yàn)得到了與LUBM類似的效果，如圖16(b)所示，SDSM算法較其他算法分別提升了1.2～2.5倍。不同的是，對于圖16(a)中的輕量級(jí)查詢Y1、Y2、Y3，查詢只從常量節(jié)點(diǎn)開始進(jìn)行有限的探索，總查詢時(shí)間較短(通常在數(shù)毫秒之內(nèi))。SDSM與Wukong相比在查詢計(jì)劃上的開銷稍高一些，但這依然在可接受的范圍之內(nèi)，因?yàn)椴樵兊钠款i通常由那些復(fù)雜查詢引起，針對復(fù)雜查詢SDSM算法的效率更高。

(a) (b)圖16 YAGO2上不同算法的平均查詢響應(yīng)時(shí)間

3.3 可擴(kuò)展性測試

本文從機(jī)器數(shù)和數(shù)據(jù)集大小兩個(gè)方面對算法的可擴(kuò)展性進(jìn)行了評估。

對于第一組實(shí)驗(yàn)，如圖17所示，當(dāng)服務(wù)器數(shù)量從2臺(tái)逐漸增加到6臺(tái)時(shí)，查詢L1-L6的查詢時(shí)間均隨著機(jī)器數(shù)量的增多逐漸減少，證明了SDSM算法能夠有效利用分布式系統(tǒng)的并行性查詢。L2由于在查詢計(jì)劃階段就通過摘要統(tǒng)計(jì)得出結(jié)果為空，所以查詢時(shí)間恒定。對于復(fù)雜查詢L4、L5、L6，查詢時(shí)間的遞減幅度略低于L1、L3，因?yàn)楦嗟姆謪^(qū)增加了通過網(wǎng)絡(luò)傳輸?shù)闹虚g數(shù)據(jù)量，但是存儲(chǔ)模型仍然有效地限制了這一開銷。

(a)

(b)圖17 SDSM在不同集群節(jié)點(diǎn)數(shù)目上的表現(xiàn)

對于第二組實(shí)驗(yàn)，本文固定服務(wù)器的數(shù)量為6臺(tái)，并且生成了不同規(guī)模的LUBM數(shù)據(jù)集來測試算法擴(kuò)展數(shù)據(jù)的能力。如圖18所示，隨著三元組數(shù)目從5.3×106增加到346×106，即使是復(fù)雜查詢，SDSM的查詢時(shí)間仍能保持近乎線性的增長。因?yàn)樗惴ㄍㄟ^對查詢圖的結(jié)構(gòu)分解，預(yù)先攜帶全歷史信息完成了能大幅度剪枝的環(huán)形結(jié)構(gòu)的匹配，并推遲了笛卡爾積部分的計(jì)算；之后通過無冗余的并行路徑節(jié)點(diǎn)的查詢，最終只需要在主機(jī)上進(jìn)行輕量級(jí)的join連接，路徑數(shù)目不會(huì)過于膨脹，具有良好的伸縮性。

圖18 SDSM算法在不同數(shù)據(jù)集規(guī)模上的表現(xiàn)

4 結(jié) 語

本文提出了一種基于圖探索策略的結(jié)構(gòu)主導(dǎo)的分布式子圖匹配優(yōu)化算法SDSM，有效回答了大規(guī)模RDF圖上的分布式SPARQL查詢。SDSM算法依據(jù)結(jié)構(gòu)特征將查詢圖進(jìn)行分解，結(jié)合基于類型的摘要統(tǒng)計(jì)和以節(jié)點(diǎn)為核心的代價(jià)模型，將復(fù)雜的圖探索問題轉(zhuǎn)化為了查詢樹模型。此外，通過分割匹配過程及推遲笛卡爾積操作來進(jìn)行優(yōu)化，進(jìn)一步加速了查詢。在基準(zhǔn)合成數(shù)據(jù)集LUBM和真實(shí)數(shù)據(jù)集YAGO2進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了算法的有效性、高效性和可拓展性。

圖數(shù)據(jù)劃分問題也是一個(gè)經(jīng)典的NP-Complete問題，未來將結(jié)合更多的圖結(jié)構(gòu)和知識(shí)語義信息作為劃分標(biāo)準(zhǔn)來進(jìn)行更細(xì)致的圖劃分算法研究，以便于更好地支持知識(shí)圖譜上查詢的快速執(zhí)行。