[發明專利]一種基于外存的圖數據存儲方法及子圖查詢方法

有效

• 申請號: 201110202697.7
• 申請日: 2011-07-19
• 公開（公告）號: CN102254012A
• 公開（公告）日: 2011-11-23
• 發明（設計）人: 彭鵬;鄒磊;趙東巖;賈愛霞
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 余長江

技術領域

本發明屬于數據庫技術領域、圖數據管理領域，主要涉及一種基于外存的對大規模圖數據進行存儲、構建索引和執行子圖查詢的方法。

背景技術

圖數據庫是一種利用圖的結構和屬性來表示與存儲信息的新型數據庫技術，是NoSQL數據庫的一種。一般的圖數據庫應該能存儲任何形式的圖，包括地理上的地圖、社會關系網絡等等。

圖數據庫是基于圖論的，它利用了圖論中點、邊等概念。其中，點常用來代表現實中的實體，如人、公司、賬戶及其他一切你希望記錄的事物。邊用來連接兩個點，用來表示兩點之間的關系。一般而言，點或邊上還會附帶其他信息。比如一個基于社交網絡的圖上，每個點代表一個人，那么這個點上不但包含有這人的名字，一般還會有諸如住址、聯系方式等其他信息，而邊上就可能會有兩個人具體關系的描述，比如父子關系、朋友關系等。

相較于傳統關系數據庫，圖數據庫能更為直接地映射到面向對象的應用中去，同時也能更自然地擴展到海量數據集上。圖數據庫不依賴于模式，所以它們也更適合于管理那些會經常被更新的數據。其中，子圖查詢是圖數據庫領域里極為重要的一項需求。例如，給定一個社交網絡圖，我們想了解某種人物關系的存在情況。顯然，我們可以將這種特殊的人物關系用一個查詢圖表示出來，之后，這就需要我們進行在大的社交網絡圖中找出查詢圖的所有匹配。

然而，對于子圖查詢，現有的方法和系統中，一方面，它們大部分都是基于內存的方法，所以只支持小規模圖上的運算，這顯然無法適應現階段不斷增長的數據規模；另一方面，它們都需要建立復雜的索引結構，而這些結構無法適應數據圖的不斷更新。可見，傳統的圖數據庫技術已經無法滿足日益增長的圖數據的存儲和查詢的需求。

發明內容

本發明的目的在于提出了一種基于外存的圖數據存儲方法及子圖查詢方法，用以支持對大規模圖數據的存儲、索引及子圖查詢，并很好的支持了擴展性。

本發明實施例提供一種大規模圖數據存儲與索引的方法，包括：

基于圖數據中邊結構的數據組織方法；

基于B+樹的圖數據存儲；

基于位圖的索引構建；

基于數據直方圖的代價估計；

對大規模圖數據的動態更新的支持；

本發明實施例提供一種支持對大規模圖數據進行子圖匹配查詢的裝置，包括：

對子圖查詢的解析的部分；

對子圖查詢的分解的部分；

對分解出的查詢圖的子模塊進行處理的部分；

對所有子模塊處理結果進行整合的部分。

其中，對子圖查詢的分解，我們設計了兩種模式的分解，分別為：

基于鄰接邊的子圖分解；

基于星結構的子圖分解。

本發明的技術方案為：

一種基于外存的圖數據存儲方法，其步驟為：

1)對圖數據格式統一為一種標準圖數據格式；其中，所述標準圖數據格式為：以“t#NNumberofVertices?NumberofEdges”開始，然后是圖中的點信息v，一個點對應于一行，格式為“v?i?LabelofVertices_i”，然后是圖的邊信息e，一條邊對應于一行，格式為“e?v_iv_j”；最后以“t#-1”結束；其中，N為圖的標識，NumberofVertices為圖中點的數量，NumberofEdges為圖中邊的數量，i是點的標識符，LabelofVertices_i是點上的唯一的標簽信息，v_i是邊的起點信息，v_j為邊的終點信息；

2)根據圖數據中每條邊的起點和終點的標簽信息，對圖中的邊進行分類存儲，然后對每類邊建立B+-Tree索引；

3)按照圖數據中每個點上的標簽信息，將圖中的點劃分為若干域，同一域中每一個點按點的標識符順序依次對應于一位；然后根據邊的起點、終點標簽信息，為步驟2)中的每一類邊建立一位圖索引；

4)對每一類邊建立一起點信息數據直方圖和一終點信息數據直方圖，記錄同類邊的統計信息。

進一步的，按照字典序為每類邊建立B+-Tree索引。