馮 鈞，王秉發(fā)，陸佳民

（河海大學(xué)計算機(jī)與信息學(xué)院，南京 211100）

0 引言

資源描述框架（Resource Description Framework，RDF）作為萬維網(wǎng)聯(lián)盟（World Wide Web consortium，W3C）定義的一種展示、共享和連接語義網(wǎng)絡(luò)數(shù)據(jù)的標(biāo)準(zhǔn)數(shù)據(jù)模型，已經(jīng)被廣泛用于各種數(shù)據(jù)科學(xué)應(yīng)用中。隨著RDF 數(shù)據(jù)規(guī)模的日益增長，集中式存儲已經(jīng)難以滿足存儲和查詢處理需求，需要高性能的分布式RDF 數(shù)據(jù)管理系統(tǒng)對大規(guī)模的RDF 數(shù)據(jù)進(jìn)行管理和重用。

現(xiàn)有的分布式RDF 系統(tǒng)通過一個無共享的集群實(shí)現(xiàn)對大規(guī)模RDF 數(shù)據(jù)的存儲和管理［1］，采用基于連接的方法（Join-based）和基于圖匹配（Graph-matching Based）的方法［2］進(jìn)行SPARQL（Simple Protocol and RDF Query Language）［3］查詢計算。得益于關(guān)系數(shù)據(jù)庫技術(shù)的成熟性、健壯性和可擴(kuò)展性，大量基于關(guān)系存儲模式的分布式RDF 系統(tǒng)應(yīng)運(yùn)而生。按照系統(tǒng)的執(zhí)行模型不同，本文中將這些系統(tǒng)分為：基于主存（Random Access Memory，RAM）的系統(tǒng)和基于Spark 的系統(tǒng)。

現(xiàn)有的基于RAM 的系統(tǒng)和基于Spark 的系統(tǒng)僅針對高選擇性的小直徑查詢進(jìn)行了優(yōu)化，可以高效地響應(yīng)小直徑查詢；但是SPARQL 查詢是一個連接密集型查詢，據(jù)研究顯示，用戶傾向請求越來越復(fù)雜的交互式查詢，交互式DBpedia 的SPARQL 查詢?nèi)罩局?，最高可達(dá)10 個連接，而生物醫(yī)學(xué)領(lǐng)域的分析查詢甚至包括50 個以上的連接［4］。因此，有必要針對交互式查詢中涉及的多連接復(fù)雜型查詢進(jìn)行優(yōu)化。為了有效提高分布式RDF 系統(tǒng)的查詢性能，現(xiàn)有的研究主要從以下兩個方面進(jìn)行優(yōu)化［5］：1）優(yōu)化關(guān)系存儲模式；2）優(yōu)化SPARQL 到SQL（Structured Query Language）的查詢轉(zhuǎn)化。通過減少查詢處理期間連接操作數(shù)量、輸入數(shù)據(jù)大小和中間結(jié)果大小［6］，提升分布式SPARQL 查詢性能。

本文的主要工作包括：1）詳細(xì)調(diào)研了現(xiàn)有的基于RAM和基于Spark 的系統(tǒng)在分布式SPARQL 查詢上的相關(guān)工作；2）將查詢準(zhǔn)確性作為分布式SPARQL 查詢的評價指標(biāo)，支持SPARQL 查詢結(jié)果的持久化，實(shí)現(xiàn)了查詢結(jié)果的校驗(yàn)；3）結(jié)合查詢準(zhǔn)確性、查詢響應(yīng)時間這兩個評價指標(biāo)，對8 個代表系統(tǒng)的查詢性能進(jìn)行了廣泛的實(shí)驗(yàn)評估；4）討論分析當(dāng)前分布式SPARQL 查詢的局限性，展望了未來可能的研究方向。

1 相關(guān)理論

1.1 SPARQL查詢

SPARQL［3］是W3C 提出的一種標(biāo)準(zhǔn)查詢語言，以實(shí)現(xiàn)對大規(guī)模RDF 數(shù)據(jù)的查詢與檢索。SPARQL 查詢的基本組成單元是三元組模式，一組三元組模式構(gòu)成了基本圖模式（Basic Graph Pattern，BGP），其形式化定義如定義1 所示。

定義1三元組模式和基本圖模式。tpi={t|t∈(I∪V∪B)×(I∪V)×(I∪L∪V∪B)}，其中：I表示國際化資源標(biāo)識符集，B表示空白節(jié)點(diǎn)集，L表示字面量集，V表示變量集，并且這四個集合互不相交。如果一個三元組是該集合中的元素，則該三元組稱為一個三元組模式tpi。，基本圖模式由一組三元組模式進(jìn)行合取運(yùn)算組成，因此也稱為合取查詢（Conjunctive Query）。

合取查詢本質(zhì)上是在數(shù)據(jù)集上對一組經(jīng)三元組模式選擇后的三元組進(jìn)行連接運(yùn)算，三元組模式選擇性［7］的形式化定義如定義2 所示。

定義2三元組模式選擇性。Sel(tpi，D)=，其中：tpi表示SPARQL 查詢Q 的三元組模式；D表示一個數(shù)據(jù)集；N為數(shù)據(jù)集D中三元組的總個數(shù)；Card(tpi，D)表示D中匹配三元組模式tpi的三元組個數(shù)。

SPARQL 查詢由基本圖模式組成，根據(jù)查詢圖的結(jié)構(gòu)可將SPARQL 查詢分為三種基本形態(tài)：鏈型查詢、星型查詢和雪花型查詢以及由這三種基本查詢組合而成的復(fù)雜查詢［8］。SPARQL BGP 的直徑定義為最長路徑，即不考慮邊的方向，最長的三元組模式連通序列［9］。

1）鏈型查詢：對三元組模式間的主語（賓語）?賓語（主語）進(jìn)行連接，其查詢圖結(jié)構(gòu)如圖1 所示，連接變量在一個三元組中位于主語位置，在另一個三元組中位于賓語位置，鏈型查詢模式的直徑對應(yīng)查詢模式中三元組模式的個數(shù)。

圖1 鏈型查詢圖結(jié)構(gòu)示意圖Fig.1 Schematic diagram of chain query graph structure

2）星型查詢：對三元組模式間的主語?主語進(jìn)行連接，其查詢圖結(jié)構(gòu)如圖2 所示，連接變量位于主語位置，查詢直徑為1。星型查詢模式在SPARQL 查詢中經(jīng)常出現(xiàn)，許多查詢處理器都針對這種工作負(fù)載進(jìn)行了優(yōu)化。

圖2 星型查詢圖結(jié)構(gòu)示意圖示意圖Fig.2 Schematic diagram of star query graph structure

3）雪花型查詢：由短路徑連接的若干個星型查詢組合而成，其查詢圖結(jié)構(gòu)如圖3 所示，該查詢圖由兩個星型查詢圖組合而成，其查詢直徑為3。

圖3 雪花型查詢圖結(jié)構(gòu)示意圖Fig.3 Schematic diagram of snowflake query graph structure

4）復(fù)雜型查詢：由三種基本查詢模式組合而成的復(fù)雜查詢，其查詢圖結(jié)構(gòu)如圖4 所示，該查詢圖由兩個星型查詢子圖和一個鏈型查詢子圖組合而成，其查詢直徑為4。

圖4 復(fù)雜型查詢圖結(jié)構(gòu)示意圖Fig.4 Schematic diagram of complex query graph structure

1.2 關(guān)系存儲模式

現(xiàn)有的基于關(guān)系的分布式RDF 系統(tǒng)中，涉及的關(guān)系存儲模式包括：

1）垂直劃分（Vertical Partitoning，VP）［10］：按照謂語創(chuàng)建關(guān)系模式為（subject，object）的表，將相同謂語的三元組的主語、賓語存入同一張表中，表的總數(shù)量為謂語的數(shù)量。

2）擴(kuò)展垂直劃分（Extended VP，ExtVP）［8］：預(yù)先對具有連接相關(guān)性的兩個垂直劃分表進(jìn)行半連接計算，當(dāng)相應(yīng)的擴(kuò)展垂直劃分表對原始的垂直劃分表縮減量達(dá)到了設(shè)定的閾值時才物化這些表。

3）寬屬性表（Wide Property Table，WPT）［11］：按照主語創(chuàng)建關(guān)系模式為（subject，property1，…，propertyn）的表，即將同類主語存入一張表中。由于不同主語的謂語集合也存在差異，容易存在空值問題。此外，寬屬性表還存在多值屬性存儲問題。

4）逆寬屬性表（inverse Wide Property Table，iWPT）［12］：按照賓語創(chuàng)建關(guān)系模式為(，object)的表，即為數(shù)據(jù)集中的每個屬性包含一個不同的列，將一個賓語的所有信息存入同一行。因此，基于賓語?賓語的連接計算可以通過對iWPT 進(jìn)行一次掃描操作獲取。

5）寬屬性表?逆寬屬性表內(nèi)連接（inner join between WPT and iWPT，jWPT-inner）：預(yù)先將寬屬性表和逆寬屬性表進(jìn)行內(nèi)連接運(yùn)算，jWPT-inner 表每一行包含一個資源一跳上的所有信息。

6）六重索引（Sextuple Indexing）［11］：以三元組〈主語，謂語，賓語〉的全排列方式對應(yīng)地創(chuàng)建主語?謂語?賓語（spo）、主語?賓語?謂語（sop）、謂語?主語?賓語（pso）、謂語?賓語?主語（pos）、賓語?主語?謂語（osp）、賓語?謂語?主語（ops）六張表。六重索引主要分為兩組：一組是主語索引集，包括spo表、sop 表和pso 表；另一組是賓語索引集，包括osp 表、ops 表和pos 表。

關(guān)系模式設(shè)計［13］對分布式SPARQL 查詢效率起著至關(guān)重要的作用，不同的關(guān)系模式設(shè)計不僅產(chǎn)生不同的物理數(shù)據(jù)分區(qū)，還意味著相同SPARQL 查詢的不同SQL 轉(zhuǎn)換。因此，通過優(yōu)化關(guān)系存儲模式，可以有效地減少連接操作數(shù)量、輸入數(shù)據(jù)大小和中間結(jié)果大小，從而提高SPARQL 查詢處理的效率。

1.3 SPARQL到SQL的查詢轉(zhuǎn)化

基于連接的SPARQL 查詢計算將每個圖模式轉(zhuǎn)化為等效的SQL 表達(dá)式，并在單張表或多張表上使用連接操作組合每次迭代的結(jié)果。在現(xiàn)有的分布式RDF 系統(tǒng)中，SPARQL 查詢是通過三元組模式進(jìn)行計算，一個查詢執(zhí)行規(guī)劃可以看作三元組模式在變量上的連接。但是由于SPARQL 查詢是連接密集型查詢，并且SPARQL 連接計劃的狀態(tài)空間的大小又與連接數(shù)量呈指數(shù)相關(guān)，在這樣的空間下，搜索最優(yōu)的查詢規(guī)劃是一個NP（Non-deterministic Polynomial）困難問題［14］。

現(xiàn)有的分布式SPARQL 查詢優(yōu)化使用確定的估計器作為查詢規(guī)劃的評估指標(biāo)［15］，對SPARQL 連接狀態(tài)空間中所有可能的查詢規(guī)劃進(jìn)行探索，通過代價評估確定最優(yōu)的查詢規(guī)劃?，F(xiàn)有的兩種主流的搜索策略為：基于動態(tài)規(guī)劃的查詢規(guī)劃和基于啟發(fā)式的查詢規(guī)劃［16］。

基于動態(tài)規(guī)劃的查詢規(guī)劃的核心思想是在搜索連接計劃時，根據(jù)預(yù)先計算的統(tǒng)計信息選擇代價估計最小的作為最優(yōu)查詢計劃，并通過合并冗余狀態(tài)，減小搜索空間。

基于啟發(fā)式的查詢規(guī)劃的核心思想是通過一定的搜索策略對部分狀態(tài)空間進(jìn)行啟發(fā)式搜索，與動態(tài)規(guī)劃方法相比，它能節(jié)約大量的搜索時間，但是確定的查詢規(guī)劃不一定是最優(yōu)的。

2 基于Spark的系統(tǒng)

S2RDF（SPARQL on Spark for RDF）［8］使用垂直劃分和基于半連接預(yù)處理的擴(kuò)展垂直劃分相結(jié)合的混合關(guān)系存儲模式進(jìn)行存儲。在數(shù)據(jù)加載階段，S2RDF 通過選擇性閾值物化部分垂直劃分?jǐn)?shù)據(jù)表之間的左半連接結(jié)果并存儲在關(guān)系數(shù)據(jù)表中，減小了連接操作時輸入數(shù)據(jù)的大小。在查詢處理階段，S2RDF 首先根據(jù)統(tǒng)計信息為基本圖模式中的每一個三元組模式選擇查詢候選表，接著通過Jena ARQ（a SPARQL Processor for Jena）將SPARQL 查詢解析到相應(yīng)的代數(shù)樹上，應(yīng)用基本的代數(shù)優(yōu)化后生成等效的Spark SQL 表達(dá)式，然后通過經(jīng)驗(yàn)知識進(jìn)行連接順序優(yōu)化，避免連接懸掛三元組模式，從而避免了笛卡兒積，減小了中間連接結(jié)果大小，有效地提高了查詢效率。S2RDF 通過預(yù)先計算三元組模式中變量的半連接結(jié)果，有效地提高了查詢性能，但導(dǎo)致磁盤占用空間大、數(shù)據(jù)加載時間長等問題。此外，優(yōu)化查詢連接時，S2RDF 假設(shè)較小的連接輸入通常導(dǎo)致較小的連接輸出，但這個假設(shè)并不是完全正確的。

SPARQLGX［17］使用垂直劃分模式進(jìn)行RDF 數(shù)據(jù)存儲，基于連接選擇性進(jìn)行連接順序優(yōu)化。在查詢處理階段，SPARQLGX 對基本圖模式的每個查詢模式分別進(jìn)行處理，從磁盤中讀取相關(guān)數(shù)據(jù)并使用常量進(jìn)行過濾；然后尋找具有相同變量的三元組模式進(jìn)行連接，通過中間結(jié)果的統(tǒng)計信息，優(yōu)化連接順序；最終將SPARQL 查詢片段中的每個操作符轉(zhuǎn)化為符合Spark 的Scala 命令序列，通過Spark API（Application Programming Interface）直接執(zhí)行查詢。Li 等［18］在SPARQLGX 的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種基于語義連接信息鏈的查詢優(yōu)化方法SparkIlink。SparkIlink 在查詢處理階段，首先根據(jù)變量對三元組模式進(jìn)行映射，然后通過循環(huán)遍歷映射圖搜索具有值交集的映射并將其加入語義信息鏈，最后根據(jù)語義信息鏈的順序和連接三元組信息確定查詢連接順序，通過Spark API 直接執(zhí)行查詢。SparkIlink 通過語義連接信息鏈優(yōu)化連接順序，減小了中間連接結(jié)果大小，在SPARQLGX 的基礎(chǔ)上有效提高了鏈型、星型和雪花型這三種基本查詢類型的查詢性能。

PRoST（Partitioned RDF on Spark Tables）［19］采用垂直劃分和寬屬性表進(jìn)行混合存儲。查詢處理階段，PRoST 將SPARQL 查詢轉(zhuǎn)化為連接樹，根據(jù)連接樹節(jié)點(diǎn)的優(yōu)先級，自底向上進(jìn)行計算。其核心思想是將主語相同的三元組模式歸為一組，存入根節(jié)點(diǎn)，使用屬性表進(jìn)行查詢；將其余的節(jié)點(diǎn)存入葉子節(jié)點(diǎn)，使用垂直劃分表處理。PRoST 通過寬屬性表減少了連接操作的數(shù)量，通過數(shù)據(jù)加載階段的統(tǒng)計信息優(yōu)化查詢連接順序，有效地減小了中間結(jié)果的大小，從而提高了查詢效率。

Hassan 等［20］在2018 年提出了兩種新的關(guān)系存儲模式VPExp 和3CStore。VPExp 模式根據(jù)賓語的顯式類型信息拆分垂直劃分表，從而最小化查詢計算時輸入數(shù)據(jù)的大??；但是它的適用范圍僅針對謂詞為“rdf_type”且賓語為字面量的三元組模式。3CStore 模式存儲三元組模式間相關(guān)性（除賓語?賓語相關(guān)）的預(yù)連接計算結(jié)果，從而減少了查詢處理時的輸入數(shù)據(jù)大小和連接操作數(shù)量。在查詢處理階段，根據(jù)查詢編譯器將SPARQL 查詢解析到相應(yīng)的代數(shù)樹中，并將相應(yīng)的關(guān)系存儲模式轉(zhuǎn)化為等效的SQL 表達(dá)式進(jìn)行查詢計算。2019 年Hassan 等［21］又在PRoST 的基礎(chǔ)上，提出了一種名為“子集寬屬性表”（Subset Property Table，SPT）的關(guān)系存儲模式，它通過顯式地避免存儲空值和采用嵌套數(shù)據(jù)結(jié)構(gòu)存儲多值屬性的方式，有效地解決了傳統(tǒng)屬性表中所存在的空值和多值問題；通過拆分寬屬性表，最小化查詢連接時輸入數(shù)據(jù)的大小，降低了連接的復(fù)雜度。SPT+VP 中采用子集寬屬性表和垂直劃分相結(jié)合的混合存儲模式存儲數(shù)據(jù)，在查詢處理階段，與PRoST 的思想一致，使用子集寬屬性表處理星型查詢，使用垂直劃分表處理其他查詢；通過自定義的查詢編譯器將SPARQL 轉(zhuǎn)化為Spark SQL，根據(jù)三元組模式中常量的數(shù)量和數(shù)據(jù)集統(tǒng)計信息設(shè)定查詢連接的優(yōu)先級，從而優(yōu)化查詢。

Chawla 等［5］提出了HyPSo，它采用垂直劃分和哈希劃分相結(jié)合的混合關(guān)系存儲模式進(jìn)行數(shù)據(jù)存儲。HyPSo 首先對初始RDF 數(shù)據(jù)集進(jìn)行垂直劃分，然后對垂直劃分后的結(jié)果集進(jìn)行基于主語的哈希劃分，這種混合劃分方式有效地減少了處理星型查詢時所需的通信開銷，同時又減少了連接操作的數(shù)量和數(shù)據(jù)搜索空間，從而優(yōu)化了星型查詢。

Schievelbein 等［12］提出了一種名為“逆屬性增強(qiáng)的寬屬性表”（iWPT）的關(guān)系存儲模式，并利用相同RDF 數(shù)據(jù)圖的多個寬屬性表擴(kuò)展表來進(jìn)行混合存儲。其核心思想是根據(jù)不同關(guān)系模式構(gòu)造中間抽象樹來表示SPARQL 查詢，以最小化查詢計算所需要的連接操作數(shù)量。實(shí)驗(yàn)結(jié)果表明，采用寬屬性表、逆寬屬性表和寬屬性表?逆寬屬性內(nèi)連接（WPT+iWPT+jWPT-inner）的混合存儲模式，優(yōu)化了除鏈型查詢外的所有查詢類型的查詢性能；但是，使用混合存儲進(jìn)行存儲時，需要權(quán)衡查詢計算中連接操作的數(shù)量與所有查詢候選表的行數(shù)。

3 基于RAM的系統(tǒng)

Gurajada 等［22］提出了內(nèi)存型分布式RDF 系統(tǒng)TriAD（Triple Asynchronous Distributed），它是一種基于內(nèi)存的分布式RDF 系統(tǒng)，使用六重索引模式進(jìn)行RDF 數(shù)據(jù)存儲，通過MPI（Message Passing Interface）協(xié)議進(jìn)行SPARQL 查詢處理。在數(shù)據(jù)預(yù)處理階段，TriAD 在主節(jié)點(diǎn)上建立一個全局概述圖，并將其水平劃分為若干塊分發(fā)到從節(jié)點(diǎn)上。在查詢處理階段，首先在主節(jié)點(diǎn)上對概述圖進(jìn)行圖匹配獲取查詢圖中每個三元組模式的候選三元組，然后在從節(jié)點(diǎn)上對數(shù)據(jù)圖上的候選三元組進(jìn)行連接操作獲得最終解。采用自底向上的動態(tài)規(guī)劃算法確定概要圖的最優(yōu)探索順序和針對六重索引的最優(yōu)三元組模式連接順序，使用灌木叢計劃來限制動態(tài)規(guī)劃搜索樹的形狀，從而減少搜索空間。TriAD 的查詢性能始終比集中式RDF 引擎性能好兩個數(shù)量級；但是，TriAD 中大量的索引導(dǎo)致數(shù)據(jù)冗余、存儲空間消耗大、數(shù)據(jù)更新的一致性維護(hù)代價大等問題。

Harbi 等［23］提出了內(nèi)存型分布式RDF 系統(tǒng)AdPart，它通過基于主語的哈希劃分方式實(shí)現(xiàn)RDF 數(shù)據(jù)的初始劃分，通過分層熱圖監(jiān)控查詢工作負(fù)載，設(shè)定頻繁閾值標(biāo)識頻繁模式，使用頻繁模式指導(dǎo)RDF 數(shù)據(jù)進(jìn)行增量重劃分。在查詢處理階段，采用動態(tài)規(guī)劃算法設(shè)計查詢連接順序，使用右深度樹約束搜索樹形狀，基于局部性哈希和自適應(yīng)劃分加速SPARQL 查詢。AdPart 通過掃描索引獲得子查詢的局部匹配結(jié)果，利用分布式半連接（Distributed Semi-Join，DSJ）算法獲得整個子查詢的計算結(jié)果。由于數(shù)據(jù)駐留在內(nèi)存中并且是哈希索引的，可以利用局部性哈希來并行處理星型查詢，最小化了查詢計算期間的通信代價。此外，使用頻繁模式驅(qū)動數(shù)據(jù)進(jìn)行增量重劃分，實(shí)現(xiàn)了對系統(tǒng)對查詢工作負(fù)載的自適應(yīng)性，有效地提高了分布式SPARQL 的查詢性能；但是，AdPart 存在查詢準(zhǔn)確性較低，查詢計算過程中發(fā)生內(nèi)存溢出等問題。

Potter 等［24］提出了內(nèi)存型分布式RDF 系統(tǒng)RDFox，它使用圖劃分的方式進(jìn)行數(shù)據(jù)存儲，使用哈希索引在內(nèi)存中索引數(shù)據(jù)。在查詢處理階段，使用索引嵌套循環(huán)連接作為分布式連接算法，讓集群節(jié)點(diǎn)在數(shù)據(jù)分區(qū)上并行計算查詢。RDFox在查詢處理期間動態(tài)交換數(shù)據(jù)，使用流量控制機(jī)制限制分布式連接計算中連接中間結(jié)果的物化，從而大大限制查詢計算期間的內(nèi)存占用。RDFox 通過動態(tài)數(shù)據(jù)交換和流量控制機(jī)制，使得RDFox 在查詢響應(yīng)時間、網(wǎng)絡(luò)通信和內(nèi)存使用方面優(yōu)于其他方法。此外，通過在分布式連接算法中限制內(nèi)存使用，成功響應(yīng)了復(fù)雜鏈型查詢。但是，RDFox 在低選擇性的復(fù)雜型查詢上的性能仍然較差。

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

4.1 對比系統(tǒng)

Abdelaziz 等［25］對12 個具有代表性的分布式RDF 系統(tǒng)在不同數(shù)據(jù)集和查詢負(fù)載上進(jìn)行了實(shí)驗(yàn)評估，實(shí)驗(yàn)結(jié)果表明AdPart 和TriAD 的查詢性能持續(xù)優(yōu)于其他系統(tǒng)。因此，本文使用AdPart 和TriAD 作為基于RAM 的分布式RDF 對比系統(tǒng)。此外，由于AdPart 和TriAD 不能響應(yīng)低選擇性的大直徑查詢，Potter 等［24］提出的RDFox 通過動態(tài)數(shù)據(jù)交換和流量控制機(jī)制成功響應(yīng)了復(fù)雜型查詢，因此，將RDFox 也作為基于RAM 的對比系統(tǒng)。由于RDFox 未公開源代碼，所以本文中與RDFox 相關(guān)的實(shí)驗(yàn)均采用了文獻(xiàn)中公布的結(jié)果。

此外，為了驗(yàn)證不同關(guān)系存儲模式對查詢性能的影響，本文還將S2RDF、PRoST、WiW（WPT+iWPT）、C3W（WPT+iWPT+jWPT-inner）和C2WVP（WPT+iWPT+VP）作為對比系統(tǒng)。其中S2RDF 的選擇性閾值設(shè)定為0.25，WiW 采用屬性表和逆屬性表進(jìn)行混合存儲，C3W 使用屬性表、逆屬性表和屬性表?逆屬性表的內(nèi)連接表進(jìn)行混合存儲，C2WVP 采用屬性表、逆屬性表和垂直劃分表進(jìn)行混合存儲，這些系統(tǒng)都沿用PRoST 中的查詢執(zhí)行器執(zhí)行SPARQL 查詢計算。以上實(shí)驗(yàn)對比系統(tǒng)的相關(guān)特征如表1 所示。

表1 實(shí)驗(yàn)對比系統(tǒng)的相關(guān)特征Tab.1 Related characteristics of experimental systems for comparison

4.2 基準(zhǔn)數(shù)據(jù)集和查詢集

基準(zhǔn)數(shù)據(jù)集可以分為合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集［7］。真實(shí)數(shù)據(jù)集可以使用真實(shí)數(shù)據(jù)和用戶查詢?nèi)罩緦ο到y(tǒng)進(jìn)行基準(zhǔn)測試，但是真實(shí)數(shù)據(jù)集無法測試不同數(shù)據(jù)集大小和查詢工作負(fù)載下RDF 系統(tǒng)的可伸縮性。合成數(shù)據(jù)集利用生成數(shù)據(jù)，有助于測試不同數(shù)據(jù)集大小下系統(tǒng)的可伸縮性。本文中同時在合成數(shù)據(jù)集WatDiv（Waterloo SPARQL Diversity Test Suite）和真實(shí)數(shù)據(jù)集YAGO2（Yet Another Great Ontology version 2.0）上進(jìn)行實(shí)驗(yàn)。表2 中展示了十億規(guī)模下的WatDiv 數(shù)據(jù)集（WatDiv-1B）和YAGO2 數(shù)據(jù)集統(tǒng)計信息。

表2 實(shí)驗(yàn)所使用數(shù)據(jù)集的統(tǒng)計信息Tab.2 Statistics of datasets used in experiments

WatDiv 基準(zhǔn)［26］：加拿大滑鐵盧大學(xué)于2014 年提出的用于描述用戶實(shí)體相關(guān)信息的數(shù)據(jù)集，包括數(shù)據(jù)生成器和查詢生成器。WatDiv 查詢集由查詢器根據(jù)預(yù)定義的查詢模板生成。本文中的查詢集由基礎(chǔ)測試用例和增量鏈型測試用例組成。其中，基礎(chǔ)測試用例由20 個預(yù)定義的基礎(chǔ)類型查詢模板生成，根據(jù)查詢形狀可分為：鏈型（Ln）、星型（Sn）、雪花型（Fn）和復(fù)雜型（Cn）四類；增量鏈型測試用例由18 個增量鏈型（Incremental Linear，IL）查詢模板生成，根據(jù)三元組模式中主語類別分為：IL-1、IL-2 和IL-3 三類查詢，IL-1、IL-2 和IL-3 查詢分別由綁定的用戶、綁定的零售商以及未綁定的主語組成，每個查詢類型的直徑由5 增大為10。

YAGO2［27］：來源于多種語言的維基百科，包含WordNet、GeoNames 和其他數(shù)據(jù)源，其中包含1.5 億個三元組。據(jù)YAGO2 查詢?nèi)罩撅@示，有77%的三元組模式都涉及星型連接，平均每個查詢有1.8 個基于主語的連接。由于YAGO2是真實(shí)數(shù)據(jù)，沒有提供查詢基準(zhǔn)，所以本文中仍然遵循文獻(xiàn)［23］中提出的四種代表性查詢類型。

4.3 評價指標(biāo)

查詢響應(yīng)時間：在各類查詢類型上的執(zhí)行查詢處理的總時間，包括查詢編譯時間和查詢執(zhí)行時間。

查詢準(zhǔn)確率：在各類查詢類型上查詢結(jié)果正確查詢的個數(shù)與查詢總個數(shù)的比值。本文中支持將SPARQL 查詢結(jié)果持久化到Hadoop 分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）文件中，通過將查詢結(jié)果與基準(zhǔn)結(jié)果進(jìn)行校驗(yàn)，從而客觀準(zhǔn)確地對系統(tǒng)的查詢準(zhǔn)確率進(jìn)行定量評估。

4.4 實(shí)驗(yàn)環(huán)境

搭建一個由10 個節(jié)點(diǎn)組成的無共享服務(wù)器集群，通過專用帶寬為1 Gb/s 的網(wǎng)絡(luò)進(jìn)行連接。每個服務(wù)器運(yùn)行Ubuntu 16.04 系統(tǒng)，有8 個vCPU、32 GB RAM 和512 GB 磁盤存儲空間，安裝Hadoop 2.7.1 和Spark 2.0.2，每個Spark 執(zhí)行器都設(shè)置為20 GB 內(nèi)存。

對每個查詢進(jìn)行10 次評估，記錄每個系統(tǒng)報告的查詢計算時間，并計算每種查詢類型的查詢時間的幾何平均值（Geometric Mean，GM）。

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

為了全面評估上述8 個分布式RDF 系統(tǒng)的查詢性能，本文中選擇了影響SPARQL 查詢性能的三個特征：查詢類型、查詢直徑以及數(shù)據(jù)集類型，對相關(guān)系統(tǒng)進(jìn)行了實(shí)驗(yàn)，并結(jié)合查詢響應(yīng)時間和查詢準(zhǔn)確性兩個指標(biāo)對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

5.1 查詢響應(yīng)時間分析

5.1.1 不同查詢類型下的查詢效率

本組實(shí)驗(yàn)使用WatDiv-1B 作為數(shù)據(jù)集，WatDiv 基礎(chǔ)測試用例作為查詢集，對各個系統(tǒng)在不同查詢類型下的查詢性能進(jìn)行評估。表3 展示了各個系統(tǒng)在不同查詢類型的查詢響應(yīng)時間。

表3 WatDiv基本查詢集上各系統(tǒng)的查詢響應(yīng)時間對比Tab.3 Comparison of query time of different systems on WatDiv basic query set

實(shí)驗(yàn)結(jié)果表明：1）不同查詢類型下的查詢時間差異明顯，基于RAM 和基于Spark 的系統(tǒng)在鏈型查詢、星型查詢上的查詢效率都優(yōu)于雪花型查詢和復(fù)雜型查詢；2）基于RAM的系統(tǒng)在基礎(chǔ)測試用例下的查詢效率優(yōu)于基于Spark 的系統(tǒng)三個數(shù)量級，在不到1 s 的時間內(nèi)就可以響應(yīng)10 億三元組的RDF 圖上的基準(zhǔn)測試查詢；3）對于基于Spark 的系統(tǒng)而言，不同的關(guān)系存儲模式對于查詢效率也有顯著的影響。

下面結(jié)合實(shí)驗(yàn)結(jié)果對各個系統(tǒng)在不同查詢類型下的查詢響應(yīng)時間進(jìn)行具體分析?；赗AM 的系統(tǒng)在基礎(chǔ)測試用例下表現(xiàn)出了優(yōu)越的查詢性能，主要原因是基礎(chǔ)查詢用例都是小直徑的高選擇性查詢，查詢連接過程中的中間結(jié)果較小，而基于RAM 的系統(tǒng)在查詢過程中將數(shù)據(jù)駐留在內(nèi)存中，并且通過異步執(zhí)行的方式進(jìn)行并行計算，有效提高了查詢效率，而基于Spark 的系統(tǒng)受限于Spark 同步執(zhí)行查詢計劃的限制，減少了查詢計算的并行性，極大影響了查詢性能。

對于雪花型查詢（Fn），其涉及的基本查詢圖模式中只包含主語?賓語連接、主語?主語連接。C3W 在該類查詢上的性能優(yōu)于其他基于Spark 的系統(tǒng)，主要是該系統(tǒng)中預(yù)先對屬性表和逆屬性表進(jìn)行了內(nèi)連接計算，通過一次表掃描就可以獲得一個資源一跳上的所有信息，從而最大限度地減少了連接操作數(shù)量，縮短了查詢時間。WiW 在查詢F4 中的性能顯著低于其他基于Spark 的系統(tǒng)，主要由于在該類查詢中涉及屬性表和逆屬性表的連接操作，從而導(dǎo)致查詢效率的降低。

對于復(fù)雜型查詢（Cn），查詢C1 和C2 包含四種不同的連接模式，查詢C3 只包含低選擇性的主語?主語連接?；赗AM 的系統(tǒng)在該類查詢上的性能比基于Spark 的系統(tǒng)高出兩個數(shù)量級，對于C3 查詢RDFox 和TriAD 可以快速響應(yīng)，但AdPart 要比它們慢兩個數(shù)量級。PRoST、WiW 以及C2WVP在C1 和C3 查詢上的性能大致相當(dāng)。S2RDF 在C3 查詢上由于涉及大量的連接操作，查詢性能顯著降低。而C3W 由于jWPT-inner 表中存在較多的行數(shù)，查詢的性能受限于輸入數(shù)據(jù)大小，因此無法響應(yīng)C2 查詢。

5.1.2 不同查詢直徑下的查詢效率

WatDiv 基礎(chǔ)測試用例可以有效地評估系統(tǒng)對于不同復(fù)雜度的查詢工作負(fù)載的效率，但是基礎(chǔ)測試用例中絕大多數(shù)查詢的查詢直徑都很小，因此為了測試實(shí)驗(yàn)系統(tǒng)在不同查詢直徑下的查詢性能，本組實(shí)驗(yàn)中使用了由Sch?tzle 等［8］提出的增量鏈型查詢集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表4 所示。

表4 WatDiv增量鏈型查詢集上各系統(tǒng)的查詢響應(yīng)時間對比Tab.4 Comparison of query response time of different systems on WatDiv incremental linear query set

實(shí)驗(yàn)結(jié)果表明：1）基于RAM 的系統(tǒng)在低選擇性的增量鏈型查詢IL-1 和IL-2 的效率高出基于Spark 的系統(tǒng)四個數(shù)量級；2）各個系統(tǒng)的查詢時間與查詢直徑大小未呈明顯關(guān)系；3）RDFox 和AdPart 在IL-1 和IL-2 上的查詢效率比TriAD 高出三個數(shù)量級；4）不同的關(guān)系存儲模式在不同查詢直徑下的查詢效率也存在較大影響；5）基于RAM 對于低選擇性查詢IL-3 的伸縮性差，AdPart 和TriAD 不能響應(yīng)IL-3 查詢，而RDFox 在此類查詢上的效率也低于基于Spark 相關(guān)系統(tǒng)一個數(shù)量級。

下面結(jié)合查詢特征進(jìn)行具體分析，由于IL-1 和IL-2 都是主語綁定的高選擇性鏈型查詢，查詢結(jié)果數(shù)量較小，因此與基礎(chǔ)測試用例下的結(jié)果基本類似，基于RAM 的系統(tǒng)查詢性能仍優(yōu)于基于Spark 的系統(tǒng)。此外，各個系統(tǒng)的查詢時間與查詢直徑大小也未呈現(xiàn)明顯關(guān)系。例如，在S2RDF 中IL-2-5雖然是IL-2 中其他查詢類型的子類型，但是其查詢效率卻是最低的，這表明增大查詢直徑甚至可以提高查詢效率。

對于IL-1-n和IL-2-n查詢，RDFox 和AdPart 的查詢性能比TriAD 高出三個數(shù)量級，主要原因是RDFox 和AdPart 使用哈希索引在內(nèi)存中索引數(shù)據(jù)，使用異步的方式沿著查詢計劃并行運(yùn)行多個連接操作，并且在進(jìn)行連接時只交換投影連接列的唯一值，通過提高查詢的并行性大大提高了查詢性能。而TriAD 通過六重索引數(shù)據(jù)，使用摘要圖對查詢搜索空間進(jìn)行剪枝，但當(dāng)執(zhí)行分布式合并連接（merge join）和哈希連接（hash join）時，TriAD 需要在集群節(jié)點(diǎn)上對連接關(guān)系進(jìn)分片，因此在并發(fā)執(zhí)行連接時產(chǎn)生較大且不必要的中間結(jié)果，從而影響了查詢效率。PRoST、WiW 以及C2WVP 在IL-1-n和IL-2-n查詢上的性能大致相當(dāng)，而C3W 由于jWPT-inner 表中存在較多的行數(shù)，查詢的效率受限于數(shù)據(jù)大小，查詢效率顯著降低。S2RDF 在選擇性閾值設(shè)定為0.25 的情況下，查詢效率低于除C3W 外的其他混合存儲模式。

對于IL-3-n型查詢，由于它是非選擇性的鏈型查詢，查詢連接的中間結(jié)果很大，返回的查詢結(jié)果數(shù)量也比其他查詢多出幾個數(shù)量級。AdPart 和TriAD 未能響應(yīng)此類查詢，主要原因是這兩個系統(tǒng)中哈希連接的內(nèi)存使用由中間結(jié)果大小決定，極大限制了系統(tǒng)的伸縮性，因此對于高選擇性的查詢這兩個系統(tǒng)都發(fā)生了內(nèi)存溢出。而RDFox 通過使用索引嵌套循環(huán)連接并通過流量控制機(jī)制限制內(nèi)存的使用，從而成功響應(yīng)IL-3-n查詢。對于基于Spark 的系統(tǒng)而言，通過內(nèi)置的調(diào)度策略對集群資源進(jìn)行調(diào)度，有效避免了內(nèi)存溢出的發(fā)生，因此S2RDF、PRoST、WiW、C3W 以及C2WVP 在IL-3-n型查詢上的效率更高。

5.1.3 不同數(shù)據(jù)集下的查詢效率

除了使用合成數(shù)據(jù)集WatDiv-1B 外，本組實(shí)驗(yàn)還使用了真實(shí)數(shù)據(jù)集YAGO2 和用戶查詢?nèi)罩具M(jìn)行對比實(shí)驗(yàn)。由于未能在TriAD 和AdPart 上完成數(shù)據(jù)集加載，因此這兩個系統(tǒng)采用文獻(xiàn)［23］中發(fā)布的實(shí)驗(yàn)結(jié)果作為參照結(jié)果，而RDFox 因?yàn)闊o法復(fù)現(xiàn)，未對其進(jìn)行相關(guān)實(shí)驗(yàn)，詳細(xì)實(shí)驗(yàn)結(jié)果如表5 所示。

表5 YAGO2查詢集上各系統(tǒng)的查詢響應(yīng)時間對比Tab.5 Comparison of query response time of different systems on YAGO2 query set

實(shí)驗(yàn)結(jié)果表明：1）YAGO2 上的查詢結(jié)果總體與WatDiv數(shù)據(jù)集上的結(jié)果一致，對于YAGO2 上的四種基準(zhǔn)查詢，AdPart 的效率比基于Spark 的系統(tǒng)高出兩個數(shù)量級，比TriAD高出一個數(shù)量級；2）對于基于Spark 的系統(tǒng)而言，不同存儲模式在YAGO2 上的查詢效率也存在明顯差別，C2WVP 除了在Y2 查詢上都取得了最佳性能。

下面針對YAGO2 數(shù)據(jù)集下各系統(tǒng)在各類查詢上的查詢響應(yīng)時間進(jìn)行具體分析。對于Y1 和Y2 查詢主要涉及主語?賓語連接，AdPart 在不需要通信的情況下就可以處理Y1 和Y2 中的大多數(shù)連接，因此AdPart 比TriAD 性能更優(yōu)越。而Y3 和Y4 查詢中包含賓語?賓語連接，因此包含逆屬性表模式的WiW 和C2WVP 系統(tǒng)在這兩類查詢上的效率明顯高于其他幾種混合關(guān)系存儲模式。C3W 雖然也采用了逆屬性表模式，但是在查詢時由于jWPT-inner 表中存在較多的行數(shù)，查詢的效率受限于輸入數(shù)據(jù)大小。

5.2 查詢準(zhǔn)確性分析

本組實(shí)驗(yàn)對比分析不同系統(tǒng)（不含RDFox）的SPARQL查詢準(zhǔn)確性，各個系統(tǒng)在不同查詢維度上的查詢準(zhǔn)確率如表6 所示。實(shí)驗(yàn)結(jié)果表明，S2RDF、AdPart 在SPARQL 查詢上存在著較大的查詢誤差。從表6 可知，在WatDiv 基礎(chǔ)測試用例上，S2RDF 的平均準(zhǔn)確率為82%、AdPart 僅為70%，主要原因是這兩個系統(tǒng)在查詢計算過程中出現(xiàn)了大量重復(fù)答案，而其余系統(tǒng)在基本查詢類型上未出現(xiàn)錯誤。對于WatdDiv 增量鏈型查詢而言，S2RDF 在增量鏈型查詢IL-1、IL-2、IL3 上出現(xiàn)了查詢錯誤，AdPart 在IL-2 上出現(xiàn)錯誤答案，而TriAD 和AdPart 由于內(nèi)存溢出未能響應(yīng)IL-3 查詢，因此在IL-3 上的準(zhǔn)確率為0。對于YAGO2 基礎(chǔ)測試用例上而言，由于YAGO2上的查詢都為高選擇性的查詢，因此上述7 個系統(tǒng)都未出現(xiàn)查詢錯誤。

表6 不同SPARQL查詢下各系統(tǒng)的查詢準(zhǔn)確率 單位：%Tab.6 Accuracy of different SPARQL queries in different systems unit：%

綜合不同維度上的實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論，現(xiàn)有系統(tǒng)僅在高選擇性的小直徑查詢上具有較高的查詢準(zhǔn)確性，對于低選擇性的大直徑查詢存在較大的查詢誤差。

5.3 實(shí)驗(yàn)總結(jié)

本文通過四組對比實(shí)驗(yàn)對8 個典型的分布式RDF 系統(tǒng)的查詢性能進(jìn)行了系統(tǒng)的評估。實(shí)驗(yàn)結(jié)果顯示，上述實(shí)驗(yàn)系統(tǒng)針對鏈型查詢和星型查詢進(jìn)行了優(yōu)化，但是對于分布式SPARQL 查詢的伸縮性差，不能動態(tài)適應(yīng)查詢工作負(fù)載的變化，部分系統(tǒng)甚至還存在查詢準(zhǔn)確性的問題。基于RAM 的系統(tǒng)可以高效地響應(yīng)高選擇性的小直徑查詢，但是對于低選擇性的大直徑查詢性能低甚至無法響應(yīng)?；赟park 的系統(tǒng)則在低選擇性的大直徑查詢上具有較高的查詢性能，但是對于高選擇性的小直徑查詢的性能差。但總的來說，現(xiàn)有的系統(tǒng)難以滿足真實(shí)應(yīng)用中對低選擇性大直徑復(fù)雜查詢的需求。

此外，經(jīng)實(shí)驗(yàn)論證上述系統(tǒng)還存在以下問題：

1）在現(xiàn)有的關(guān)系存儲模式中存在著數(shù)據(jù)傾斜、表掃描時間過長的問題，例如在WatDiv-1B 數(shù)據(jù)集對應(yīng)的VP 表中，最大的VP 表中含有4.5 億個三元組，而最小的VP 表僅含有240 個三元組。嚴(yán)重的數(shù)據(jù)傾斜導(dǎo)致了SPARQL 查詢計算的連接復(fù)雜度過高，對大表的掃描時間過長，同時還導(dǎo)致了集群節(jié)點(diǎn)之間的通信代價增大，制約了分布式SPARQL 查詢的性能。

2）上述的基于Spark 的系統(tǒng)依賴RDF 特定的概要統(tǒng)計信息或特征集的方式進(jìn)行基數(shù)評估，采用貪婪搜索的方式規(guī)劃查詢計劃；基于RAM 的系統(tǒng)依賴基于摘要圖進(jìn)行基數(shù)評估，采用動態(tài)規(guī)劃的方式搜索查詢計劃。但是這些系統(tǒng)中的基數(shù)評估方法依賴條件獨(dú)立性假設(shè)、函數(shù)依賴性假設(shè)或者一致性假設(shè)，但是這些假設(shè)并非總是成立，限制了基數(shù)評估的準(zhǔn)確性，導(dǎo)致了查詢優(yōu)化器生成次優(yōu)的查詢連接計劃，從而限制了分布式SPARQL 的查詢性能。

3）上述系統(tǒng)在SPARQL 查詢規(guī)劃階段，采用貪婪搜索或者動態(tài)規(guī)劃的方式規(guī)劃查詢計劃，選擇代價估計最小的作為最優(yōu)查詢計劃，但是對于大直徑的復(fù)雜型查詢，搜索SPARQL 查詢連接狀態(tài)空間的時空復(fù)雜性過高，導(dǎo)致查詢編譯時間極大。在查詢規(guī)劃過程中，除了TriAD 外，均將查詢計劃構(gòu)造為左深度樹或右深度樹，極大限制了SPARQL 查詢計算的并行度，從而影響了分布式SPARQL 查詢效率。

6 結(jié)語

本文系統(tǒng)地闡述了現(xiàn)有的基于RAM 和基于Spark 的分布式RDF 系統(tǒng)的查詢優(yōu)化方法，使用了大規(guī)模的合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集對具有代表性的8 個系統(tǒng)進(jìn)行了廣泛的實(shí)驗(yàn)評估，并對實(shí)驗(yàn)結(jié)果進(jìn)行了全面的總結(jié)分析。

通過本文的實(shí)驗(yàn)分析與比較，可以看出目前分布式SPARQL 查詢優(yōu)化上已經(jīng)取得了一定的成果；但是仍然存在著查詢效率低、查詢準(zhǔn)確性差和伸縮性差等局限性，在垂直領(lǐng)域的應(yīng)用上仍面臨著許多問題和挑戰(zhàn)。因此，未來的研究方向包括：

1）探索面向垂直領(lǐng)域應(yīng)用的關(guān)系存儲模式，針對垂直領(lǐng)域查詢需求對RDF 數(shù)據(jù)進(jìn)行高效、平衡劃分，實(shí)現(xiàn)數(shù)據(jù)的負(fù)載均衡，有效解決現(xiàn)有系統(tǒng)中由于存在數(shù)據(jù)傾斜而導(dǎo)致的連接復(fù)雜性過高的問題。

2）設(shè)計基于混合存儲模式的數(shù)據(jù)索引與過濾機(jī)制，對表中不包含目標(biāo)值的數(shù)據(jù)進(jìn)行快速過濾，減少不必要的磁盤I/O 操作，從而提高SPARQL 查詢計算過程中目標(biāo)RDF 數(shù)據(jù)的查找速度，有效解決實(shí)驗(yàn)中出現(xiàn)的查詢性能受限于表掃描時間的問題。

3）設(shè)計一種高準(zhǔn)確性的SPARQL 基數(shù)估計器，例如使用基于學(xué)習(xí)的方法訓(xùn)練基數(shù)評估器，通過神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)RDF 數(shù)據(jù)特征以及三元組模式間的相關(guān)性，提高對查詢連接中間連接結(jié)果大小的預(yù)測準(zhǔn)確度，實(shí)現(xiàn)對三元組模式間連接順序、連接方式的優(yōu)化，有效防止實(shí)驗(yàn)中出現(xiàn)的由于中間結(jié)果過大而導(dǎo)致內(nèi)存溢出、查詢復(fù)雜度過高的問題。

4）設(shè)計一種基于代價評估的啟發(fā)式查詢規(guī)劃算法，利用代價評估模型生成最優(yōu)查詢計劃，并將最優(yōu)查詢計劃構(gòu)造為并行性更高的查詢樹，有效解決現(xiàn)有系統(tǒng)中查詢并行度低、查詢編譯時間和執(zhí)行時間長的問題，從而有效提高分布式SPARQL 查詢的性能。