[發明專利]基于稀疏矩陣的RDF數據存儲和查詢方法

在審

• 申請號: 201811004427.3
• 申請日: 2018-08-30
• 公開（公告）號: CN109325029A
• 公開（公告）日: 2019-02-12
• 發明（設計）人: 張小旺;張明月;馮志勇
• 申請（專利權）人: 天津大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/242;G06F16/2455
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 劉國威

1.一種基于稀疏矩陣的RDF數據存儲和查詢方法，其特征是，步驟如下：

步驟一：將原始RDF數據的字符串類型哈希編碼成整數類型；

步驟二：對編碼后的RDF數據構建RDF立方體RDF Cube；

步驟三：通過建立謂詞索引，采用一系列稀疏矩陣的形式來存儲RDF Cube；

步驟四：解析并優化SPARQL查詢語句得到最優的查詢計劃；

步驟五：基于稀疏矩陣的Join查詢執行，結果輸出。

2.如權利要求1所述的基于稀疏矩陣的RDF數據存儲和查詢方法，其特征是，步驟四具體地：對于給定的一個RDF數據的SPARQL查詢語句，將其解析成一個查詢圖，然后再根據查詢圖中每條邊的統計數據進行排序，在保證邊與邊連接的情況下重構查詢執行計劃。

3.如權利要求2所述的基于稀疏矩陣的RDF數據存儲和查詢方法，其特征是，步驟四進一步具體地：輸入的是一個SPARQL查詢語句，其形式是一個L＝(e₁,e₂,...,e_n)，包含這個查詢語句的所有邊，首先初始化一個記為N的點集合來記錄選取的邊的點，并且按照L中所有的邊的統計數據對L進行排序；然后在排序后的查詢語句L中選取第一條邊加入Q中，并將所選取的邊的點加入N中，并更新L；只要L不為空，依次循環的從L中選取一條統計數小并且和之前已選邊有關聯的邊加入Q中，所選邊的點∈N并將該所選邊的點加入到N中，更新L；最終得到的查詢計劃Q即為最優查詢計劃。

4.如權利要求1所述的基于稀疏矩陣的RDF數據存儲和查詢方法，其特征是，步驟五具體地：通過步驟四得到給定的優化后的查詢計劃，對查詢計劃中的每一個稀疏矩陣依次執行基于稀疏矩陣的Join算法得到最終的查詢結果，其中，每兩個稀疏矩陣具體執行的是SMJoin算法。

5.如權利要求4所述的基于稀疏矩陣的RDF數據存儲和查詢方法，其特征是，步驟五進一步具體地：算法1是對于給定的優化后的計劃中的每個稀疏矩陣進行Join算法運算處理，輸出最終查詢結果；算法2是給定兩個稀疏矩陣執行核心SMJoin算法；

對于算法1，輸入的是給定的一個經過優化后的查詢計劃Q，先從優化后的查詢計劃Q中取出第一個記為R_t稀疏矩陣并更新Q，然后依次從Q中取出下一個記為SpTable稀疏矩陣，兩個稀疏矩陣R_t和SpTable進行SMJoin操作，并更新結果至R_t，重復的從Q中選取下一個稀疏矩陣進行SMJoin操作直至Q為空，最終的查詢結果即為R_t；

對于算法2，SMJoin描述的是算法1中給定的兩個稀疏矩陣A和B進行join操作，首先遍歷矩陣A的每個非零行，然后對矩陣A中的每個非零行中的每個非零項，從矩陣B中找到與其匹配的非零項，如果滿足條件就將其匹配后的結果輸出至結果矩陣R_t中，最終輸出join操作的結果矩陣即為R_t。