一種基於外存的圖數據存儲方法及子圖查詢方法
2023-11-04 12:48:17 2
專利名稱：一種基於外存的圖數據存儲方法及子圖查詢方法
技術領域：
本發明屬於資料庫技術領域、圖數據管理領域，主要涉及一種基於外存的對大規模圖數據進行存儲、構建索引和執行子圖查詢的方法。
背景技術：
圖資料庫是一種利用圖的結構和屬性來表示與存儲信息的新型資料庫技術，是 NoSQL資料庫的一種。一般的圖資料庫應該能存儲任何形式的圖，包括地理上的地圖、社會關係網絡等等。圖資料庫是基於圖論的，它利用了圖論中點、邊等概念。其中，點常用來代表現實中的實體，如人、公司、帳戶及其他一切你希望記錄的事物。邊用來連接兩個點，用來表示兩點之間的關係。一般而言，點或邊上還會附帶其他信息。比如一個基於社交網絡的圖上，每個點代表一個人，那麼這個點上不但包含有這人的名字，一般還會有諸如住址、聯繫方式等其他信息，而邊上就可能會有兩個人具體關係的描述，比如父子關係、朋友關係等。相較於傳統關係資料庫，圖資料庫能更為直接地映射到面向對象的應用中去，同時也能更自然地擴展到海量數據集上。圖資料庫不依賴於模式，所以它們也更適合於管理那些會經常被更新的數據。其中，子圖查詢是圖資料庫領域裡極為重要的一項需求。例如， 給定一個社交網絡圖，我們想了解某種人物關係的存在情況。顯然，我們可以將這種特殊的人物關係用一個查詢圖表示出來，之後，這就需要我們進行在大的社交網絡圖中找出查詢圖的所有匹配。然而，對於子圖查詢，現有的方法和系統中，一方面，它們大部分都是基於內存的方法，所以只支持小規模圖上的運算，這顯然無法適應現階段不斷增長的數據規模；另一方面，它們都需要建立複雜的索引結構，而這些結構無法適應數據圖的不斷更新。可見，傳統的圖資料庫技術已經無法滿足日益增長的圖數據的存儲和查詢的需求。
發明內容
本發明的目的在於提出了一種基於外存的圖數據存儲方法及子圖查詢方法，用以支持對大規模圖數據的存儲、索引及子圖查詢，並很好的支持了擴展性。本發明實施例提供一種大規模圖數據存儲與索引的方法，包括基於圖數據中邊結構的數據組織方法；基於B+樹的圖數據存儲；基於位圖的索引構建；基於數據直方圖的代價估計；對大規模圖數據的動態更新的支持；本發明實施例提供一種支持對大規模圖數據進行子圖匹配查詢的裝置，包括對子圖查詢的解析的部分；對子圖查詢的分解的部分；
對分解出的查詢圖的子模塊進行處理的部分；對所有子模塊處理結果進行整合的部分。其中，對子圖查詢的分解，我們設計了兩種模式的分解，分別為基於鄰接邊的子圖分解；基於星結構的子圖分解。本發明的技術方案為一種基於外存的圖數據存儲方法，其步驟為1)對圖數據格式統一為一種標準圖數據格式；其中，所述標準圖數據格式為以 「t#NNumberofVertices NumberofEdges」開始，然後是圖中的點信息ν，一個點對應於一行，格式為「V i LabelofVerticesj 」，然後是圖的邊信息e，一條邊對應於一行，格式為「e v_iv_j」；最後以「t#-l」結束；其中，N為圖的標識，NumberofVertices為圖中點的數量， NumberofEdges為圖中邊的數量，i是點的標識符，LabelofVertices」是點上的唯一的標籤信息，v_i是邊的起點信息，v_j為邊的終點信息；2)根據圖數據中每條邊的起點和終點的標籤信息，對圖中的邊進行分類存儲，然後對每類邊建立B+-Tree索引；3)按照圖數據中每個點上的標籤信息，將圖中的點劃分為若干域，同一域中每一個點按點的標識符順序依次對應於一位；然後根據邊的起點、終點標籤信息，為步驟2)中的每一類邊建立一位圖索引；4)對每一類邊建立一起點信息數據直方圖和一終點信息數據直方圖，記錄同類邊的統計信息。進一步的，按照字典序為每類邊建立B+-Tree索引。進一步的，為每一類邊建立以位圖索引的方法為首先根據邊的起點、終點標籤信息建立每一類邊的起點位圖索引和終點位圖索引，然後對於某條邊屬於某類,v在所有標籤是L1的點中的第k名，則在對應的起點位圖索引第k列取值為1， u在所有標籤是L2的點中的第η名，則在這類邊的終點位圖索引第η列取值為1。進一步的，每一類邊的起點數據直方圖和終點數據直方圖的建立方法為設有Ii1 條邊屬於類，且這Ii1條邊的起點都為v，同時ν為所有標籤是L1的點中的第k名，則在對應的起點數據直方圖第k列取值為Ii1 ；同理，設有n2條邊屬於類，且這 n2條邊的終點都為u，同時u為所有標籤是L2的點中的第m名，則在對應的終點數據直方圖第m列取值為n2。進一步的，當刪除一條邊時，首先找到所刪除的邊在B+-Tree中位置，然後在圖數據中予以刪除並重新統計邊的分布信息，用以更新這類邊的數據直方圖。進一步的，當從邊的統計信息中某個點不再含有該類的邊，則將該類邊的位圖索引的對應位置變為O。進一步的，當新增一條邊時，首先找到所新增的邊在B+-Tree中位置，然後在圖數據中增加該邊並重新統計邊的分布信息，用以更新這類邊的數據直方圖；如果新增之後發現某個點從沒有該類的邊變成含有該類邊，則將該類別的位圖索引的對應位置變為1。進一步的，當更新一個點時，首先遍歷這個點可能在的所有的邊的類，然後更新這個點的所有的相關邊。
一種基於權利要求1所述方法存儲圖數據的子圖查詢方法，其步驟為1)根據圖數據的數據直方圖索引搜索源查詢子圖中當前最優的鄰接邊P ；2)從源查詢子圖中去掉P，得到一個減小的查詢子圖，並將P作為查詢子圖的子模式保存起來；在剩餘查詢子圖中重複利用數據直方圖索引找當前最優的鄰接邊，然後將其去掉並作為一子模式保存，直到將源查詢子圖分解完，得到一子模式集合；3)根據每一查詢子模式所對應的邊信息，找出該邊對應的類，然後讀取這個類對應的位圖索引；4)將讀取的所有位圖索引的對應部分進行一次邏輯「與」運算，當「與，，運算結果為「1」時，從邊信息的B+-Tree存儲中讀出匹配的邊信息，得到所有子模式在圖數據中匹配的邊；5)對於所有匹配的邊，如果兩個匹配的邊所對應的子模式包含有相同的查詢點， 則將這兩個子模式所對應的匹配邊拼接起來，得到與源查詢子圖匹配的查詢結果。一種基於權利要求1所述方法存儲圖數據的子圖查詢方法，其步驟為1)根據圖數據的數據直方圖索引搜索源查詢子圖中當前最優的星結構P ；2)從源查詢子圖中去掉P，得到一個減小的查詢子圖，並將P作為查詢子圖的子模式保存起來；在剩餘查詢子圖中重複利用數據直方圖索引找當前最優的星結構，然後將其去掉並作為一子模式保存，直到將源查詢子圖分解完，得到一子模式集合；3)根據每一查詢子模式所對應的邊信息，找出該邊對應的類，然後讀取這個類對應的位圖索引；4)將讀取的所有位圖索引的對應部分進行一次邏輯「與」運算，當「與，，運算結果為「1」時，從邊信息的B+-Tree存儲中讀出匹配的邊信息，得到所有子模式在圖數據中匹配的邊；5)對於所有匹配的邊，如果兩個匹配的邊所對應的子模式包含有相同的查詢點， 則將這兩個子模式所對應的匹配邊拼接起來，得到與源查詢子圖匹配的查詢結果。與現有技術相比，本發明的積極效果為本發明利用位圖索引的思想，將圖數據有效地組織起來，並極好地支持了子圖匹配查詢。相較於現有技術，一方面本發明是基於外存的，進而保證了比已有的大部分基於內存的技術有更高的可擴展性；另一方面本發明能獲得極高的效率，快於已有的基於外存的圖資料庫技術。另外，本發明的內容支持對大規模圖數據的動態更新，這是現有的基於外存的圖資料庫技術所不具備的。
圖1為本發明實施例中本方法的整體框架的圖示；圖2為本發明實施例中大規模圖數據預處理的方法的圖示；圖3為本發明實施例中大規模圖數據子圖查詢的方法的圖示；圖4為本發明實施例中大規模圖數據的更新方法的圖示。
具體實施例方式本發明是針對圖數據的特點進行存儲與查詢的方法，整個方法框架參見圖1。方法分為兩大部分，數據預處理部分和查詢執行部分。數據預處理主要是我們針對大規模圖數據的特點設計的對其進行存儲並構建索引的方法，其中，構建的索引包括基於數據直方圖的代價估計模塊、針對圖數據的位圖索引和B+-Tree存儲；查詢執行部分是針對我們所設計的索引與存儲進行子圖查詢的實現方法，查詢執行部分是先利用代價估計模塊對查詢圖進行分解，得到若干子模式，然後利用位圖索引將子模式之間進行連接得到中間結果，之後，我們根據中間結果利用數據預處理部分生成的B+-Tree存儲的圖數據找到子模式的在圖數據上的匹配結果，進而將這些子模式的結果拼接起來，從而得到最終結果。在我們的方法中，我們所利用的B+-Tree技術是業內公知的一種基於外存的技術，它保證了我們的方法能實現利用外存來支持大規模圖數據的存儲和管理，以有別於現有的大部分方法。現有方法多是基於內存的，無法滿足大規模的圖數據。另一方面，在索引中，我們合理地利用了位圖的思想，並在子圖匹配查詢的過程中結合位圖的優勢，從而使得我們能快速地執行子圖查詢。同時各個索引模塊之間界限清晰，索引內部也並不是過於複雜，這使得我們的索引易於更新，進而有別於現有的少數幾個能擴展到外存的方法。現有的方法有幾個能擴展到外存，但鑑於其本身索引結構的複雜，無法支持圖數據的動態更新。參見圖2，實施例中，大規模圖數據預處理的方法包括步驟101 大規模圖數據的規範化。實際中，我們得到的原始數據會是各種各樣的形式，我們首先就需要將這些數據轉化成我們規定的格式，這裡我們會提供一個標準化的圖數據格式。該數據格式中以 "t#NNumberofVertices NumberofEdges，，開始，以 『『t#-l，，結束，其中 N 為這個圖的標識， NumberofVertices為圖中點的數量，NumberofEdges為圖中邊的數量，t為用以表示數據開始。然後，緊跟著的就是圖中的點信息，一個點對應於一行，格式是「V i LabelofVertices, i」，其中i是點的標識符，這裡我們要求i從0開始，以1為單位遞增，LabelofVertices_i 是點上的唯一的標籤信息；之後，便是邊信息，一條邊也對應於一行「e v_i v_j」，其中，v_i 是這條邊的起點信息，v_j為這條邊的終點信息。示例如下t#N NumberofVertices NumberofEdgesν O NumberofVertices_0......ν NumberofVertices-I NumberofVertices_n-le x_0 y_0......e x_NumberofEdges-l y_NumberofEdges-lt#-l該示例為一個標識符為N的圖的示例。它包含有η個點，一個點對應以字母「V」 開始的一行，編號從O到NumberofVertices-1，每一個點對應於唯一的標籤。注意，這裡雖然每個點只對應於一個標籤，但不同的點可以有相同的標籤。然後就是所有邊的信息，共計有NumberofEdges條邊，每條邊對應以字母「e」開始的一行，之後跟著的先是邊的起點的編號，然後是邊的終點的編號。這裡，我們提供圖數據的格式規範，然後根據此規範要求查詢圖。現實中，用戶需要將自己所需處理的圖文件，按照這個格式進行轉化。例如，對於三元組 形式的RDF數據，我們在處理的過程中，就以其中所有的實體作為點，並按照字典序為其打上標識符。然後根據每個實體的本體信息，為每個點打上標籤。之後，我們根據三元組中實體的關係，將這些點連接起來，形成邊。如此，我們就可以形成一個符合我們規範的圖，進而可以利用我們的方法，對圖進行操作。步驟102 大規模圖數據的組織和管理。當圖數據符合我們規範的圖數據之後，我們就需要對其進行組織和管理。這裡我們將會按照圖中每條邊的起點和終點的標籤信息，對圖中所有的邊進行分類。然後，對於每類邊，我們按照字典序為其建立B+-Tree索引。B+-Tree是常見的基於外存的數據結構，它可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度，進而方便我們在進行子圖查詢的時候讀取邊上的信息。這裡，由於每個點都對應於一個標籤，所以每條邊根據其起點和終點的標籤都能對應上唯一的一個標籤對。比如，假設點1的標籤是A，點2的標籤是B，那麼如果存在邊，則對應的標籤對是<A，B〉。根據每條邊上的標籤信息，我們可以將邊進行分類。 例如，接上面的例子，如果對應的標籤對也是，那麼我們將和劃為一類邊。然後，我們就可以將所有的邊分成若干類，並把同類的邊存儲在一起。存儲時， 我們可以按照起點和終點的標識符的大小對邊規定出大小順序，進而按照B+-Tree的方式對同類邊進行組織。在這裡，為了提高效率，我們冗餘地保存邊的信息，即同一類的邊將被分別保存兩次。第一次，這些邊將先按起點標識符的字典序排序，如起點一樣，按終點標識符的字典序排序；第二次，這些邊將先按終點標識符的字典序排序，如終點一樣，按起點標識符的字典序排序。步驟103 大規模圖數據位圖索引構建。為了快速的實現查詢，本方法利用位圖索引的思想在上面數據結構的基礎上為圖數據構建索引。由於利用了位圖索引，子圖查詢中的很多操作均可轉換成位運算，從而將極大地節省I/O操作和空間消耗，進而減少運算的時間。首先，我們按照每個點上的標籤信息，將點劃分為若干域。所有標籤一樣的點在同一個域中。如果給定的域包含η個點，則在這個域對應的位圖索引就會包含η個比特位， 每一個點按標識符順序依次對應於一位。如此，則對於步驟102中所述的每一類邊，都會對應到兩個域的位圖索引——起點的位圖索引和終點位圖索引，這裡記為HeadBitMap和 TailBitMap。假設存在某條邊屬於某類，設ν在所有標籤是L1的點中的第k 名，則在對應的HeadBitMap的第k列取值為1 ；同理，若u在所有標籤是L2的點中的第η名，則在這類邊的TailBitMap的第η列取值為1。如此，我們就可以為步驟102中所述的每一類邊建立位圖索引，進而利用其提升後面的子圖查詢效率。步驟104 大規模圖數據數據立方圖索引的構建。當一個子圖查詢進來之後，我們會先將子圖查詢進行分解，將其分解成若干子模式，然後先對子模式進行處理，最後將子模式拼裝起來。實際中，每個查詢圖都遠不止一種分解方法，所以我們需要設計一個好的策略來確定一個合適的分解。為此，我們利用數據直方圖的思想，為我們進行代價估計提供依據。承接上文所述，我們將圖數據中的邊按上面的標籤信息分成了若干個類，相同類的邊組織在一起，並為之建立了位圖索引。這裡，對任意類的邊，我們為其建立兩個數據直方圖——起點信息數據直方圖和終點信息數據直方圖，在這裡我們將它們分別表示為HeadHistogram和TailHistogram。數據直方圖是資料庫領域常用的一種統計信息表示方式，用以記錄數據的分布。在這裡，我們用直方圖的方式來記錄同類邊的統計信息， 以方便對後面的查詢過程的優化。直方圖構建過程如下假設有Ii1條邊屬於類， 且這Ii1條邊的起點都為v，同時ν在所有標籤是L1的點中的第k名，則在對應的 HeadHistogram的第k列取值為Ii1 ；同理，假設有n2條邊屬於類，且這n2條邊的終點都為u，同時u在所有標籤是L2的點中的第m名，則在對應的TailHistogram的第m列取值為n2。注意，此處叫和 均可為0;參見圖3，實施例中，大規模圖數據子圖查詢的方法的包括步驟201:查詢分解這裡，我們假設每個查詢圖和數據圖有同樣的格式規範，但是每個查詢圖的規模遠小於數據圖的規模。我們的目標是在數據圖中找出所有與查詢圖同構的子圖。以我們目前所了解的情況來看，現有的方法都是基於查詢圖點的依次匹配。具體而言，這些方法首先都會找出針對查詢圖的點的信息來找到其在數據圖上的可能的匹配， 然後將這些可能的候選點按照查詢圖的結構拼起來。如果能拼裝成功，則拼裝結果即為查詢的解；若一個解都沒拼出來，則當前查詢圖在數據圖上無解。方法之間的差異主要體現在針對點信息找可能匹配的過程及可能的匹配之間的拼裝的方法上。但是這裡我們為了高效地利用我們的索引以提高查詢效率，我們首先將查詢圖分解成若干子模式，然後將找出每個子模式的可能的匹配，然後將它們拼裝出解。通過理論上的分析可知，對一個查詢圖而言，找出最優的分解方法是不能在可接受的時間內實現的，所以我們提出了一個近似的分解方法。同時，根據分解出的子模式的不同，最終的效率也會不盡一樣。這裡我們按照分解的最終子模式的不同，分別設計了兩種分解的方法基於鄰接邊的子圖分解和基於星結構的子圖分解。基於鄰接邊的子圖分解是將子圖分解成若干鄰接邊，所謂鄰接邊就是指兩條相鄰的邊組成的邊對；基於星結構的子圖分解是將子圖分解成若干星結構，所謂星結構就是一組有公共端點的邊。理論上可以證明，找出最優的分解是無法在可接受的時間裡完成的，所以本發明中我們借鑑貪心算法的思想進行分解，進而得到局部最優的分解方案。首先，我們利用前文所述的數據直方圖索引找出當前最優的鄰接邊(或者星結構)P，具體而言，我們首先枚舉出所有可能的子模式，然後對於每個子模式，我們讀出這個模式所有的邊所對應的數據直方圖的值，進而求出這些值的乘積，並以這個乘積來作為子模式的代價。注意，這裡由於我們在接下來的拼接操作是類似於關係資料庫的連接操作，而連接操作在業內公知就是用直方圖的乘積來估算代價的，所以這裡我們使用我們數據直方圖的值的乘積來估計子模式代價。當算出所有的子模式代價之後，以代價最小的子結構為當前最優的鄰接邊(或者星結構)P。找出最優子模式後，我們從查詢圖中去掉P，從而得到一個減小的查詢圖，並將P 作為子模式保存起來。之後，在這個減小的查詢圖中我們重複利用數據直方圖索引找當前最優的鄰接邊(或者星結構)並去掉的過程。在這裡，由於每次找到的當前最優子模式都是在減小的查詢圖上得到的，所以每次過程都能保證引入之前沒引入過的邊。因此，此過程迭代若干次之後，一定能將源查詢圖分解完。當整個源查詢圖的所有邊都被去掉時，分解結
束ο如此，我們就可以得到一個覆蓋掉查詢圖中所有邊的子模式集合，這個集合是近似最優的分解結果。步驟202:子模式處理當子模式分解好之後，我們需要對每個子模式進行處理。在這裡，我們根據查詢子模式中每條邊上的信息，找出該子模式對應的邊對應的類，然後把這個類對應的位圖索引讀出來。由於不論是鄰接邊還是星結構，這些子模式中都會含有一個公共端點。所以， 我們可以將所有位圖索引的對應於公共端點的部分拿出來進行一次邏輯「與」運算，以此來確定查詢圖中公共端點可能對應的數據圖上的點。具體而言，如果某個子模式的公共端點中對應於某條邊的起點，那麼我們就將這條邊的起點標籤信息對應的位圖索引——即 HeadBitMap——讀出來；如果某個子模式的公共端點中對應於某條邊的終點，那麼我們就將這條邊的終點標籤信息對應的位圖索引——即TailBitMap——讀出來。之後，我們對這些位圖進行一次大的邏輯「與」運算，如果邏輯「與」運算結果中某一位若為0，則意味著這一位對應的那個點不可能成為進入最終解。這可以極大地剪枝掉不少中間結果。之後，我們按照這個位圖索引與運算的結果中的「1」，從邊信息的B+-Tree存儲中讀出相應的邊信息。這些邊信息讀出來之後，我們就可以按照子模式的結果，組裝出當前子模式在數據圖上的匹配。可以通過理論證明，這樣操作後得到的解是與當前子模式匹配的邊。步驟203:子模式拼接當所有子模式在數據圖上的匹配都找到之後，我們就需要將這些子模式的匹配結果拼接起來。在這裡，我們的操作將類似於關係資料庫的連接操作，也即根據不同子模式之間相同的查詢點將它們的匹配連接起來。兩個不同子模式對應的兩個匹配的邊之間是可拼接的，前提在於如果這兩個匹配的邊對應的子模式包含有相同的查詢點，那麼這兩個匹配的邊在該查詢點對應的位置上有相同的值。根據這個原則，我們依次將每個子模式的匹配邊拼接起來，從而得到最終結果。而由於每一個點都是通過根據邊的標籤信息形成的類找到的，所以這個點上的標籤一定是對的，從而保證了查詢結果中點的正確性；同時，由於每一條邊至少存在與一個子模式中，所以這也就可以保證查詢結果中邊匹配的正確性；最後，由於我們的拼接，保證了查詢結果在符合查詢圖的結果。參見圖4，實施例中，大規模圖數據的更新方法的包括步驟301:邊信息的更新這裡我們規定，當更新邊信息的時候不會改變點信息，不論是新增還是刪除邊都不會增加或者刪除點。這樣規定可以保證各部分之間的獨立性，從而使得增強本方法的魯棒性，即當某個部分被修改，對其他部分會儘量少地產生影響。具體而言，我們規定當如果新增的邊中包含有新的點，我們先調用點信息更新模塊新增點，之後再新增邊；如果刪除某條邊後，哪怕某個點不再和任意邊連接，仍然不刪除這個點。基於上述規定，當刪除一條邊時，我們首先根據這條邊的標籤信息確定其所屬的類，然後改變這個類的相關索引。具體而言，首先我們找到所刪除的邊在B+-Tree中位置，並予以刪除。在這個過程中我們需重新統計邊的分布信息，即重新對具有相同端點的邊進行計數，得到的計數用以更新這類邊的數據直方圖。若從統計信息中我們發現某個點不再含有該類的邊，也即計數為0，則將位圖索引的對應位置變為0。新增邊的過程與上述過程類似，僅僅將在B+-Tree部分的操作由刪除改為新增，同時，如果新增之後發現某個點從沒有該類的邊變成含有該類邊，則將位圖索引的對應位置變為1。B+-Tree的增加、刪除和範圍查詢是在業內有公知的高效，所以這也就保證我們的方法的可行性與效率。而每次新增或刪除一條邊，只需要最多修改位圖索引中的一位，這也保證我們有較低的更新代價。步驟302 點信息的更新這裡我們仍然規定，當更新點信息的時候不會改變邊信息，不論是新增還是刪除點都不能增加或者刪除邊。所以如果我們要刪除某個點時，先調用點信息更新模塊刪除所有相關的邊，之後再刪除點；而新增點的時候，對邊信息影響相對較小。基於上述規定，當更新一個點時，我們首先更新這個點的所有的相關邊，這就需要我們遍歷這個點可能在的所有的邊的類。例如，我們打算更新標籤信息為L的點V，那麼我們需要更改所有與L相關的邊的類的索引信息，哪怕這個類的邊不存在與ν相關的邊。之後，我們就需要更新這些類的B+-Tree上所有的與ν相關的邊信息，然後更新位圖索引及數據直方圖相應位。綜上所述，本發明實例中，針對規模日益增長的圖數據，我們設計了一種基於外存的存儲與索引圖數據的方法，並結合這些方法實現了對大規模圖數據的進行子圖匹配查詢。在這裡，我們利用B+-Tree、位圖索引和數據直方圖等技術，存儲圖數據並為其構建索引。這些技術簡潔有效，不但能極好地支持對大規模圖數據的存儲和管理，還能支持對圖數據的更新。在查詢時，我們有效地利用我們的存儲結構與索引，設計了相應的方法來高效地支持子圖匹配。顯然，本領域的技術人員可以對本發明進行各種改動和變型而不脫離本發明的精神和範圍。這樣，倘若對本發明的這些修改和變型屬於本發明權利要求及其等同技術的範圍之內，則本發明也意圖包含這些改動和變型在內。
權利要求
1.一種基於外存的圖數據存儲方法，其步驟為1)對圖數據格式統一為一種標準圖數據格式；其中，所述標準圖數據格式為以 「t#NNumberofVertices NumberofEdges」開始，然後是圖中的點信息ν，一個點對應於一行，格式為「V i LabelofVerticesj」，然後是圖的邊信息e，一條邊對應於一行，格式為「e v_iv_j」；最後以「t#-l」結束；其中，N為圖的標識，NumberofVertices為圖中點的數量， NumberofEdges為圖中邊的數量，i是點的標識符，LabelofVertices」是點上的唯一的標籤信息，v_i是邊的起點信息，v_j為邊的終點信息；2)根據圖數據中每條邊的起點和終點的標籤信息，對圖中的邊進行分類存儲，然後對每類邊建立B+-Tree索引；3)按照圖數據中每個點上的標籤信息，將圖中的點劃分為若干域，同一域中每一個點按點的標識符順序依次對應於一位；然後根據邊的起點、終點標籤信息，為步驟幻中的每一類邊建立一位圖索引；4)對每一類邊建立一起點信息數據直方圖和一終點信息數據直方圖，記錄同類邊的統計fe息。
2.如權利要求1所述的方法，其特徵在於按照字典序為每類邊建立B+-Tree索引。
3.如權利要求1或2所述的方法，其特徵在於為每一類邊建立以位圖索引的方法為 首先根據邊的起點、終點標籤信息建立每一類邊的起點位圖索引和終點位圖索引，然後對於某條邊屬於某類，ν在所有標籤是L1的點中的第k名，則在對應的起點位圖索引第k列取值為l，u在所有標籤是L2的點中的第η名，則在這類邊的終點位圖索引第η列取值為1。
4.如權利要求3所述的方法，其特徵在於每一類邊的起點數據直方圖和終點數據直方圖的建立方法為設有Ii1條邊屬於類，且這Ii1條邊的起點都為v，同時ν為所有標籤是L1的點中的第k名，則在對應的起點數據直方圖第k列取值為Ii1 ；同理，設有 n2條邊屬於類，且這n2條邊的終點都為u，同時u為所有標籤是L2的點中的第m名， 則在對應的終點數據直方圖第m列取值為n2。
5.如權利要求1所述的方法，其特徵在於當刪除一條邊時，首先找到所刪除的邊在 B+-Tree中位置，然後在圖數據中予以刪除並重新統計邊的分布信息，用以更新這類邊的數據直方圖。
6.如權利要求5所述的方法，其特徵在於當從邊的統計信息中某個點不再含有該類的邊，則將該類邊的位圖索引的對應位置變為O。
7.如權利要求1所述的方法，其特徵在於當新增一條邊時，首先找到所新增的邊在 B+-Tree中位置，然後在圖數據中增加該邊並重新統計邊的分布信息，用以更新這類邊的數據直方圖；如果新增之後發現某個點從沒有該類的邊變成含有該類邊，則將該類別的位圖索引的對應位置變為1。
8.如權利要求1所述的方法，其特徵在於，當更新一個點時，首先遍歷這個點可能在的所有的邊的類，然後更新這個點的所有的相關邊。
9.一種基於權利要求1所述方法存儲圖數據的子圖查詢方法，其步驟為1)根據圖數據的數據直方圖索引搜索源查詢子圖中當前最優的鄰接邊P；2)從源查詢子圖中去掉P，得到一個減小的查詢子圖，並將P作為查詢子圖的子模式保存起來；在剩餘查詢子圖中重複利用數據直方圖索引找當前最優的鄰接邊，然後將其去掉並作為一子模式保存，直到將源查詢子圖分解完，得到一子模式集合；3)根據每一查詢子模式所對應的邊信息，找出該邊對應的類，然後讀取這個類對應的位圖索引；4)將讀取的所有位圖索引的對應部分進行一次邏輯「與」運算，當「與」運算結果為「1」 時，從邊信息的B+-Tree存儲中讀出匹配的邊信息，得到所有子模式在圖數據中匹配的邊；5)對於所有匹配的邊，如果兩個匹配的邊所對應的子模式包含有相同的查詢點，則將這兩個子模式所對應的匹配邊拼接起來，得到與源查詢子圖匹配的查詢結果。
10. 一種基於權利要求1所述方法存儲圖數據的子圖查詢方法，其步驟為1)根據圖數據的數據直方圖索引搜索源查詢子圖中當前最優的星結構P；2)從源查詢子圖中去掉P，得到一個減小的查詢子圖，並將P作為查詢子圖的子模式保存起來；在剩餘查詢子圖中重複利用數據直方圖索引找當前最優的星結構，然後將其去掉並作為一子模式保存，直到將源查詢子圖分解完，得到一子模式集合；3)根據每一查詢子模式所對應的邊信息，找出該邊對應的類，然後讀取這個類對應的位圖索引；4)將讀取的所有位圖索引的對應部分進行一次邏輯「與」運算，當「與」運算結果為「1」 時，從邊信息的B+-Tree存儲中讀出匹配的邊信息，得到所有子模式在圖數據中匹配的邊；5)對於所有匹配的邊，如果兩個匹配的邊所對應的子模式包含有相同的查詢點，則將這兩個子模式所對應的匹配邊拼接起來，得到與源查詢子圖匹配的查詢結果。
全文摘要
本發明公開了一種基於外存的圖數據存儲方法及子圖查詢方法，屬於資料庫技術領域。本方法為1)對圖數據格式統一為一種標準圖數據格式；2)根據圖數據中每條邊的起點和終點的標籤信息，對圖中的邊進行分類存儲並對每類邊建立B+-Tree索引；3)按照圖數據中每個點上的標籤信息，將圖中的點劃分為若干域，同一域中每一點按標識符順序依次對應於一位；然後根據邊的起點、終點標籤信息，為2)中每一類邊建立一位圖索引；4)對每一類邊建立一起點信息數據直方圖和一終點信息數據直方圖。關於子圖查詢，首先對對查詢子圖進行分解，然後將分解出的子模塊進行查詢並將查詢結果進行整合。本發明具有查詢效率高、可擴展性好的特點。
文檔編號G06F17/30GK102254012SQ20111020269
公開日2011年11月23日 申請日期2011年7月19日 優先權日2011年7月19日
發明者彭鵬, 賈愛霞, 趙東巖, 鄒磊 申請人:北京大學