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

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

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

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

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