[發(fā)明專利]基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 202110086134.X
• 申請日: 2021-01-22
• 公開（公告）號: CN112835920B
• 公開（公告）日: 2022-10-14
• 發(fā)明（設(shè)計）人: 馮鈞;鄧治國;陸佳民
• 申請（專利權(quán)）人: 河海大學(xué)
• 主分類號: G06F16/242
• 分類號: G06F16/242;G06F16/2453;G06F16/2455;G06F16/2458
• 代理公司: 南京蘇高專利商標事務(wù)所(普通合伙) 32204
• 代理人: 成立珍

1.基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，包括以下步驟：

1)構(gòu)建RDF數(shù)據(jù)存儲模塊，包括數(shù)據(jù)特征集的生成、前綴樹索引的構(gòu)建以及RDF數(shù)據(jù)的存儲，具體步驟如下：

1.1)基于原始三元組表數(shù)據(jù)生成數(shù)據(jù)集的基本特征信息，包括三元組的數(shù)量、不同主語的數(shù)量、不同賓語的數(shù)量、不同謂語的數(shù)量；

1.2)構(gòu)建前綴樹索引；

1.3)基于三元組表構(gòu)建垂直劃分表和寬屬性表；

2)構(gòu)建SPARQL查詢模塊，包括查詢解析、查詢優(yōu)化、查詢執(zhí)行，具體步驟如下：

2.1)查詢解析

在執(zhí)行SPARQL查詢時，首先使用JenaARQ對SPARQL查詢進行解析，分解成若干個待匹配的三元組；

2.2)查詢優(yōu)化

SPARQL查詢的本質(zhì)是子圖匹配，在基于關(guān)系模式查找對應(yīng)數(shù)據(jù)的過程中涉及的操作包括連接操作，連接操作涉及磁盤讀寫和數(shù)據(jù)的傳輸；

2.3)查詢執(zhí)行

依據(jù)上一步驟中優(yōu)化后的查詢連接順序，構(gòu)造連接樹，并采用自底向上的方式處理書中的節(jié)點；連接樹中的節(jié)點代表SPARQL查詢的子查詢，在處理完樹中所有的節(jié)點后，樹的根節(jié)點即代表最終的查詢結(jié)果。

2.根據(jù)權(quán)利要求1所述的基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，所述的步驟1.2)中，前綴樹索引的構(gòu)建是基于前綴樹的變種進行構(gòu)建的，用于SPARQL查詢匹配過程中符合一定條件三元組的快速檢索，避免不必要的磁盤讀取操作。

3.根據(jù)權(quán)利要求1所述的基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，所述的步驟1.2)中，包括構(gòu)建以主語為根的前綴樹索引和以賓語為根的前綴樹索引；構(gòu)建兩個不同的前綴樹索引，利用三元組中已知的主語和謂語來快速檢索到賓語，或者是通過已知的賓語和謂語快速檢索到對應(yīng)的主語。

4.根據(jù)權(quán)利要求1所述的基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，所述的步驟1.3)中，所述的垂直劃分表的構(gòu)建是基于三元組表中不同謂語來構(gòu)建的，即含有共同謂語的三元組被劃分到同一個表中，該表只有兩列，分別為主語列和賓語列，表的名稱對應(yīng)一個謂語；所述的寬屬性表的構(gòu)建，是基于三元組的主語進行劃分，將相同主語的元組劃分為一行，三元組的賓語通過主語，謂語進行定位；對于主語和賓語中一對多的情形，使用一個集合容器，存儲不同的賓語；最終使用ORC列式存儲，并結(jié)合SNAPPY壓縮算法，將數(shù)據(jù)存儲在磁盤上。

5.根據(jù)權(quán)利要求1所述的基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，所述的步驟2.2)中，查詢的優(yōu)化首先依據(jù)分解后的三元組的變量的個數(shù)進行非遞減排序，變量個數(shù)相同的依據(jù)元組的數(shù)據(jù)特征集和選擇性進行非遞減排序，然后依據(jù)排序后的元組構(gòu)建連接樹；連接樹中的每一個節(jié)點代表SPARQL查詢的一個子查詢，在執(zhí)行子查詢的過程中，具有共享主語變量或者賓語變量的元組被劃分到同一個節(jié)點中。

6.根據(jù)權(quán)利要求5所述的基于混合存儲模式的分布式SPARQL查詢優(yōu)化方法，其特征在于，所述的步驟2.3)中，查詢的執(zhí)行涉及到查詢的轉(zhuǎn)換操作，即將相應(yīng)的SPARQL子查詢轉(zhuǎn)換為等價的Spark SQL查詢；Spark SQL查詢根據(jù)RDF數(shù)據(jù)加載過程中生成并存儲在MySQL中的元數(shù)據(jù)，關(guān)聯(lián)存儲在磁盤中的物理數(shù)據(jù)，通過Spark算子操作，計算得到相應(yīng)的子查詢結(jié)果；對于子查詢中的三元組匹配操作，包括下述幾種情形：

3.1)索引匹配；若當前元組只包含一個變量，且該變量對應(yīng)位置為主語或者賓語所在位置，則根據(jù)構(gòu)建好的前綴樹索引快速匹配變量位置對應(yīng)的映射常量；

3.2)查詢垂直劃分表；若節(jié)點中只有一個三元組且謂語所在位置為常量，則通過謂語匹配到對應(yīng)的垂直劃分表，在垂直劃分表中進行數(shù)據(jù)的匹配；

3.3)查詢寬屬性表；若節(jié)點中包含若干個三元組，且這些三元組的主語是其共享變量，則通過查詢寬屬性表，找到對應(yīng)的主語，即一次獲取相應(yīng)的變量應(yīng)當映射到的常量。