圖數(shù)據(jù)上可達(dá)性查詢關(guān)鍵技術(shù)研究.pdf

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

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

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

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