高 峰 楊帆玉 顧進(jìn)廣

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

0 引 言

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

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

1 相關(guān)工作

1.1 RDF流和C-SPARQL

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

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

1.2 RDFS流推理

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

表1 RDFS規(guī)則集

RDF數(shù)據(jù)的推理可以采用前向鏈?zhǔn)胶秃笙蜴準(zhǔn)絻煞N不同的策略進(jìn)行推理。前向鏈?zhǔn)酵评硎菑臄?shù)據(jù)開始，通過利用規(guī)則集循環(huán)迭代得到新的RDF數(shù)據(jù)，將派生的RDF數(shù)據(jù)添加到原始RDF數(shù)據(jù)中，以供后期查詢和推理，如Cichlid；而后向鏈?zhǔn)酵评韯t是根據(jù)查詢條件出發(fā)，根據(jù)規(guī)則集動(dòng)態(tài)查詢是否有滿足的事實(shí)，如EP-SPARQL[10]。文獻(xiàn)[11]提出，前向鏈?zhǔn)酵评硐鄬?duì)縮短了查詢響應(yīng)時(shí)間，但是資源開銷比較大而且會(huì)有重復(fù)數(shù)據(jù)。

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

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

本節(jié)在CSPARQL引擎的基礎(chǔ)上擴(kuò)展，并提出一種基于多級(jí)索引的前向語義數(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主要由以下四個(gè)部分組成。

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

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

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

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

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

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

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

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

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

進(jìn)一步對(duì)于所有與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)存在，那么放入該子圖，如果不存在則新建子圖并放入該元素；生成同一學(xué)校的學(xué)生與所屬學(xué)校對(duì)應(yīng)的一個(gè)子圖。

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

2.3 中間集消除

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

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

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

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

3.1 實(shí)驗(yàn)配置

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

3.2 實(shí)驗(yàn)場(chǎng)景設(shè)置

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

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

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

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

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

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

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

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

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

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

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

表3 索引效率評(píng)估

續(xù)表3

4 結(jié) 語

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