1、作為一種通用的數(shù)據(jù)結構，圖可以用來表示數(shù)據(jù)對象之間的復雜聯(lián)系。例如：圖可以表示化合物的分子結構，蛋白質交互網(wǎng)絡，社會網(wǎng)絡等。隨著科學與工程領域中圖數(shù)據(jù)的大量出現(xiàn)和累積，圖數(shù)據(jù)管理已成為數(shù)據(jù)管理領域一個重要和熱點研究的子領域。圖數(shù)據(jù)庫查詢處理是其中最重要的研究分支之一，其對圖相關的絕大部分處理和應用（例如：圖挖掘、化學數(shù)據(jù)庫PubChem）起著基礎支撐作用。本文主要對圖數(shù)據(jù)庫中的查詢處理技術進行深入研究，歸納總結了現(xiàn)有研究成果的主要思想和

2、優(yōu)缺點，提出了一些新的圖數(shù)據(jù)庫查詢處理方法，主要研究成果如下：
　　1.提出一種圖數(shù)據(jù)庫中高效處理超圖包含查詢的新方法。新方法綜合的從圖數(shù)據(jù)庫的壓縮組織、構造有效的特征索引以及基于壓縮組織來處理查詢三個方面著手考慮問題。(1)在圖數(shù)據(jù)庫的壓縮組織方面，提出圖數(shù)據(jù)庫的有效組織方法，以提高整體查詢處理效率?，F(xiàn)有的采用過濾-驗證機制的方法將圖數(shù)據(jù)庫中的圖逐個的獨立存放。提出方法將圖數(shù)據(jù)庫中圖結構化的壓縮組織起來。通過壓縮組織方法，產生一

3、個邏輯數(shù)據(jù)結構GPTree，其中記錄了數(shù)據(jù)庫中圖的公共子圖的信息。為了優(yōu)化的構造GPTree，形式化定義了最優(yōu)誘導子圖選擇問題；證明了其是一個NP難問題，并提出了一個近似比為2的近似算法。(2)在構造有效的特征索引方面，提出高效而不依賴于歷史查詢的子圖索引特征生成方法，以及兩種索引結構CRGraph和FGPForest。首先基于分析，給出索引特征的顯著性度量。提出了找出所有顯著性不小于用戶需求的索引特征的方法，即精確索引特征生成方法。為

4、了適應需要更加快速的生成索引的應用場景，提出了特征索引構造的一個近似方法。這兩種方法都是基于圖模式挖掘的方法。為了高效使用索引特征，對索引特征進行排序；并且基于理論分析給出了求解其最優(yōu)排序的算法。(3)在基于壓縮組織來處理查詢方面，提出從多個圖到一個圖的子圖同構檢測的新方法，稱為GPTreeTest?，F(xiàn)有方法逐個的考察每個圖對進行檢測，新方法能夠利用壓縮組織中公共子圖的信息，顯著減少對多個圖的子圖同構檢測的總時間。最后，在真實數(shù)據(jù)集和合

5、成數(shù)據(jù)集上的實驗結果表明，提出方法比目前最好方法高效1至2個數(shù)據(jù)量級。
　　2.提出不確定圖數(shù)據(jù)庫上概率top-k子圖匹配查詢的新問題、以及一種查詢處理方法。首先給出不確定圖數(shù)據(jù)模型，結合現(xiàn)實需求提出概率top-k子圖匹配查詢問題。一個頂點的鄰居子圖是由其距離不大于給定閾值內的所有頂點和邊構成的子圖。基于圖結構空間相關性的特點，以附帶概率信息的鄰居子圖為基礎，設計一種有效的索引結構NG-Index。NG-Index索引可以很容易實

6、現(xiàn)于成熟的關系數(shù)據(jù)庫中，具有強健壯性。提出一種高效的基于搜索樹的算法來進行查詢處理。其中運用了一種概率剪枝技術來提高性能。最后通過實驗考察并證實提出方法具有良好的效率和可擴展性。
　　3.提出結合概念分層的圖統(tǒng)計信息定義以及查詢處理方法。具體地說，給出了結合頂點關聯(lián)的概念分層，根據(jù)用戶指定的搜索興趣來高效地計算數(shù)據(jù)圖中統(tǒng)計信息的方法。首先提出一種結合概念分層的圖統(tǒng)計分布表示。本文將用戶搜索興趣建模為概念圖，并以用戶概念圖的子圖匹配

7、計數(shù)為基礎來表示圖統(tǒng)計信息。其次，為了高效計算此統(tǒng)計分布信息，設計了一種基于子圖密度的索引結構并提出兩階段的計算方法:(1)先基于索引快速地去除數(shù)據(jù)圖中的不相關邊并將數(shù)據(jù)圖打散劃分為若干小尺寸的連通圖；(2)再對這些連通小圖分別計算統(tǒng)計信息，最后合并得出結果。在連通小圖上計算統(tǒng)計信息的核心是概念圖的子圖匹配計數(shù)問題。文中針對這個子問題著重提出兩種高效算法:前向計算算法和后向計算算法。這種在精確計算之前將數(shù)據(jù)大圖快速打散為多個小圖的分治思

8、想是總體效率提升的關鍵所在。最后，在真實數(shù)據(jù)集上的實驗結果表明所提出方法具有良好的效率和可擴展性。
　　4.提出了一種較大尺寸的標簽圖子圖同構檢測方法及其應用方法。所提出的檢測方法是一種基于搜索的方法。本文從標簽圖的特性出發(fā)，以標簽信息和圖拓撲結構相結合的方式來縮減搜索空間。首先，將標簽按照出現(xiàn)的頻率比轉換為數(shù)值。然后，將標簽信息與結構相結合，來構造多組細粒度的頂點不變量。頂點不變量是關于頂點的固有屬性，其在同構映射下保持不變。借

9、助于所構造的細粒度的頂點不變量，將標簽信息沿圖拓撲結構傳播開來，并縮減匹配頂點候選集來減小搜索空間。再次，基于頂點不變量生成了細粒度的剪枝條件。由于結合標簽信息和拓撲結構，這些條件具有更強的剪枝能力。另外，將提出檢測方法中的技術細節(jié)應用到第2章提出的GPTree結構上，來顯示其可用來優(yōu)化已有方法的適用性。最后實驗結果表明，提出方法具有良好的高效性，同時應用新技術的GPTreeTest*算法效率優(yōu)于原始方法GPTreeTest。