面向圖數(shù)據(jù)的結(jié)構(gòu)化正則路徑查詢方法

邱濤　王嶼涵　鄧國(guó)鵬　孫堯　呂光華　夏秀峰

摘 要：正則路徑查詢是一種應(yīng)用正則表達(dá)式在圖數(shù)據(jù)上進(jìn)行查詢的技術(shù)，通常利用有限狀態(tài)自動(dòng)機(jī)實(shí)現(xiàn)查詢匹配?，F(xiàn)有正則路徑查詢方法的匹配結(jié)果為頂點(diǎn)對(duì)的序列，未能充分保留圖的結(jié)構(gòu)，為了解決這一問題，提出了一種面向圖數(shù)據(jù)的結(jié)構(gòu)化正則路徑查詢方法，通過在不同的序列間加以結(jié)構(gòu)化約束，使得查詢結(jié)果由路徑轉(zhuǎn)變?yōu)樽訄D。為了實(shí)現(xiàn)這一目的，首先定義了一種結(jié)構(gòu)化的正則路徑查詢語言，并設(shè)計(jì)了結(jié)構(gòu)化的查詢解析以及基于此結(jié)構(gòu)的匹配算法。實(shí)驗(yàn)在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了測(cè)試與分析，驗(yàn)證了網(wǎng)絡(luò)規(guī)模對(duì)查詢速度的影響，并設(shè)置了對(duì)照實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，提出方法能夠在保證滿足正則表達(dá)式約束的前提下實(shí)現(xiàn)結(jié)構(gòu)化查詢。

關(guān)鍵詞：正則路徑查詢； 圖數(shù)據(jù)； 有限狀態(tài)自動(dòng)機(jī)； 子圖匹配

中圖分類號(hào)：TP311.12 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2023）10-021-3022-06

doi：10.19734/j.issn.1001-3695.2023.02.0079

Efficient method of structured regular path query for graph data

Qiu Tao1， Wang Yuhan1， Deng Guopeng2， Sun Yao2， Lyu Guanghua2， Xia Xiufeng1

（1.School of Computer Science， Shenyang Aerospace University， Shenyang 110136， China; 2.Shenyang Aircraft Industry （Group） Co. Ltd.， Shenyang 110034， China）

Abstract：Regular path query is a technique of using regular expressions to query graph data， usually uses finite state automata to achieve query matching. The matching result of the existing regular path query method is a sequence of vertex pairs， and the structure of the graph is not fully preserved. In order to solve this problem， this paper proposed a method of structured regu-lar path query for graph data. By structuring constraints between different sequences， the query results could be transformed from paths to subgraphs. For this purpose， the method firstly defined a structured regular path query language， and then designed a structured query parsing and a matching algorithm based on this structure. Experimental results on simulated and real datasets verify the influence of network size on query speed. This paper compared the proposed method with the control group. Experimental results show that the proposed method can realize structured query under the premise of satisfying regular expression constraints.

Key words：regular path query; graph data; finite state automaton; subgraph matching

0 引言

隨著信息社會(huì)的發(fā)展，在圖數(shù)據(jù)中實(shí)現(xiàn)高效、準(zhǔn)確并且可擴(kuò)展的查詢已經(jīng)引起越來多的關(guān)注和研究。正則路徑查詢最早用于文本上的查詢，近年來作為一種面向圖數(shù)據(jù)的查詢方法，已經(jīng)成為檢測(cè)、分析數(shù)據(jù)的重要手段。正則路徑查詢能夠?qū)D數(shù)據(jù)中滿足某種查詢模式實(shí)現(xiàn)匹配，得到滿足查詢中約束條件的結(jié)果序列，具有快速、準(zhǔn)確的特點(diǎn)，因此被廣泛地應(yīng)用到生物信息檢索［1］、社交推薦系統(tǒng)［2］等各個(gè)領(lǐng)域。

目前，基于正則路徑查詢的工作主要有帶標(biāo)簽約束的可達(dá)性查詢問題和根據(jù)完整的正則表達(dá)式進(jìn)行查詢匹配的問題，前者常常應(yīng)用與可達(dá)性算法中的部分優(yōu)化技術(shù)，后者主要是基于狀態(tài)自動(dòng)機(jī)的方法，將正則表達(dá)式解析為對(duì)應(yīng)的狀態(tài)自動(dòng)機(jī)，可進(jìn)一步指導(dǎo)圖上的搜索，獲得圖中滿足該正則表達(dá)式的路徑相連接的“源—目標(biāo)”頂點(diǎn)對(duì)的序列。例如，某社交軟件的網(wǎng)絡(luò)圖描述了若干用戶構(gòu)成的關(guān)系網(wǎng)，通過正則路徑查詢，不僅可以驗(yàn)證該網(wǎng)絡(luò)圖中存在的某種關(guān)系，還能夠查詢滿足該關(guān)系的兩個(gè)實(shí)體（該模式下兩個(gè)頂點(diǎn)之間的可達(dá)性）。

由于圖數(shù)據(jù)使用圖的方式來表現(xiàn)數(shù)據(jù)對(duì)象之間的聯(lián)系，而正則路徑查詢僅能進(jìn)行路徑匹配，匹配結(jié)果僅僅為多條由圖中頂點(diǎn)和邊構(gòu)成的路徑組成的序列，雖然匹配結(jié)果中的每一條路徑各自滿足正則表達(dá)式的語義，卻無法在路徑間進(jìn)行有效的結(jié)構(gòu)化約束，將結(jié)果表示成網(wǎng)狀結(jié)構(gòu)。

為了描述路徑之間的關(guān)系，體現(xiàn)查詢的結(jié)構(gòu)性，本文提出在圖上進(jìn)行結(jié)構(gòu)化的正則路徑查詢方法。該方法基于正則路經(jīng)查詢，通過路徑間的結(jié)構(gòu)化約束模式生成由若干路徑構(gòu)成的關(guān)系網(wǎng)，在圖中表示為一種結(jié)構(gòu)（如在社交網(wǎng)絡(luò)圖中由關(guān)系“父子”“母子”“夫妻”構(gòu)成的結(jié)構(gòu)——“家庭”），因此該方法對(duì)于路徑之間的關(guān)系能進(jìn)行有效描述。本文的主要貢獻(xiàn)如下：

a）定義了一種結(jié)構(gòu)化正則路徑查詢語言來描述結(jié)構(gòu)化正則路徑查詢，在保留正則表達(dá)式約束的同時(shí)，在路徑之間加以結(jié)構(gòu)化約束，規(guī)定了某兩條路徑之間也滿足某種關(guān)系。

b）提出了結(jié)構(gòu)化的正則路徑查詢解析，定義了非確定性有窮自動(dòng)機(jī)（SNFA）作為查詢執(zhí)行的載體，該查詢解析體現(xiàn)了結(jié)構(gòu)化查詢語言的特殊性。

c）設(shè)計(jì)了基于圖上深度優(yōu)先遍歷的自動(dòng)機(jī)匹配方法。SRPQMatch算法能夠根據(jù)輸入的數(shù)據(jù)圖和自動(dòng)機(jī)進(jìn)行查詢結(jié)果的反饋；基于遞歸的算法getNextState用于記錄查詢中間結(jié)果和監(jiān)控自動(dòng)機(jī)運(yùn)行狀態(tài)；isParallelState算法可實(shí)現(xiàn)對(duì)路徑之間約束的處理。通過該方法能夠分別從正則表達(dá)式約束和路徑結(jié)構(gòu)化約束兩個(gè)維度實(shí)現(xiàn)結(jié)構(gòu)化查詢，同時(shí)保證匹配結(jié)果的準(zhǔn)確性和匹配過程高效性。

1 相關(guān)工作

圖數(shù)據(jù)是一種使用圖結(jié)構(gòu)進(jìn)行語義查詢的數(shù)據(jù)庫(kù)，使用頂點(diǎn)、邊和屬性來表示和存儲(chǔ)數(shù)據(jù)，其中頂點(diǎn)表示現(xiàn)實(shí)中的實(shí)體，頂點(diǎn)之間的邊可表達(dá)實(shí)體之間的聯(lián)系。與傳統(tǒng)關(guān)系型數(shù)據(jù)相比，圖數(shù)據(jù)在處理海量數(shù)據(jù)關(guān)聯(lián)關(guān)系時(shí)具有非常高的性能優(yōu)勢(shì)，能夠快速找到實(shí)體間的深度關(guān)聯(lián)關(guān)系且數(shù)據(jù)模型非常靈活，可以輕松實(shí)現(xiàn)添加或刪除頂點(diǎn)、邊，擴(kuò)充或者縮小圖模型。此外，圖數(shù)據(jù)模型非常敏捷直觀，降低數(shù)據(jù)挖掘和業(yè)務(wù)開發(fā)門檻，提供生產(chǎn)開發(fā)效率。

目前，對(duì)圖數(shù)據(jù)的描述主要有屬性圖模型和RDF（資源描述框架）圖模型［3］兩種數(shù)據(jù)模型，前者實(shí)際上仍然采用“鍵—值”的形勢(shì)進(jìn)行存儲(chǔ)，頂點(diǎn)上具有屬性表，代表查詢語言有Cypher、Gremlin等，代表系統(tǒng)有Neo4j等；后者是從語義網(wǎng)演變而來的，采用的結(jié)構(gòu)是“主謂賓”形式的三元組，代表查詢語言有SPARQL［4］，代表系統(tǒng)有g(shù)Store［5］等。Bornea等人［6］描述了一種新的RDF存儲(chǔ)和查詢機(jī)制，在現(xiàn)有關(guān)系表示的基礎(chǔ)上將RDF分解成關(guān)系；Abadi等人［7］研究了當(dāng)前RDF數(shù)據(jù)管理解決方案擴(kuò)展性差的原因，并探討了這些方法的基本可擴(kuò)展性的局限性。RDF-3X引擎［8］基于SPARQL實(shí)現(xiàn)了卓越的性能。Weiss等人［9］提出了一種RDF存儲(chǔ)方案，將三元組擴(kuò)展到六元，增強(qiáng)了RDF數(shù)據(jù)管理的效率和可擴(kuò)展性。Peng等人［10］提出了在分布式環(huán)境中通過大型RDF圖處理SPARQL查詢的技術(shù)，通過在RDF圖的每個(gè)片段中引入局部部分匹配作為部分答案。

正則路徑查詢是在圖數(shù)據(jù)上進(jìn)行查詢的重要技術(shù)，目的是找到有向數(shù)據(jù)圖中滿足正則表達(dá)式約束的路徑集合，每條路徑以頂點(diǎn)對(duì)的形式表示，表示這兩點(diǎn)之間存在至少一條滿足正則表達(dá)式約束的路徑。Libkin等人［11］將圖數(shù)據(jù)庫(kù)典型查詢語言與數(shù)據(jù)查詢的標(biāo)準(zhǔn)關(guān)系機(jī)制結(jié)合，提出了面向圖數(shù)據(jù)的正則路徑查詢。目前，已有很多應(yīng)用于系統(tǒng)上的正則路徑查詢算法：Zhang等人［12，13］對(duì)查詢的正則表達(dá)式進(jìn)行劃分，首先處理最長(zhǎng)的固定謂詞序列，然后再對(duì)包含閉包的子表達(dá)式進(jìn)行處理。Yakovets等人［14］提出WavePlan，為1.1版本的SPARQL查詢構(gòu)建了基于成本的優(yōu)化器，從而進(jìn)行有效的優(yōu)化和評(píng)估。Koschmieder等人［15，16］提出使用RareLabel的方法，采用分治策略將完整的正則路徑查詢劃分成若干規(guī)模較小的子查詢，在自建的圖數(shù)據(jù)索引上進(jìn)行雙向的廣度優(yōu)先遍歷。

子圖匹配本質(zhì)上是在一張圖上找到另一張圖的所有匹配，又稱為子圖同構(gòu)，其判定和列舉所有子圖匹配出現(xiàn)的位置都具有高復(fù)雜性，在實(shí)踐中需要大量算法進(jìn)行優(yōu)化。其中子圖判定是NP-complete問題，其思想是對(duì)查詢圖Q加以限制；子圖位置列舉是NP-hard問題，在實(shí)踐中可采用大量的過濾策略來檢索搜索空間，從而提高查詢的性能。Mhedhbi等人［17］研究了優(yōu)化子圖查詢的問題，在查詢執(zhí)行期間更改最壞情況最佳子計(jì)劃的順序；Sun等人［18］提出了基于深度優(yōu)先加回溯的方式實(shí)現(xiàn)子圖匹配；Wi等人［19］提出了基于廣度優(yōu)先的多路連接方法，在列式數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上引入了字典來優(yōu)化存儲(chǔ)與運(yùn)算性能；Han等人［20］提出一種使用SIMD指令的集合交集算法，提高了子圖匹配的效率；Zeng等人［21］設(shè)計(jì)了一種高效的子圖同構(gòu)算法，通過利用GPU架構(gòu)的特性突破了子圖同構(gòu)性能在實(shí)際應(yīng)用中的瓶頸。

2 預(yù)備工作

2.1 圖數(shù)據(jù)

在本文設(shè)計(jì)的模型中，圖的類型為有向圖，以頂點(diǎn)和標(biāo)簽來表示。其中，兩個(gè)頂點(diǎn)分別表示圖中邊的起點(diǎn)和終點(diǎn)的關(guān)系實(shí)體，標(biāo)簽則表示這兩個(gè)頂點(diǎn)之間連成的邊上的屬性，也代表實(shí)體之間的關(guān)系。

定義1 數(shù)據(jù)圖。數(shù)據(jù)圖G=G（V，E，L）包含了現(xiàn)實(shí)中任意兩個(gè)實(shí)體之間的關(guān)系及其類型，其本質(zhì)是一個(gè)有向圖，是由頂點(diǎn)集合V（如社交網(wǎng)絡(luò)中的用戶）、有向邊集合E（如兩個(gè)用戶之間的關(guān)系）以及邊上的關(guān)聯(lián)函數(shù)集合L（關(guān)系的類型）構(gòu)成的有序三元組。對(duì)于任意的l∈L={l1，l2，…，lk}，它使得任意e∈E對(duì)應(yīng)V中的一個(gè)有序頂點(diǎn)對(duì)（v1，v2）。本文使用數(shù)字及小寫字母表示圖上的頂點(diǎn)（如頂點(diǎn)v1、v2等），小寫字母表示邊上的屬性（如標(biāo)簽a、b等），如圖1所示。

例1 圖1展示了某社交網(wǎng)絡(luò)圖中多個(gè)用戶之間的社交關(guān)系。圖中包含11個(gè)頂點(diǎn)，若干條邊，以及a、b、c共三種標(biāo)簽類型。這些頂點(diǎn)和邊上標(biāo)簽共同構(gòu)成正則路徑查詢的匹配圖G。

數(shù)據(jù)圖可以用布爾矩陣M表示。僅當(dāng)（v0，ex，v1）是G中的一條邊時(shí)，M［i，j］=1，稱M為G的鄰接矩陣。另一種方法是采用鄰接鏈表，即一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)都用鏈表來表示。

定義2 路徑。在數(shù)據(jù)圖G中，若任意兩點(diǎn)間能夠連通，則稱這兩點(diǎn)間存在至少一條路徑，表示為p，具有單向性。在數(shù)據(jù)圖中，一條路徑表示為頂點(diǎn)對(duì)及邊上標(biāo)簽構(gòu)成的三元組T的一個(gè)序列，即p={（v0，e0，v1），…，（vn-1，ex，vn）}，表示從v0到vn的一條路徑。其中，v0…vn∈V，ex∈E。序列中相鄰的頂點(diǎn)對(duì)均滿足首尾相連。

例2 圖1所示的數(shù)據(jù)圖G=G（V，E，L）中存在的一條路徑v1av2bv5cv6cv9bv11，根據(jù)定義2可以表示為p={（v1，a，v2），（v2，b，v5），（v5，c，v6），（v6，c，v9），（v9，b，v11）}。

2.2 查詢

在圖上的查詢需要通過正則表達(dá)式進(jìn)行約束，正則路經(jīng)查詢（RPQ）是面向帶標(biāo)簽的圖數(shù)據(jù)上的一種重要查詢，是對(duì)圖數(shù)據(jù)中滿足某種特定查詢模式的路徑進(jìn)行識(shí)別操作，旨在找出由至少一條滿足條件的路徑相連接的頂點(diǎn)對(duì)，其中需滿足的條件以正則表達(dá)式表達(dá)，查詢結(jié)果表示為頂點(diǎn)對(duì)的序列。

定義3 正則路徑查詢（RPQ）。正則路徑查詢可表示為Q=（s，R，t），其中，s，t∈V，分別表示圖中的兩個(gè)頂點(diǎn)，R為正則表達(dá)式。

正則路經(jīng)查詢的實(shí)現(xiàn)是利用有限狀態(tài)自動(dòng)機(jī)（finite state automaton）實(shí)現(xiàn)，由正則表達(dá)式解析得到，其本質(zhì)是一個(gè)識(shí)別器，對(duì)每個(gè)輸入的字符進(jìn)行識(shí)別和判斷，以確定其能到達(dá)的最終狀態(tài)或狀態(tài)集和路徑。有限狀態(tài)自動(dòng)機(jī)分為不確定的有限自動(dòng)機(jī)（NFA）［22］和確定的有限自動(dòng)機(jī)（DFA）兩類。以下將介紹基于NFA的解析方式。在NFA中，使用數(shù)字及小寫字母表示自動(dòng)機(jī)上的狀態(tài)（如q1、q2），小寫字母表示邊上的關(guān)系屬性（如標(biāo)簽a、b）。如圖2所示，NFA的初始狀態(tài)為s0=q0，接受狀態(tài)為q9∈F。

NFA在數(shù)據(jù)圖中按其狀態(tài)的轉(zhuǎn)移順序依次遍歷，通常采用深度優(yōu)先遍歷來實(shí)現(xiàn)，實(shí)現(xiàn)過程如圖3所示。在匹配過程中，將數(shù)據(jù)圖上匹配到的邊記錄為三元組T=（va，ex，vb），其中，va，vb∈V，ex∈E。當(dāng)一輪查詢結(jié)束時(shí)，稱由若干個(gè)三元組T構(gòu)成的集合序列p={T0，…，Tx，…Tm}為一條路徑，其中，x∈（0，m），m≤|n（n－1）/2|，且n=|V|。通常情況下，存在多個(gè)符合匹配約束條件的路徑結(jié)果，因此用R表示一組路徑的集合，|R|表示該集合的大小。

例3 圖2展示的NFA對(duì)應(yīng)正則表達(dá)式R=ab*（b|c）c+，NFA的生成是根據(jù)正則表達(dá)式，通過查詢解析樹進(jìn)行語法解析后得到的。給定圖1的數(shù)據(jù)圖G和圖2的NFA，在匹配過程中共有6次遍歷到達(dá)最終狀態(tài)，經(jīng)過同類項(xiàng)合并后的路徑有4條，如p1={（v1，a，v2），（v2，b，v5），（v5，b，v8），（v8，c，v7）}，此時(shí)|R|=4。

正則路經(jīng)查詢解決了對(duì)數(shù)據(jù)圖的正則表達(dá)式約束，但是沒有回答路徑結(jié)構(gòu)化約束問題，因此設(shè)計(jì)了結(jié)構(gòu)化正則表達(dá)式，并基于此提出了結(jié)構(gòu)化正則路經(jīng)查詢。

定義4 結(jié)構(gòu)化正則路徑查詢（structured regular path query，SRPQ），表示為QS=（s，RS，t）。其中，s和t分別表示查詢的起點(diǎn)和終點(diǎn)；RS為結(jié)構(gòu)化正則表達(dá)式，是由字符串組成的集合。字符串是符號(hào)的有限序列，包括基本運(yùn)算符和有限字母表Σ。QS通過正則表達(dá)式約束和路徑結(jié)構(gòu)化約束，在給定查詢圖G=G（V，E，L）上進(jìn)行頂點(diǎn)之間邊上標(biāo)簽的查詢，找到G上所有滿足RS約束條件的匹配結(jié)果集合。

結(jié)構(gòu)化正則表達(dá)式RS規(guī)定了四種基本運(yùn)算符，對(duì)于其中任意兩個(gè)子表達(dá)式RS1和RS2，存在以下規(guī)則：

a）連接（RS1·RS2）。查詢中先執(zhí)行子式RS1，再執(zhí)行RS2，兩個(gè)子表達(dá)式首尾相連。

b）選擇（RS1|RS2）。選擇子式RS1或RS2的其中一個(gè)執(zhí)行，若子式都滿足查詢條件，則作為多條查詢結(jié)果處理。

c）重復(fù)（RS1+或RS1*）。子式RS1經(jīng)過多次連接運(yùn)算得到。其中，+表示至少進(jìn)行1次連接運(yùn)算，*表示運(yùn)算0次及以上。

d）并列（RS1&RS2）。子式RS1與RS2必須同時(shí)滿足約束條件，否則不執(zhí)行，經(jīng)過該規(guī)則約束后的查詢結(jié)果數(shù)量不變。

值得注意的是，連接、選擇和重復(fù)實(shí)現(xiàn)了RS的正則表達(dá)式約束，即代表查詢結(jié)果的序列中的每條路徑都滿足正則表達(dá)式約束。并列運(yùn)算是結(jié)構(gòu)化的RPQ中最顯著的特征，該運(yùn)算體現(xiàn)了對(duì)查詢結(jié)果的路徑結(jié)構(gòu)化約束，即序列中的路徑之間滿足特定的約束。因此，由字母表Σ和運(yùn)算符構(gòu)成的新的用于表示程序語言中單詞的正則表達(dá)式，形成了一種結(jié)構(gòu)化正則路徑查詢語言，用于描述結(jié)構(gòu)化查詢。

定義5 問題定義。給定數(shù)據(jù)圖G=G（V，E，L）和結(jié)構(gòu)化正則路徑查詢QS，找到圖上所有滿足結(jié)構(gòu)化正則表達(dá)式RS中所有約束條件的匹配結(jié)果，表現(xiàn)形式為子圖的集合C。具體的實(shí)現(xiàn)方法將在第3章中詳細(xì)闡述。

結(jié)構(gòu)化正則路徑查詢的匹配流程如圖4所示。以數(shù)據(jù)圖G和查詢QS為系統(tǒng)的輸入，系統(tǒng)輸出即為數(shù)據(jù)圖G中由頂點(diǎn)和邊上標(biāo)簽構(gòu)成的圖路徑的集合，這些子結(jié)構(gòu)必須滿足查詢QS的所有約束條件。

3 結(jié)構(gòu)化正則路徑查詢匹配方法

3.1 結(jié)構(gòu)化查詢解析

在本小節(jié)中，對(duì)結(jié)構(gòu)化正則表達(dá)式的解析進(jìn)行了說明。為了體現(xiàn)查詢QS的路徑結(jié)構(gòu)化約束，需要構(gòu)造與RS相應(yīng)的自動(dòng)機(jī)，使其既能夠合理地表達(dá)正則表達(dá)式的全部?jī)?nèi)容，又符合自動(dòng)機(jī)的規(guī)范。

定義6 結(jié)構(gòu)化非確定性有窮自動(dòng)機(jī)（SNFA），表示為六元組AS=（SS，Σ，δS，s0，F(xiàn)，S&）。其中：SS表示有限狀態(tài)的非空集合，對(duì)于任意的q∈SS，稱q是SS中的一個(gè)狀態(tài)；Σ是正則表達(dá)式RS上的有限字母表的集合；δS是自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)，記錄了相鄰狀態(tài)之間的轉(zhuǎn)移；s0是自動(dòng)機(jī)的初始狀態(tài)，s0∈SS；F是接受狀態(tài)集合，F(xiàn)SS，對(duì)于任意的q∈F，稱q為SNFA的一個(gè)接受狀態(tài)；S&是并列約束函數(shù)。

在NFA的基礎(chǔ)上，SNFA定義了新的有限狀態(tài)，由此產(chǎn)生了新的轉(zhuǎn)移函數(shù)。在有限狀態(tài)集合中，狀態(tài)分為以下幾種類型：

a）初始狀態(tài)，自動(dòng)機(jī)執(zhí)行的最初狀態(tài)。

b）直接狀態(tài)，經(jīng)過轉(zhuǎn)移函數(shù)δS后到達(dá)的新狀態(tài)。值得注意的是，由于結(jié)構(gòu)化正則路徑查詢語言解析后可能存在空屬性邊ε（RS中存在空表達(dá)式），影響匹配的效率，所以在自動(dòng)機(jī)每一步匹配之前需要先對(duì)這些邊進(jìn)行處理。

c）間接狀態(tài)，到達(dá)直接狀態(tài)后，跳過其后所有的空屬性邊，直到不再出現(xiàn)ε為止。在解析過程中，一個(gè)直接狀態(tài)可能對(duì)應(yīng)多個(gè)間接狀態(tài)（如分支結(jié)構(gòu)），都視為自動(dòng)機(jī)執(zhí)行下一跳的開始。

d）接受狀態(tài)，該狀態(tài)后不存在自動(dòng)機(jī)的其他狀態(tài)。若到達(dá)這一步，查詢結(jié)束，找到一條路徑。

e）并列狀態(tài)，NFA在圖上執(zhí)行匹配時(shí)，無論以何種方式，狀態(tài)的轉(zhuǎn)移是唯一的，即只能從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。SNFA在NFA的基礎(chǔ)上提出了并列狀態(tài)，對(duì)應(yīng)結(jié)構(gòu)化正則表達(dá)式的并列操作符。在SNFA中，并列狀態(tài)集合表示為&，分為兩個(gè)子集，分別為&start和&end。其中，&start為并列開始狀態(tài)集合，經(jīng)過并列開始狀態(tài)可同時(shí)到達(dá)其后多個(gè)直接狀態(tài)；&end為并列結(jié)束狀態(tài)集合，并列結(jié)束狀態(tài)同時(shí)作為多個(gè)狀態(tài)的直接后繼狀態(tài)。在SNFA中，由于任意一個(gè)并列結(jié)構(gòu)都需要具備一對(duì)并列狀態(tài)，所以需要使用函數(shù)實(shí)現(xiàn)關(guān)聯(lián)約束。

定義7 并列約束函數(shù)，表示為S&=（q1，q2，d）。其中，q1∈&start，q2∈&end。對(duì)于并列狀態(tài)集合中任意一個(gè)并列開始狀態(tài)，都唯一對(duì)應(yīng)一個(gè)并列結(jié)束狀態(tài)，兩者共同對(duì)兩者間的分支結(jié)構(gòu)進(jìn)行約束；d表示兩者共同的度，即這對(duì)狀態(tài)之間的分支數(shù)量。

圖5所示為一個(gè)結(jié)構(gòu)化的NFA，其中，初始狀態(tài)為s0=q0，接受狀態(tài)為q9∈F，并列約束函數(shù)為S&={q2，q6，2}。

例4 給定正則表達(dá)式RS=a·（（b·a）&（c|a））·c+，其中，子式（b·a）和（c|a）為并列關(guān)系。RS轉(zhuǎn)換為SNFA后，以q2和q6組成的一對(duì)并列狀態(tài)之間的兩條子路徑形成了結(jié)構(gòu)化約束。與此同時(shí)，q3、q4和q5三個(gè)頂點(diǎn)形成了子圖結(jié)構(gòu)，它們兩兩之間都存在著約束。

若要在數(shù)據(jù)圖G上成功查詢，需要找到SNFA最后可能出現(xiàn)的狀態(tài)，然后判斷最后的狀態(tài)中是否存在接受狀態(tài)。對(duì)于SNFA中出現(xiàn)的每一個(gè)狀態(tài)，當(dāng)其在數(shù)據(jù)圖上匹配到下一條邊時(shí)，能夠達(dá)到的狀態(tài)的個(gè)數(shù)是不確定的（不確定性有限狀態(tài)特性），因此需要一個(gè)集合來記錄所有能夠到達(dá)的狀態(tài)。

定義8 激活狀態(tài)集合（SA）。記錄了SNFA在圖G上匹配的過程中，哪些狀態(tài)（頂點(diǎn)）被激活。首先，將集合初始化為SA={s0}，將初始狀態(tài)激活。若后續(xù)狀態(tài)可以通過狀態(tài)轉(zhuǎn)移函數(shù)δS激活，則動(dòng)態(tài)添加到激活狀態(tài)集合中，同時(shí)將之前的激活狀態(tài)移除。從初始狀態(tài)之后，每次執(zhí)行激活之前，需要保證集合中的狀態(tài)均為間接狀態(tài)或并列狀態(tài)。

例5 在圖5中，SNFA的初始狀態(tài)集合SA={q0}。若下一條邊a被激活，狀態(tài)集合更新為SA={q2}，其中q2為q0的間接狀態(tài)。其對(duì)于并列狀態(tài)q2，當(dāng)且僅當(dāng)q3和q4均可到達(dá)時(shí)才能發(fā)生狀態(tài)轉(zhuǎn)移，此時(shí)的狀態(tài)集合為SA={q3，q4}。對(duì)于并列狀態(tài)q6，當(dāng)且僅當(dāng)q5和q3均已激活，且q3可通過邊a到達(dá)時(shí)才能發(fā)生狀態(tài)轉(zhuǎn)移，并更新為下一個(gè)間接狀態(tài)，此時(shí)的狀態(tài)集合為SA={q7}。

查詢解析過程實(shí)質(zhì)上是根據(jù)輸入的正則表達(dá)式字符串構(gòu)造自動(dòng)機(jī)的過程，首先，識(shí)別出表達(dá)式中的邏輯運(yùn)算符，預(yù)先設(shè)定邏輯運(yùn)算符的優(yōu)先級(jí)，將表達(dá)式分割重組，生成字母表、狀態(tài)集和函數(shù)集。至此，查詢解析環(huán)節(jié)結(jié)束。

3.2 查詢匹配方法

3.2.1 結(jié)構(gòu)化的NFA匹配算法

基于自動(dòng)機(jī)的匹配是將自動(dòng)機(jī)看做一種匹配模式，在數(shù)據(jù)圖上尋找相同的結(jié)構(gòu)，類似于子圖匹配。當(dāng)基于正則表達(dá)式的自動(dòng)機(jī)構(gòu)造完成后，查詢由原來的字符串形式轉(zhuǎn)為圖的形式，且查詢圖具有起點(diǎn)。為了選擇在數(shù)據(jù)圖上的匹配位置，首先在圖上建立基于標(biāo)簽的倒排索引列表，將數(shù)據(jù)圖中所有的邊，按照?qǐng)D中字母表進(jìn)行分類，以字母表中的屬性為表頭，表中存儲(chǔ)的是具有該屬性的有向頂點(diǎn)對(duì)，可根據(jù)數(shù)據(jù)圖上的屬性值（邊上的標(biāo)簽）來查找記錄（頂點(diǎn)對(duì)）。

下面利用本文提出的結(jié)構(gòu)化的NFA匹配算法在數(shù)據(jù)圖上做查詢匹配。當(dāng)輸入數(shù)據(jù)圖和查詢后，系統(tǒng)會(huì)首先將查詢QS解析為SNFA，并建立不同的模塊來存儲(chǔ)解析后的各個(gè)組件。設(shè)置初始的激活狀態(tài)集合SA，用于記錄自動(dòng)機(jī)匹配過程中狀態(tài)的變化情況；設(shè)置路徑p，記錄根據(jù)自動(dòng)機(jī)狀態(tài)匹配得到的實(shí)時(shí)路徑，隨著自動(dòng)機(jī)的執(zhí)行動(dòng)態(tài)更新；設(shè)置路徑結(jié)果集合C，將符合條件的結(jié)果序列存儲(chǔ)下來；設(shè)置訪問標(biāo)志數(shù)組，用于記錄圖中頂點(diǎn)的訪問情況，在初始化階段，所有頂點(diǎn)均為未訪問狀態(tài)。初始化完成后，確保SNFA的字母表中的元素在數(shù)據(jù)圖的字母表中存在映射，否則，數(shù)據(jù)圖中不存在符合條件的匹配結(jié)果。接下來將自動(dòng)機(jī)中的初始邊與數(shù)據(jù)圖上的邊逐一匹配，確定在圖上的開始位置；當(dāng)匹配完成執(zhí)行之后，路徑結(jié)果集合會(huì)根據(jù)查詢結(jié)果寫入相應(yīng)的路徑，該過程如算法1所示。

在算法1中，第12行g(shù)etNextState方法使用了圖中查詢的起點(diǎn)、自動(dòng)機(jī)初始狀態(tài)以及初始化的激活狀態(tài)集合作為輸入，通過遞歸的方式執(zhí)行圖上的深度優(yōu)先遍歷，實(shí)現(xiàn)過程如算法2所示。在查詢遍歷開始時(shí)，通過使用倒排索引能夠根據(jù)列表元素和自動(dòng)機(jī)初始狀態(tài)快速地在圖上鎖定查詢起點(diǎn)（第8～10行）。

對(duì)算法1的時(shí)間復(fù)雜度進(jìn)行分析。設(shè)數(shù)據(jù)圖的規(guī)模為M條邊，解析后的自動(dòng)機(jī)有N條邊。由于自動(dòng)機(jī)是按照順序進(jìn)行解析的，查詢起點(diǎn)位于自動(dòng)機(jī)解析函數(shù)的第一項(xiàng)，所以算法1中第8行的外層循環(huán)復(fù)雜度為O（1），內(nèi)層循環(huán)中最多需要遍歷M次，故算法1的時(shí)間復(fù)雜度為O（M）。

3.2.2 更新激活狀態(tài)集合

在深度優(yōu)先搜索算法中，通過算法1輸入的數(shù)據(jù)作為查詢開始條件，采用遞歸式搜索策略，使得每一次的遍歷結(jié)果能夠在執(zhí)行過程中保存，若查詢的某一分支在數(shù)據(jù)圖上無法匹配到相應(yīng)結(jié)果時(shí)，可通過回溯法尋找其他分支。在每一次遞歸過程中都將更新路徑和激活狀態(tài)集合，自動(dòng)機(jī)的狀態(tài)設(shè)置為當(dāng)前狀態(tài)的后繼狀態(tài)。

算法2 基于深度優(yōu)先遍歷的更新算法 getNextState

輸入：當(dāng)前激活狀態(tài)集合SA;當(dāng)前狀態(tài)q;當(dāng)前頂點(diǎn)v。

輸出：下一個(gè)激活狀態(tài)集合SA。

1 for each f start from q in AS.δS

2if label l in function is empty

3 add q.next to SA and delete q from SA;

4SA←getNextState（SA，v，q.next）;

5return SA;

6 if q not in S&

7check if q is a final state;

8 delete q from SA;

9for each e in G.E

10 for each f in AS.δS

11 if e.match（f）

12add q.next to SA and add e to path p;

13 SA←getNextState（SA，w，q.next）;

14 else

15 SA←isParallelState （SA，v，q）;

16 return SA.

在算法2中，首先是對(duì)直接狀態(tài)的處理（第1～5行），剔除自動(dòng)機(jī)中不包含屬性的邊，避免算法在每一次迭代中存在無法匹配的情況。接下來執(zhí)行自動(dòng)機(jī)在圖上的正則表達(dá)式約束，對(duì)SNFA中除了并列以外的狀態(tài)，這是與傳統(tǒng)自動(dòng)機(jī)匹配算法相似的部分。首先判斷其是否到達(dá)最終狀態(tài)（第7行）；然后按順序遍歷自動(dòng)機(jī)和數(shù)據(jù)圖，若存在匹配的標(biāo)簽，則將自動(dòng)機(jī)上通過標(biāo)簽到達(dá)的狀態(tài)添加到激活狀態(tài)集合中，并將圖上的對(duì)應(yīng)路徑加入到路徑集合中，該過程為遞歸式的深度優(yōu)先搜索（第9～13行）。對(duì)并列狀態(tài)的處理算法如算法3所示。

算法3 并列狀態(tài)處理算法isParallelState

輸入：當(dāng)前激活狀態(tài)集合SA;當(dāng)前狀態(tài)q;當(dāng)前頂點(diǎn)v。

輸出：下一個(gè)激活狀態(tài)集合SA。

1 if q in &start

2delete q from SA;

3for each e in G.E and v.next is not visited

4for each f start from q in AS.δS

5 if e.match（f） and q.next is not visited

6set q.next and v.next are visited;

7queue Q.add（q.next， e）;

8 for each f start from q in AS.δS

9if q.next is not visited

10return SA;

11 S&.degree←queue.size（） where S&.q1.equals（q）;

12for each element in Q

13add q.next to SA and add e to path p;

14 SA←getNextState（SA，w，q.next）;

15 return SA;

16 else if q in &end

17set S&.degree-1 where S&.q2.equals（q）;

18if （S&.degree）.equals（0）

19 delete q.next to SA and delete q from SA;

20SA←getNextState（SA，w，q.next）;

21return SA.

算法3中，若輸入并列開始狀態(tài)，則在該狀態(tài)標(biāo)記為已訪問狀態(tài)后，將其后續(xù)所有的直接狀態(tài)與圖中目標(biāo)頂點(diǎn)存入隊(duì)列（第6、7行），其目的是為了統(tǒng)計(jì)該狀態(tài)之后的分支數(shù)量，作為該頂點(diǎn)的度。在算法第8～10行中，篩掉了未滿足全部分支約束的情況，保證該狀態(tài)之后的所有狀態(tài)都可到達(dá)；隨后，在每一條分支上執(zhí)行深度優(yōu)先遍歷（第12～14行）。若輸入并列結(jié)束狀態(tài)，由于其入度與對(duì)應(yīng)的并列開始頂點(diǎn)的出度相等，所以在每次訪問后，該頂點(diǎn)的入度減1。當(dāng)入度減少為0時(shí)，表明其所有的前驅(qū)狀態(tài)都已訪問過，并列狀態(tài)處理結(jié)束。

由于需要依次遍歷自動(dòng)機(jī)和圖上的邊，算法2和3的時(shí)間復(fù)雜度均為O（MN）?；趫D上深度優(yōu)先遍歷的自動(dòng)機(jī)匹配過程如圖6所示。圖中的每個(gè)頂點(diǎn)標(biāo)明了數(shù)據(jù)圖上的頂點(diǎn)以及自動(dòng)機(jī)的當(dāng)前狀態(tài)。非并列狀態(tài)下的查詢過程為樹型結(jié)構(gòu)，每次遍歷到葉子頂點(diǎn)時(shí)，不存在與自動(dòng)機(jī)狀態(tài)匹配的數(shù)據(jù)圖上的頂點(diǎn)時(shí)，回溯至上一個(gè)頂點(diǎn)繼續(xù)查詢。并列狀態(tài)下的查詢過程為有向無環(huán)圖結(jié)構(gòu)，當(dāng)遍歷到并列結(jié)束狀態(tài)頂點(diǎn)時(shí)，需等待其他分支全部遍歷完成后才能繼續(xù)查詢。

例6 隨著匹配過程的迭代，執(zhí)行樹上節(jié)點(diǎn)對(duì)應(yīng)的激活狀態(tài)集合發(fā)生變化，其中虛線矩形部分為自動(dòng)機(jī)查詢中并約束。葉子節(jié)點(diǎn)中存在兩個(gè)接受狀態(tài)v9和v10。

3.2.3 判斷最終狀態(tài)是否匹配

在算法2中，每當(dāng)遍歷執(zhí)行時(shí)，需要判斷當(dāng)前狀態(tài)q是否在自動(dòng)機(jī)的接受狀態(tài)集合F中。若q是一個(gè)接受狀態(tài)，則成功找到一個(gè)符合要求的結(jié)果，將路徑p存入結(jié)果集合C中。

圖6所示的算法執(zhí)行樹中，符合約束的查詢結(jié)果有兩個(gè)，分別是以v4頂點(diǎn)開始，以v9和v10頂點(diǎn)結(jié)束的兩條序列。每條序列中的頂點(diǎn)對(duì)構(gòu)成一個(gè)子圖，如圖7所示。當(dāng)自動(dòng)機(jī)在數(shù)據(jù)圖上的遍歷完成后，系統(tǒng)最終以算法1為結(jié)束，輸出查詢結(jié)果集合C。在本樣例中，集合C中包含了兩條序列p1和p2。圖7中，子圖序列p2以加粗邊的形式展現(xiàn)。

查詢結(jié)果表明，經(jīng)過結(jié)構(gòu)化的正則路徑查詢可得到子圖形式的查詢結(jié)果。在數(shù)據(jù)圖中，連接頂點(diǎn)v5、v6和v8之間的三條路徑之間同時(shí)滿足一定的約束，三個(gè)頂點(diǎn)構(gòu)成了圖結(jié)構(gòu)，實(shí)現(xiàn)了結(jié)構(gòu)化查詢的目標(biāo)。

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

本章通過實(shí)驗(yàn)測(cè)試對(duì)提出的利用深度優(yōu)先遍歷遞歸實(shí)現(xiàn)結(jié)構(gòu)化正則路徑查詢匹配方法進(jìn)行性能分析和評(píng)價(jià)。實(shí)驗(yàn)在基于C++的原型系統(tǒng)中實(shí)現(xiàn)了前面描述的所有查詢?cè)u(píng)估技術(shù)。

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

本文使用了真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行評(píng)估，數(shù)據(jù)集來自Stanford大學(xué)的大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站整理的基于社交網(wǎng)絡(luò)的Advogato數(shù)據(jù)集，共包含5 200個(gè)點(diǎn)，47 100條邊（以三元組表示），每條邊以起點(diǎn)、標(biāo)簽、終點(diǎn)形式給出，邊上的標(biāo)簽一共有三種。查詢采用手動(dòng)構(gòu)造的符合數(shù)據(jù)集中包含的標(biāo)簽的結(jié)構(gòu)化正則路徑查詢，根據(jù)查詢中體現(xiàn)的路徑結(jié)構(gòu)化約束將查詢分為四組，每組包含20個(gè)查詢。查詢的設(shè)置如表1所示，Q1～Q4分別為根據(jù)標(biāo)準(zhǔn)劃定的不同類型的四組查詢，每組查詢中邊的標(biāo)簽均包含在自動(dòng)機(jī)定義的字母表中。其中，Q1組查詢解析后不存在并列結(jié)構(gòu)；Q2組只存在串聯(lián)或并聯(lián)的并列結(jié)構(gòu)，且每個(gè)并列結(jié)構(gòu)中不存在子式；Q3組在Q2組的基礎(chǔ)上，允許并列結(jié)構(gòu)中包含子式，但不允許子式中存在并列結(jié)構(gòu)；Q4組查詢中存在并列結(jié)構(gòu)的嵌套，查詢Q1～Q4的復(fù)雜程度依次遞增。

實(shí)驗(yàn)基于以下兩個(gè)方面進(jìn)行評(píng)估：a）通過控制變量法，分析查詢的解析和匹配性能；b）通過對(duì)比實(shí)驗(yàn)，分析本文算法的優(yōu)勢(shì)。實(shí)驗(yàn)在Intel Core 2.60 GHz CPU i7和16 GB內(nèi)存的Windows 10系統(tǒng)上進(jìn)行。

4.2 實(shí)驗(yàn)評(píng)估

實(shí)驗(yàn)基于分組后不同類型的查詢進(jìn)行性能檢驗(yàn)。在第一個(gè)實(shí)驗(yàn)中，分別測(cè)試了查詢解析和查詢匹配的時(shí)間，并設(shè)置了對(duì)比實(shí)驗(yàn)；在第二個(gè)實(shí)驗(yàn)中，通過隨機(jī)選取數(shù)據(jù)集上不同規(guī)模的子集，測(cè)試了數(shù)據(jù)網(wǎng)絡(luò)規(guī)模對(duì)匹配速度的影響。

4.2.1 查詢整體時(shí)間對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)分別設(shè)置了Q1～Q4四種不同類型的結(jié)構(gòu)化正則路徑查詢，每種查詢?cè)O(shè)置20個(gè)為一組進(jìn)行實(shí)驗(yàn)，解析和匹配時(shí)間選取各組的平均值。對(duì)照組采用相同的查詢，但是其解析和匹配基于一般的正則路徑查詢。由于一般方法中無法對(duì)路徑結(jié)構(gòu)化約束進(jìn)行有效描述，所以規(guī)定在對(duì)照組中，當(dāng)遍歷執(zhí)行到并列時(shí)，只選取其一條分支而忽略另一條分支，之后將未遍歷到的剩余分支作為單獨(dú)的查詢進(jìn)行處理，最后通過累加作為總體匹配時(shí)間。如對(duì)查詢Q2的處理：首先選取子表達(dá)式（b&c）中的b和（c&a）中的c作為主要路徑，將查詢轉(zhuǎn)換為abcca；接下來處理剩余的分支acc和caa；最后將這三個(gè)正則表達(dá)式分別進(jìn)行解析和匹配，所需時(shí)間的總和作為對(duì)照組的查詢時(shí)間。實(shí)驗(yàn)效果如圖8所示。結(jié)果表明，在查詢字母表不變的情況下，隨著查詢結(jié)構(gòu)的復(fù)雜化，其對(duì)應(yīng)的解析和匹配的速度均呈降低趨勢(shì)。各組查詢中，結(jié)構(gòu)化正則路徑查詢方法的匹配速度總體上優(yōu)于對(duì)照組。

4.2.2 查詢匹配時(shí)間梯度實(shí)驗(yàn)

實(shí)驗(yàn)基于真實(shí)數(shù)據(jù)集Advogato。首先，分別隨機(jī)選取數(shù)據(jù)集中10%、30%、50%、80%和100%的邊，形成五種不同規(guī)模的數(shù)據(jù)圖，再將Q1～Q4共四組查詢依次輸入，各組查詢?cè)跀?shù)據(jù)集上的平均匹配時(shí)間如圖9所示。

結(jié)果表明，數(shù)據(jù)集的規(guī)模對(duì)匹配速度有著明顯的影響，兩者呈現(xiàn)正比的關(guān)系。例如在查詢Q2中，當(dāng)其數(shù)據(jù)集的規(guī)模呈直線增加時(shí)，匹配時(shí)間也是線性增長(zhǎng)的。由于數(shù)據(jù)集中頂點(diǎn)之間邊的分布是不均勻的，實(shí)際結(jié)果與理論值會(huì)有所偏差。

5 結(jié)束語

本文研究了基于有限狀態(tài)自動(dòng)機(jī)的結(jié)構(gòu)化正則路徑查詢問題，目的是使得查詢?cè)趫D上的匹配結(jié)果序列不僅滿足傳統(tǒng)自動(dòng)機(jī)匹配算法的正則表達(dá)式約束，同時(shí)使得路徑之間滿足結(jié)構(gòu)化約束，以解決傳統(tǒng)正則路徑查詢?cè)趫D上的查詢結(jié)果的信息丟失問題。本文提出了結(jié)構(gòu)化約束的概念，設(shè)計(jì)了結(jié)構(gòu)化正則路徑查詢語言和結(jié)構(gòu)化非確定性自動(dòng)機(jī)來實(shí)現(xiàn)這種方式。在提出的結(jié)構(gòu)化正則路徑查詢匹配方法中，引入自動(dòng)機(jī)的并列狀態(tài)，進(jìn)行路徑結(jié)構(gòu)化約束，最后通過基于圖上的深度優(yōu)先遍歷算法實(shí)現(xiàn)了自動(dòng)機(jī)在數(shù)據(jù)圖上的匹配。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的可行性，對(duì)于匹配性能上的提升將是下一步的努力方向。

參考文獻(xiàn)：

［1]Wang Mingyu，Zhang Jiaheng，Liu Jun，et al. PDD graph：bridging electronic medical records and biomedical knowledge graphs via entity linking［C］//Proc of the 16th International Semantic Web Confe-rence.Berlin：Springer-Verlag，2017：219-227.

［2]Ma Hao，Zhou Dengyong，Liu Chao，et al.Recommender systems with social regularization［C］//Proc of the 4th ACM International Confe-rence on Web Search and Data Mining.New York：ACM Press，2011：287-296.

［3]杜方，陳躍國(guó)，杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述［J］.軟件學(xué)報(bào)，2013，24（6）：1222-1242.（Du Fang，Chen Yueguo，Du Xiao-yong. Survey of RDF query processing techniques［J］.Journal of Software，2013，24（6）：1222-1242.）

［4]王鑫，鄒磊，王朝坤，等.知識(shí)圖譜數(shù)據(jù)管理研究綜述［J］.軟件學(xué)報(bào)，2019，30（7）：2139-2174.（Wang Xin，Zou Lei，Wang Chaokun，et al.Research on knowledge graph data management：a survey［J］.Journal of Software，2019，30（7）：2139-2174.）

［5]Zou Lei，Mo Jinghui，Chen Lei，et al.gStore：answering SPARQL queries via subgraph matching［J］.Proceedings of the VLDB Endowment，2011，4（8）：482-493.

［6]Bornea M A，Dolby J，Kementsietsidis A，et al.Building an efficient RDF store over a relational database［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2013：121-132.

［7]Abadi D， Marcus A， Madden S， et al. SW-Store：a vertically partitioned DBMS for Semantic Web data management［J］.The VLDB Journal，2009，18（2）：385-406.

［8]Neumann T， Weikum G. The RDF-3X engine for scalable management of RDF data［J］.The VLDB Journal，2010，19（1）：91-113.

［9]Weiss C， Karras P， Bernstein A. Hexastore： sextuple indexing for semantic Web data management［J］.Proceedings of the VLDB Endowment，2008，1（1）：1008-1019.

［10]Peng Peng， Zou Lei， zsu M T， et al. Processing SPARQL queries over distributed RDF graphs［J］.The VLDB Journal，2016，25（2）：243-268.

［11]Libkin L， VrgoCˇ D. Regular path queries on graphs with data［C］//Proc of the 15th International Conference on Database Theory.New York：ACM Press，2012：74-85.

［12]Zhang Xiaowang， Feng Zhiyong， Wang Xin， et al. Context-free path queries on RDF graphs［C］//Proc of the 15th International Semantic Web Conference.Berlin：Springer-Verlag，2016：632-648.

［13]Zhang Xiaowang， Van den Bussche J. On the power of SPARQL in expressing navigational queries［J］.The Computer Journal，2015，58（11）：2841-2851.

［14]Yakovets N， Godfrey P， Gryz J. Query planning for evaluating SPARQL property paths［C］//Proc of International Conference on Management of Data.New York：ACM Press，2016：1875-1889.

［15]Koschmieder A， Leser U. Regular path queries on large graphs［C］//Proc of the 24th International Conference on Scientific and Statistical Database Management.Berlin：Springer-Verlag，2012：177-194.

［16]Koschmieder A. Cost-based optimization of regular path queries on large graphs［EB/OL］.（2010-03-25）.https：//ceur-ws.org/Vol-581/gvd2010_2_1.pdf.

［17]Mhedhbi A， Salihoglu S. Optimizing subgraph queries by combining binary and worst-case optimal joins［J］.Proceedings of the VLDB Endowment，2019，12（11）：1692-1704.

［18]Sun Shixuan， Luo Qiong. In-memory subgraph matching： an in-depth study［C］//Proc of ACM SIGMOD International Conference on Mana-gement of Data.New York：ACM Press，2020：1083-1098.

［19]Wi S， Han W S， Chang C， et al. Towards multi-way join aware optimizer in SAP HANA［J］.Proceedings of the VLDB Endowment，2020，13（12）：3019-3031.

［20]Han Shuo， Zou Lei， Yu J X. Speeding up set intersections in graph algorithms using SIMD instructions［C］//Proc of International Conference on Management of Data.New York：ACM Press，2018：1587-1602.

［21]Zeng Li， Zou Lei， zsu M T， et al. GSI： GPU-friendly subgraph isomorphism［C］//Proc of the 36th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2020：1249-1260.

［22]Holzer M， Kutrib M. Nondeterministic finite automata-recent results on the descriptional and computational complexity［J］.International Journal of Foundations of Computer Science，2009，20（4）：563-580.

收稿日期：2023-02-10；修回日期：2023-04-29

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62002245）；遼寧省自然科學(xué)基金資助項(xiàng)目（2022-BS-218）

作者簡(jiǎn)介：邱濤（1989-），男，江西萍鄉(xiāng)人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)樾蛄袛?shù)據(jù)處理、查詢優(yōu)化、數(shù)據(jù)挖掘;王嶼涵（1997-），男（通信作者），遼寧沈陽(yáng)人，碩士，主要研究方向?yàn)閿?shù)據(jù)查詢（wangyuhan@stu.sau.edu.cn）；鄧國(guó)鵬（1977-），男，遼寧開原人，主要研究方向?yàn)檫b測(cè)數(shù)據(jù)分析處理；孫堯（1984-），男，河北遷西人，高級(jí)工程師；呂光華，男，安徽界首人，高級(jí)工程師；夏秀峰（1964-），男，山東青島人，教授，碩導(dǎo)，博士，主要研究方向?yàn)閿?shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘.