基于關(guān)系數(shù)據(jù)庫的關(guān)鍵詞搜索系統(tǒng)的研究.pdf

1、隨著Web服務(wù)的發(fā)展和網(wǎng)絡(luò)上的數(shù)據(jù)量呈幾何式的增長,人們認(rèn)識到將關(guān)系數(shù)據(jù)庫和信息檢索的技術(shù)融合到一起可以給用戶提供更高效的信息檢索服務(wù)。
　　 論文討論了在關(guān)系數(shù)據(jù)庫上進(jìn)行基于q個關(guān)鍵詞(k1,k2,k3,…,kq)的搜索方法。這里的關(guān)系數(shù)據(jù)庫可以被建模為帶權(quán)圖模型G(V,E)。其中的V是指圖上的結(jié)點(diǎn)(即數(shù)據(jù)庫中的元組)；E是指數(shù)據(jù)圖上的邊,它表示的是元組間的外主鍵關(guān)聯(lián)。假設(shè)Si表示一組包含關(guān)鍵詞ki的結(jié)點(diǎn),并且Si∈V。我們研

2、究的問題是怎樣找到權(quán)重最小的k個結(jié)果樹,并且結(jié)果樹要包含每個集合Si中的至少一個結(jié)點(diǎn)。當(dāng)k等于1時,該問題等價于最小斯坦納樹問題(Steiner Tree Problem),該問題是NP難的。
　　 該問題還有兩個前提,即關(guān)鍵詞的個數(shù)q很小,因為用戶一般不會輸入過多的關(guān)鍵詞；而且圖中的邊的數(shù)目m和結(jié)點(diǎn)數(shù)的關(guān)系,通常滿足不等式m<　　 基于上述特性,本文最主要的工作是提出了一個在數(shù)據(jù)圖上進(jìn)行關(guān)鍵