論文英文標題：Graph-based Indexing Method for Searching in RDF Data
論文中譯標題：基於圖形的RDF數據索引方法
來源：2019 International Conference on Advanced Information Technologies (ICAIT)
作者：Khin Myat Kyu, Aung Nway Oo
編譯：任騰龍，孫靜正，劉博藝，數據挖掘組
01
摘要
RDF是語義Web的基於圖形的通用數據模型，SPARQL是用於訪問RDF數據的查詢語言。隨著RDF數據大小的增加，回答複雜的SPARQL查詢非常昂貴，因為需要多個自聯接進行處理。在這項工作中，我們考慮基於RDF數據的圖結構的索引和搜索方法，以減少聯接操作的數量。它可以加快查詢的性能，並支持鏈和星形SPARQL查詢。通過考慮每個頂點周圍邊緣的結構，從RDF數據圖中提取出鏈狀和星形子圖。獲得的子圖存儲為索引，稱為CS-index。為了執行查詢，首先基於所有三元模式的公共聯接變量將查詢分解為查詢子圖。通過在CS-index中而不是在整個數據圖中搜索查詢子圖來檢索查詢結果。所提出的索引結構和搜索方法傾向於通過減少聯接數來加快查詢響應時間。我們對LUBM數據集進行了一項性能研究，發現我們的方法比比賽優勝幾個數量級。
02
核心內容
創新點：這篇工作主要從 RDF 圖結構的角度提出減少 JOIN 次數的方法，從而提高SPARQL 查詢效率。提出了一種新的索引結構 CS-index，該索引結構主要針對鏈狀和星形查詢，根據所有三元組模式的公共變量將查詢分解為對應查詢子圖，查詢時通過對應子圖進行查詢，而無需對整個圖進行查詢。最後提出對應的搜索算法主要通過減少 JOIN 次數來加快查詢響應時間。
科學問題：針對複雜查詢，現如今的研究大多不能有效解決多個三元組查詢帶來的多個 JOIN 問題，這些問題會嚴重影響查詢效率。一般採取的措施主要為減少 JOIN 次數、較少中間結果數、優化查詢順序。本篇工作主要從圖索引結構和搜索算法方面入手，通過減少連接操作數量來提高系統性能。
解決方法：本工作暫時只支持鏈狀和星型查詢，提出一種新的索引結構-CS-index， 具體地，通過收集從 RDF 圖中頂點吸收邊和發射變的頂點和邊來捕獲 RDF 實體之間的數據關係。定義鏈狀子圖，和星型子圖對應不同類型的查詢。最後對索引結構中實體的度進行升序排序，來減少查詢搜索時對應的數據搜索空間。數據搜索層面， 通過提出一種搜索算法來優化查詢性能。
03
主要試驗情況
1. 建立 CS-index 索引
解析 RDF 圖數據，將數據解析為 S，P，O 形式。為節省存儲開銷，採取整數編碼將每個主謂賓的部分編碼為唯一的整數值。其中定義兩個字典分別存儲節點和謂詞-節點字典和謂詞字典，並以鍵值對（ID，value）的形式表示，其中 ID 為整數值，value 表示 URI 和文字部分。鏈狀和星型子圖提取，因為 CS-index 索引的建立首先提取鏈和星型子圖， 因此首先定 義並提取相應的子圖。
鏈狀子圖：具有至少一個從目標頂點傳入或傳出的子圖定義為鏈狀子圖
星型子圖：具有多個傳入或傳出邊緣的子圖定義為星型子圖。
具體的索引偽代碼如下圖所示：
第 1-2 行：輸入：RDF 數據集，定義的入度，出度變量，以及入度-邊， 出度-邊的變量。 第 3 行：該算法輸出 CS-index 索引，頂點字典，謂詞字典。第 5-11 行：如果變量 v 為 subject 或者 object，則該變量為頂點，以鍵值對的形式存入頂點字典，如果變量 v 為 predicate，則該變量為謂語或者邊，則以鍵值對的形式存入謂語字典中。第 12-26 行：如果變量 v 為 subject，則該頂點具有出度，即有發射邊，執行子圖提取和度的計算；如果變量 v 為 object，則該頂點具有入度，具有吸收邊。根據頂點與邊的關係提取鏈狀和星型子圖。第 28-30：建立 CS-index 索引結構。第 31 行：對索引結構進行升序排序。
完成所有 RDF 三元組的處理後，提取子圖作為 CS-index，並存儲在三列表中（傳出邊緣，傳入邊緣，Vi），事例如下圖所示：
2. 查詢搜索算法
在查詢處理階段，查詢處理器找到大多數 triple pattern 中都包含的連接變量， 並根據連接變量對 triple pattern 進行分區，每個共同的變量都是用兩個字典進行編碼，然後對每個公共連接的變量，計算出度，入度，輸出邊緣，輸入邊緣。查詢搜索算法偽代碼如下圖所示：
第 1-2 行：算法輸入：SPARQL 查詢語句，CS-index,兩個字典算法輸出：查詢結果 第 3-8 行：查詢處理器找到大多數 triple pattern 中都包含的連接變量，並根據連接變量對 triple pattern 進行分區。匹配階段：第 1-4 行：將輸出邊緣對和輸入邊緣與 CS 索引中的輸出邊緣對和輸入邊緣進行 匹配。最後處理：當 CS-index 中找到匹配對時，需要通過與字典的映射將所有頂點 ID 解析為原始字符串，且系統以人類可讀的格式輸出最終結果。
3. 實驗部分
實驗數據集為：LUBM10（一百萬個三元子），LUBM20（300 萬個三元組） 查詢語句：14 個基準查詢，其中 9 個為測試查詢，比較本文方法和 axonDB 之間的執行時間。Q13 為鏈狀查詢，Q6，Q14 時具有一個 triple pattern 的查詢，其餘皆為星型查詢。實驗環境：1.9GHz，4GB RAM 和 64 位 Ubuntu 14.04 LTS 的 PC，測試查詢運行10 次，獲得平均響應時間，每個查詢處理的最大時間間隔限制為 5min。
1.實驗結果分析：
首先對比索引建立的時間：本文提出的方法考慮頂點周圍的傳出和傳入邊緣的優勢，因此索引建立的時間較短。
2. 查詢響應時間對比:
實驗結果顯示兩個數據集在 9 個測試查詢的運行時間，實驗結果表明，即使輸入數據集很大，但是該方法仍能夠有效提高兩種查詢的響應時間，同時可以處理具有一個查詢語句的簡單查詢。
為了進行對比實驗，使用 LUBM20 數據集和 axonDB 進行了對比評測本系統性能。結果顯示本文提出的方法對所有查詢都具有很好的性能，而 axonDB 在 Q（1，3，4，5，10，11）中未能得到很好的處理。
該圖更能清楚的看到評估結果，在 LUBM20 數據上針對三個分別具有不同的查詢進行了其他實驗。通過實驗結果表明，本文方法可以處理響應時間稍有不同的所有查詢，即使查詢語句數量增加到一倍，但響應時間幾乎不變，但是 axonDB 卻不能得到更好的效果。
分析：本文提出新穎的索引結構較少 JOIN 次數過多帶來的性能提升較慢的現象，但本文具有一定的侷限性，只能處理較少類型的查詢，且沒有查詢優化環節。
Abstract
RDF is a generic graph-based data model of Semantic Web, and SPARQL is a query language for accessing the RDF data. With the increasing size of RDF data, answering complex SPARQL queries is expensive because multiple self-joins are needed to process.In this work, we consider an indexing and searching approach based on the graph structure of RDF data to reduce the number of join operations. It can speed up the queries’ performance and support chain and star shaped SPARQL query. Chain and star shaped subgraphs are extracted from the RDF data graph by considering the structure of edges around each vertex. The subgraphs obtained are stored as the index, named as CS-index. To execute a query, the query is firstly decomposed into query subgraphs based on the common join variable of its all triple patterns. And the query results are retrieved by searching the query subgraphs in CS-index, not in the whole data graph. The proposed index structure and searching approach tend to speed up the query response time by reducing the number of joins. We conduct a performance study on LUBM data set and see that our method outperforms the contest by a few orders of magnitude.
鏈接：https://pan.baidu.com/s/17StLla5_ejWA45EXwGAC4w
提取碼：xjk9
閱讀更多 RoboticAI 的文章
