基于區(qū)間標(biāo)記索引的可達(dá)性查詢設(shè)計(jì)及其在外包數(shù)據(jù)庫中的應(yīng)用.pdf

1、圖是數(shù)據(jù)結(jié)構(gòu)中重要的組成部分。在圖模型中，點(diǎn)代表事物，邊代表事物之間的關(guān)系。圖模型有著非常廣泛的應(yīng)用背景，如生物網(wǎng)絡(luò)、web網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)等。近幾年來，隨著互聯(lián)網(wǎng)的發(fā)展，各種網(wǎng)絡(luò)內(nèi)容成指數(shù)級(jí)增長，對(duì)其進(jìn)行快速有效地分析與查詢是研究重點(diǎn)。其中許多問題都可以用圖模型來解決，這使得圖數(shù)據(jù)分析成為一個(gè)研究熱點(diǎn)。在圖數(shù)據(jù)分析中，可達(dá)性查詢是一項(xiàng)基本的查詢。而在眾多的可達(dá)性查詢方法中，區(qū)間標(biāo)記索引近來備受關(guān)注。然而，當(dāng)圖發(fā)生更新時(shí)，傳統(tǒng)的區(qū)間標(biāo)記

2、索引算法并不能迅速地更新索引。
　　本文研究了基于區(qū)間標(biāo)記索引的可達(dá)性查詢，利用預(yù)留空間的思想提出了一種可以動(dòng)態(tài)更新區(qū)間索引的方法，又結(jié)合了二進(jìn)制索引樹以使可達(dá)性查詢代價(jià)降低。該方法能針對(duì)不同的圖更新情形進(jìn)行處理。實(shí)驗(yàn)部分驗(yàn)證了本文提出的動(dòng)態(tài)更新算法能有效支持區(qū)間索引的更新。
　　另外，目前企業(yè)的存儲(chǔ)數(shù)據(jù)量迅速增長，一些中小型企業(yè)處理并非核心業(yè)務(wù)的數(shù)據(jù)代價(jià)太高，這時(shí)將數(shù)據(jù)庫外包也成為企業(yè)的合理選擇。隨著圖數(shù)據(jù)的發(fā)展與應(yīng)用，圖

3、數(shù)據(jù)的外包查詢驗(yàn)證成為一個(gè)研究熱點(diǎn)。然而針對(duì)圖數(shù)據(jù)的外包文獻(xiàn)相對(duì)較少，主要集中在子圖相似性查詢等領(lǐng)域。截止到本文完稿，可達(dá)性查詢尚無已發(fā)表的查詢驗(yàn)證機(jī)制。
　　本文針對(duì)區(qū)間索引方式的可達(dá)性查詢設(shè)計(jì)了驗(yàn)證信息及查詢驗(yàn)證方案，使得用戶能夠在外包數(shù)據(jù)庫的背景下驗(yàn)證數(shù)據(jù)的正確性及完整性。本文結(jié)合了MB-tree等驗(yàn)證索引方式，簡化了驗(yàn)證對(duì)象的大小，降低了驗(yàn)證數(shù)據(jù)量。本文的驗(yàn)證索引數(shù)據(jù)結(jié)構(gòu)能夠合理的應(yīng)用于外包數(shù)據(jù)庫中。實(shí)驗(yàn)評(píng)估部分顯示該方案