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

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

1 引言

在語(yǔ)義網(wǎng)中，資源描述框架[1]（Resource Description Framework，RDF）是一種基于圖的數(shù)據(jù)模型，用于Web端的信息共享。給定一個(gè)數(shù)據(jù)圖G和一個(gè)模式圖Q，模式匹配（子圖同構(gòu)）問(wèn)題是指搜索數(shù)據(jù)圖G 中所有同構(gòu)于模式圖Q 的數(shù)據(jù)子圖。多模式匹配問(wèn)題是對(duì)模式匹配問(wèn)題的一種擴(kuò)展，其主要的挑戰(zhàn)是多個(gè)模式圖之間的并行策略。為了提高匹配執(zhí)行效率：一方面，對(duì)于存在包含關(guān)系的多個(gè)模式圖，需要避免對(duì)公共查詢子圖的重復(fù)計(jì)算；另一方面，在匹配執(zhí)行過(guò)程中，盡量減少候選數(shù)據(jù)子圖的量。因此，本文提出一種面向RDF 圖的快速多模式匹配方法。

模式匹配問(wèn)題是一種子圖同構(gòu)問(wèn)題。子圖同構(gòu)問(wèn)題是一種典型的NP 完全問(wèn)題，隨著數(shù)據(jù)圖規(guī)模的不斷增大，匹配的時(shí)間效率呈指數(shù)級(jí)變化。在面向RDF 圖匹配處理中，大部分的研究者將RDF 數(shù)據(jù)存儲(chǔ)到關(guān)系表中。Hexastore 采用一種基于索引的解決方案，將RDF 數(shù)據(jù)直接存儲(chǔ)在B+樹(shù)[2]。SW-Store 通過(guò)模式集合中的常量標(biāo)簽將RDF數(shù)據(jù)存儲(chǔ)到一系列的垂直分片表中[3]，然后，通過(guò)構(gòu)建關(guān)系表的索引快速地定位到需求的表。Jena 和Sesame 是基于圖數(shù)據(jù)庫(kù)的思想[4-5]，其抽離出RDF數(shù)據(jù)的概念構(gòu)成屬性表?；陉P(guān)系表的研究者采用了相似的匹配策略。首先，其通過(guò)模式集合的有界標(biāo)簽來(lái)縮減對(duì)數(shù)據(jù)關(guān)系表的搜索空間；其次，過(guò)濾表中不需要的RDF數(shù)據(jù)，以便于達(dá)到對(duì)局部結(jié)果的存儲(chǔ)，降低匹配處理過(guò)程的執(zhí)行代價(jià)；最后，對(duì)局部結(jié)果進(jìn)行連接運(yùn)算，最終形成匹配的子圖集合。然而，由于RDF數(shù)據(jù)的索引構(gòu)建和預(yù)處理會(huì)有大量的時(shí)間消耗，因此，對(duì)于RDF數(shù)據(jù)的匹配處理具有相當(dāng)大的延遲。

面向一般圖的子圖同構(gòu)算法主要分為三類，基于樹(shù)搜索[6-7]、基于約束傳播[8-9]和基于圖索引[10-11]的子圖同構(gòu)算法。其中，基于圖索引的子圖同構(gòu)算法與基于關(guān)系表的模式匹配算法類似，通過(guò)構(gòu)建圖索引，減少搜索空間，快速搜索到模式圖的匹配子圖。然而，這種方法需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行全存儲(chǔ)，從而導(dǎo)致大量的時(shí)間消耗和存儲(chǔ)代價(jià)?；跇?shù)搜索的子圖同構(gòu)算法利用可行性規(guī)則對(duì)一個(gè)樹(shù)型搜索空間中不需要的候選集進(jìn)行裁剪，以達(dá)到快速匹配的目的?；诩s束傳播的子圖同構(gòu)算法是將子圖同構(gòu)問(wèn)題同構(gòu)于約束傳播問(wèn)題，其目的是找尋那些分配到滿足共同約束的變量集中的值。其主要的思想是基于局部約束的傳播特性，節(jié)點(diǎn)或者邊的一致性會(huì)傳播到圖中的其他部分。因此，在圖中只有很少的候選集被保留。

多模式匹配問(wèn)題是對(duì)模式匹配的一種擴(kuò)展，其主要的挑戰(zhàn)是多個(gè)模式圖之間的并行執(zhí)行策略。多模式匹配處理過(guò)程主要包括多模式圖匹配序列優(yōu)化和匹配策略。多模式圖匹配序列優(yōu)化一般通過(guò)計(jì)算多個(gè)模式圖之間的包含關(guān)系構(gòu)建多模式圖的依賴圖或者依賴樹(shù)。文獻(xiàn)[12]通過(guò)計(jì)算多個(gè)模式圖之間的包含關(guān)系，生成最小依賴樹(shù)，并利用依賴樹(shù)的執(zhí)行序列進(jìn)行多模式匹配，一定程度上減少了候選集規(guī)模。文獻(xiàn)[13]提出多模式圖的依賴圖構(gòu)建和優(yōu)化方法，其通過(guò)一個(gè)啟發(fā)式算法制定模式圖執(zhí)行序列，減少了冗余計(jì)算以及候選集緩存。多模式圖匹配策略主要的挑戰(zhàn)是候選集的計(jì)算代價(jià)。文獻(xiàn)[14]提出一個(gè)動(dòng)態(tài)解決方法。該方法能夠避免形成冗余候選集，并且可以在形成最大候選集之前到達(dá)結(jié)果集。文獻(xiàn)[15]提出一種最大公共子圖的優(yōu)化算法，通過(guò)代價(jià)模型計(jì)算確保匹配代價(jià)最小。文獻(xiàn)[16]通過(guò)提出的三元節(jié)點(diǎn)標(biāo)簽序列計(jì)算分組因子，從而得到模式包含映射，通過(guò)模式包含映射得到模式執(zhí)行序列。

本文提出一種面向RDF 圖的快速多模式匹配算法。首先，在D-Tree 構(gòu)建算法中加入剪枝策略，通過(guò)剪枝策略使得構(gòu)建的D-Tree最優(yōu)。其次，提出節(jié)點(diǎn)分片表的概念。為了編排多個(gè)模式圖之間的執(zhí)行序列，構(gòu)建了一種多模式圖的依賴樹(shù)。然而，包含關(guān)系是一種單一、抽象的表示，它不足以表示多個(gè)查詢節(jié)點(diǎn)間的交叉關(guān)系。因此，提出了一個(gè)NFT的概念，用來(lái)表示節(jié)點(diǎn)間的執(zhí)行關(guān)系。最后，提出一個(gè)基于D-Tree 和NFT 的多模式匹配算法，通過(guò)遍歷一次RDF 數(shù)據(jù)圖就可以得到多個(gè)模式圖匹配的數(shù)據(jù)子圖。當(dāng)然，本文方法同樣適用其他的所有有標(biāo)簽、無(wú)標(biāo)簽的圖結(jié)構(gòu)，對(duì)于無(wú)標(biāo)簽的圖，可以對(duì)其定點(diǎn)和邊進(jìn)行唯一標(biāo)識(shí)。如通過(guò)統(tǒng)一字典編碼技術(shù)對(duì)屬性圖編碼等。

2 依賴樹(shù)和節(jié)點(diǎn)分片表

2.1 問(wèn)題定義

定義1（基本模式圖）一個(gè)基本模式圖p(Vp,Ep,Lp,?p,varp)是一個(gè)有向標(biāo)簽圖，其中Vp表示節(jié)點(diǎn)集；Ep表示有向邊集；是一個(gè)有向函數(shù)，表示從u到v的一條有向邊，其中u,v∈Vp；Lp表示邊和節(jié)點(diǎn)標(biāo)簽集；varp表示一個(gè)標(biāo)簽變量集；表示一個(gè)將節(jié)點(diǎn)和邊映射到對(duì)應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。在一個(gè)模式集中，不存在任意一個(gè)模式圖同構(gòu)于模式p，則p為基本圖模式。

定義2（數(shù)據(jù)圖）一個(gè)數(shù)據(jù)圖是一個(gè)有向標(biāo)簽圖，其中Vd表示節(jié)點(diǎn)集；Ed表示多個(gè)有向邊集；是一個(gè)有向函數(shù)，表示從u到v的一條有向邊，其中u,v∈Vd；Ld表示邊和節(jié)點(diǎn)標(biāo)簽集；?d:Vd?Ed→Ld表示一個(gè)將節(jié)點(diǎn)和邊映射到對(duì)應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。

基本模式圖與數(shù)據(jù)圖區(qū)別在基本模式圖的標(biāo)簽可以為變量，變量標(biāo)簽指的是常量標(biāo)簽的一個(gè)集合，也可以稱為標(biāo)簽的值域。因此，給定一個(gè)常量標(biāo)簽c和一個(gè)變量標(biāo)簽v，如果c是v值域內(nèi)的一個(gè)常量，那么c∈v。

定義3（子圖同構(gòu)）給定一個(gè)基本模式圖p(Vp,Ep,Lp,?p,varp)和一個(gè)數(shù)據(jù)圖當(dāng)且僅當(dāng)存在一個(gè)雙射函數(shù)f:Vp→Vd滿足：

子圖同構(gòu)處理方法是找尋所有滿足子圖同構(gòu)的節(jié)點(diǎn)對(duì)。給定一個(gè)基本模式圖中節(jié)點(diǎn)vp和數(shù)據(jù)圖中的節(jié)點(diǎn)vd，如果f(vp)=vd并且滿足定義3中（1）和（2），那么搜索到的節(jié)點(diǎn)對(duì)為(vp,vd)。多模式匹配問(wèn)題是對(duì)模式匹配的一個(gè)擴(kuò)展，其側(cè)重于多個(gè)模式圖之間的并行執(zhí)行策略。因此，避免多個(gè)模式圖之間的重復(fù)計(jì)算問(wèn)題是本文研究的重點(diǎn)。

定義4（多模式匹配問(wèn)題）給定一個(gè)基本模式圖集和一個(gè)數(shù)據(jù)圖d，m∈N+。給定任意的一個(gè)基本模式圖p∈P，多模式匹配指的是依次地搜索d中同構(gòu)于p所有匹配的數(shù)據(jù)子圖。

圖1 描述的是多個(gè)模式圖以及它們之間的公共子圖。圖（a）表示多個(gè)基本模式圖，圖中符號(hào)分別表示頂點(diǎn)和邊的標(biāo)簽，“？”表示當(dāng)前標(biāo)簽為變量。任意一個(gè)基本模式圖都不同構(gòu)于其他的基本模式圖。圖（b）表示多個(gè)基本模式圖的公共子圖，其中p6為模式圖p1、p2、p4和p5的公共子圖。

圖1 基本模式圖及其公共子圖

2.2 依賴樹(shù)

依賴樹(shù)的構(gòu)建能夠清晰地描繪出多個(gè)基本模式圖之間的依賴關(guān)系。大部分研究者通過(guò)計(jì)算多個(gè)基本模式圖之間的公共查詢子圖，依靠基本模式圖與公共查詢子圖的包含關(guān)系構(gòu)建依賴樹(shù)和依賴圖。然而，并不是所有的公共查詢子圖都要構(gòu)建到最終的依賴樹(shù)或者依賴圖中的，因?yàn)楣膊樵冏訄D可能存在重疊的部分或者多個(gè)公共查詢子圖依賴一個(gè)相同的基本模式圖集。因此，提出一種公共子圖的裁剪策略。

依賴樹(shù)的構(gòu)建過(guò)程主要包括依賴圖的生成和生成樹(shù)的構(gòu)建。依賴圖的生成是通過(guò)計(jì)算多個(gè)基本模式圖之間的公共查詢子圖，依靠基本模式圖與公共查詢子圖的包含關(guān)系構(gòu)建依賴圖，生成樹(shù)的構(gòu)建是通過(guò)代價(jià)評(píng)估模型對(duì)依賴圖的剪枝操作，為了能夠清晰地表述出代價(jià)評(píng)估模式，給出了殘差圖的定義。

定義5（殘差圖）給定兩個(gè)模式圖pa和pb，并且pa子圖同構(gòu)于pb，那么pb相對(duì)于pa的殘差圖為pb-pa，包含pb中除去子圖同構(gòu)于pa部分后剩余部分的節(jié)點(diǎn)和邊。這些頂點(diǎn)和邊被稱之為殘差點(diǎn)和殘差邊。依賴樹(shù)索引構(gòu)建過(guò)程分為以下幾步：

（1）依賴圖生成（算法1，2～9 行），目的是找到模式間的包含關(guān)系。首先采用子圖同構(gòu)算法找尋多個(gè)基本模式圖的子圖同構(gòu)關(guān)系，若存在子圖同構(gòu)關(guān)系，則構(gòu)造它們之間的依賴關(guān)系。若不存在子圖同構(gòu)關(guān)系，則計(jì)算多個(gè)基本模式圖之間的公共查詢子圖，然后構(gòu)造基本模式圖與公共查詢子圖之間的依賴關(guān)系。

圖1 所示的模式圖集構(gòu)建的依賴圖如圖2（a）所示。依賴圖為一個(gè)有向圖，圖中每條邊連接的兩個(gè)節(jié)點(diǎn)間具有子圖同構(gòu)關(guān)系，如p1子圖同構(gòu)于p4。圖（a）中，p6也子圖同構(gòu)于p4，但是由于p6通過(guò)p1連接到p4，因此省略p6指向p4的邊。圖中實(shí)線節(jié)點(diǎn)表示模式集中存在的節(jié)點(diǎn)，虛線節(jié)點(diǎn)表示加入到模式集中的最大公共子圖。

圖2 依賴樹(shù)構(gòu)建過(guò)程

算法1 BuildDTree(P,?)

Input：pattern graph setP={p1,p2,…,pn}，user specified parameter for VFT building

Output：D-Tree

1.InitialT=?

2.for each petternpiinPdo

3. for each patternpjinPdo

4.if（SubgraphIsomorphism(pi,pj)）then

7. end if

8. end for

9.end for

10.CutRedundantEdge(T)

11.ReturnT

依賴圖構(gòu)建時(shí)間復(fù)雜度為O(N2)，N為模式圖的個(gè)數(shù)。

（2）代價(jià)評(píng)估模型，目的是對(duì)依賴圖的冗余節(jié)點(diǎn)和邊進(jìn)行裁剪操作。根據(jù)定義5，生成樹(shù)的代價(jià)函數(shù)表示為：

其中，eij為基本模式圖pi到pj的一條有向邊和表示中節(jié)點(diǎn)和邊的數(shù)量。?為人為給定的參數(shù)。通過(guò)公式（1），可以為每條邊賦予一個(gè)代價(jià)，表示基于pi的匹配結(jié)果執(zhí)行pj匹配的代價(jià)。為了對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估，本文設(shè)計(jì)了一個(gè)權(quán)重函數(shù)，對(duì)虛線節(jié)點(diǎn)代價(jià)評(píng)估。權(quán)重函數(shù)構(gòu)建為：

定義6（可裁剪節(jié)點(diǎn)）給定虛線節(jié)點(diǎn)pi，若其滿足以下條件：①；②，則稱其為可裁剪節(jié)點(diǎn)。其中，parent[pj]表示pj的父親節(jié)點(diǎn)。

例1（可裁剪節(jié)點(diǎn)舉例）如圖2 所示，節(jié)點(diǎn)p6有兩個(gè)孩子節(jié)點(diǎn)分別為p1、p2，p1有兩個(gè)父親節(jié)點(diǎn)分別為p6、p7，p2有兩個(gè)父親節(jié)點(diǎn)分別為p6、p8，因此p6滿足定義6 中兩條約束為可裁剪節(jié)點(diǎn)，在其同一層次中p7、p8也為可裁剪節(jié)點(diǎn)。

（3）依賴樹(shù)構(gòu)建，目的是為了最小化整體的匹配代價(jià)，減少重復(fù)計(jì)算。這一步對(duì)依賴圖進(jìn)行節(jié)點(diǎn)和邊的裁剪，裁剪后的依賴圖稱為依賴樹(shù)。裁剪節(jié)點(diǎn)時(shí)，由于虛線節(jié)點(diǎn)不需要結(jié)果集的輸出，因此只對(duì)虛線節(jié)點(diǎn)及其相連的邊進(jìn)行裁剪。由出度為零的節(jié)點(diǎn)出發(fā)向上遍歷，若某個(gè)節(jié)點(diǎn)為可裁剪節(jié)點(diǎn)，且同層次（從根節(jié)點(diǎn)向下遍歷路徑長(zhǎng)度相同的節(jié)點(diǎn)為同一層次）上有多個(gè)可裁剪節(jié)點(diǎn)時(shí)，比較這些節(jié)點(diǎn)的權(quán)重，將權(quán)重最大的節(jié)點(diǎn)裁剪掉，直到這一層無(wú)可裁剪節(jié)點(diǎn)為止。重復(fù)此裁剪過(guò)程，直到依賴圖中不存在可裁剪節(jié)點(diǎn)，則停止裁剪。圖2（a）中可裁剪節(jié)點(diǎn)為p6、p7、p8，設(shè) ?=0.5，則分別為4.5、3.5、5，p8權(quán)重最大，將p8及其相連節(jié)點(diǎn)裁剪，此時(shí)p6、p7不再是可裁剪節(jié)點(diǎn)，且同層以及依賴圖都無(wú)可裁剪節(jié)點(diǎn)，則停止裁剪，得到圖2（b）。裁剪邊時(shí)，使用最小生成樹(shù)算法，對(duì)于每個(gè)節(jié)點(diǎn)只保留代價(jià)最小的入度邊，以此保證每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。裁剪邊后得到圖2（c）。時(shí)間復(fù)雜度為O(N)，N為模式圖的個(gè)數(shù)。

依賴樹(shù)的存儲(chǔ)引入了模式邊表（圖3）的形式。模式邊表（PE 表）分為三列，第一列表示所有依賴樹(shù)中的節(jié)點(diǎn)（基本模式圖或者公共模式圖），第二列表示第一列中節(jié)點(diǎn)的父節(jié)點(diǎn)，第三列表示第一列中節(jié)點(diǎn)與第二列中父節(jié)點(diǎn)的殘差邊。

圖3 模式邊表

2.3 節(jié)點(diǎn)分片表

依賴樹(shù)是對(duì)多個(gè)基本模式圖之間依賴關(guān)系的一種描述。這種依賴關(guān)系可以以理解為對(duì)殘差邊的抽象。通過(guò)這些依賴關(guān)系可以有效地制定多個(gè)基本模式圖之間的執(zhí)行序列。然而，很難在這些單一的，抽象的依賴關(guān)系中發(fā)掘出有助于匹配效率的輔助信息。因此，提出了一個(gè)可以細(xì)化、實(shí)例化依賴關(guān)系的節(jié)點(diǎn)分片表。首先，給出了內(nèi)部邊和外部邊的定義。

定義7（內(nèi)部邊和外部邊）由D-Tree根節(jié)點(diǎn)依次向下遍歷，給定兩個(gè)模式圖p1、p2，p1∈D-Tree，p2∈D-Tree且。存在節(jié)點(diǎn)，且存在節(jié)點(diǎn)，，邊e(u,v)為節(jié)點(diǎn)u、v的內(nèi)部邊，記為i-edge。存在節(jié)點(diǎn)，且存在節(jié)點(diǎn)則為節(jié)點(diǎn)u的外部邊，節(jié)點(diǎn)w的內(nèi)部邊，記為o-edge。

NFT由內(nèi)部節(jié)點(diǎn)片表（簡(jiǎn)寫(xiě)為iNFT）和外部節(jié)點(diǎn)分片表（簡(jiǎn)寫(xiě)為oNFT）組成，其中包含內(nèi)部邊的為iNFT和包含外部邊的為oNFT。NFT 包含兩列：節(jié)點(diǎn)和邊。在NFT 每行中，節(jié)點(diǎn)列只存放一個(gè)節(jié)點(diǎn)v，邊列存放與v節(jié)點(diǎn)相連的內(nèi)部或外部邊，因此iNFT和oNFT被形式化為和

NFT 是基于D-Tree 構(gòu)建的（算法2、算法3）。在DTree 中，由于沒(méi)有其他節(jié)點(diǎn)同構(gòu)于根節(jié)點(diǎn)，因此根節(jié)點(diǎn)的節(jié)點(diǎn)和邊被直接存入iNFT 中（算法3 的5、6 行）。給定一個(gè)節(jié)點(diǎn)p1（不是根節(jié)點(diǎn)），它的父親節(jié)點(diǎn)p2和一個(gè)節(jié) 點(diǎn)u∈Vp2，存 在 節(jié) 點(diǎn)v∈Vp1，使 得e(u,v)∈Ep1，，則為u的外部邊，v的內(nèi)部邊。u和被存入oNFT（算法3的8、9行），v和e(u,v)被存入iNFT。算法偽代碼如下：

算法2 NFT(P,?)

Input：pattern graph setP={p1,p2,…,pn}，user specified parameter for NFT building

Output：NFT={nft1,nft2,…,nftn}

1.Initial NFT=?

2.T=BuildPatternTree(P,?)

3.P← {b|a=root，child[a]}

4.for each patternpinPdo

5.nft←sub-NFT(p,T,NFT)

6. NFT←NFT ∪nft

7.end for

8.return NFT

例2（NFT 構(gòu)建過(guò)程舉例） 圖 2 為 D-Tree 構(gòu)建的構(gòu)建過(guò)程，圖4表示的是NFT表。p9：由于p9為根節(jié)點(diǎn)，p9中節(jié)點(diǎn)？B、？D以及邊e4被存入iNFT中。p6：對(duì)于p9中節(jié)點(diǎn) ？B，在p6中存在節(jié)點(diǎn)？E，使得e2={?B,，因此e2為節(jié)點(diǎn)？B的外部邊；對(duì)于p6中節(jié)點(diǎn)？E，在p6中存在節(jié)點(diǎn)？B，使得，因此e2為節(jié)點(diǎn)？E的內(nèi)部邊。

圖4 節(jié)點(diǎn)分片表

3 多模式匹配算法

描述多模式匹配算法前，首先給定基本模式圖與數(shù)據(jù)圖之間的節(jié)點(diǎn)關(guān)系。給定數(shù)據(jù)圖中的任意節(jié)點(diǎn)vd，模式圖中存在節(jié)點(diǎn)vp與vd匹配，則vd是vp的一個(gè)實(shí)例，被表示為節(jié)點(diǎn)對(duì)(vp,vd)。給定數(shù)據(jù)圖的任意兩個(gè)節(jié)點(diǎn)，模式圖中存在節(jié)點(diǎn)，滿足的一個(gè)實(shí)例，的一個(gè)實(shí)例，且的一個(gè)三元組實(shí)例。

算法3 sub-NFT(P,T,NFT)

Input:pattern graph setP，PatternTreeT，NFT

Output：NFT

1.Initial NFT=?

2.for each patternpinPdo

3. for eachvin patternpdo

4. ifv?NFT then

5.E(v)={e|eu,v,u∈V(v)} is i-edge

6. iNFT (v)←E(v)∪iNFT(v)

7. else

8.E(v)={e|eu,v,u∈V(v)}-iNFT(v) is o-edge

9. oNFT (v)←E(v)∪oNFT(v)

10. end if

11. end for

12. if child[p]≠? then

13.P=child[p]

14. sub-NFT(P,T,NFT)

15. end if

16.end for

17.return NFT

多模式匹配算法基于D-Tree和NFT，多模式匹配結(jié)果是通過(guò)先序遍歷D-Tree 逐步得到的。得到根節(jié)點(diǎn)proot的結(jié)果集分為以下幾步：

（1）給定proot中的一個(gè)固定節(jié)點(diǎn)，在數(shù)據(jù)圖中獲得一個(gè)的實(shí)例節(jié)點(diǎn)vd，并且把它做為一個(gè)初始的數(shù)據(jù)節(jié)點(diǎn)。固定節(jié)點(diǎn)是由和D-Tree得到的。若節(jié)點(diǎn)為固定的，當(dāng)且僅當(dāng)固定節(jié)點(diǎn)由函數(shù)確定。

（2）順序遍歷vd的一階鄰居節(jié)點(diǎn)獲得節(jié)點(diǎn)序，并設(shè)置為下一跳遍歷的初始數(shù)據(jù)節(jié)點(diǎn)。下一跳遍歷數(shù)據(jù)圖時(shí)，給定一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)和由它獲得的節(jié)點(diǎn)，存在節(jié)點(diǎn)vp，滿足是vp的一個(gè)實(shí)例且則被寫(xiě)入p9的結(jié)果集中。若，則被存入臨時(shí)結(jié)果集Temp中。

算法4 Multi-pattern Matching(D,P,?)

Input：pattern graph setP={p1,p2,…,pn} ，Data graph setD={d1,d2,…,dn}；user specified parameter for VFT building

Output：matching set ofp

1.Initialize Temp=? ，VFT=? ，set=?

2.VFT，collectionlable=VFT(P,?)

3.for eachdinDdo

4. get any nodev∈basicpattern ind

5. Temp←addnode(v,d,VFT,Temp)

6. While Temp≠? do

7. while Tempinnode≠?do

8. TraverseInnerNode (Temp,NFT)//遍 歷 內(nèi) 部 節(jié)點(diǎn)，并存到Temp中

9. end while

10. ifTempinnode≠V（basicpattern） then

11. traverse the next data graph

12. end if

13. basicset←d∪ basicset

14. whileTempoutnode≠?do

15. TraverseOuterNode（Temp，NFT）//遍歷外部節(jié)點(diǎn)，并存到Temp中

16. end while

17. ifpiin collectionlable ∈Tempinnodethen

19. end if

21. end while

22.end for

23.return set

（3）執(zhí)行proot匹配，直到?jīng)]有新的三元組實(shí)例被加入到結(jié)果集中。

孩子節(jié)點(diǎn)結(jié)果集獲得過(guò)程不同于根節(jié)點(diǎn)，需要通過(guò)父親節(jié)點(diǎn)的結(jié)果集和臨時(shí)結(jié)果集來(lái)獲得，主要分為以下幾步：

（1）將父親節(jié)點(diǎn)的結(jié)果集復(fù)制到孩子節(jié)點(diǎn)中。

（2）給定孩子節(jié)點(diǎn)pchild的一個(gè)固定節(jié)點(diǎn)，在數(shù)據(jù)圖中找到的一個(gè)實(shí)例節(jié)點(diǎn)vd，并把它做為臨時(shí)結(jié)果集中的初始節(jié)點(diǎn)。若節(jié)點(diǎn)為固定的，當(dāng)且僅當(dāng)固定節(jié)點(diǎn)由函數(shù)確定。

（3）順序遍歷vd的一階鄰居節(jié)點(diǎn)獲得臨時(shí)結(jié)果集的節(jié)點(diǎn)序，并設(shè)置為下一跳遍歷的初始數(shù)據(jù)節(jié)點(diǎn)。下一跳遍歷臨時(shí)結(jié)果集時(shí)，給定一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)和由他獲得的節(jié)點(diǎn)，存在模式節(jié)點(diǎn)vp，滿足是vp的一個(gè)實(shí)例且，則被寫(xiě)入pchild的結(jié)果集中。在臨時(shí)結(jié)果集上重復(fù)執(zhí)行一跳遍歷，直到?jīng)]有新的三元組實(shí)例被添加到臨時(shí)結(jié)果集中。

（4）將臨時(shí)結(jié)果集上最終的初始化數(shù)據(jù)節(jié)點(diǎn)做為數(shù)據(jù)圖上的初始數(shù)據(jù)節(jié)點(diǎn)，并執(zhí)行（2）、（3）兩步獲得孩子節(jié)點(diǎn)結(jié)果集。

（5）重復(fù)執(zhí)行（1）～（4）直到獲得所有模式的結(jié)果集為止。

圖5 面向RDF圖多模式匹配過(guò)程

例3（面向RDF 圖多模式匹配過(guò)程）多模式匹配過(guò)程如圖5 所示。圖（a）表示一個(gè)待匹配的數(shù)據(jù)圖，圖（b）、（c）表示D-Tree進(jìn)行多模式匹配過(guò)程中結(jié)果集的變化，其中Result表示結(jié)果集，Temp表示臨時(shí)結(jié)果集。

p9：由于p9是D-Tree的根節(jié)點(diǎn)，它的匹配過(guò)程只需要借助內(nèi)部表。首先，，從?C、?D中任意選擇一個(gè)節(jié)點(diǎn)做為固定模式節(jié)點(diǎn)。假設(shè)?B為固定模式節(jié)點(diǎn)，在數(shù)據(jù)圖中b1為?B的實(shí)例節(jié)點(diǎn)，并把b1設(shè)置為一個(gè)（a）的初始數(shù)據(jù)節(jié)點(diǎn)。通過(guò)一跳遍歷b1，三元組實(shí)例被寫(xiě)入p9的結(jié)果集中，三元組實(shí)例被寫(xiě)入臨時(shí)結(jié)果集。之后，順序的得到d1、d2并將它們?cè)O(shè)置為下一次遍歷的初始節(jié)點(diǎn)。通過(guò)一跳遍歷d1、d2，三元組實(shí)例被寫(xiě)入p9的結(jié)果集中，三元組實(shí)例被寫(xiě)入臨時(shí)結(jié)果集中。

p6：p6的匹配過(guò)程需要借助內(nèi)部表和外部表。由于p6為p9的父節(jié)點(diǎn)，把p9的結(jié)果復(fù)制到p6的結(jié)果集中。圖5中由于圖片大小問(wèn)題，將不復(fù)制結(jié)果，只顯示新遍歷得到的結(jié)果。首先，由公式得到固定節(jié)點(diǎn)為?B，b1為?B的實(shí)例節(jié)點(diǎn)，并把b1設(shè)置為臨時(shí)結(jié)果集的一個(gè)初始數(shù)據(jù)節(jié)點(diǎn)。通過(guò)一跳遍歷b1，三元組實(shí)例被寫(xiě)入p6的結(jié)果集中，之后獲得節(jié)點(diǎn)e1，由于e1在結(jié)果集中不存在，因此將其做為下一次遍歷的初始節(jié)點(diǎn)。由于，三元組實(shí)例被寫(xiě)入p6的結(jié)果集中。至此，p6的結(jié)果集便得到了。其他模式的模式匹配過(guò)程與p6相似。通過(guò)M-PM 算法，通過(guò)遍歷一次數(shù)據(jù)集便可得到所有模式圖的結(jié)果集。

將本文多模式匹配算法分別與基本多模式匹配算法、文獻(xiàn)[12]的多模式匹配算法以及文獻(xiàn)[16]多模式優(yōu)化算法進(jìn)行比較。其中，基本多模式匹配思想是將DTree 中父節(jié)點(diǎn)的匹配結(jié)果集做為其孩子節(jié)點(diǎn)的輸入的局部結(jié)果集，因此，它能夠很好地降低父節(jié)點(diǎn)與孩子節(jié)點(diǎn)之間重疊部分的計(jì)算。假設(shè)模式圖集大小為n，數(shù)據(jù)集數(shù)量（指三元組模式的數(shù)量）為m，基本多模式匹配的時(shí)間復(fù)雜度為。文獻(xiàn)[12]中多模式匹配算法（MPT），分為基本模式匹配和擴(kuò)展模式匹配兩步，每次將基本模式的匹配結(jié)果集作為擴(kuò)展模式匹配的輸入，因此仍然有一部分?jǐn)?shù)據(jù)圖需要多次遍歷，時(shí)間復(fù)雜度為，且其每次都需要對(duì)中間結(jié)果進(jìn)行保存，大大增加了空間復(fù)雜度，其空間復(fù)雜度為。而此多模式匹配算法不需要對(duì)中間結(jié)果進(jìn)行保存。文獻(xiàn)[16]中多查詢優(yōu)化算法（MQO），通過(guò)模式包含映射確定一個(gè)多模式匹配序列，匹配時(shí)多個(gè)父模式的匹配結(jié)果集作為子模式的匹配數(shù)據(jù)集，因此時(shí)間復(fù)雜度為同時(shí)需要對(duì)中間結(jié)果進(jìn)行緩存，空間復(fù)雜度為。本文多模式匹配算法的時(shí)間復(fù)雜度為因此本文的多模式匹配效率高于其他三個(gè)多模式匹配算法。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

基本模式圖集。在選擇模式集時(shí)，基本模式圖之間的殘差圖是一個(gè)重要影響因素。在D-Tree 中，非葉節(jié)點(diǎn)的殘差圖與模式子圖重疊部分相關(guān)聯(lián)。D-Tree 的深度不斷增加，越靠近根節(jié)點(diǎn)的模式圖，匹配執(zhí)行的次數(shù)越多。

數(shù)據(jù)集：實(shí)驗(yàn)中，選擇一個(gè)仿真數(shù)據(jù)集。DBpedia 2015A描述了運(yùn)動(dòng)和運(yùn)動(dòng)事件的相關(guān)信息，它包含20個(gè)三元組模式的30 000多個(gè)RDF三元組實(shí)例。由于現(xiàn)有較大的真實(shí)數(shù)據(jù)集中三元組模式種類較少（如DBpedia、WikiData、YAGO），很難反映模式圖殘差邊數(shù)量對(duì)多模式匹配效率的影響，因此，對(duì)三元組模式圖進(jìn)行了仿真擴(kuò)展，用于提高三元組模式的維度，生成了一個(gè)基于DBpedia 2015A的仿真數(shù)據(jù)集，它包括300個(gè)三元組模式的300萬(wàn)個(gè)RDF三元組實(shí)例。

為了得出多模式匹配與D-Tree深度、寬度以及殘差邊數(shù)量之間的關(guān)系，同時(shí)為了更準(zhǔn)確的進(jìn)行實(shí)驗(yàn)，合成的數(shù)據(jù)集要符合現(xiàn)實(shí)世界中觀察到的一般特征，如模式、結(jié)構(gòu)、大小、分布等。在生成仿真數(shù)據(jù)集時(shí)，首先采用文獻(xiàn)[17]中的方法對(duì)原始數(shù)據(jù)進(jìn)行一定的擴(kuò)展，為某些實(shí)例引入新的謂詞，增加三元組模式的個(gè)數(shù)，同時(shí)刪除某些三元組，這個(gè)過(guò)程生成了更加現(xiàn)實(shí)和復(fù)雜的數(shù)據(jù)集，增加了邊的多樣性，符合現(xiàn)實(shí)世界的現(xiàn)狀和特征。

其次，采用一個(gè)隨機(jī)生成器對(duì)上一步生成的數(shù)據(jù)集進(jìn)行規(guī)模擴(kuò)展。以數(shù)據(jù)圖節(jié)點(diǎn)數(shù)N和最終數(shù)據(jù)集大小S作為輸入，每次隨機(jī)選擇S/N個(gè)節(jié)點(diǎn)作為核心數(shù)據(jù)節(jié)點(diǎn)，對(duì)于每個(gè)核心數(shù)據(jù)節(jié)點(diǎn)v，選擇10～15 個(gè)與v距離為5 跳的節(jié)點(diǎn)，并且用邊將它們隨機(jī)連接起來(lái)，重復(fù)多次，直到達(dá)到需要的數(shù)據(jù)大小。

實(shí)驗(yàn)配置：實(shí)驗(yàn)環(huán)境為Intel Xeon 5118，擁有24 GB RAM。

4.2 實(shí)驗(yàn)分析

在自己生成的仿真數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，分析D-Tree具有不同深度、寬度以及深度改變時(shí)的多模式匹配效率。

圖6 描述具有相同深度不同寬度D-Tree 的執(zhí)行時(shí)間，圖7 描述具有相同寬度不同深度D-Tree 的執(zhí)行時(shí)間。根節(jié)點(diǎn)包含80 個(gè)三元組模式，并且每個(gè)孩子節(jié)點(diǎn)比其父親節(jié)點(diǎn)多10 條邊。隨著深度的增加，本文算法時(shí)間消耗與基本多模式匹配算法、MPT算法、MQO算法相比分別提高約70%、50%、30%的時(shí)間效率。由于子圖同構(gòu)是一個(gè)NP 完全問(wèn)題，其隨著數(shù)據(jù)的規(guī)模不斷增加呈現(xiàn)指數(shù)級(jí)的時(shí)間復(fù)雜度，因此，在圖6 和圖7 中，隨著深度和廣度的增加，三元組模式的數(shù)量也在不斷的增加。從線性的變化趨勢(shì)中，可以發(fā)現(xiàn)其近似于指數(shù)型的變化，然而，由于三元組模式圖的數(shù)量遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)圖數(shù)量，因此，實(shí)驗(yàn)線性的指數(shù)型變化不夠明顯。

圖6 不同寬度D-Tree的執(zhí)行時(shí)間

圖7 不同深度D-Tree的執(zhí)行時(shí)間

從圖6和圖7綜合來(lái)看，當(dāng)寬度和深度相同時(shí)，算法執(zhí)行時(shí)間相同，因此算法的執(zhí)行時(shí)間受深度和廣度的影響相似。

采用相同數(shù)量的三元組模式和殘差邊，改變殘差邊在D-Tree中不同深度位置，執(zhí)行時(shí)間如圖8所示。隨著D-Tree深度改變，深度越深，模式間殘差邊越少，本文算法比其他多模式匹配算法波動(dòng)小，更加穩(wěn)定。而其他算法隨著深度的增加，執(zhí)行的時(shí)間消耗呈現(xiàn)增大。因?yàn)椋疃仍礁?，公共部分的重?fù)計(jì)算的次數(shù)越多，然而，其對(duì)本文算法的影響微乎其微。因此，本文算法僅與殘差邊的數(shù)量有關(guān)。

圖8 模式圖深度改變的執(zhí)行時(shí)間

為增加實(shí)驗(yàn)的真實(shí)性和可靠性，在仿真數(shù)據(jù)集Wet-Div 上進(jìn)行對(duì)比實(shí)驗(yàn)，如圖9 所示。WatDiv 是一個(gè)關(guān)于電子商務(wù)的合成數(shù)據(jù)集，包括購(gòu)買(mǎi)產(chǎn)品并撰寫(xiě)評(píng)論的用戶，以及提供產(chǎn)品的零售商等。本文采用擴(kuò)展因子為30，生成有300萬(wàn)個(gè)RDF三元組的數(shù)據(jù)集。

圖9 仿真數(shù)據(jù)集WatDiv實(shí)驗(yàn)

為增加實(shí)驗(yàn)的真實(shí)性和可靠性，同樣在真實(shí)數(shù)據(jù)集YAGO上進(jìn)行對(duì)比實(shí)驗(yàn)（如圖10），采用的數(shù)據(jù)集中包含900多萬(wàn)個(gè)三元組模式。

圖10 真實(shí)數(shù)據(jù)集YAGO實(shí)驗(yàn)

由圖9、10 在仿真數(shù)據(jù)集WatDiv 以及真實(shí)數(shù)據(jù)集YAGO上的實(shí)驗(yàn)可以看出，在仿真和真實(shí)數(shù)據(jù)集上本文算法同樣優(yōu)于其他算法，且算法時(shí)間復(fù)雜度只與殘差邊的多少有關(guān)，與D-Tree的深度、寬度無(wú)關(guān)，當(dāng)深度改變時(shí)本文算法更加穩(wěn)定。

5 結(jié)束語(yǔ)

本文提出了一種面向RDF 圖的多模式匹配方法。為了表示模式間的依賴關(guān)系，減少重復(fù)計(jì)算，它構(gòu)建了樹(shù)形索引結(jié)構(gòu)（依賴樹(shù)），制定了模式間的執(zhí)行序列。同時(shí)利用節(jié)點(diǎn)分片表，表示節(jié)點(diǎn)間的執(zhí)行序列，根據(jù)節(jié)點(diǎn)序和模式序進(jìn)行多模式匹配，進(jìn)一步減少了重復(fù)計(jì)算，而且能在很大程度上提高模式匹配的效率。盡管此種算法很大的優(yōu)點(diǎn)，但仍有許多可改進(jìn)之處，故在今后的研究中會(huì)對(duì)此算法進(jìn)行進(jìn)一步的優(yōu)化并增加真實(shí)數(shù)據(jù)的實(shí)驗(yàn)評(píng)估。