面向圖數(shù)據(jù)基于區(qū)間標(biāo)記的可達(dá)性查詢研究.pdf

1、隨著Web和相關(guān)領(lǐng)域的深入發(fā)展，新應(yīng)用不斷出現(xiàn)并產(chǎn)生了大量帶有關(guān)聯(lián)關(guān)系的數(shù)據(jù)。為了能高效地表示和管理這種數(shù)據(jù)，研究者們提出用表達(dá)能力豐富的圖數(shù)據(jù)模型來建模。圖作為一種基本的數(shù)據(jù)模型已經(jīng)被廣泛研究了很長時間，但是，直到最近圖數(shù)據(jù)模型才因其適用性而被廣泛應(yīng)用在多種新應(yīng)用中，并且受到了很大關(guān)注。不同的應(yīng)用對應(yīng)不同的圖數(shù)據(jù)模型，需要不同的處理方法，從而導(dǎo)致了圖數(shù)據(jù)管理上的不同算法。圖數(shù)據(jù)的有效管理已經(jīng)成為一個熱門的研究領(lǐng)域。圖數(shù)據(jù)上的可達(dá)性查詢

2、是圖數(shù)據(jù)管理中的一個基本操作，在圖數(shù)據(jù)管理中有著廣泛的應(yīng)用。
　　當(dāng)前，針對圖數(shù)據(jù)上的可達(dá)性查詢已經(jīng)提出了一些索引算法，但是這些索引算法因其局限性而不能靈活地擴(kuò)展到大的圖數(shù)據(jù)。本文首先介紹了已有的處理圖數(shù)據(jù)上可達(dá)性查詢的索引算法，并且分析了這些算法存在的不足。為了克服已有索引算法的缺點(diǎn)，本文提出了一種新的處理靜態(tài)圖上可達(dá)性查詢的索引算法。該索引算法以區(qū)間標(biāo)記為基礎(chǔ)，并且將結(jié)點(diǎn)的標(biāo)記信息表示成四元組，前兩個元素是區(qū)間標(biāo)記，編碼生成樹

3、的可達(dá)性信息，后兩個元素編碼非樹邊的可達(dá)性信息。新的索引算法查詢時只需索引且索引創(chuàng)建代價小。
　　現(xiàn)實(shí)應(yīng)用中的圖數(shù)據(jù)很多都是在不斷變化的。為了有效處理動態(tài)圖上的可達(dá)性查詢，本文將新提出的靜態(tài)圖上的索引算法擴(kuò)展到動態(tài)圖，提出了一種新的處理動態(tài)圖上可達(dá)性查詢的索引算法。
　　最后，通過大量在真實(shí)和人工生成數(shù)據(jù)集上的實(shí)驗(yàn)證明了新提出的靜態(tài)圖上的可達(dá)性查詢索引算法的高效性和可擴(kuò)展性，并且通過實(shí)驗(yàn)證明了新提出的動態(tài)圖上的可達(dá)性查詢索引