圖數據上可達性查詢關鍵技術研究.pdf

1、可達性查詢是圖查詢中一個主要的研究方向，引發(fā)了越來越多人的關注。隨著大數據時代的來臨，數據規(guī)模的不斷擴大，越來越多的復雜結構數據需要用圖的結構表示，因此對于圖的研究就顯得越來越有必要?？蛇_性查詢目的是判斷在有向圖中是否存在一條路徑使得兩點相互連接。關于可達性查詢方面的研究已經進行了二十多年，而且一直是數據庫領域研究的熱點。目前可達性查詢研究已經廣泛應用于各個領域:在社交網絡中，將每個人表示成圖中的頂點，可達性查詢有助于確定兩個人之間的關

2、系;在蛋白質網絡中，頂點可以表示成分子，邊則表示為分子間的反應關系，可達性體現(xiàn)了不同分子之間的反應特性。此外，引文網絡和圖的模式匹配也都能看到可達性查詢的影子。
　　如何提高查詢效率一直是可達性查詢研究的主要問題，很多研究圍繞這點進行展開。隨著研究的不斷深入，已經出現(xiàn)了可達性查詢的變形，如標簽約束可達性查詢等。本文主要針對當前圖數據的特征，研究不同數據可達性定義下的優(yōu)化方法。首先綜合路徑劃分和區(qū)間標記的思想，提出了一種路徑區(qū)間標記

3、的可達性查詢方法?，F(xiàn)有的多重區(qū)間標記方法需要不斷的迭代進行查詢，特別是對于兩點存在真實可達性關系的情況，查詢時間代價約等于深度優(yōu)先遍歷，在很大程度上不夠優(yōu)化。因此本文添加了路徑的相關信息，該方法能夠有效地減少迭代次數，迅速判斷不可達關系，縮短查詢時間。基于不同路徑之間的關系，本文給出了一種ESQ查詢策略。不同的路徑之間可以通過等價的邊相互連接，記錄不同路徑之間的等價邊信息，相比傳遞閉包減少了空間的消耗，獲得了更好的時間效率。其次，基于約

4、束可達性研究的內容，提出了一種有向圖權重約束可達性的概念。目前的研究只有無向圖上權重約束查詢，在此基礎上解決了加權有向圖可達性查詢的問題。對于有向圖附加的權值信息，本文從傳遞閉包的角度出發(fā)為有向圖建立索引，給出了一種優(yōu)化的傳遞閉包算法。最后，借鑒無環(huán)圖的思想，將加權有向圖轉化為等價的加權無環(huán)圖。按照反拓撲序列進行傳遞閉包的計算，有效的減少了頂點對重復邊的搜索，能夠在更短的時間內完成傳遞閉包的建立。
　　本文對研究內容中所提出的理論