聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)綜述

彭鵬 ，鄒磊

1.湖南大學(xué)，信息科學(xué)與工程學(xué)院,湖南 長沙 410082

2.北京大學(xué)，王選計算機研究所,北京 100080

引言

由于科學(xué)數(shù)據(jù)本身存在的復(fù)雜結(jié)構(gòu)，以及它們之間的復(fù)雜關(guān)聯(lián)性，很多科學(xué)數(shù)據(jù)發(fā)布者將其數(shù)據(jù)表示為知識圖譜的形式。比如，由歐洲生物信息研究所、瑞士生物信息研究所以及美國蛋白質(zhì)信息資源中心構(gòu)建的一個全面的、高質(zhì)量的、可免費使用的蛋白質(zhì)序列與功能信息知識圖譜UniProt[1]；由阿爾伯塔大學(xué)構(gòu)建的一個生物信息學(xué)和化學(xué)信息學(xué)知識圖譜DrugBank[2]；由京都大學(xué)化學(xué)研究所構(gòu)建的關(guān)于基因組、生物化學(xué)物質(zhì)等信息的知識圖譜KEGG[3]。

目前，在生命科學(xué)領(lǐng)域構(gòu)建知識圖譜的過程中，知識圖譜的表示方式以W3C 提出的RDF[4]最為有名且已經(jīng)被廣泛地應(yīng)用。RDF (Resource Description Framework，即資源描述框架)是W3C 提出的一組知識表示的模型，以便更為豐富地描述和表達(dá)網(wǎng)絡(luò)資源的內(nèi)容與結(jié)構(gòu)。RDF 利用國際化資源標(biāo)識符（Internationalized Resource Identifier，IRI）來標(biāo)識對象。這些IRI所對應(yīng)的對象既可以是真實世界中的實體（比如一個蛋白質(zhì)），也包括人們在社會實踐中形成的概念（比如疾?。┑?。這些IRI 所對應(yīng)的事物又被稱為資源。RDF 的基本數(shù)據(jù)單元是一個三元組，可以表示為< 主體，屬性，客體>。每個三元組表示某個資源的一個屬性值或者某個資源與其他資源的關(guān)系。在實際中，人們還經(jīng)常將RDF 數(shù)據(jù)視為通過預(yù)先定義的語義所構(gòu)成的一個或多個連通圖。其中，RDF 數(shù)據(jù)中每個資源被視為一個點，而每個三元組被視為連接兩個資源的一條邊。而基于圖模型的RDF數(shù)據(jù)模型是被最普遍應(yīng)用的知識圖譜數(shù)據(jù)模型。

在定義RDF 數(shù)據(jù)模型的同時，W3C 也定義了結(jié)構(gòu)化查詢語言SPARQL（Simple Protocol and RDF Query Language）[5]，以實現(xiàn)針對RDF 知識圖譜數(shù)據(jù)的查詢與管理。SPARQL語言與目前關(guān)系數(shù)據(jù)庫中的SQL 語言是很相近的。在SPARQL 語法中，用戶也是用SELECT語句查詢滿足特定條件的RDF 知識圖譜數(shù)據(jù)片段。具體而言，對于一個SELECT 語句中，SELECT子句指定查詢應(yīng)當(dāng)返回的內(nèi)容，F(xiàn)ROM子句是指定將要使用的數(shù)據(jù)集，WHERE 子句一組三元模式組成用以指定所返回的RDF 數(shù)據(jù)片段需要滿足的模式。與RDF 數(shù)據(jù)的圖形式表示類似，一個SPARQL查詢可以表示為一個查詢圖[6,7]，查詢中每個變量或者常量對應(yīng)一個查詢圖上的點，每個WHERE 子句中的三元模式對應(yīng)一條邊。

實際科學(xué)數(shù)據(jù)管理應(yīng)用中，特別是生命科學(xué)領(lǐng)域應(yīng)用中，RDF知識圖譜數(shù)據(jù)存儲被數(shù)據(jù)方存儲在若干分布于不同機器的、各自“自治”的RDF知識圖譜數(shù)據(jù)源上，即聯(lián)邦型分布式RDF知識圖譜。如UniProt被存在歐洲生物研究機構(gòu)的RDF知識圖譜數(shù)據(jù)源上；DrugBank被存在加拿大阿爾伯塔大學(xué)的RDF知識圖譜數(shù)據(jù)源上；KEGG被存在日本京都大學(xué)的RDF知識圖譜數(shù)據(jù)源上；中國科學(xué)院微生物研究所落戶的世界微生物數(shù)據(jù)中心存儲著微生物資源、微生物及交叉技術(shù)方法、研究過程及工程、微生物組學(xué)、微生物技術(shù)以及微生物文獻(xiàn)、專利、專家、成果等微生物方面的RDF知識圖譜數(shù)據(jù)。

針對上述如此之多的RDF知識圖譜數(shù)據(jù)源，我們需要將它們集成到一個系統(tǒng)下，以方便用戶使用。這樣的系統(tǒng)就被稱為“聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)”。在這種系統(tǒng)中，不同機器上的子數(shù)據(jù)庫系統(tǒng)獨立地進(jìn)行查詢處理且不被干涉。具體到在聯(lián)邦型RDF知識圖譜數(shù)據(jù)管理系統(tǒng)，RDF 數(shù)據(jù)存儲在若干分布于不同機器的、各自“自治”的RDF知識圖譜數(shù)據(jù)源上。當(dāng)處理SPARQL查詢時，一個中心機器對查詢進(jìn)行調(diào)度并得到最終結(jié)果。

目前，已有一些生命科學(xué)領(lǐng)域的研究機構(gòu)構(gòu)建了自己的聯(lián)邦型RDF知識圖譜數(shù)據(jù)管理系統(tǒng)來進(jìn)行RDF數(shù)據(jù)管理。歐洲分子生物學(xué)實驗室下屬的生物信息學(xué)研究所發(fā)布了他們SPARQL查詢接口1. https://www.ebi.ac.uk/rdf/services/sparql，可以支持聯(lián)邦式地查詢多個RDF數(shù)據(jù)源，包括 Biomodels、Biosamples、ChEMBL、Ensembl、Reactome、ExpressionAtlas等；德國萊比錫大學(xué)、愛爾蘭國立大學(xué)等研究機構(gòu)的研究人員針對著名的癌癥基因組地圖項目（The Cancer Genome Atlas，TCGA）構(gòu)建了聯(lián)邦型RDF知識圖譜數(shù)據(jù)管理系統(tǒng)——TopFed2. http://tcga.deri.ie/，來協(xié)助研究人員管理和查詢癌癥基因組RDF數(shù)據(jù)。

本文將介紹現(xiàn)有的聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)。在第二章，本文將給出聯(lián)邦型RDF數(shù)據(jù)模型的形式化定義；在第三章，本文將介紹常見聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)的架構(gòu)；在第四章，本文將介紹常見聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)重點查詢分解與數(shù)據(jù)源選擇方法；在第五章，本文將介紹常見聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)重點查詢處理與優(yōu)化方法。最后，本文給出對現(xiàn)有聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)的總結(jié)。

1 問題定義

本章將首先給出了聯(lián)邦型RDF 數(shù)據(jù)管理的形式化定義，然后給出SPARQL查詢模型的定義。

一個RDF 數(shù)據(jù)集可以看做一系列三元組的集合。每一條三元組又可被稱為一條聲明（statement）。一條三元組包括三個元素：主體（subject）、屬性（property）及客體（object），通常描述了兩個資源間的關(guān)系或是一個資源的某種屬性。當(dāng)某條三元組描述了某個資源的屬性時，其三個元素也被稱為主體、屬性及屬性值（property value）。相關(guān)的形式化定義如下。

定義1：資源。資源（resource）是可區(qū)別性且獨立存在的某種事物。RDF知識圖譜數(shù)據(jù)中的每一個資源均被分配一個獨一無二的標(biāo)識，稱為國際化資源標(biāo)識（IRI，Internationalized Resource Identifiers）。

定義2： 三元組。RDF 數(shù)據(jù)中的三元組（triple）又稱聲明（statement），通常被表示為 < 主體（subject），屬性（property）,客體（object）>。同時三元組也可表示為<主體（subject）,屬性（property）,屬性值（property value）>，這種方式主要用來描述實體的相關(guān)屬性。三元組的取值空間可形式化表示為(U∪ B)×(U ∪ B) ×(U ∪ B ∪ L)，其中 U 代表URI的集合，B 代表空值點，L 代表文本。

除了基本的三元組模型，圖模型也被廣泛地用來描述RDF 數(shù)據(jù)。通過將主體及客體視為頂點且將三元組視為連接頂點與頂點之間的有向邊，RDF 數(shù)據(jù)集可以被看作為一張有向圖。定義3給出了RDF數(shù)據(jù)圖的定義。

定義3：RDF 數(shù)據(jù)圖。RDF 數(shù)據(jù)圖被表示為有向圖G = ,其中：V 表示 RDF 數(shù)據(jù)圖中的點集，V 中的每個點對應(yīng)于所有 RDF 三元組中的主體或者客體，其可以是資源點、空值點或者文本點；E =V ×V是RDF 數(shù)據(jù)圖中的有向邊集，每條邊對應(yīng)于 RDF 數(shù)據(jù)中的一個三元組 1≤i≤N；L是所有邊的標(biāo)簽集合，即屬性集合，每條邊的標(biāo)簽是其所對應(yīng)三元組中的屬性。

對于聯(lián)邦型RDF 數(shù)據(jù)管理系統(tǒng)，RDF知識圖譜數(shù)據(jù)分布在若干“自治”的RDF知識圖譜數(shù)據(jù)源上。每個RDF知識圖譜數(shù)據(jù)源提供一個SPARQL查詢處理接口。SPARQL查詢處理接口能支持輸入SPARQL查詢并求出解。針對這個特性，本文擴展前人工作關(guān)于關(guān)聯(lián)數(shù)據(jù)的定義[8]來描述聯(lián)邦型的RDF數(shù)據(jù)管理系統(tǒng)如下。

定義4：聯(lián)邦型的RDF 數(shù)據(jù)系統(tǒng)。一個聯(lián)邦型的RDF 數(shù)據(jù)系統(tǒng)被定義為一個三元組W = (S,g,d)。其中S是一個RDF 數(shù)據(jù)源的集合，其中每個數(shù)據(jù)源通過查詢IRI來獲得；g : S →2E是一個映射，用以將每個數(shù)據(jù)源映射到存儲于其中的RDF 數(shù)據(jù)圖的子圖；d : V→S是一個滿射的部分函數(shù)用以將RDF 數(shù)據(jù)圖中每個點映射到唯一對應(yīng)的數(shù)據(jù)源。點u 對應(yīng)的數(shù)據(jù)源d(u) 稱為u 的主機。

由此，整個RDF 數(shù)據(jù)圖可以通過整合所有RDF數(shù)據(jù)源的數(shù)據(jù)來得到，即∪s∈s g(s)=G。

對于SPARQL查詢而言，其基本單元是基本圖模式（Basic Graph Pattern）。本文基于 Jorge Pérez 等人的工作[9]來定義SPARQL查詢及它的匹配。

定義5：變量。SPARQL查詢中的變量是以“?”開頭的一串字符，當(dāng)且僅當(dāng)兩個字符串完全相同時，相對應(yīng)的變量被視為同一個變量。任何主體、屬性或客體均視為變量的一個匹配。

定義6：三元組模式。當(dāng)三元組中的主體、屬性或客體被變量取代時，該三元組被稱三元組模式（triple pattern）。三元組模式的取值空間為(U ∪ B ∪ V)×(U ∪ B ∪ V) ×(U ∪ B ∪ L ∪ V)，其中 V 為所有可能變量的集合。一個三元組稱為是某個三元組模式的匹配當(dāng)且僅當(dāng)該三元組與三元組模式的對應(yīng)元素相匹配，其中變量可以匹配到任何常量，而常量僅能匹配與其標(biāo)簽完全一致的常量。

定義7：SPARQL查詢。一個SPARQL查詢是一系列三元組模式以點操作 “.”相連接的組合。一個圖結(jié)構(gòu)視為某個基本圖模式的匹配當(dāng)且僅當(dāng)該SPARQL查詢中的變量和三元組模式與該圖結(jié)構(gòu)中的頂點和三元組的匹配關(guān)系形成一一映射。

一個SPARQL查詢同樣可以被表示為一個圖結(jié)構(gòu)。其定義如下。

定義8：SPARQL查詢圖。一個SPARQL查詢可以被表示為有向圖Q =。其中，VQ=V ∪Vv，其中Vv是表示變量的頂點的集合，而V的定義與定義3中相同；EQ=VQ×VQ是SPARQL 數(shù)據(jù)圖中的有向邊集，每條邊對應(yīng)于SPARQL查詢中的一個三元組模式；LQ是所有邊的標(biāo)簽集合，即屬性集合與邊上的變量集合。

根據(jù)上述定義可知，尋找SPARQL查詢的結(jié)果的過程可以被視為在RDF 數(shù)據(jù)圖中尋找子圖匹配的過程。于是，一個SPARQL查詢的匹配定義如下。

定義9：SPARQL查詢匹配。給定RDF 數(shù)據(jù)圖G 和基本圖模式查詢圖Q，若Q 有n個頂點{v1,…,vn}，圖G 中的n 個頂點{u1,…,un} 被稱為是Q的一個匹配當(dāng)且僅當(dāng)存在一個匹配函數(shù)f 滿足下列條件: 如果頂點vi不是變量，則f (vi) 和vi有相同的URL 或者字符值；如果頂點vi是變量，則f (vi) 可為任意值；如果存在邊是Q中從vi到vj的一條邊，那么在G 中存在相應(yīng)的邊，且如果的標(biāo)簽為p，則也必須為p。

在上述語境下，SPARQL查詢的處理可以被視為在RDF 數(shù)據(jù)圖中尋找相應(yīng)的子圖匹配的過程。

2 聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)

目前，大部分聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)的系統(tǒng)框架如圖1所示。

聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)中，系統(tǒng)需要提前將用戶輸入的SPARQL查詢分解成若干子查詢并傳送到它們對應(yīng)的RDF數(shù)據(jù)源，以讓這些對應(yīng)的RDF 數(shù)據(jù)源對子查詢獨立地進(jìn)行處理并得到部分解。之后，系統(tǒng)將這些部分解收集起來并通過連接操作得到最終解。

圖1 目前聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)架構(gòu)Fig.1 System architecture of existing Federated RDF Systems

對于聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)而言，由于各個RDF知識圖譜數(shù)據(jù)源之間相互獨立地自治，所以系統(tǒng)在查詢處理階段無法中斷各個RDF知識圖譜數(shù)據(jù)源的處理進(jìn)程。因此，在聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)中，第一個挑戰(zhàn)就是如何將SPARQL查詢分解成若干子查詢并傳送到它們對應(yīng)的RDF知識圖譜數(shù)據(jù)源。

之后，系統(tǒng)將這些子查詢的匹配收集起來并通過連接操作得到最終匹配。在聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)中，第二個挑戰(zhàn)就是如何優(yōu)化子查詢執(zhí)行以及中間結(jié)果連接。

3 查詢分解與數(shù)據(jù)源選擇

在查詢分解與數(shù)據(jù)源選擇階段，聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)將用戶輸入的查詢分解成若干子查詢并確定出每個子查詢所涉及的RDF知識圖譜數(shù)據(jù)源。這些系統(tǒng)可以分成兩類：基于元數(shù)據(jù)的方法和基于ASK查詢的方法。

DARQ[10]是最早討論如何在聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)上進(jìn)行SPARQL查詢處理。當(dāng)SPARQL查詢輸入以后，DARQ 根據(jù)一個叫服務(wù)描述（Service Description）的索引確定出相關(guān)的RDF 數(shù)據(jù)源。所謂服務(wù)描述，就是DARQ 所構(gòu)建的一種索引，用以標(biāo)識出相關(guān)數(shù)據(jù)源。數(shù)據(jù)描述中包含若干性能，每個性能對應(yīng)一個數(shù)據(jù)源。每個性能包含若干元組t =(p,r)，其中p 表示該數(shù)據(jù)源有p 這個屬性，r 對應(yīng)于當(dāng)屬性為p 時主體或者客體若干限制。當(dāng)用戶輸入查詢之后，DARQ 首先根據(jù)服務(wù)描述確定相關(guān)RDF知識圖譜數(shù)據(jù)源。然后，DARQ 將查詢分解成若干子查詢?；镜淖硬樵兪菃蝹€三元組模式，所以每個子查詢都能根據(jù)服務(wù)描述確定其相關(guān)的數(shù)據(jù)源。如果兩個三元組模式都只涉及一個相同的數(shù)據(jù)源，那么這兩個子查詢可合并成一個子查詢。

在DARQ 的服務(wù)描述之外，還有Q-Tree[11-12]作為另一種用來確定子查詢RDF知識圖譜數(shù)據(jù)源的索引。在Q-Tree中，每個三元組中的主體、屬性和客體都通過哈希函數(shù)映射到一個整數(shù)。于是，每個三元組都可以視為一個三維向量，進(jìn)而視為一個三維空間上的點。然后，對這些三維空間上的點，系統(tǒng)構(gòu)建一種類似于R-Tree的索引——Q-Tree。Q-Tree與R-Tree 的不同體現(xiàn)于Q-Tree 葉節(jié)點所存儲的不是一個個項，而是項的數(shù)量以及相應(yīng)RDF知識圖譜數(shù)據(jù)源集合。利用Q-Tree 索引，系統(tǒng)將SPARQL查詢中每個查詢語句都可以視為一個Q-Tree 上的一個帶界矩形框查詢（MBB，Minimum Bounding Boxes）。于是，SPARQL查詢轉(zhuǎn)化為MBB 的連接，進(jìn)而得到每個查詢?nèi)M對應(yīng)的RDF 數(shù)據(jù)源。

在上述方法之外，還有SPLENDID[13]、HiBISCuS[14]、TopFed[15]等方法。其中，SPLENDID[13]根據(jù)每個知識圖譜數(shù)據(jù)源的VOID 信息建立一個倒排索引。這個索引將每個屬性和類型信息映射到一個數(shù)據(jù)對（d,c），其中d 表示屬性或類型信息所在的數(shù)據(jù)源，c 表示在d 這個數(shù)據(jù)源上屬性或類型信息的數(shù)量。HiBISCuS[14]也構(gòu)建了與DARQ 類似的索引。只是，在確定各個子查詢的相關(guān)RDF 數(shù)據(jù)源階段，HiBISCuS 將查詢圖建模成一個有向帶標(biāo)簽的超圖，并利用這個有向帶標(biāo)簽的超圖進(jìn)一步減少每個子查詢的候選RDF 知識圖譜數(shù)據(jù)源。TopFed[15]是一個生物學(xué)方面關(guān)于腫瘤的聯(lián)邦型RDF 數(shù)據(jù)庫。在TopFed 中，其用來確定相關(guān)RDF 數(shù)據(jù)源的索引是一個N3文件和從組織源站點（Tissue Source Site）到腫瘤（Tumour）的哈希表。前者那個N3 文件用來描述每個RDF 數(shù)據(jù)源的元數(shù)據(jù)，后者那個從組織源站點（Tissue Source Site）到腫瘤（Tumour）的哈希表用來計算每個組織源站點到腫瘤信息的信息。

針對在國家重點研發(fā)項目“科學(xué)大數(shù)據(jù)管理系統(tǒng)”中中科院微生物所進(jìn)行微生物RDF知識圖譜數(shù)據(jù)管理的需求，本文作者所在實驗室也構(gòu)建了一個聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)——FMQO[16-17]。FMQO先后獲得了國際學(xué)術(shù)會議DASFAA 2018的Best Paper Award和APWeb-WAIM 2019的Best Demo Award。

圖2 查詢分解和數(shù)據(jù)源選擇技術(shù)的評測結(jié)果Fig.2 Evaluating query decomposition and source selection technique

FMQO提出利用基于RDF知識圖譜數(shù)據(jù)源的拓?fù)潢P(guān)系進(jìn)行查詢分解與數(shù)據(jù)源選擇方法。FMQO首先使用一個網(wǎng)絡(luò)爬蟲來找出哪些RDF知識圖譜數(shù)據(jù)源有數(shù)據(jù)共享?；谒l(fā)現(xiàn)的共享數(shù)據(jù)，F(xiàn)MQO定義RDF知識圖譜數(shù)據(jù)源拓?fù)潢P(guān)系圖并將這個RDF 數(shù)據(jù)源拓?fù)潢P(guān)系圖維護(hù)在控制機器上。于是，F(xiàn)MQO提出一個基于RDF知識圖譜數(shù)據(jù)源拓?fù)潢P(guān)系圖的策略來對每個本地查詢相關(guān)的RDF 數(shù)據(jù)源進(jìn)行剪枝。這個策略的基本思想在于兩個子查詢可以連接當(dāng)且僅當(dāng)兩個子查詢所對應(yīng)的RDF知識圖譜數(shù)據(jù)源在RDF知識圖譜數(shù)據(jù)源拓?fù)潢P(guān)系圖上相鄰。

我們通過在一個包含1億三元組的RDF數(shù)據(jù)管理基準(zhǔn)測試數(shù)據(jù)集WatDiv[20]上進(jìn)行實驗，來評測了FMQO中所提出的基于RDF知識圖譜數(shù)據(jù)源拓?fù)潢P(guān)系圖的查詢分解和數(shù)據(jù)源選擇技術(shù)。圖2顯示了我們的評測結(jié)果。這里，我們與兩種基準(zhǔn)技術(shù)進(jìn)行了對比。第一種作為對比的技術(shù)是沒有使用任何RDF 數(shù)據(jù)源拓?fù)潢P(guān)系來進(jìn)行查詢分解和數(shù)據(jù)源選擇（這種方法被記為MQO-Basic）；另一種作為對比的技術(shù)是擴展自Q-Tree[11,12]（這種方法被記為Q-Tree）。Q-Tree僅僅使用RDF 數(shù)據(jù)源拓?fù)潢P(guān)系中兩個RDF 數(shù)據(jù)源相鄰這個關(guān)系來進(jìn)行查詢分解和數(shù)據(jù)源選擇。圖2所示，F(xiàn)MQO的查詢分解和數(shù)據(jù)源選擇技術(shù)導(dǎo)致的遠(yuǎn)程調(diào)用次數(shù)和查詢響應(yīng)時間都最少。

不同于上述利用索引來確定相關(guān)RDF 數(shù)據(jù)源的方法，F(xiàn)edX[19]則可以在查詢處理階段實時確定相關(guān)數(shù)據(jù)源。當(dāng)SPARQL查詢輸入以后，F(xiàn)edX[19]首先將查詢中每個三元組模式都傳到所有RDF知識圖譜數(shù)據(jù)源上并通過SPARQL查詢語義中的ASK 來確定相關(guān)數(shù)據(jù)源。

4 查詢處理與優(yōu)化

在查詢分解與數(shù)據(jù)源選擇階段完成后，每個RDF知識圖譜數(shù)據(jù)源都會對應(yīng)若干需要它處理的子查詢。這些子查詢被執(zhí)行并返回給控制機器之后，聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)將子查詢的匹配連接起來得到最終匹配。

基本的子查詢匹配連接策略是擴展經(jīng)典的關(guān)系數(shù)據(jù)庫中的連接順序確定算法System-R 式動態(tài)規(guī)劃[18]來找出最優(yōu)查詢執(zhí)行計劃，然后按照此查詢執(zhí)行計劃執(zhí)行。然而，針對聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)，很多文章也提出自己的連接優(yōu)化策略。

DARQ[10]所使用的代價生成方法是System-R 式動態(tài)規(guī)劃[18]的變種。對于這種查詢計劃生成方式，最重要的就是如何估計代價。DARQ提出了兩個子查詢連接有兩種方式：一是嵌套循環(huán)連接，就是一般的自然連接；二是綁定式連接，就是一個子查詢先找出解，然后將解傳輸?shù)搅硪粋€子查詢那里，然后將解綁定到第二個子查詢那里進(jìn)行過濾。DARQ給出了這兩種連接方式的代價模型，并基于這個代價模型進(jìn)行System-R 式動態(tài)規(guī)劃。

FedX[19]連接操作順序的計算方法也是System-R[36]的變種。FedX 所使用的連接方式也是和DARQ 相似的綁定式連接，但是FedX 在傳輸中間結(jié)果的時候不再是一個一個傳，而是利用UNION操作符實現(xiàn)若干個中間結(jié)果合在一起傳。

在實際應(yīng)用中，傳到一個RDF知識圖譜數(shù)據(jù)源的子查詢相互間經(jīng)常共享部分結(jié)構(gòu)。這些共享的結(jié)構(gòu)使得這些本地查詢在被處理時能共享一些計算。于是，F(xiàn)MQO[16,17]提出一個基于查詢重寫的策略來優(yōu)化每個RDF 數(shù)據(jù)源上的多子查詢處理。這個方法利用了SPARQL查詢模型中的OPTIONAL操作符和FILTER操作符來將每個RDF知識圖譜數(shù)據(jù)源所接受的子查詢重寫成更少的幾個重寫查詢。圖3給出一個FMQO進(jìn)行查詢重寫的例子。

圖3 FMQO [16, 17]中查詢重寫示例Fig.3 Example query rewriting in FMQO[16, 17]

圖4 FMQO中查詢重寫規(guī)則的評測結(jié)果Fig.4 Evaluating rewriting strategies in FMQO

我們也在包含1億三元組的RDF數(shù)據(jù)管理基準(zhǔn)測試數(shù)據(jù)集WatDiv[20]上進(jìn)行實驗對在上述FMQO中所提出的查詢重寫規(guī)則進(jìn)行評測。實驗中，我們對比的包括4 個方法：僅僅利用基于OPTIONAL 操作符的查詢重寫規(guī)則進(jìn)行重寫的多查詢處理方法（記為OPT-only）；僅僅利用基于FILTER 操作符的查詢重寫規(guī)則進(jìn)行重寫的多查詢處理方法（記為FIL-only）；利用混合查詢重寫規(guī)則進(jìn)行重寫的多查詢處理方法（記為MQO）；此外，我們擴展了Wangchao Le 等人提出的單機版基于查詢重寫的多查詢優(yōu)化算法[21]在聯(lián)邦型知識圖譜數(shù)據(jù)管理系統(tǒng)中。圖4顯示了這4個不同的基于查詢重寫的多查詢處理方法在查詢響應(yīng)時間與遠(yuǎn)程調(diào)用次數(shù)上進(jìn)行對比實驗的結(jié)果。如圖所示，因為MQO 相對于其它方法是利用更全的重寫規(guī)則進(jìn)行重寫的，所以MQO 所生成的重寫查詢數(shù)量最少，進(jìn)而使得MQO 進(jìn)行的遠(yuǎn)程調(diào)用更少，同時查詢響應(yīng)時間最短。

此外，F(xiàn)MQO討論了在進(jìn)行多個子查詢匹配集的連接時如何通過共享部分計算來降低查詢整體響應(yīng)時間。實際中，用戶在一個時間段內(nèi)輸入的查詢會有些公共子結(jié)構(gòu)，這些公共結(jié)構(gòu)會使得由不同查詢分解而得的本地查詢匹配進(jìn)行連接時有些連接操作計算是可以相同的。因此，處理這些用戶輸入的相似查詢時，F(xiàn)MQO可以通過共享相同的連接操作計算來降低查詢整體響應(yīng)時間。具體而言，如果兩組相互連接子查詢結(jié)構(gòu)一樣且進(jìn)行連接的變量位置一樣，這兩組連接可以合成一個連接。

5 結(jié)論

在科學(xué)數(shù)據(jù)管理中，人們將越來越多的數(shù)據(jù)按照知識圖譜進(jìn)行組織，以便于人們操作與利用。現(xiàn)階段，知識圖譜模型很多都是以RDF框架作為底層數(shù)據(jù)存儲結(jié)構(gòu)，而采用SPARQL查詢語言對數(shù)據(jù)進(jìn)行查詢。隨著越來越多的科學(xué)數(shù)據(jù)以RDF模型的形式被不同數(shù)據(jù)提供者發(fā)布出來，如何利用聯(lián)邦型RDF知識圖譜數(shù)據(jù)管理系統(tǒng)進(jìn)行多數(shù)據(jù)源的RDF數(shù)據(jù)管理和SPARQL查詢處理成為一個重要的研究問題。在本文中，我們簡單介紹了現(xiàn)有聯(lián)邦型RDF數(shù)據(jù)管理系統(tǒng)所采用的技術(shù)。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。