面向大規模rdf圖數據的sparql並行查詢方法
2023-04-28 11:47:31
面向大規模rdf圖數據的sparql並行查詢方法
【專利摘要】本發明涉及RDF圖數據處理，為提供一種對大規模RDF圖數據的高效並行查詢處理方法，減少磁碟讀寫次數，提高查詢效率，為此，本發明採用的技術方案是，面向大規模RDF圖數據的SPARQL並行查詢方法，包括下列步驟：1)使用整體同步並行BSP模型描述RDF圖數據；2)使用資源的URI來標記；3)對於RDF圖數據集中的每一條三元組；4)對於3)中的每一條邊e，使用URIr作為er的標記；5)獲得用戶提交的查詢請求q0；6)選擇不同的傳播路徑，並行傳播；7)利用貪心算法評估qi-1中的每條子句所包含的信息量；8)重複6)和7)，直到所有子句都經過綁定。本發明主要應用於圖數據處理。
【專利說明】面向大規模RDF圖數據的SPARQL並行查詢方法
【技術領域】
[0001]本發明涉及RDF (Resource Description Framework,資源描述框架)圖數據處理和查詢、查詢領域，具體來說，涉及面向大規模RDF圖數據的並行查詢領域，即面向大規模RDF 圖數據的 SPARQL (SPARQL Protocol and RDF Query Language，SPARQL 協議與 RDF 查詢語言)並行查詢方法。
【背景技術】
[0002]網際網路中的信息由大量的計算機發送和接收，但是目前計算機並不能理解這些信息。針對這種情況，1998年Tim Berners-Lee提出語義網的概念。資源描述框架(RDF)是語義網的基本數據格式。由於RDF圖數據格式具有非常好的擴展性和靈活性，因此社交網絡、生物信息等越來越多的領域採用RDF格式發布數據，實現對RDF圖的查詢是利用這些信息的基礎。SPARQL是在RDF模型基礎上的標準查詢語言。與傳統的關係型資料庫中進行的查詢不同，在圖上進行的查詢具有更高的複雜度，因為這種查詢實際上是在一張RDF圖上進行子圖匹配(BGP)。
[0003]然而目前單機集中存儲和處理的管理方式已經無法應對RDF圖數據的巨大規模，分布式存儲和並行處理是語義Web的發展趨勢，也是目前對RDF圖數據進行管理和計算的有效手段。MapReduce (—種面向大規模數據的並行分布式編程模型)可以高效地處理大規模數據，但是對於更適合用消息傳遞模式來解決的圖計算，MapReduce並不是最佳選擇。
[0004]目前來看，無論是基於索引的存儲，還是基於文件的存儲，MapReduce框架下的查詢處理方式都是將大的完整的查詢拆分成小的子查詢，這些子查詢從各個數據節點上獲得部分結果，再將這些部分結果集中起來，做連接處理，最終獲得完整的結果。目前集中在分布式RDF圖數據上的查詢研究焦點也是如何拆分完整的查詢和如何將部分結果連接成最終結果。這樣的查詢處理過程存在以下一些問題:
[0005](I)沒有充分利用RDF圖數據的圖結構特徵，也就是沒有利用圖數據裡相鄰頂點的連接關係。機械地將圖數據當作獨立的邊來處理。
[0006](2 )沒有充分利用SPARQL語句的圖圖結構特徵。
[0007](3)查詢過程中涉及到多次輸入輸出，且輸入輸出的數據量巨大。
【發明內容】
[0008]為克服現有技術的不足，提供一種對大規模RDF圖數據的高效並行查詢處理方法，充分利用RDF圖數據的圖的特性，清晰直觀地完成SPARQL查詢任務，減少磁碟讀寫次數，提高查詢效率。為此，本發明採用的技術方案是，面向大規模RDF圖數據的SPARQL並行查詢方法，包括下列步驟:
[0009]I)使用整體同步並行BSP (Bulk Synchronous Parallel字頭縮寫)模型描述RDF圖數據，RDF圖數據中的每一個資源都被具體為一個可執行計算的BSP中的計算單元；
[0010]2)使用資源的URI來標記每一個與該資源對應的計算單元；[0011]3)對於RDF圖數據集中的每一條三元組:主語計算單元S，謂語P，賓語計算單元0，建立主語計算單元S到賓語計算單元O的有向邊e，使用謂語P的URI作為e的標記，並將e的相關信息保存在主語計算單元S的本地數據域中；
[0012]4)對於3)中的每一條邊e，建立一條方向相反的邊士，使用UR^作為&的標記，其中URI為謂語P的URI，並將e,的相關信息保存在賓語計算單元O的本地數據域中；
[0013]5)獲得用戶提交的SPARQL查詢請求qQ,分析qQ,利用貪心算法評估qQ中每條子句分別包含的信息量，將包含信息量最多的子句tPi，i為計數器，初始時i=l，作為首要待處理子句，將Qci發送給tPi的主語計算單元S,若S是未知變量,則發送給賓語計算單元O ;
[0014]6)S或O接收到時，在正向邊或反向邊中查找滿足tPi的可能解的集合Ei，並根據Ei中的信息對CIh中的變量進行綁定，得到部分綁定後的查詢qi，由於可能出現多個互不矛盾的綁定可能，所以存在多個不同的Qi，每個Qi根據所包含信息的不同，選擇不同的傳播路徑，並行傳播；
[0015]7)i=i+l，利用貪心算法評估CIh中的每條子句所包含的信息量，將包含信息量最多的子句tPi作為首要待處理子句，將qi_i發送給tPi的主語計算單元S，若S是未知變量，則發送給賓語計算單元O ;
[0016]8)重複6)和7)，直到所有子句都經過綁定，且各個子句綁定變量時沒有出現衝突，如果得到多於O個查詢結果，則返回這些結果。
[0017]上述的步 驟5)中，使用貪心算法評估每個子句所包含的信息量，並根據子句所包含的信息量決定從哪一個計算單元開始執行查詢，子句共分為八種類型，優先級的高低受該子句所包含的信息量的影響。最有可能匹配、匹配代價最小的子句將被排在靠前的位置，相對最難匹配、匹配代價最大的子句將被放在靠後的位置，如果某一子句包含的信息量比較大，或者該子句包含了一個出現次數比較高的變量，那麼這個子句的排序就比較靠前；反之，如果子句中變量較多，或者其所包含的變量在其他子句中出現的次數較少，則該子句排序就比較靠後。
[0018]本發明的技術特點及效果:
[0019]本發明針對大規模RDF圖數據的SPARQL查詢，提供了一種基於BSP並行計算模型的解決方法，滿足了大規模分布式存儲環境下的基本圖模式查詢要求，提高了對大規模RDF圖數據的查詢速度，有助於RDF圖數據的利用和管理。
【專利附圖】
【附圖說明】
[0020]圖1是某查詢在計算單元之間的轉發路徑。
[0021]圖2是本發明對RDF圖數據結構的擴展結果。
[0022]圖3在各個不同大小的數據集上執行10個查詢的平均時間圖。
[0023]圖4在不同大小的DBpedia數據集上不同複雜程度的查詢的平均響應時間效果圖。
【具體實施方式】
[0024]本發明採用的技術方案是:
[0025]9)使用BSP模型描述RDF圖數據，RDF圖數據中的每一個資源都被具體為一個可執行計算的BSP中的計算單元；
[0026]10)使用資源的URI (Uniform resource identifier,統一資源標示符)來標記每一個與該資源對應的計算單元；
[0027]11)對於RDF圖數據集中的每一條三元組(S，P, 0)，建立主語計算單元S到賓語計算單元O的有向邊e，使用謂語P的URI作為e的標記，並將e的相關信息保存在主語計算單元S的本地數據域中；
[0028]12)對於3)中的每一條邊e，建立一條方向相反的邊化使用URIr (其中URI為謂語P的URI)作為&的標記，並將&的相關信息保存在賓語計算單元O的本地數據域中；
[0029]13)獲得用戶提交的SPARQL查詢請求qQ，分析qQ，利用貪心算法評估qQ中每條子句分別包含的信息量，將包含信息量最多的子句tPi (i=l)作為首要待處理子句，將％發送給tPi的主語計算單元S (若S是未知變量，則發送給賓語計算單元O)；
[0030]14) S (或O)接收到qg時，在正向邊或反向邊中查找滿足tPi的可能解的集合Ei,並根據Ei中的信息對qg中的變量進行綁定，得到部分綁定後的查詢Qi (由於可能出現多個互不矛盾的綁定可能，所以存在多個不同的1，每個％根據所包含信息的不同，選擇不同的傳播路徑，並行傳播)；
[0031]15) i=i+l，利用貪心算法評估CIh中的每條子句所包含的信息量，將包含信息量最多的子句tPi作為首要待處理子句，將qi_i發送給tPi的主語計算單元S(若S是未知變量，則發送給賓語計算單元O);
[0032]16)重複6)和7)，直到所有子句都經過綁定，且各個子句綁定變量時沒有出現衝突。如果得到多於O個查詢結果，則返回這些結果。
[0033]上述的步驟5)中，使用貪心算法評估每個子句所包含的信息量，評估方法為:給每條子句打分，不包含未知變量的子句得分高於部分成分未知的子句，所有成分均未知的子句得分最低；包含公共變量的子句得分高於包含非公共變量的子句。根據子句得分決定從哪一個計算單元開始執行查詢。子句共分為八種類型，優先級的高低受該子句所包含的信息量的影響。最有可能匹配、匹配代價最小的子句將被排在靠前的位置，相對最難匹配、匹配代價最大的子句將被放在靠後的位置。如果某一子句包含的信息量比較大(例如，只含有一個變量或者不含變量)，或者該子句包含了一個出現次數比較高的變量(例如，星狀查詢的中心變量)，那麼這個子句的排序就比較靠前；反之，如果子句中變量較多，或者其所包含的變量在其他子句中出現的次數較少，則該子句排序就比較靠後。
[0034]上述步驟6)中。當某個計算單元接到中間結果％後，從Qi的未處理子句中讀取優先級最高的子句tp，檢查tp是8種子句中的哪一種:若變量出現在謂語或賓語的位置上，說明當前計算單元是tp的主語。此時，當前計算單元需要在出邊中查找與tp相匹配的信息，並根據查找到的信息對tp中的變量進行綁定；若變量出現在主語的位置上，說明當前計算單元是tp的賓語。此時，當前計算單元需要在入邊中查找與tp相匹配的信息，並根據查找到的信息對tp中的變量進行綁定。綁定不僅僅限於tp，若其他未處理子句中也包含tp中的變量，則需要對這些同名變量一併綁定。綁定完成後，當前計算單元需要把tp添加已處理的邊列表中，並從未處理的邊列表中將其刪除。由於綁定導致未處理邊列表中子句的變量狀態發生了變化，因此在轉發qi+1給下一個計算單元之前，需要對未處理邊列表中的邊重新確定處理優先級順序。[0035]下面結合附圖對本發明作進一步詳細說明。
[0036]圖1是一個查詢請求在其所涉及到的計算單元之間的轉發路徑，其中在計算單元01處出現了一個分支，下面結合該過程對實施方式進行詳細說明:
[0037]I)使用BSP模型描述RDF圖數據，RDF圖數據中的每一個資源都被具體為一個可執行計算的BSP中的計算單元，計算單元由圖1中的矩形表示；
[0038]2)使用資源的URI來標記每一個與該資源對應的計算單元；
[0039]3)對於RDF圖數據集中的每一條三元組(S，P, O),建立主語計算單元S到賓語計算單元O的有向邊e，使用謂語P的URI作為e的標記，並將e的相關信息保存在主語計算單元S的本地數據域中，圖1中單向箭頭表示兩個計算單元之間的一條邊；
[0040]4)對於3)中的每一條邊e，建立一條方向相反的邊士，使用URIr (其中URI為謂語P的URI)作為&的標記，並將&的相關信息保存在賓語計算單元O的本地數據域中，^沒有在圖中畫出，每一條都是與對應的e反向的邊,如圖2所示；
[0041]5)獲得用戶提交的SPARQL查詢請求q^,分析q^,利用貪心算法評估Qtl中每條子句分別包含的信息量，將包含信息量最多的子句tPi作為首要待處理子句，將％發送給tPi的主語計算單元S (若S是未知變量，則發送給賓語計算單元O)；
[0042]6) S (或O)接收到qg時，在正向邊或反向邊中查找滿足tPi的可能解的集合Ei,並根據Ei中的信息對qg中的變量進行綁定，得到部分綁定後的查詢Qi (由於可能出現多個互不矛盾的綁定可能，所以存在多個不同的1，每個％根據所包含信息的不同，選擇不同的傳播路徑，並行傳播)；
[0043]7)i=i+l，利用貪心算法評估CIh中的每條子句所包含的信息量，將包含信息量最多的子句tPi作為首要待處理子句，將qi_i發送給tPi的主語計算單元S(若S是未知變量，則發送給賓語計算單元O);
[0044]8)重複6)和7)，直到所有子句都經過綁定，且各個子句綁定變量時沒有出現衝突。如果得到多於O個查詢結果，則返回這些結果。
[0045]上述的步驟5)中，使用貪心算法評估每個子句所包含的信息量，並根據子句所包含的信息量決定從哪一個計算單元開始執行查詢，子句共分為8種類型，如表3所示。優先級的高低受該子句所包含的信息量的影響。最有可能匹配、匹配代價最小的子句將被排在靠前的位置，相對最難匹配、匹配代價最大的子句將被放在靠後的位置。如果某一子句包含的信息量比較大(例如，只含有一個變量或者不含變量)，或者該子句包含了一個出現次數比較高的變量(例如，星狀查詢的中心變量)，那麼這個子句的排序就比較靠前；反之，如果子句中變量較多，或者其所包含的變量在其他子句中出現的次數較少，則該子句排序就比較靠後。
[0046]上述步驟6)中。當某個計算單元接到中間結果％後，從Qi的未處理子句(用列表tps_toprocess表示)中讀取優先級最高的子句tp,確定tp屬於8種子句類型中的哪一種:若變量出現在謂語或賓語的位置上，說明當前計算單元是tp的主語。此時，當前計算單元需要在出邊中查找與tp相匹配的信息，並根據查找到的信息對tp中的變量進行綁定；若變量出現在主語的位置上，說明當前計算單元是tp的賓語。此時，當前計算單元需要在入邊中查找與tp相匹配的信息，並根據查找到的信息對tp中的變量進行綁定。綁定不僅僅限於tp，若其他未處理子句中也包含tp中的變量，則需要對這些同名變量一併綁定。綁定完成後，當前計算單元需要把tp添加已處理的邊列表(用tps_processed表示)中，並從未處理的邊列表中將其刪除。由於綁定導致未處理邊列表中子句的變量狀態發生了變化，因此在轉發qi+1給下一個計算單元之前，需要對未處理邊列表中的邊重新確定處理優先級順序。具體步驟如下:
[0047]輸入:tps_toprocess, tps_processed
[0048]輸出:tps_toprocess, tps_processed
[0049]1.接收其他頂點發送來的tps_toprocess和tps_processed.新建標誌變量flag.[0050]2.取出待處理的三元組模式中處理優先級最高的一條tp=tps_toprocess.get (O).[0051]3.判斷tp中是否包含未知變量.[0052]3.1.若包含，設該變量名為X，在出邊列表或入邊中查找滿足tp的邊，數量為η.[0053]如果η>0，對於滿足tp的邊edgei執行下面的操作:
[0054]根據edgei中的信息,綁定tps_toprocess中所有的χ,令fIag=L
[0055]如果n=0,令 fIag=0.[0056]3.2.若不包含，在出邊列表或入邊列表中查找是否存在邊滿足tp的邊，若存在則flag=l,否貝丨J fIag=O ；
[0057]3.3.如果 flag==l:將 tp 從 tps_toprocess 中刪除並添加到 tps_processed 中；如果 f Iag==O:拋棄 tps_toprocess 和 tps_processed.[0058]4.檢查tpS_t0pr0CeSS是否為空.若是，說明所有三元組模式都匹配完畢，當前結果為最終結果，將當前結果作為最終結果返回.若否，將tps_toprocess和tps_processed傳遞給下一個計算單元.[0059]例如,對於圖1中的查詢q，初始時包括三條子句，如表1所示，q中共包含了兩個未知變量X和y，在經過一次傳播後，q中的一個未知變量被綁定，得到表2所示結果。
[0060]本發明使用了LUBM (Lehigh University Benchmark)數據集和 DBpedia 數據集作為測試數據。LUBM提供了一個 數據生成器和14條標準的查詢測試語句，從中選出了 10條測試查詢。圖3是在各個不同大小的數據集上執行10個查詢的平均時間。隨著數據集大小的增加，查詢時間也隨之上升。10個查詢在LUBM-1上執行的平均時間為0.497s，在LUBM-10上執行的平均時間為2.191s，雖然三元組數量增長了 11.8倍，但是查詢時間只增長了 3.4倍。
[0061]圖4描述了在不同大小的DBpedia數據集上不同複雜程度的查詢的平均響應時間。從圖中可以看到，查詢執行時間隨查詢語句包含的三元組模式數量和數據集規模的增長而增長。對查詢中的每一個三元組模式，無論其是否包含未知變量，都需要一個超步來處理，因此處理一個查詢所需要的總的超步數量與BGP查詢中包含的三元組模式數量相同。對於同一個數據集，查詢時間與查詢語句中的三元組模式數量線性相關。對同一條查詢語句，當數據集規模變大時，查詢時間變長，但是時間的增長速度遠遠小於數據的增長速度。
[0062]
【權利要求】
1.一種面向大規模RDF圖數據的SPARQL並行查詢方法，其特徵是，包括下列步驟: 面向大規模RDF圖數據的SPARQL並行查詢方法，包括下列步驟: 1)使用整體同步並行BSP(Bulk Synchronous Parallel字頭縮寫)模型描述RDF圖數據，RDF圖數據中的每一個資源都被具體為一個可執行計算的BSP中的計算單元； 2)使用資源的URI來標記每一個與該資源對應的計算單元； 3)對於RDF圖數據集中的每一條三元組:主語計算單元S，謂語P，賓語計算單元0，建立主語計算單元S到賓語計算單元O的有向邊e，使用謂語P的URI作為e的標記，並將e的相關信息保存在主語計算單元S的本地數據域中； 4)對於3)中的每一條邊e，建立一條方向相反的邊使用UR仁作為&的標記，其中URI為謂語P的URI，並將e,的相關信息保存在賓語計算單元O的本地數據域中； 5)獲得用戶提交的SPARQL查詢請求％，分析％，利用貪心算法評估％中每條子句分別包含的信息量，將包含信息量最多的子句tPi，i為計數器，初始時i=l，作為首要待處理子句，將Qci發送給tPi的主語計算單元S,若S是未知變量,則發送給賓語計算單元O ; 6)S或O接收到時，在正向邊或反向邊中查找滿足tPi的可能解的集合Ei,並根據Ei中的信息對qg中的變量進行綁定，得到部分綁定後的查詢qi;由於可能出現多個互不矛盾的綁定可能，所以存在多個不同的Qi，每個Qi根據所包含信息的不同，選擇不同的傳播路徑，並行傳播； 7)i=i+l，利用貪心算法評估qi_i中的每條子句所包含的信息量，將包含信息量最多的子句tPi作為首要待處理子句，將qi_i發送給tPi的主語計算單元S，若S是未知變量，則發送給賓語計算單元O ; 8)重複6)和7)，直到所有子句都經過綁定，且各個子句綁定變量時沒有出現衝突，如果得到多於O個查詢結果，則返回這些結果。
2.如權利要求1所述的面向大規模RDF圖數據的SPARQL並行查詢方法，其特徵是，上述的步驟5)中，使用貪心算法評估每個子句所包含的信息量，並根據子句所包含的信息量決定從哪一個計算單元開始執行查詢，子句共分為八種類型，優先級的高低受該子句所包含的信息量的影響。最有可能匹配、匹配代價最小的子句將被排在靠前的位置，相對最難匹配、匹配代價最大的子句將被放在靠後的位置，如果某一子句包含的信息量比較大，或者該子句包含了一個出現次數比較高的變量，那麼這個子句的排序就比較靠前；反之，如果子句中變量較多，或者其所包含的變量在其他子句中出現的次數較少，則該子句排序就比較靠後。
【文檔編號】G06F17/30GK103778251SQ201410056349
【公開日】2014年5月7日 申請日期:2014年2月19日 優先權日:2014年2月19日
【發明者】呂雪棟, 馮志勇, 王鑫 申請人:天津大學