[發明專利]一種大規模數據集上的關系查詢方法

有效

• 申請號: 201110259125.2
• 申請日: 2011-09-02
• 公開（公告）號: CN102332009A
• 公開（公告）日: 2012-01-25
• 發明（設計）人: 許坤;趙東巖;鄒磊;賈愛霞
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 余長江

技術領域

本發明屬于數據庫技術領域、語義網領域，涉及一種大規模數據集上的帶標簽限制的關系查詢方法。

背景技術

語義數據是一種表示實體的屬性信息以及實體之間語義關系的數據，一般以三元組的集合形式來表示，三元組的格式為<主體，謂詞，客體>。例如：<北京航空航天大學，校長，懷進鵬>，<懷進鵬，畢業于，吉林大學>，......，<吉林大學，校長，展濤>。

語義數據有一種很重要的用途即語義推斷，以上面的三元組為例，我們可以推斷出北京航空航天大學到展濤的一種關系，在傳統的關系查詢方法中，往往使用2-hop之類的方法對路徑進行索引，不過隨著圖的規模不斷增長，該類方法的索引計算量也隨之劇增，相應的計算時間也急劇加大，可見傳統的關系查詢方法已經不能滿足日益增長的實體關系查詢的要求。

發明內容

本發明的目的在于提出了一種大規模數據集上的關系查詢方法，用以支持海量數據的關系查詢，并且很好地支持了擴展性。

本發明的技術方案為：

一種大規模數據集上的關系查詢方法，其步驟為：

1)提供或建立語義數據圖的語義數據有向圖；

2)針對語義數據有向圖中每一種標簽，計算只包含同一種標簽的連通子圖；

3)對步驟2)得到的連通子圖進行合并，將所述語義數據有向圖劃分為若干子圖；

4)計算步驟3)合并后的每一子圖中最強連通子圖C，并計算其二部圖，得到進入C的邊界點集合S₁和從C出去的邊界點集合S₂；

5)對于每一最強連通子圖C，利用基于標簽的最短路徑搜索方法計算S₁中每個點到S₂中每個點的最短路徑，將所有最強連通子圖的所述最短路徑存儲到一路徑集合RS中；

6)記錄步驟3)劃分的每一子圖中具有標簽非冗余路徑的兩個點的標簽，得到每一子圖的標簽集合；

7)利用所述標簽集合判斷語義數據有向圖中是否存在符合查詢條件的路徑；如果有，則返回查詢路徑結果；否則，在子圖之間進行遍歷，根據所述路徑集合RS確定可到達目標節點的子圖，然后利用該子圖的標簽集合返回查詢路徑結果。

進一步的，對步驟2)得到的連通子圖進行合并的方法為：針對每一個連通子圖，首先計算其E(p)/C(p)的值，其中E(p)代表連通子圖中邊的數目，C(p)代表連通子圖中的連通區域數目；然后選擇E(p)/C(p)值最大的兩個連通子圖進行合并，其中合并后的子圖中包含的標簽數要小于設定的最大標簽數，子圖中的節點數要小于設定的最大節點數。

進一步的，如果查詢條件中的路徑標簽是當前子圖的標簽集集合，則判定語義數據有向圖中存在符合查詢條件的路徑。

進一步的，采用2-hop方法對步驟3)劃分的每一子圖建立索引，記錄每一子圖中具有標簽非冗余路徑的兩個點的標簽。

進一步的，所述語義數據有向圖的建立方法為：

1)將語義數據圖中的實體抽象成點，將實體之間的關系抽象成有向邊；

2)將同一種關系對應的邊抽象成一個標簽；其中，標簽代表邊的種類，點與點之間的路徑長度為該路徑上標簽的種類數。

進一步的，所述基于標簽的最短路徑搜索方法為dijkstra算法。

本發明實施提出了一種基于標簽的分圖方法，包括：

利用標簽的數目與圖的連通區域數目的比值來確定子圖結合的順序。

利用設定的查詢子圖標簽總數和查詢子圖中點的數目來約束查詢子圖的大小。

本發明實施提出了一種將帶有標簽的有向圖轉變成帶有標簽的二部圖的方法，包括：

確定該圖的最強連通分支；

找到每個連通分支內的兩類邊界點，并利用基于標簽的最短路徑搜索方法確定該二部圖。

本發明實施提出了一種基于分層的查詢方法，包括：

利用分圖方法的特性，采用提前計算加上臨時搜索的方法來查詢關系。

與現有技術相比，本發明的積極效果為：

本發明首次提出了以標簽作為主要考慮因素的分圖方法，并且用實驗證明了該方法的優越性，而且首次提出了將圖分塊的想法進行關系查詢，并改進了dijkstra算法以適應于現在的問題，支持海量數據的關系查詢，并且很好地支持了擴展性。

附圖說明

圖1為該發明的總體方法流程圖。

圖2為抽象出的有向圖。

圖3為劃分最強連通子圖的示例圖。