圖數(shù)據(jù)庫(kù)上的查詢問(wèn)題.pdf

1、隨著數(shù)據(jù)庫(kù)技術(shù)的廣泛應(yīng)用，數(shù)據(jù)管理的對(duì)象從非結(jié)構(gòu)化數(shù)據(jù)向結(jié)構(gòu)化數(shù)據(jù)延伸。依賴于圖數(shù)據(jù)結(jié)構(gòu)強(qiáng)大的表述能力，一些新興數(shù)據(jù)庫(kù)如XML文檔數(shù)據(jù)庫(kù)、社會(huì)關(guān)系網(wǎng)、化合物分子數(shù)據(jù)庫(kù)以及蛋白質(zhì)基因結(jié)構(gòu)匹配數(shù)據(jù)庫(kù)等都采用圖數(shù)據(jù)結(jié)構(gòu)建模。 另一方面，作為信息獲取的重要工具，查詢操作是數(shù)據(jù)庫(kù)領(lǐng)域經(jīng)久不衰的研究課題之一?；趫D數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)庫(kù)，不僅引入了新的數(shù)據(jù)模型，同時(shí)由于圖結(jié)構(gòu)自身的復(fù)雜性，給查詢問(wèn)題帶來(lái)了新的挑戰(zhàn)。 圖數(shù)據(jù)庫(kù)上的查詢問(wèn)題指

2、的是查找并驗(yàn)證查詢圖在圖數(shù)據(jù)庫(kù)上的所有出現(xiàn)?；卮鹪摬樵儐?wèn)題通?？梢苑譃閮蓚€(gè)階段，即查詢過(guò)濾階段與查詢驗(yàn)證階段。不同于相關(guān)工作聚焦于查詢過(guò)濾階段，本文把更多的注意力放在查詢驗(yàn)證階段，通過(guò)對(duì)數(shù)據(jù)庫(kù)的索引以及關(guān)鍵信息統(tǒng)計(jì)，加速該階段的性能。本文的研究成果主要有： (1)提出了查詢驗(yàn)證時(shí)間開銷的度量模型。本文從基本的子圖匹配算法入手，繼而研究了其搜索空間，并給出了形式化的度量模型。在該度量模型的指導(dǎo)下，發(fā)現(xiàn)查詢驗(yàn)證階段的性能瓶頸。同時(shí)，

3、該度量模型也給本文提出的查詢驗(yàn)證階段的加速技術(shù)提供了理論依據(jù)。 (2)發(fā)現(xiàn)了調(diào)整查詢圖的邊序可以加速查詢驗(yàn)證過(guò)程。提出了邊序重排的啟發(fā)式算法框架，并分別給出了基于概率模型以及基于木桶模型的啟發(fā)式算法eSI_prob以及eSI_barrel。實(shí)驗(yàn)表明，兩個(gè)算法都能夠有效的提高查詢驗(yàn)證階段的性能。與此同時(shí)，eSI_prob和eSI_barrel使用的統(tǒng)計(jì)信息，與圖數(shù)據(jù)庫(kù)本身比較，只占用了很小的存儲(chǔ)空間。 (3)發(fā)現(xiàn)了索引子圖

4、片段在數(shù)據(jù)庫(kù)中的出現(xiàn)可以加速查詢驗(yàn)證過(guò)程。提出了索引高度自同構(gòu)的頻繁子圖或索引分布距離較遠(yuǎn)的頻繁子圖兩種索引項(xiàng)選擇方案，并使用有向無(wú)環(huán)圖組織索引項(xiàng)的索引，形成了基于片段索引的子圖查詢方案pSI_auto以及pSI_cluster。實(shí)驗(yàn)表明，兩個(gè)算法均可以進(jìn)一步的提高子圖驗(yàn)證的性能。當(dāng)圖數(shù)據(jù)庫(kù)中的自同構(gòu)結(jié)構(gòu)頻繁出現(xiàn)時(shí)，pSI_auto效果更為顯著。同時(shí)，本文討論了當(dāng)數(shù)據(jù)庫(kù)執(zhí)行插入、刪除與修改時(shí)，索引的更新操作，并提出了索引自動(dòng)重建策略。