[發明專利]基于圖的高效SPARQL查詢應答方法、裝置和設備

有效

• 申請號: 202011471406.X
• 申請日: 2020-12-15
• 公開（公告）號: CN113220820B
• 公開（公告）日: 2022-09-16
• 發明（設計）人: 郭得科;羅來龍;王希;張千楨;鄭龍
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/332;G06F16/33;G06F16/338;G06F40/30
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 曾志鵬

1.一種基于圖的高效SPARQL查詢應答方法，其特征在于，包括：

將RDF數據集的三元組建模為有向標記圖，對有向標記圖的實體頂點進行分組和合并，形成多級抽象圖，其中三元組中的對象和主體為所述有向標記圖的實體頂點；其中，RDF數據集為RDF數據的集合，RDF數據是s,p,o形式的三元組，其中s是實體或類，p表示一個與實體或類關聯的屬性，o是實體、類或文本值；有向標記圖G＝(U_G,E_G,∑_G,L_G)，其中U_G是與RDF數據中的所有主體和對象相對應的一組頂點，是連接主體和對象的一組有向邊，Σ_G是頂點和邊的一組有限標簽集合，標簽函數L_G將每個頂點或邊映射到Σ_G中的一個標簽上；有向標記圖包括文本頂點、實體頂點及變量頂點，合并有向標記圖中的連接同一個類的實體頂點，以形成所述多級抽象圖，所述多級抽象圖為語義抽象圖，其為是多級概念圖；

構建輔助數據結構，結合所述有向標記圖中連接同一類的實體頂點，構造抽象圖作為索引，所述輔助數據結構包括有向標記圖模式中語義包含關系的集合，所述有向標記圖模式用于描述所述有向標記圖的特征；其中，輔助數據結構表示有向標記圖模式中語義包含關系的一系列集合，有向標記圖模式允許增強RDF圖中的描述，輔助數據結構由四個集合組成SubPro(·)集合、SubClass(·)集合、Domain(·)集合及Range(·)集合，SubPro(·)集合為給定有向標記圖模式中的邊屬性p，SubPro(p)是p的子屬性集合，SubClass(·)集合為給定有向標記圖模式中的類頂點t，SubClass(t)是t的子類頂點集合，Domain(·)集合為給定有向標記圖模式中的類頂點t，Domain(t)是屬于t的定義域的邊屬性集合，Range(·)集合為給定有向標記圖模式中的類頂點t，Range(t)是屬于t的范圍的邊屬性集合；所述構造抽象圖作為索引為在所述輔助數據結構的基礎上，合并有向標記圖中的連接同一個類的實體頂點，構造一個抽象圖作為索引，在輔助數據結構構造過程中，需要獲得相應的超類頂點來構造索引，超類頂點為當不存在其他類頂點t時，使得類頂點t_s∈SubClass(t)，則稱類頂點t_s為超類頂點；

通過訪問抽象圖進行查詢，并給出應答結果。

2.根據權利要求1所述的方法，其特征在于，所述方法還包括：

對所述有向標記圖中的實體頂點附近的鄰居結構編碼成一個比特串，并對候選頂點進行剪枝，進行多級修剪進行細化，以給出經過優化后的應答結果。

3.根據權利要求1所述的方法，其特征在于，所述方法還包括：

通過按需飽和策略對所述應答結果是否完整進行檢測，包括以下兩個階段：

對數據邊所包含的子屬性進行檢查，以查看是否有任何子屬性與查詢邊匹配；

對實體頂點是否與抽象圖中的查詢頂點類型匹配進行檢查。

4.根據權利要求1所述的方法，其特征在于，所述方法還包括：

通過鄰域編碼對每一查詢邊的邊屬性信息進行無效候選的剪除。

5.根據權利要求4所述的方法，其特征在于，所述鄰域編碼包括：

將每一實體頂點描述為一個bit串，以作為頂點簽名；

通過Bloom過濾器將RDF圖中的每個頂點的相鄰邊屬性和相應的相鄰頂點屬性編碼成bit串。

6.根據權利要求1所述的方法，其特征在于，所述方法還包括：

當RDF圖更新時，通過邊插入處理和邊刪除處理對所述抽象圖進行增量維護。