基于多級索引的前向語義數據流推理

高 峰 楊帆玉 顧進廣

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

0 引 言

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

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

1 相關工作

1.1 RDF流和C-SPARQL

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

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

1.2 RDFS流推理

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

表1 RDFS規則集

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

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

2 數據流推理引擎設計

本節在CSPARQL引擎的基礎上擴展，并提出一種基于多級索引的前向語義數據流推理引擎(CSPARQL-Ci)，其系統架構如圖1所示。

圖1 CSAPRQL-Ci系統架構

2.1 系統架構

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

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

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

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

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

2.2 優化傳遞規則推理

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

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

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

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

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

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

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

算法1傳遞規則推理

輸入：三元組triples。

輸出：推理結果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)子圖索引構建：將篩選滿足傳遞規則的三元組作為輸入數據；開始遍歷三元組，如果該三元組表示的元素所屬的子圖已經存在，那么放入該子圖，如果不存在則新建子圖并放入該元素；生成同一學校的學生與所屬學校對應的一個子圖。

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

2.3 中間集消除

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

表2 索引結構

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

算法2中間集消除

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

輸出：消除后結果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++)

//未知變量的數量

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)根據常量篩選滿足的集合，建立查詢條件——滿足條件三元組集合的關系表，將輸入的每個三元組放入滿足條件的集合，如果存在一個三元組滿足多個條件，需放入多個集合中。

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

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

3 實 驗

3.1 實驗配置

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

3.2 實驗場景設置

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

3.3 實驗結果分析

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

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

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

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

圖4 傳遞規則查詢延遲

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

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

圖5 索引構建與查詢

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

表3 索引效率評估

續表3

4 結 語

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