[發明專利]一種基于最小屬性割的分布式SPARQL查詢優化方法

在審

• 申請號: 202111451035.3
• 申請日: 2021-12-01
• 公開（公告）號: CN114116785A
• 公開（公告）日: 2022-03-01
• 發明（設計）人: 彭鵬;田楨;秦拯
• 申請（專利權）人: 湖南大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/242
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于最小屬性割的分布式SPARQL查詢優化方法，屬于分布式系統領域，其包含步驟：(1)讀取原始RDF數據圖，保存邊屬性集合L；(2)計算每個邊屬性的弱連通分量及相應的代價；(3)盡可能多地選擇內部屬性，得到數據圖的粗化圖；(4)對粗化圖進行頂點劃分，并且反粗化處理，得到最終分區；(5)將SPARQL查詢分解成一組可獨立執行的子查詢；(6)各個分區內并行執行分解后的子查詢，獲得匹配結果。本發明擴展了分布式RDF系統中可獨立執行的查詢類型，減少分區間的連接，降低數據通信時間，提升查詢效率。

技術領域

本發明涉及分布式系統領域，更為具體地講，涉及到分布式RDF系統的數據劃分和查詢處理。

背景技術

RDF(Resource Description Framework)是一種由W3C組織提出的數據模型，其用三元組主語，謂語，賓語的基本形式表示web資源的屬性、關系，目前在知識圖譜、社交網絡分析等領域均有應用。RDF數據模型表示形式靈活，不僅可以表示成關系數據庫中的表，也可以表示成圖模型。當RDF表示成圖時，一個三元組代表著一條由主體指向客體的有向邊及其連接的兩個頂點，主體、客體是邊的兩個頂點，謂語則是有向邊上的標簽。W3C在提出RDF的同時，也提出了一種標準查詢語言SPARQL(simple protocol and RDFquerylanguage)。SPARQL與RDF一樣，也能表示成圖模型。查詢圖中的邊稱為三元組模式，三元組模式中的主語、謂語、賓語均可以是變量或常量。因為SPARQL與RDF都可以表示成圖模型，所以SPARQL查詢可以轉換成子圖匹配問題。

隨著互聯網的快速發展，RDF數據集的規模不斷增大，傳統的單機系統已經無法有效地處理海量RDF數據，因此出現了分布式RDF系統。在分布式系統中，數據劃分是一個最基本的過程。具體而言，即將RDF數據圖G分成一組子圖{F₁，F₂，…，F_k}，每個子圖稱為分區，分布在不同的機器中。目前分布式RDF系統中使用較多的數據劃分方法是按頂點劃分，即將每個頂點劃分到不同分區中，例如常見的哈希劃分。在該類方法中，一些邊會在分區之間被“分割”，即邊的兩個頂點被劃分到不同的分區中。為了保證圖的完整性，這些被分割的邊會重復保存在兩個分區中，稱為一跳復制。如果一條邊的兩個頂點在同一個分區內，則稱為內部邊；否則稱為跨越邊。

查詢的匹配類型與邊的類型一樣，也可以分成兩類：內部匹配，匹配結果只包含在一個分區內；跨越匹配，匹配結果包含在多個分區內。當待執行的查詢只有內部匹配時，則只需要在每個分區內獨立執行即可。對于含有跨越匹配的查詢，現有的方法大多將查詢分解成一組星形查詢，然后在每個分區中獨立執行星形查詢，最后執行分區間連接得到最終結果。但是分區間連接會涉及到數據通信和額外計算的開銷，對查詢性能影響較大。并且，在傳統的按頂點劃分的方法中，可獨立執行的查詢只能是星形，限制較大，在處理一般的查詢時，通常會進行分布式連接，因此查詢效率并不高。

發明內容

現有的分布式RDF系統只根據查詢圖的結構來判斷查詢是否可以獨立執行，只有當查詢圖是星形時才被認為可以獨立執行。本發明在考慮圖數據中邊的屬性之后，擴展了可獨立執行的查詢類型，而不僅僅局限于星形查詢。本發明的目的之一在于提供一種基于最小屬性割的圖數據劃分方法，該方法能夠減少跨越屬性的數量，從而避免分區間的連接操作，降低數據通信時間。本發明的目的之二在于提供一種查詢分解方法，該方法能夠將不可以獨立執行的原始查詢分解成一組可以獨立執行的子查詢，從而充分利用最小屬性割數據劃分的優勢，提升查詢效率。

本發明提供的一種基于最小屬性割的分布式SPARQL查詢優化方法，包含以下步驟：

步驟S1：讀取原始RDF數據圖G，并將邊屬性保存到集合L中；

步驟S2：計算每個邊屬性的弱連通分量及相應的代價；

步驟S3：盡可能多地選擇內部屬性，得到數據圖的粗化圖；