[發(fā)明專利]一種基于最小屬性割的分布式SPARQL查詢優(yōu)化方法

在審

• 申請?zhí)枺?/td>: 202111451035.3
• 申請日: 2021-12-01
• 公開（公告）號: CN114116785A
• 公開（公告）日: 2022-03-01
• 發(fā)明（設(shè)計）人: 彭鵬;田楨;秦拯
• 申請（專利權(quán)）人: 湖南大學(xué)
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/242
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于最小屬性割的分布式SPARQL查詢優(yōu)化方法，其特征在于，包含如下步驟：

(1)讀取原始RDF數(shù)據(jù)圖，保存邊屬性集合L；

(2)計算每個邊屬性的弱連通分量及相應(yīng)的代價；

(3)盡可能多地選擇內(nèi)部屬性，得到數(shù)據(jù)圖的粗化圖；

(4)對粗化圖進行頂點劃分，并且反粗化處理，得到最終分區(qū)；

(5)將SPARQL查詢分解成一組可獨立執(zhí)行的子查詢；

(6)各個分區(qū)內(nèi)并行執(zhí)行分解后的子查詢，獲得匹配結(jié)果。

2.根據(jù)權(quán)利要求1所述的基于最小屬性割的分布式SPARQL查詢優(yōu)化方法，其特征在于，步驟2在計算弱連通分量時，為了便于在選擇內(nèi)部屬性時對屬性進行度量，會將弱連通分量的大小作為屬性的代價。

3.根據(jù)權(quán)利要求1所述的基于最小屬性割的分布式SPARQL查詢優(yōu)化方法，其特征在于，步驟3在處理靜態(tài)圖數(shù)據(jù)時，邊屬性的數(shù)量是固定不變的，且類型只有內(nèi)部屬性、跨越屬性兩種；通過使用啟發(fā)式的貪心算法盡量選擇更多的內(nèi)部屬性，從而實現(xiàn)跨越屬性最少，即達到最小屬性割目的；在選擇完內(nèi)部屬性后，內(nèi)部屬性中每個弱連通分量作為一個超點，得到數(shù)據(jù)圖的粗化圖。

4.根據(jù)權(quán)利要求1所述的基于最小屬性割的分布式SPARQL查詢優(yōu)化方法，其特征在于，步驟4在對粗化圖進行頂點劃分時，可以使用哈希、METIS等任意一種按頂點劃分的分區(qū)算法，但在劃分之時確保每個分區(qū)中的頂點數(shù)量不超過(1+ε)×|V|/k，以實現(xiàn)分區(qū)間負載均衡；其中，ε是用戶自定義的、最大的不均衡比例，k是分區(qū)數(shù)量。

5.根據(jù)權(quán)利要求1所述的基于最小屬性割的分布式SPARQL查詢優(yōu)化方法，其特征在于，步驟5會根據(jù)步驟3中得到的跨越屬性對原始的SPARQL查詢進行分解，分解得到的子查詢可以在分區(qū)內(nèi)獨立執(zhí)行，并且子查詢的形狀不局限于星形查詢。