基于多級索引的前向語義數(shù)據(jù)流推理

高 峰 楊帆玉 顧進廣

(武漢科技大學計算機科學與技術(shù)學院 湖北 武漢 430065)(湖北省智能信息處理與實時工業(yè)系統(tǒng)重點實驗室 湖北 武漢 430065)

0 引 言

在大數(shù)據(jù)領(lǐng)域，語義數(shù)據(jù)量急速增長，越來越多的應用程序要求能夠?qū)崟r處理語義數(shù)據(jù)流，特別是在處理和查詢龐大復雜的RDF(Resource Description Framework)數(shù)據(jù)流方面，仍然有著巨大難題。一方面，為了滿足數(shù)據(jù)流的高吞吐量和低延遲，流處理引擎處理必須足夠有效；另一方面，查詢語言必須具有一定的表述能力，才能支持可能需要遞歸的邏輯推理。目前，流處理模型還沒有一個統(tǒng)一的標準，流處理系統(tǒng)應該有自己的流模型和查詢語言，由于缺乏統(tǒng)一的標準，所以設計流系統(tǒng)變得異常困難。由于RDF流數(shù)據(jù)的生成速率極快，連續(xù)的SPARQL[1]查詢通常涉及到密集的聯(lián)接操作，這些操作很可能會造成性能瓶頸，因此需要針對性的優(yōu)化技術(shù)。與連續(xù)SPARQL查詢處理相比，RDF流推理的復雜性和支持實時推理的難度更大，特別是在傳遞規(guī)則的推理方面，其推理結(jié)果是指數(shù)級的；與此同時，推理結(jié)果并不全是有用的，如何去消除中間集減少冗余數(shù)據(jù)也是一個難題。

針對上述難題，本文提出了CSPARQL-Ci，即基于C-SPARQL[2]和Cichlid[3]的RDFS流推理平臺，使用支持復雜事件處理的ESPER[4]流處理引擎，其吞吐量達到每秒十萬級別；基于Spark[5]的Cichlid進行RDFS流推理，并針對傳遞規(guī)則的推理效率低和推理中間集冗余提出了多級索引算法，主要包括優(yōu)化的傳遞規(guī)則推理算法和中間集消除算法。優(yōu)化的傳遞規(guī)則推理算法是將RDF結(jié)果集分割為多個具有相同傳遞規(guī)則的子圖，再將子圖內(nèi)部各個節(jié)點相互聯(lián)接得到新的RDF。中間集消除算法主要是根據(jù)單個查詢條件分割生成對應的子圖，再通過查詢條件依賴關(guān)系進行聯(lián)接操作得到滿足條件的集合。和ECS[6]、C-SPARQL和BigSR[7]等平臺在相同的LUBM[8]數(shù)據(jù)集做對比實驗和評估，結(jié)果表明大部分情況下查詢延遲都有很明顯的優(yōu)勢。

1 相關(guān)工作

1.1 RDF流和C-SPARQL

RDF流由一系列成對的有序序列組成，每對序列由一個RDF三元組和對應的時間戳組成，每個RDF三元組對應的結(jié)構(gòu)是t∈的形式，是W3C推薦描述資源的標準模型；在數(shù)據(jù)流處理系統(tǒng)中，三元組通常會加上一個時間戳來表示進入系統(tǒng)的時間，即t∈，其中τ為一個時間戳。由于時間戳并不唯一，所以并不嚴格遞增，相同的時間戳表示這些RDF同時出現(xiàn)。

最早提出的C-SPARQL采用ESPER處理RDF數(shù)據(jù)流和Jena[9]進行SPARQL查詢。本文的中間集消除算法則是在上述查詢語句的基礎(chǔ)上建立常量和變量索引，通過常量索引得到滿足任一查詢條件的三元組，通過變量索引得到滿足全部查詢條件的三元組。

1.2 RDFS流推理

基于RDF，RDFS定義了一組表示隱藏信息的規(guī)則，RDFS推理規(guī)則集如表1所示，而推理是通過使用RDFS推理規(guī)則從現(xiàn)有的RDF數(shù)據(jù)中推斷出隱式信息的過程。例如，給定一個RDF圖G，可以從RDFS規(guī)則中得到一些表示為T的新的三元組，將T添加到G，則可以獲得更大的RDF圖G′，從G到G′的過程稱為推理。

表1 RDFS規(guī)則集

RDF數(shù)據(jù)的推理可以采用前向鏈式和后向鏈式兩種不同的策略進行推理。前向鏈式推理是從數(shù)據(jù)開始，通過利用規(guī)則集循環(huán)迭代得到新的RDF數(shù)據(jù)，將派生的RDF數(shù)據(jù)添加到原始RDF數(shù)據(jù)中，以供后期查詢和推理，如Cichlid；而后向鏈式推理則是根據(jù)查詢條件出發(fā)，根據(jù)規(guī)則集動態(tài)查詢是否有滿足的事實，如EP-SPARQL[10]。文獻[11]提出，前向鏈式推理相對縮短了查詢響應時間，但是資源開銷比較大而且會有重復數(shù)據(jù)。

目前，針對語義數(shù)據(jù)流的推理研究主要關(guān)注對復雜推理能力的支持，或?qū)唵尾樵兊男阅軆?yōu)化。在評測集方面，SRBench[12]、CSRBench[13]、CityBench[14]和YABench[15]等常見的RDF流處理評測集對于流系統(tǒng)的設計有很大的幫助。在處理系統(tǒng)方面，有很多RDF流處理系統(tǒng)相繼被提出。最先提出的C-SPARQL內(nèi)置推理性能一般；CQELS[16]是最先進行連續(xù)SPARQL查詢優(yōu)化的系統(tǒng)，CQELS將輸入流預處理，然后通過查詢優(yōu)化后獲取了很高的性能；ETALIS[17]是一個基于規(guī)則的復雜事件處理引擎，EP-SPARQL在ETALIS的基礎(chǔ)上插入了一個編譯器層，將連續(xù)的SPARQL查詢編譯為邏輯規(guī)則。StreamRule[18]使用RSP引擎和Clingo[19]進行數(shù)據(jù)流預處理和推理查詢，吞吐量較之前提升數(shù)倍，但在推理能力仍有不足；Laser[20]和Ticker[21]都是基于Lars[22]架構(gòu)的流處理引擎，Ticker主要專注于增量模型維護，但是依賴外部引擎而降低了一定的性能；Laser提出了基于時間的增量模型，降低了重復計算；BigSR是結(jié)合Spark和Lars架構(gòu)的分布式流推理平臺，有著百萬級別的吞吐量和毫秒以內(nèi)的延遲。本文采用的是前向鏈式推理策略，并針對重復數(shù)據(jù)問題，在YARS[23]和ECS的索引基礎(chǔ)上提出一種改進的中間集消除算法。

2 數(shù)據(jù)流推理引擎設計

本節(jié)在CSPARQL引擎的基礎(chǔ)上擴展，并提出一種基于多級索引的前向語義數(shù)據(jù)流推理引擎(CSPARQL-Ci)，其系統(tǒng)架構(gòu)如圖1所示。

圖1 CSAPRQL-Ci系統(tǒng)架構(gòu)

2.1 系統(tǒng)架構(gòu)

圖1所示的CSPARQL-Ci主要由以下四個部分組成。

(1)ESPER流處理引擎：主要負責將輸入的RDF流與對應的查詢進行綁定，然后進行窗口操作，并提取滑動區(qū)間內(nèi)的三元組數(shù)據(jù)放入Cichlid推理引擎中。

(2)Cichlid推理引擎：將ESPER輸出的RDF數(shù)據(jù)進行處理，并根據(jù)RDFS推理規(guī)則的依賴關(guān)系，建立一次推理順序，然后利用傳遞規(guī)則算法進行RDFS的傳遞規(guī)則推理，最后將推理的結(jié)果進行數(shù)據(jù)除重。

(3)中間集消除：根據(jù)查詢條件的常量和變量建立不同的索引，并根據(jù)推理出來的結(jié)果進行分類，篩選出滿足查詢條件中常量的RDF數(shù)據(jù)，再將相同變量進行聯(lián)接操作以進一步篩選得到大部分滿足的推理結(jié)果，最后放入SPARQL查詢引擎中。

(4)SPARQL引擎：將篩選后的三元組數(shù)據(jù)放入該引擎中，構(gòu)建圖模型并進行SPARQL查詢，最后將查詢得到的結(jié)果輸出。

2.2 優(yōu)化傳遞規(guī)則推理

傳遞規(guī)則推理衍生的結(jié)果是指數(shù)級別的，并且推理過程需要多次迭代，例如規(guī)則集中的規(guī)則5和規(guī)則11，以及本文應用的schoolMate規(guī)則等。進行傳遞規(guī)則推理本質(zhì)上是在RDF圖上計算傳遞閉包，從關(guān)系代數(shù)理論的角度來看，計算傳遞閉包的一種常見的方法是對數(shù)據(jù)流執(zhí)行自聯(lián)接，但是該方法有兩個缺點：1)包含太多的迭代處理，長度為n的傳遞鏈需要進行n倍的迭代計算；2)推理過程冗余，以計算傳遞鏈p1→p2→…→p10為例，在計算從到或者從到時，會被計算多次。為了提升推理性能，本文在智能可傳遞閉包算法[24]的基礎(chǔ)上進行改進，提出了優(yōu)化的傳遞規(guī)則進行RDF流推理。

本文使用的LUBM數(shù)據(jù)集是一個主要描述學校組織關(guān)系的數(shù)據(jù)集，其本體模型中的屬性memberOf表示學生和學校之間的關(guān)聯(lián)關(guān)系，即該生為該校成員；schoolMate表示校友關(guān)系，s1和s2都是該校的成員，那么s1和s2就互為校友，如果一個學校的成員有n(n>1)個人，要查詢互為校友的成員，其結(jié)果為n×(n-1)個。針對上述場景，本文定義了如下傳遞推理規(guī)則。

(s1,memeberOf,u),(s2,memberOf,u)=>

(s1,schoolMate,s2),(s2,schoolMate,s1)

進一步對于所有與schoolMate類似的傳遞規(guī)則的屬性，有如下定義：

(p,type,transitive),(s1,p,s2)=>(s2,p,s1)

具體的傳遞規(guī)則推理算法分為兩步，如算法1所示。

算法1傳遞規(guī)則推理

輸入：三元組triples。

輸出：推理結(jié)果out。

begin

valmap=Map

valin=Set

valout=Set

for(tintriples){

if(map.containsKey(t.p))

input.add(t)

}

valg=Map>

for(tinin){

if (!g.get(t.p).containsKey(t.o))

g.get(t.p).put(t.o,Set)

g.get(t.p).get(t.o).add(t.s)

}

for(transing.keySet())

for(uing.get(trans).keySet())

for(s1,s2ing.get(trans).get(u))

out.add(Triple(s1,map.get(trans),s2))

returnout

end

(1)子圖索引構(gòu)建：將篩選滿足傳遞規(guī)則的三元組作為輸入數(shù)據(jù)；開始遍歷三元組，如果該三元組表示的元素所屬的子圖已經(jīng)存在，那么放入該子圖，如果不存在則新建子圖并放入該元素；生成同一學校的學生與所屬學校對應的一個子圖。

(2)遍歷各子圖：將第一步中多個子圖進行遍歷，最后取出處于同一子圖的元素進行聯(lián)接得到輸出結(jié)果。

2.3 中間集消除

經(jīng)過Cichlid推理引擎得到的輸出結(jié)果數(shù)量是巨大的，經(jīng)過了數(shù)據(jù)除重之后仍然大部分的數(shù)據(jù)都是與查詢不相關(guān)的，如何根據(jù)查詢語句建立索引將無用數(shù)據(jù)最大程度的剔除掉顯得尤為重要。經(jīng)過分析，查詢語句中存在常量和變量，通過常量可以很直接地消除大部分不滿足的三元組，通過不同查詢語句中相同變量集合進行聯(lián)接可以消除掉只滿足部分查詢條件的三元組。根據(jù)查詢語句的結(jié)構(gòu)，設計了以下6種索引結(jié)構(gòu)，其中“?”表示查詢的變量，對應的右邊的變量索引下標(該變量在查詢中首次出現(xiàn)的下標，“0”表示為常量)，根據(jù)這些索引可以將輸入的三元組分為這6種集合，每種集合都滿足該查詢的索引結(jié)構(gòu)，具體如表2所示。

表2 索引結(jié)構(gòu)

具體消除算法可大致分為三步，如算法2所示。

算法2中間集消除

輸入：三元組triples,變量表indexList。

輸出：消除后結(jié)果set。

begin

valmap=Map>

valmapSet=Map

valin=List>

for(indexinindexList){

for(tintriples)

if(index.match(t))In.get(index).add(t)

}

for(i

valindex=indexList.get(i)curr=0

for(j

valt=in.get(i).get(j)

map.get(index.sIndex).get(curr).add(t.s)

map.get(index.pIndex).get(curr).add(t.p)

map.get(index.oIndex).get(curr).add(t.o)

}}

for(i<=num;i++)

//未知變量的數(shù)量

for(tinmap.get(i).get(0)){

while(j

!map.get(i).get(j).contains(t)?b=false break

j++}

b?mapSet.get(i).add(t)

}

returnmapSet

end

(1)根據(jù)常量篩選滿足的集合，建立查詢條件——滿足條件三元組集合的關(guān)系表，將輸入的每個三元組放入滿足條件的集合，如果存在一個三元組滿足多個條件，需放入多個集合中。

(2)建立變量集合表，將所有滿足不同查詢條件的相同變量分別放入與變量對應的集合中，相同變量的集合構(gòu)成了變量集合表。

(3)聯(lián)接獲取所有變量集合表中每個變量的子集，將屬于同一變量的子集依次進行聯(lián)接操作，可以得到滿足所有查詢條件的公共子集。

3 實 驗

3.1 實驗配置

實驗代碼基于Java8，數(shù)據(jù)集和查詢測試可在GitHub(https://github.com/qq348991318/CSPARQL-Ci.git)上獲取。實驗使用的操作系統(tǒng)是MacOS 10.15，CPU是8259U，主頻2.3 GHz，內(nèi)存16 GB。實驗數(shù)據(jù)集是綜合基準的LUBM50數(shù)據(jù)集，它是一種廣泛使用的標準基準；采用系統(tǒng)吞吐量和查詢延遲作為主要的性能指標，吞吐量表示單位時間內(nèi)可以處理多少數(shù)據(jù)，在本文中表示為每秒多少個三元組；延遲是指輸入到達和生成輸出之間消耗的時間。將CSPARQL-Ci與ECS、C-SPARQL和BigSR在單機的環(huán)境下做了對比實驗。設計了多組查詢語句，每個查詢分別為每秒200、400和800個三元組，窗口大小為10 s、20 s、40 s和80 s，并統(tǒng)計多次查詢延遲和吞吐量的平均值。

3.2 實驗場景設置

本文根據(jù)LUBM數(shù)據(jù)集設計了9組查詢語句，分別對實體層次結(jié)構(gòu)(Q2、Q4)、屬性層次結(jié)構(gòu)(Q3、Q4)、實體和屬性關(guān)系的層次結(jié)構(gòu)(Q1、Q4、Q5、Q6、Q7、Q9)及傳遞規(guī)則(Q8)進行推理。實體層次結(jié)構(gòu)是指實體的上下位關(guān)系，例如本科生是學生的子類，查找所有學生就需要對本科生進行推理；屬性層析結(jié)構(gòu)是指屬性的上下位關(guān)系，例如為學校工作的教授是該學校的成員，那么工作就是成員的子屬性。實體和屬性關(guān)系的層次結(jié)構(gòu)是混合了實體和屬性的多層次結(jié)構(gòu)。

3.3 實驗結(jié)果分析

1)吞吐量。圖2展示了系統(tǒng)的吞吐量，一共統(tǒng)計了9組不同的查詢。在單機下，最高吞吐量達到每秒19.5萬個三元組；在傳遞規(guī)則推理查詢中吞吐量會降到每秒6萬個。經(jīng)過中間集消除算法，系統(tǒng)吞吐量在C-SPARQL的4萬的吞吐量的基礎(chǔ)上提升了近4倍；但由于本實驗中系統(tǒng)為集中式處理系統(tǒng)，在吞吐量上對比分布式的BigSR有一定差距。

圖2 CSPARQL-Ci在LUBM查詢吞吐量

2)延遲。統(tǒng)計9組不同的查詢，記錄了多次查詢延遲的平均值，并分別與C-SPARQL和BigSR在單機的條件下作了對比實驗，分別記錄了多組數(shù)據(jù)的平均查詢延遲和傳遞規(guī)則查詢延遲，實驗結(jié)果如圖3和圖4所示。

圖3 CSPARQL-Ci與同類引擎查詢延遲對比

圖4 傳遞規(guī)則查詢延遲

如圖3所示，在單機測試環(huán)境下，平均查詢延遲是最低的；但是因為查詢還是基于Jena，所以隨著吞吐量的提升，查詢延遲比BigSR增幅要快。如圖4所示，針對傳遞規(guī)則查詢的統(tǒng)計中，由于推理結(jié)果是指數(shù)級，因此查詢的延遲也大幅度提升。實驗結(jié)果表明，優(yōu)化算法大幅度減少了推理和查詢時間。

3)索引結(jié)構(gòu)。本文也與在流平臺下的ECS索引進行了對比實驗。由于ECS是基于文件的靜態(tài)索引，在持續(xù)的流查詢中性能無法評估，并且ECS的查詢時間是微秒級別的，因此統(tǒng)計了索引的構(gòu)建時間作為查詢延遲，索引文件的載入時間不計算在內(nèi)。如圖5所示，本文在ECS的基礎(chǔ)上采用了部分索引，簡化了索引構(gòu)建過程，但在一定程度上增加了查詢時間，綜合效果更好。

圖5 索引構(gòu)建與查詢

4)索引效率。本文針對不同的查詢統(tǒng)計了多級索引刪除冗余數(shù)據(jù)的效率，如表3所示，在每秒一萬個三元組的速率下，分別統(tǒng)計了推理結(jié)果后、經(jīng)過常量索引篩選后、經(jīng)過變量索引篩選后和最終滿足查詢結(jié)果的數(shù)量。在統(tǒng)計過程中，中間級消除算法可以減少近99%的無關(guān)推理結(jié)果，因為算法依賴查詢條件之間常量和變量之間的依賴關(guān)系，所以隨著查詢條件的增多，消除比例也在增加。

表3 索引效率評估

續(xù)表3

4 結(jié) 語

本文在C-SPARQL的基礎(chǔ)上，加入了Cichlid推理引擎。針對前向推理數(shù)據(jù)冗余提出了傳遞規(guī)則優(yōu)化算法和中間級消除算法，并與ECS、BigSR和C-SPARQL做了對比實驗，實驗結(jié)果表明，本文的推理機制不僅提高了原有系統(tǒng)吞吐量，而且大幅度地降低了查詢延遲。但是本文方法仍然存在一些不足，例如基于Jena查詢在一定程度上限制了查詢效率，因此系統(tǒng)在處理大規(guī)模的RDF流推理仍存在不足，未來可以考慮實現(xiàn)分布式索引查詢，增加RDF流推理的規(guī)模。