魯富宇，冷泳林

（渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121013）

0 引言

隨著領(lǐng)域知識(shí)圖譜的不斷完善、規(guī)模的不斷擴(kuò)大，其數(shù)據(jù)管理問題愈加重要［1］. RDF作為人工智能領(lǐng)域存儲(chǔ)和管理知識(shí)圖譜的通用框架，采用三元組形式描述知識(shí)，大量知識(shí)構(gòu)成三元組庫. 三元組庫以實(shí)體、屬性和值為基本構(gòu)件，通過屬性和值描述知識(shí)之間的關(guān)系. 同時(shí)一條三元組也可以看做是實(shí)體指向?qū)傩灾档挠邢蜻?，這些有向邊連接到一起構(gòu)成有向圖，圖頂點(diǎn)表示實(shí)體和值，有向邊表示屬性. 知識(shí)圖譜中包含了豐富的語義知識(shí)，這些語義知識(shí)構(gòu)成領(lǐng)域知識(shí)圖譜［2］. 根據(jù)鏈接開放數(shù)據(jù)發(fā)布的信息顯示，很多領(lǐng)域知識(shí)圖譜的規(guī)模在10億條以上，如維基百科和地理信息知識(shí)圖譜的三元組達(dá)到30億條，蛋白質(zhì)知識(shí)圖譜超過130億條. 如此大規(guī)模的領(lǐng)域知識(shí)圖譜數(shù)據(jù)給數(shù)據(jù)高效存儲(chǔ)和檢索都提出巨大挑戰(zhàn)［3］.

基于關(guān)系的RDF數(shù)據(jù)存儲(chǔ)是一種常見的存儲(chǔ)方式，三元組表［4-5］、垂直分割［6］以及屬性表［7］都是采用替代的關(guān)系存儲(chǔ)方式存儲(chǔ)RDF三元組，來加速數(shù)據(jù)檢索，但這種基于元組的存儲(chǔ)方式忽略了數(shù)據(jù)間知識(shí)的聯(lián)系，并且在處理大規(guī)模數(shù)據(jù)時(shí)的空值、自連接等問題嚴(yán)重影響了數(shù)據(jù)的檢索效率. 一些存儲(chǔ)索引系統(tǒng)如RDF-3X［8］，Hexastore［9］和SPOVC［10］通過構(gòu)建三元組不同組合方式的索引存儲(chǔ)多個(gè)索引副本，并輔助相應(yīng)的查詢優(yōu)化技術(shù)，提高了查詢效率. 當(dāng)面臨大規(guī)模數(shù)據(jù)時(shí)，這些索引都是以空間來換取時(shí)間效率的. 另外，gStore［11］采用樹狀索引和鄰接表的方式對(duì)RDF數(shù)據(jù)進(jìn)行索引，TripleBit［12］依據(jù)RDF謂語對(duì)元組進(jìn)行索引并進(jìn)行壓縮存儲(chǔ). 這兩種索引在執(zhí)行查詢過程中過濾大量不相關(guān)數(shù)據(jù)，提高查詢效率. 但它們都是基于元組的檢索，需要利用查詢優(yōu)化技術(shù)降低查詢中間結(jié)果. 為降低查詢中間結(jié)果，RP-index（RDF Path in?dex）［13］和RG-index（RDF graph index）［14］兩種基于路徑和圖的過濾索引用來實(shí)現(xiàn)數(shù)據(jù)的有效過濾. 其中RP-index索引RDF圖中入邊路徑信息，RG-index將路徑索引擴(kuò)展至圖結(jié)構(gòu)索引實(shí)現(xiàn)元組的有效過濾，這兩種索引的規(guī)模會(huì)隨著圖規(guī)模的不斷擴(kuò)大而迅速增加. 基于以上分析，自連接、副本和壓縮方法是影響SPARQL查詢效率的主要因素.

本文通過分析RDF數(shù)據(jù)發(fā)現(xiàn)，鏈?zhǔn)浇Y(jié)構(gòu)做為一種常見數(shù)據(jù)結(jié)構(gòu)，有效的反映出知識(shí)之間的關(guān)聯(lián)，在數(shù)據(jù)檢索和知識(shí)推理中都具有非常重要的作用. 基于此，提出一種基于路徑的索引樹（Path tree，P-tree）及建立在該索引結(jié)構(gòu)上的三元組壓縮和檢索算法（Compressed and retrieval triples，CRK2-triples），來實(shí)現(xiàn)RDF數(shù)據(jù)模型下知識(shí)圖譜數(shù)據(jù)的快速檢索.

1 路徑索引樹（P-tree）構(gòu)建

RDF有向圖的每條邊鏈接知識(shí)主體（主語）和知識(shí)主體所對(duì)應(yīng)的屬性值（賓語），邊代表著主體的特征. 通過對(duì)SPARQL查詢圖特征進(jìn)行分析得出星型、鏈?zhǔn)?、環(huán)型、樹型是SPARQL查詢圖的基本結(jié)構(gòu). 其中鏈?zhǔn)浇Y(jié)構(gòu)是指主語又同時(shí)作為賓語的結(jié)構(gòu)，本文針對(duì)鏈?zhǔn)竭@種常見的結(jié)構(gòu)，構(gòu)建P-tree索引.

給定一個(gè)RDF有向圖G，如果G中存在一個(gè)頂點(diǎn)v滿足鏈接它的所有邊中只有出邊，沒有入邊，則稱頂點(diǎn)v為源點(diǎn). 相反，如果v滿足只有入邊沒有出邊，稱之為匯點(diǎn). 對(duì)于一個(gè)RDF有向圖，從源點(diǎn)出發(fā)，沿有向邊的方向進(jìn)行深度優(yōu)先遍歷，直到遇到第一個(gè)匯點(diǎn)結(jié)束，所得到的路徑，稱之為一條由源點(diǎn)到匯點(diǎn)的完整路徑. 將一個(gè)RDF知識(shí)圖譜按從源點(diǎn)到匯點(diǎn)進(jìn)行分解，會(huì)得到多條完整路徑. 文獻(xiàn)［15］已經(jīng)證明，RDF圖中的任意一個(gè)實(shí)體或?qū)傩约八鼈冎g的有向邊都至少屬于一條完整路徑，由此可以保證一個(gè)RDF有向圖可以由一個(gè)完整路徑集合表示.

對(duì)于一個(gè)給定的SPARQL查詢，同樣也以源點(diǎn)到匯點(diǎn)的完整路徑分解方式將其分解為完整查詢路徑集合，文獻(xiàn)［15］同樣給出了如果SPARQL查詢是RDF子圖，那么一定至少存在一條完整路徑，滿足查詢路徑是完整路徑的子路徑.

由于RDF圖中頂點(diǎn)及邊都是采用統(tǒng)一資源標(biāo)識(shí)符（URI）進(jìn)行表示，直接的字符串匹配查詢?cè)诓樵冃噬嫌幸欢ㄓ绊?，而基于二進(jìn)制的位串利用邏輯運(yùn)算所進(jìn)行的匹配查詢效率要明顯優(yōu)于字符串的匹配.因此本文對(duì)完整路徑及查詢路徑利用布魯姆過濾器進(jìn)行編碼，生成能夠快速配的二進(jìn)制位串.

將RDF圖分解成一個(gè)全路徑集合，集合中每一條全路徑上的邊信息構(gòu)成一條概要路徑，對(duì)于每條概要路徑將路徑上每條邊的屬性信息通過k個(gè)Hash函數(shù)h1，h2，…，hk映射到長(zhǎng)度為m的向量V中，生成一個(gè)布魯姆編碼. 則所有的n條完整路徑對(duì)應(yīng)生成n個(gè)布魯姆編碼V1，V2，…，Vk. 接下來通過計(jì)算這n個(gè)編碼之間的漢明距離，得到任意一對(duì)完整路徑之間的相似性，然后利用AP聚類，對(duì)生成的n條完整路徑進(jìn)行聚類.

AP聚類在聚類時(shí)不需要指定聚類中心，將所有數(shù)據(jù)作為潛在的聚類中心，然后通過迭代的方式在數(shù)據(jù)點(diǎn)間傳遞吸引度和歸屬度消息，通過迭代不段更新吸引度和歸屬度矩陣，直到產(chǎn)生k個(gè)高質(zhì)量的exem?plar為止. 通過聚類產(chǎn)生的每一個(gè)聚類集合中包含若干條路徑，這些路徑在邊的信息上相似性最大. 因此接下來對(duì)這些相似路徑的布魯姆編碼執(zhí)行按位“與”操作，得到一個(gè)復(fù)合布魯姆編碼，此編碼代表一個(gè)完整路徑集合，這個(gè)集合中的完整路徑具有相似的路徑邊信息. P-tree就是將每一個(gè)聚類集合對(duì)應(yīng)的布魯姆編碼作為葉子節(jié)點(diǎn)，然后采用自底向上的過程構(gòu)建的，一層一層構(gòu)建，直到只有一個(gè)根節(jié)點(diǎn)為止，圖1展示了P-tree構(gòu)建過程.

圖1 P-tree構(gòu)建過程

2 元組壓縮與檢索算法

P-tree索引樹的每個(gè)葉子節(jié)點(diǎn)都會(huì)對(duì)應(yīng)一組相似的完整路徑，這些完整路徑擁有相似的路徑邊信息.當(dāng)將SPARQL分解為完整查詢路徑后，通過對(duì)P-tree執(zhí)行自頂向下的邏輯“與”運(yùn)算找到匹配的葉子節(jié)點(diǎn)時(shí)，相當(dāng)于在眾多的完整路徑中找到了與之匹配的路徑信息. 為了得到最終的查詢結(jié)果，還需要將葉子節(jié)點(diǎn)所對(duì)應(yīng)的全路徑集合與查詢路徑進(jìn)行精確匹配. 本部分將依據(jù)相似完整路徑具有的相同邊信息設(shè)計(jì)一個(gè)元組壓縮和檢索算法CRK2-triples，該算法利用k2-tree壓縮存儲(chǔ)每一個(gè)路徑邊所對(duì)應(yīng)的元組集合.

由于每一個(gè)葉子節(jié)點(diǎn)都包含一組相似的完整路徑集合，這些完整路徑包含的路徑邊有很大的相似性. 因此每一個(gè)謂語都會(huì)對(duì)應(yīng)著一個(gè)元組集合. 當(dāng)將RDF圖分解為完整路徑時(shí)，一個(gè)元組有可能出現(xiàn)在多條完整路徑中，因此就會(huì)產(chǎn)生很多元組副本. 為降低副本冗余，通過聚類完整相似路徑已經(jīng)將具有相同邊的元組聚類到一起，在對(duì)元組進(jìn)行存儲(chǔ)時(shí)，利用k2-triples進(jìn)一步將具有相同邊的元組進(jìn)行統(tǒng)一的壓縮存儲(chǔ)，可以進(jìn)一步降低元組的副本率. 其中每一條邊所對(duì)應(yīng)的元組集合采取的是二級(jí)壓縮模式，一級(jí)壓縮是建立在k2-triples基礎(chǔ)上實(shí)現(xiàn)的，二級(jí)壓縮采取RLE（Run-length encoding）方式.

k2-triples是一種專門針對(duì)共享屬性的元組設(shè)計(jì)的元組壓縮存儲(chǔ)方式，其基本思想是建立在k2-tree基礎(chǔ)上的. k2-triples利用一個(gè)位矩陣存儲(chǔ)具有相同屬性元組，其中位矩陣的行和列分別對(duì)應(yīng)元組的主語和賓語. 當(dāng)位矩陣中任意位所對(duì)應(yīng)的主語和賓語存在時(shí)，將其設(shè)置為1，否則設(shè)為0. 對(duì)于生成的位矩陣，存在大量主語和賓語的不關(guān)聯(lián)關(guān)系，所以位矩陣中會(huì)有大量0出現(xiàn). 如果直接采用位矩陣進(jìn)行存儲(chǔ)，非常浪費(fèi)存儲(chǔ)空間. 為此，k2-triples將位矩陣轉(zhuǎn)換成一個(gè)k2-tree進(jìn)行壓縮存儲(chǔ)，圖2描述了位矩陣采用k2-tree的存儲(chǔ)方式。

圖2 k2-triples壓縮方案

當(dāng)k為2時(shí)，將位矩陣分成k2個(gè)子矩陣，k2-tree的根節(jié)點(diǎn)包含k2個(gè)子節(jié)點(diǎn)，對(duì)k2子矩陣按自上而下，自左向右順序依次判斷每個(gè)矩陣，如果子矩陣中的各個(gè)位都為0，則k2-tree的子節(jié)點(diǎn)對(duì)應(yīng)為0，否則為1. 如圖2所示，左側(cè)矩陣分解為4個(gè)子矩陣時(shí)，第3個(gè)子矩陣中全部為0，因此對(duì)應(yīng)k2-tree節(jié)點(diǎn)即為0. 當(dāng)?shù)谝粚庸?jié)點(diǎn)生成后，對(duì)應(yīng)值為1的節(jié)點(diǎn)繼續(xù)重復(fù)上述步驟，直到節(jié)點(diǎn)值為0或者分割矩陣元素個(gè)數(shù)為k2為止.

生成的k2-tree，按照從根節(jié)點(diǎn)到葉節(jié)點(diǎn)，從左到右的順序?qū)⑺泄?jié)點(diǎn)值連接成一個(gè)二進(jìn)制的壓縮位串. 同樣，壓縮位串中仍然有很多連續(xù)的1或0，為了縮小存儲(chǔ)空間，繼續(xù)對(duì)這個(gè)位串利用RLE進(jìn)行壓縮.如圖2，經(jīng)過一級(jí)壓縮后形成的位串為1101011010010101001100110010001000010010，二級(jí)壓縮后為“［1］2 1 1 1 2 1 1 2 1 1 1 1 1 2 2 2 2 2 1 3 1 4 1 2 1 1”.

當(dāng)已知檢索謂語時(shí)，需要在上述的壓縮串中根據(jù)已知主語查找對(duì)應(yīng)賓語，或者已知賓語查找對(duì)應(yīng)主語. 以檢索主語為例，壓縮串檢索算法步驟如下：

步驟1：判斷檢索主語與矩陣中哪些子矩陣相關(guān)，同時(shí)記錄關(guān)聯(lián)子矩陣對(duì)應(yīng)列的起始位置；

步驟2：在壓縮串中獲取子矩陣壓縮串，同時(shí)尋找主語對(duì)應(yīng)的子矩陣；

步驟3：重復(fù)上述方法，當(dāng)搜索到葉子節(jié)點(diǎn)為1，并且滿足與主語關(guān)聯(lián)，則此列對(duì)應(yīng)賓語即為與主語關(guān)聯(lián)的元組的賓語.

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

本文將P-tree索引和CRK2-triples壓縮和檢索算法同RDF-3X（v0.3.8），Bitmat［16］和TripleBit在合成和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).

3.1 數(shù)據(jù)集及環(huán)境設(shè)置

本部分選擇LUBM、SP2Bench合成數(shù)據(jù)集和Uniprot真實(shí)數(shù)據(jù)集，同時(shí)這三種數(shù)據(jù)集又對(duì)應(yīng)設(shè)計(jì)了相應(yīng)的標(biāo)準(zhǔn)查詢測(cè)試語句，表1 給出了每個(gè)數(shù)據(jù)集的詳細(xì)信息. 本文利用C++程序設(shè)計(jì)語言編寫索引生成代碼，用G++編譯，選擇O2優(yōu)化等級(jí)進(jìn)行優(yōu)化. 運(yùn)行環(huán)境PC機(jī)配置：Intel Xeon 2.00 GHz處理器，20 GB內(nèi)存.考慮到緩存，本文每個(gè)查詢都執(zhí)行三次，取平均結(jié)果以避免OS的影響.

表1 數(shù)據(jù)集

3.2 查詢性能

表2和表3顯示了幾種索引存儲(chǔ)方案在LUBM數(shù)據(jù)集上執(zhí)行SPARQL查詢反應(yīng)時(shí)間. 從表中可以看出，本文的編碼索引樹P-tree與CRK2-triples的查詢反應(yīng)時(shí)間，尤其是在執(zhí)行復(fù)雜查詢時(shí)的時(shí)間效率比其它三種索引結(jié)構(gòu)更有優(yōu)勢(shì). 分析原因：（i）本文基于完整路徑構(gòu)建的P-tree索引是一種路徑邊的組合索引，通過它可以過濾大量不相關(guān)元組，縮小檢索范圍；（ii）本文提出的壓縮存儲(chǔ)及其對(duì)應(yīng)存儲(chǔ)模式下的直接檢索，使相同內(nèi)存情況下CRK2-triples加載更多的查詢數(shù)據(jù)，降低了I/O代價(jià)；另外，基于完整路徑的檢索，使大多數(shù)連接僅發(fā)生在很小一部分元組中間，也降低了最終結(jié)果連接的數(shù)量，同時(shí)提高了查詢效率.

在表2和表3數(shù)據(jù)顯示P-tree檢索大規(guī)模數(shù)據(jù)集時(shí)更有效. 如LUBM50和LUBM2000數(shù)據(jù)集執(zhí)行結(jié)果中，采用RDF-3X索引查詢時(shí)間跳躍性很大，尤其是復(fù)雜查詢Q1和Q3. 但CRK2-triples的最大變化卻很平穩(wěn). 原因是RDF-3X需要解壓加載多種索引，當(dāng)數(shù)據(jù)增加時(shí)，時(shí)間代價(jià)變大. 而基于元組的Bitmat和TripleBit，產(chǎn)生的中間結(jié)果要高于CRK2-triples，因此查詢性能也就低于CRK2-triples.

表2 LUBM50查詢反應(yīng)時(shí)間（秒）

表3 LUBM2000查詢反應(yīng)時(shí)間（秒）

Unirpot數(shù)據(jù)集的元組規(guī)模達(dá)到7億條. Bitmat使用本文提供的硬件環(huán)境得不到查詢結(jié)果. 因此表4只對(duì)比了RDF-3X、TripleBit和STLIS三種方法的查詢時(shí)間. 由于很多元組之間的連接操作是在執(zhí)行P-tree檢索后的路徑集合中完成的，導(dǎo)致參與連接的中間結(jié)果集很小，所以同基于元組的過濾相比，CRK2-triples在路徑模板樹的過濾效果要好于其它兩種.

表4 Uniprot查詢效率（秒）

我們同樣在數(shù)據(jù)集SP2Bench上執(zhí)行查詢，表5列出了各個(gè)查詢的執(zhí)行時(shí)間. 由于SP2Bench數(shù)據(jù)集規(guī)模很小，大多數(shù)查詢的中間結(jié)果都能一次性加載入內(nèi)存，因此STLIS執(zhí)行查詢的優(yōu)勢(shì)沒有在LUBM數(shù)據(jù)集上明顯，由此也驗(yàn)證了STLIS對(duì)大規(guī)模數(shù)據(jù)集的有效性.

表5 SP2B-100M查詢效率（秒）

3.3 存儲(chǔ)空間對(duì)比

本文比較了四種索引的存儲(chǔ)空間，本文存儲(chǔ)空間包含存儲(chǔ)數(shù)據(jù)集和索引所消耗的存儲(chǔ)空間. 除了Bitmat，其它的三個(gè)索引方案中均包含節(jié)點(diǎn)的字典工具. 表6列出了各存儲(chǔ)方案在不同數(shù)據(jù)集上所消耗的存儲(chǔ)空間. 其中在所有數(shù)據(jù)集上，CRK2-triples所耗費(fèi)的存儲(chǔ)空間都低于RDF-3X. 原因是RDF-3X包含6個(gè)聚類索引和9個(gè)聚集索引，因此，RDF-3X是一種以空間換時(shí)間的索引. 另外，隨著數(shù)據(jù)規(guī)模的增加，RDF-3X和Bit?mat存儲(chǔ)空間較CRK2-triples增加迅速. 因而CRK2-triples更加合適大規(guī)模數(shù)據(jù). LUBM和SP2Bench的謂語數(shù)量較小導(dǎo)致分解后的完整路徑相似性較大，降低了元組副本量，所以CRK2-tree和TripleBit在這兩個(gè)數(shù)據(jù)集上的存儲(chǔ)空間相差不大.

表6 存儲(chǔ)空間（GB）

4 結(jié) 論

本文針對(duì)基于元組模式索引知識(shí)圖譜時(shí)產(chǎn)生的頻繁連接和數(shù)據(jù)冗余問題，提出一種基于路徑檢索的索引樹P-tree. P-tree通過分解RDF有向圖，得到從源點(diǎn)到匯點(diǎn)的完整路徑，然后利用完整路徑邊信息結(jié)合布魯姆過濾器生成路徑編碼，再針對(duì)路徑編碼相似性實(shí)現(xiàn)相似完整路徑的聚類. 對(duì)每一個(gè)聚類集合，結(jié)合位運(yùn)算生成索引樹葉子節(jié)點(diǎn)，采用自底向上方式構(gòu)建而成. 對(duì)于索引樹葉節(jié)點(diǎn)對(duì)應(yīng)的相似完整路徑集合，本文利用k2-tree實(shí)現(xiàn)元組的壓縮存儲(chǔ)，并給出基于CRK2-trriples索引的元組精確匹配.

在實(shí)驗(yàn)中，將所提出的P-tree索引樹及CRK2-triples同現(xiàn)有基于元組的索引存儲(chǔ)方案在時(shí)間和空間性能上進(jìn)行對(duì)比. 實(shí)驗(yàn)結(jié)果表明本文提出的索引方案在處理大規(guī)模復(fù)雜查詢時(shí)更有效. 同時(shí)，CRK2-triples的壓縮存儲(chǔ)方式極大的降低了數(shù)據(jù)存儲(chǔ)空間.