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

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

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

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

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