基于關(guān)鍵字的數(shù)據(jù)庫搜索研究綜述
2008-12-31 00:00:00朱凡微吳明暉金蒼宏呂嘉應(yīng)晶
計算機應(yīng)用研究 2008年11期
（浙江大學(xué) 計算機學(xué)院， 杭州 310027）
摘要：介紹了基于關(guān)鍵字的關(guān)系數(shù)據(jù)庫搜索技術(shù)的研究成果，從數(shù)據(jù)建模、體系結(jié)構(gòu)、關(guān)鍵算法等幾個方面詳細(xì)分析和比較了各種技術(shù)的特點和優(yōu)劣，并指出了現(xiàn)有技術(shù)中存在的一些問題，提出數(shù)據(jù)庫關(guān)鍵字搜索技術(shù)未來的研究方向。
關(guān)鍵詞：基于關(guān)鍵字的搜索； 數(shù)據(jù)庫模式； 相關(guān)性排序； top-k查詢
中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A
文章編號：1001-3695(2008)11-3238-05
Survey of keyword-based search over databases
ZHU Fan-wei， WU Ming-hui， JIN Cang-hong， LV Jia， YING Jing
(College of Computer Science Technology， Zhejiang University， Hangzhou 310027， China)
Abstract:This paper introduced the related research of keyword-based search technologies over relational databases， analyzed and compared the models， architectures， and algorithms of the existing systems. Also， mentioned deficiencies and problems and prospected the future work.
Key words：keyword-based search; database schema; relevance ranking; top-k query
基于關(guān)鍵字的搜索引擎是人們在互聯(lián)網(wǎng)上搜索信息的重要方式。然而，現(xiàn)有的互聯(lián)網(wǎng)搜索引擎主要針對靜態(tài)網(wǎng)頁進(jìn)行索引。在網(wǎng)絡(luò)應(yīng)用中，大量數(shù)據(jù)保存在后臺數(shù)據(jù)庫中，以動態(tài)網(wǎng)頁的形式提供給用戶，不能被現(xiàn)有的搜索引擎索引；同時，存儲在數(shù)據(jù)庫尤其是關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)，由于需要特定的查詢接口也不能被搜索引擎直接訪問[1]。互聯(lián)網(wǎng)上大量的關(guān)系數(shù)據(jù)庫構(gòu)成了Deep Web的主要組成部分，也是現(xiàn)有互聯(lián)網(wǎng)搜索技術(shù)所面臨的一大難題。基于關(guān)鍵字的數(shù)據(jù)庫搜索技術(shù)正是在這樣的背景下成為數(shù)據(jù)庫、信息檢索、互聯(lián)網(wǎng)等領(lǐng)域的學(xué)者共同關(guān)注的研究熱點。
本文詳細(xì)介紹了基于關(guān)鍵字的關(guān)系數(shù)據(jù)庫搜索的研究現(xiàn)狀，比較數(shù)據(jù)庫搜索中經(jīng)典的數(shù)據(jù)模型和搜索模型，概括出各種模型的優(yōu)缺點，并介紹了改進(jìn)的模型。基于應(yīng)用系統(tǒng)實例，總結(jié)出數(shù)據(jù)庫搜索系統(tǒng)的兩種體系結(jié)構(gòu)及各自特點，著重對數(shù)據(jù)庫搜索中的關(guān)鍵算法進(jìn)行了分析評價，并提出了改進(jìn)意見。
1研究現(xiàn)狀
由于關(guān)系數(shù)據(jù)庫是使用最為廣泛的數(shù)據(jù)庫，也是Deep Web的主要構(gòu)成部分，基于關(guān)鍵字的關(guān)系數(shù)據(jù)庫搜索主要也是針對關(guān)系數(shù)據(jù)庫進(jìn)行的。縱觀近十年來該領(lǐng)域的研究成果，可以分為三個階段：
a)第一階段是對基礎(chǔ)理論和算法的研究，包括對關(guān)系數(shù)據(jù)庫的建模、系統(tǒng)實現(xiàn)的體系結(jié)構(gòu)和搜索排序算法的研究。
1998年，R.Goldman等人[2]首先將信息檢索中的鄰域搜索方法引入數(shù)據(jù)庫中，在學(xué)術(shù)界掀起了數(shù)據(jù)庫搜索引擎的研究熱潮。2002年，S.Agrawal等人[3]針對關(guān)系數(shù)據(jù)庫實現(xiàn)了一個基于關(guān)鍵字的搜索引擎DBXplorer。Aditya等人提出將搜索結(jié)果進(jìn)行排序的思想，并實現(xiàn)了支持相關(guān)性排序和結(jié)果展現(xiàn)的BANKS系統(tǒng)[4]。V.Hristidis等人[5]在文獻(xiàn)[3，4]的基礎(chǔ)上對體系結(jié)構(gòu)和算法優(yōu)化作了進(jìn)一步的研究，提出了DISCOVER系統(tǒng)。2003年V.Hristidis等人[6]又將IR領(lǐng)域已經(jīng)很成熟的排序策略運用于數(shù)據(jù)庫搜索中，提出IR-Style排序策略。2004年A.Balmin等人[7]在Google的PageRank算法啟發(fā)下，提出了一種基于權(quán)威(authority-based)的相關(guān)性排序算法ObjectRank。
b)第二個階段是對搜索準(zhǔn)確性的探討和提高，研究主要涉及排序算法、搜索性能、搜索結(jié)果顯示的優(yōu)化等。
2005年文繼軍等人[8]對數(shù)據(jù)庫搜索語言進(jìn)行了擴(kuò)展，基于三類關(guān)鍵字，即Keyword、Keyword: Keyword、Keyword: 〈op〉 Value實現(xiàn)的SEEKER系統(tǒng)不僅可以支持屬性值的搜索，而且還可以對元數(shù)據(jù)進(jìn)行搜索；并對相關(guān)性評分機制作了改進(jìn)，將top-k結(jié)果返回給用戶。2006年Liu Fang等人[9]通過對影響搜索有效性的關(guān)鍵因子的識別和規(guī)范化定義，提出一種有效的新的排序策略，并通過大量實驗證明了搜索的有效性。Ding Bolin等人[10]針對尋找最小代價的Steiner tree問題提出了新的參數(shù)化解決方案，將動態(tài)規(guī)劃法與Best-First策略相結(jié)合，有效地降低了原有搜索算法的時間/空間復(fù)雜度。Peng Zhao-hui等人[11]針對搜索結(jié)果的顯示問題，提出了一種新的聚類方法——TreeCluster。該方法包含模式聚類和關(guān)鍵字聚類兩個步驟，將同一主題的搜索結(jié)果歸入同一個cluster中，為用戶提供了一種根據(jù)cluster的描述方便地選擇感興趣結(jié)果的方式。2007年，He Hao等人[12]提出一種新的雙層索引機制Bi-level索引，很好地減小了逆向搜索的時間代價。Luo Yi等人[13]在IR-Style排序的基礎(chǔ)上，基于虛擬文檔的模型，提出了一種新的相關(guān)性排序方法，大大地簡化了IR-Style排序中相關(guān)性評分的計算，同時提出了Skyline Sweeping算法和Block Pipeline算法，減少了查詢執(zhí)行期間對數(shù)據(jù)庫的訪問。
c)第三階段是對傳統(tǒng)搜索系統(tǒng)的擴(kuò)展，包括語義搜索的研究、分布式數(shù)據(jù)庫搜索等。Zhang Jun等人[14]提出了基于本體的語義搜索，利用領(lǐng)域本體的層次結(jié)構(gòu)來實現(xiàn)關(guān)鍵字的概念比較。與之前系統(tǒng)采用的簡單關(guān)鍵字匹配相比，這種方法很好地提高了查詢的召回率（recall rate）和正確率（precision rate）。 Yu Bei等人[15]將面向單數(shù)據(jù)源的關(guān)鍵字搜索擴(kuò)展為多數(shù)據(jù)源的搜索，解決了相關(guān)數(shù)據(jù)源的選擇問題，將傳統(tǒng)的基于關(guān)鍵字的數(shù)據(jù)庫搜索擴(kuò)展為支持分布式數(shù)據(jù)庫的搜索。類似地，M.Sayyadian等人[16]也針對實際應(yīng)用中存在的自治和異構(gòu)的關(guān)系數(shù)據(jù)庫，提出了將數(shù)據(jù)庫模式匹配與結(jié)構(gòu)發(fā)現(xiàn)技術(shù)結(jié)合的方法來發(fā)掘異構(gòu)數(shù)據(jù)庫中主外鍵關(guān)系，以實現(xiàn)對異構(gòu)數(shù)據(jù)庫高效快速的關(guān)鍵字查詢。
2關(guān)系數(shù)據(jù)庫搜索模型
21數(shù)據(jù)模型
對數(shù)據(jù)庫建模是數(shù)據(jù)庫搜索的第一步，數(shù)據(jù)模型的優(yōu)劣不僅決定了搜索的準(zhǔn)確性和完備性，同時也影響到搜索的效率。考慮到關(guān)系數(shù)據(jù)庫中的關(guān)系通過主外鍵關(guān)系來連接這一特點，現(xiàn)有的搜索方法大都采用了有向圖的方式來對數(shù)據(jù)庫建模，主要可以分為模式圖方法和數(shù)據(jù)圖方法兩類。
211模式圖方法
模式圖(schema graph)方法將數(shù)據(jù)庫中的每個關(guān)系表示為一個節(jié)點，關(guān)系之間的主外鍵聯(lián)系表示為節(jié)點之間的有向邊，由主鍵所在節(jié)點指向外鍵所在節(jié)點。圖1是DBLP[17]數(shù)據(jù)庫的模式圖。進(jìn)行關(guān)鍵字搜索時，根據(jù)模式圖和關(guān)鍵字集合生成候選網(wǎng)絡(luò)(candidate network)，通過執(zhí)行候選網(wǎng)絡(luò)對應(yīng)的SQL語句來產(chǎn)生結(jié)果。采用這種方法的關(guān)鍵字搜索系統(tǒng)有DBXplorer[3]、Discover[6]、IR-Style[6]等。
212數(shù)據(jù)圖方法
數(shù)據(jù)圖(data graph)方法則是將數(shù)據(jù)庫中的每個元組作為一個節(jié)點，元組直接的主外鍵關(guān)系表示為聯(lián)系節(jié)點的有向邊與模式圖方法相同，也是由主鍵所在節(jié)點指向外鍵所在節(jié)點。DBLP數(shù)據(jù)庫的數(shù)據(jù)圖[17]如圖2所示。進(jìn)行關(guān)鍵字搜索時，首先根據(jù)DBMS提供的索引機制選擇出包含關(guān)鍵字的節(jié)點集，然后在數(shù)據(jù)庫上搜索包含該集合的子圖作為搜索結(jié)果。BANKS系統(tǒng)[4]首先采用這種方法實現(xiàn)了數(shù)據(jù)庫關(guān)鍵字搜索 。
213建模方法比較和改進(jìn)
模式圖方法只需在關(guān)系層面對數(shù)據(jù)庫建模，存儲的是數(shù)據(jù)庫的結(jié)構(gòu)信息，抽象程度高，在內(nèi)存中存儲的空間較小，但是在生成候選網(wǎng)絡(luò)上耗費的代價較大；而數(shù)據(jù)圖方法建模的粒度具體到每一個節(jié)點，存儲了數(shù)據(jù)庫中詳細(xì)的數(shù)據(jù)信息，占用較大的內(nèi)存空間，但是在搜索上具有較高的效率。這兩種方法的有向圖簡單地通過有向邊的指向體現(xiàn)了數(shù)據(jù)表或?qū)嶓w間的主外鍵聯(lián)系，不能很好地支持相關(guān)性排序。因此對建模方法的改進(jìn)主要有兩方面[4]：a)將模式圖和數(shù)據(jù)圖的方法相結(jié)合，在內(nèi)存中保存簡潔的模式圖，而將詳細(xì)的數(shù)據(jù)圖存放于硬盤上；b)為有向圖的邊賦予表示相連對象的相關(guān)性權(quán)重值，以支持相關(guān)性排序。
針對傳統(tǒng)建模方式的不足，ObjectRank[7]系統(tǒng)采用權(quán)威傳遞圖（authority transfer graph）對數(shù)據(jù)庫建模，依據(jù)主外鍵聯(lián)系在語義上緊密程度的不同，對每條邊賦予一個相應(yīng)的權(quán)威值，表示該聯(lián)系的權(quán)威性，不僅很好地表達(dá)了數(shù)據(jù)庫元組的語義信息，而且可以從語義相關(guān)的角度支持搜索結(jié)果的相關(guān)性排序，是數(shù)據(jù)模型研究上的一大突破。權(quán)威傳遞圖包括權(quán)威傳遞模式圖(authority transfer schema graph)和權(quán)威傳遞數(shù)據(jù)圖(authority transfer data graph)。這兩種有向圖與原有的模式圖和數(shù)據(jù)圖的區(qū)別是，通過主外鍵相關(guān)的節(jié)點由正反向兩條帶權(quán)威值的邊相連，權(quán)威傳遞圖中的邊不僅表示了對象之間的關(guān)聯(lián)，而且反映了權(quán)威值在圖中的流動狀況。在ObjectRank系統(tǒng)中，對每一條邊都創(chuàng)建了一條相應(yīng)的反向邊(backforward edge)，并賦予權(quán)威值。這是因為在實際數(shù)據(jù)庫中，權(quán)威值的傳遞不僅可以從主鍵節(jié)點傳給外鍵節(jié)點，也可以從外鍵節(jié)點傳給主鍵節(jié)點，而且正反方向傳遞的值可能不同。例如在DBLP數(shù)據(jù)庫中，一篇文章的權(quán)重可以傳遞給他的作者；同樣，一個作者的權(quán)重也可以傳遞給他的文章。圖3是ObjectRank中對DBLP數(shù)據(jù)庫建立的權(quán)威傳遞圖。
22搜索過程的形式化表示
為了描述數(shù)據(jù)庫搜索的過程和算法，綜合現(xiàn)有系統(tǒng)的建模方式[3~7，9，10，13~15，18]，對數(shù)據(jù)庫搜索過程中涉及到的關(guān)鍵元素定義如下：
定義1數(shù)據(jù)庫模式。其形式化地表示為一個模式有向圖SG(RS，ES)。其中：RS={R1，R2，…，Rn}，Ri是圖中的一個節(jié)點，表示數(shù)據(jù)庫中的一個關(guān)系；如果對于任意兩個節(jié)點Ri，Rj，存在Ri到Rj的主外鍵聯(lián)系，則定義一條邊〈i，j〉∈ES。
定義2數(shù)據(jù)庫數(shù)據(jù)。其形式化表示為一個數(shù)據(jù)有向圖DG(ND，ED)。其中：ND={N1，N2，…，Nn}，Ni是圖中的一個節(jié)點，表示數(shù)據(jù)庫中的一個元組；如果對于任意兩個元組Ni，Nj，存在Ni到Nj的主外鍵聯(lián)系，則定義一條邊〈i，j〉∈ED。
定義3搜索條件。其表示為一系列關(guān)鍵字的集合Q={kw1，kw2，…，kwm}。
定義4中間結(jié)果。其表示為以包含關(guān)鍵字的節(jié)點以及一些輔助節(jié)點連接而成的元組樹(tuple tree)，一棵代表一個可能的搜索結(jié)果的元組樹應(yīng)滿足三個條件：a)每個葉子節(jié)點至少包含一個關(guān)鍵字；b)每個元組在元組樹中最多出現(xiàn)一次；c)輔助節(jié)點的個數(shù)不能超過關(guān)鍵字的個數(shù)。其中，條件a)是完備性要求，保證該元組樹滿足搜索條件；條件b)c)保證不存在冗余，得到的元組樹是最小的。
例如，圖4表示的是一個數(shù)據(jù)庫的模式圖Q={k1，k2，k3}，黑色的節(jié)點表示包含關(guān)鍵字的節(jié)點，則表示可能結(jié)果的元組樹有四棵，如圖5所示[3]。
定義5查詢結(jié)果。其采用SQL語句查詢中間結(jié)果得到的最后結(jié)果，表示為元組的自然連接。
23數(shù)據(jù)庫搜索模型的分類
根據(jù)搜索匹配的類型，可以分為關(guān)鍵字匹配和語義匹配兩類。第一階段（見第1章）的搜索技術(shù)多為精確的關(guān)鍵字匹配，即包含搜索關(guān)鍵字的元組滿足搜索條件，而不包含關(guān)鍵字的元組則不滿足搜索條件。支持語義匹配的搜索模型則是從語義理解的角度對關(guān)鍵字匹配的搜索模型作了改進(jìn)，它不但考慮了搜索條件字面上的匹配，同時更注重搜索條件在概念上的比較。ObjectRank[7]在排序算法中引入權(quán)威值，在一定程度上體現(xiàn)了語義匹配的思想，而在第二階段出現(xiàn)的基于本體的語義搜索則是利用領(lǐng)域本體的層次結(jié)構(gòu)關(guān)系，根據(jù)查詢關(guān)鍵字的語義進(jìn)行概念上的匹配，并采用向量空間模型來計算語義相似度。文獻(xiàn)[14]就是典型的語義匹配搜索系統(tǒng)，很好地提高了搜索的召回率。
根據(jù)搜索模型支持的結(jié)構(gòu)，現(xiàn)有的數(shù)據(jù)庫搜索技術(shù)可以分為兩類：一類僅支持AND結(jié)構(gòu)搜索，即返回的結(jié)果應(yīng)當(dāng)滿足所有的查詢關(guān)鍵字，早期的數(shù)據(jù)庫搜索技術(shù)如文獻(xiàn)[2~5]都是僅支持AND結(jié)構(gòu)的；另一類是既支持AND又支持OR結(jié)構(gòu)的搜索，即搜索系統(tǒng)允許返回只滿足部分關(guān)鍵字的結(jié)果，只是這些結(jié)果的相關(guān)性評分相對滿足全部關(guān)鍵字的結(jié)果而言較低，2003年之后大多數(shù)數(shù)據(jù)庫搜索系統(tǒng)都是既支持AND結(jié)構(gòu)又支持OR的，典型的如文獻(xiàn)[6~10，13~15，19，20]等。
根據(jù)搜索的數(shù)據(jù)源不同，可以分為單數(shù)據(jù)源搜索和多數(shù)據(jù)源搜索。傳統(tǒng)的數(shù)據(jù)庫搜索都是針對單數(shù)據(jù)源，即在單個數(shù)據(jù)庫中進(jìn)行搜索。隨著分布式數(shù)據(jù)庫應(yīng)用以及Internet中面向服務(wù)的體系結(jié)構(gòu)的發(fā)展，支持多數(shù)據(jù)源搜索的技術(shù)也應(yīng)運而生。文獻(xiàn)[15，16]詳細(xì)介紹了在多數(shù)據(jù)源搜索中選擇相關(guān)數(shù)據(jù)源以及對數(shù)據(jù)源排序的算法。
3體系結(jié)構(gòu)
數(shù)據(jù)庫關(guān)鍵字搜索系統(tǒng)的體系結(jié)構(gòu)可以根據(jù)是否直接查詢實時數(shù)據(jù)庫分為兩大類，即在線搜索結(jié)構(gòu)和離線搜索結(jié)構(gòu)。在線搜索系統(tǒng)在用戶的搜索請求到來時，直接查詢實時數(shù)據(jù)庫來生成查詢結(jié)果，典型的系統(tǒng)有DISCOVER、BANKS、IR-Style；離線搜索系統(tǒng)首先對數(shù)據(jù)庫進(jìn)行預(yù)處理，用戶提交關(guān)鍵字時，是在預(yù)處理的結(jié)果中進(jìn)行搜索，典型的系統(tǒng)有DBXplorer、ObjectRank。在線搜索結(jié)構(gòu)和離線搜索結(jié)構(gòu)的對比如表1所示。
表1在線搜索和離線搜索對比
對比項目在線搜索離線搜索
是否需要預(yù)處理否是
查詢目標(biāo)實時數(shù)據(jù)庫預(yù)處理后的數(shù)據(jù)庫
響應(yīng)時間較長較短
維護(hù)代價低高數(shù)據(jù)庫更新后需要重新進(jìn)行預(yù)處理
適用情況中小型數(shù)據(jù)庫更新較少的數(shù)據(jù)庫
典型應(yīng)用DISCOVER、BANKS、IR-Style等DBXplore、ObjectRank等
31在線搜索體系結(jié)構(gòu)
IR-Style[6]是一個典型的在線搜索系統(tǒng)，它的體系結(jié)構(gòu)是在DISCOVER的基礎(chǔ)上完善發(fā)展而來的，主要分成以下三個模塊：
a)IR Engine。當(dāng)用戶的搜索請求Q到來時，IR Engine根據(jù)DBMS提供的全文索引，從每個關(guān)系R中選出滿足搜索關(guān)鍵字的元組集RQ={t∈R|score(t，Q)>0}。其中：score(t，Q)是元組t針對搜索請求Q的相關(guān)性排序函數(shù)。
b)CNG(candidate network generator)。它將IR Engine輸出的相關(guān)元組集作為輸入，并結(jié)合數(shù)據(jù)庫模式來產(chǎn)生候選網(wǎng)絡(luò)表示符合條件的元組的連接關(guān)系。
c)Execution Engine。這個模塊將候選網(wǎng)絡(luò)表示的結(jié)果轉(zhuǎn)換為用SQL語言查詢數(shù)據(jù)庫得到的最終結(jié)果，并以top-k的形式反饋給用戶。
32離線搜索的體系結(jié)構(gòu)
典型的離線搜索體系結(jié)構(gòu)如ObjectRank系統(tǒng)。ObjectRank分為預(yù)處理和查詢兩大模塊。其中預(yù)處理模塊在DBXplorer中也稱為發(fā)布模塊(publish)，體現(xiàn)了離線搜索系統(tǒng)的特征。
a)預(yù)處理模塊。它通過ObjectRank執(zhí)行模塊來實現(xiàn)，將可供查詢的數(shù)據(jù)庫以及ObjectRank中需要的一些參數(shù)作為輸入，輸出所有關(guān)鍵字的AuthoRank索引。AuthoRank索引與RDMS提供的全文索引不同，它是以〈id(t)，rk(t)〉形式來標(biāo)志包含關(guān)鍵字k的元組t。其中：id(t)表示元組t的編號；rk(t)表示元組t關(guān)于關(guān)鍵字k的權(quán)威值。在ObjectRank中只對rk(t)大于某一閾值的元組進(jìn)行索引。
b)查詢模塊。該模塊包括查詢處理模塊和數(shù)據(jù)庫訪問模塊。其中，查詢處理模塊接收AuthoRank執(zhí)行模塊輸出的ObjectRank索引和用戶輸入的搜索關(guān)鍵字，并結(jié)合搜索算法中所需的參數(shù)，在AuthoRank索引中進(jìn)行搜索，輸出滿足條件的top-k的id；數(shù)據(jù)庫訪問模塊則根據(jù)這些id來查詢數(shù)據(jù)庫，將最終的結(jié)果返回給用戶。
4關(guān)鍵技術(shù)及算法
41創(chuàng)建索引策略
對數(shù)據(jù)庫中的關(guān)鍵字創(chuàng)建索引的優(yōu)劣在很大程度上決定了搜索效率的高低和搜索結(jié)構(gòu)的準(zhǔn)確性。較為廣泛應(yīng)用的創(chuàng)建索引的策略主要有IR索引、符號表和AuthoRank索引。
IR索引[4，6]就是RDBMS支持的對文本屬性的全文索引，它是一個逆排文件，以〈ki，occ(ki)〉的形式記錄了關(guān)鍵字ki在數(shù)據(jù)庫中出現(xiàn)的位置。在線搜索系統(tǒng)采用的多是這種索引算法，如IR-Style、BANKS等。
符號表[3]是DBXplorer系統(tǒng)中采用的索引方法，它繼承IR索引的思想，但是利用專門的符號表來記錄關(guān)鍵字和該關(guān)鍵字存在的元組編號。符號表的每一項形如〈ki，id(ki)〉。
AuthoRank索引[7]則是ObjectRank系統(tǒng)提出的。對于每個關(guān)鍵字，它記錄的是它所在元組的編號和該元組針對該關(guān)鍵字的權(quán)威值〈id(t)，rk(t)〉。該索引算法不僅記錄了關(guān)鍵字的位置，同時也包含了關(guān)鍵字的權(quán)威信息，便于對結(jié)果進(jìn)行排序。
以上三種索引算法的優(yōu)缺點比較如表2所示。
表2索引算法比較
索引算法優(yōu)點缺點
IR索引可以利用RDMS自帶的全文索引難以定位跨表連接得到的結(jié)果的位置
符號表便于直接定位關(guān)鍵字所在元組，支持跨表連接需要創(chuàng)建和存儲符號表的額外代價
AuthoRank索引直接定位關(guān)鍵字所在元組，支持跨表連接，便于結(jié)果的相關(guān)性排序維護(hù)符號表的代價；創(chuàng)建索引過程復(fù)雜；占用內(nèi)存空間較大；維護(hù)代價較高
Bi-level索引是在BLINK機制中提出的[12]，它針對上述索引算法存在的內(nèi)存需求大、最差情形下性能差的問題，解決了在搜索效率和空間需求上尋找一個平衡點的問題。Bi-level索引包含頂層塊索引(top-level block index)和塊內(nèi)索引(intra-block)兩部分。首先將數(shù)據(jù)圖劃分為小塊（block），由頂層塊索引記錄關(guān)鍵字到每一塊的映射關(guān)系，以引導(dǎo)塊間的搜索，而每一塊的詳細(xì)信息則存儲在塊內(nèi)索引中，用來加速塊內(nèi)的查詢。
42相關(guān)性排序算法
對數(shù)據(jù)庫關(guān)鍵字搜索的結(jié)果按照相關(guān)性進(jìn)行排序是數(shù)據(jù)庫關(guān)鍵字搜索中的一大突破。DISCOVER系統(tǒng)中首次提出了排序的思想，之后很多研究都致力于排序算法的優(yōu)化和改進(jìn)，現(xiàn)有的算法主要有基于連接數(shù)排序、基于權(quán)重的排序、基于權(quán)威值的排序、基于IR索引的排序四種算法。
基于連接數(shù)的排序算法[3]是一種最簡單的排序算法。根據(jù)關(guān)系數(shù)據(jù)庫主外鍵連接的特點，可以很直觀地認(rèn)為，如果一個搜索答案是通過較多個元組的連接而得到的，那么它與搜索條件的相關(guān)性較低；反之，滿足搜索條件的單個元組具有最高的相關(guān)性。因此基于連接數(shù)的排序算法就是按照結(jié)果所包含的連接數(shù)多少來進(jìn)行排序，連接數(shù)越多，相關(guān)性越低。DISCOVER系統(tǒng)采用的就是這種算法。
基于權(quán)重的算法[4]是繼承了互聯(lián)網(wǎng)中PageRank算法的思想，它考慮到數(shù)據(jù)庫關(guān)系之間的主外鍵聯(lián)系程度并非完全相同，而是依賴于數(shù)據(jù)庫的語義，如在DBLP數(shù)據(jù)庫中，paper表和writes表之間的聯(lián)系顯然要比paper表和cites表之間的聯(lián)系要強，因此，該算法對不同的主外鍵連接賦予不同的權(quán)重。同時，根據(jù)PageRank的思想，有很多邊指向的節(jié)點，權(quán)重相對要高，因此算法根據(jù)指向節(jié)點的邊的多少對節(jié)點賦予一個權(quán)重。算法主要包括以下步驟：
a)根據(jù)主外鍵聯(lián)系的強度給每條邊賦予權(quán)重值Weightedge(u，v)，權(quán)重值通常由領(lǐng)域?qū)＜医o出。
b)對于每條邊edge(u，v)創(chuàng)建一條反向邊backward edge(v，u)，反向邊的權(quán)重值：
weightedge(v，u)=weightedge(u，v)×x×log(1+x)
其中：x表示該邊的內(nèi)連(inlinks)數(shù)目。
c)根據(jù)指向節(jié)點的邊的數(shù)目給每個節(jié)點賦予權(quán)重值：
weightnode(i)=log(1+x)
其中：x表示該節(jié)點的入度數(shù)(in-degree)。
d)對于搜索結(jié)果，將邊權(quán)重和節(jié)點權(quán)重依據(jù)一定的函數(shù)進(jìn)行組合得到最后的相關(guān)性得分，組合公式為
weighttotal=(1-λ)weightedge+λweightnode
基于權(quán)威值的算法是基于權(quán)威傳遞數(shù)據(jù)圖實現(xiàn)的[7]，在權(quán)威傳遞數(shù)據(jù)圖中每條邊都帶有一個權(quán)威值：
α(e)=0，ifoutDeg(u，e)=0
α(e)/outDeg(u，e)ifoutDeg(u，e)＞0
其中:outDeg(u，e)表示節(jié)點u的出度。
基于權(quán)威的算法對每一個節(jié)點賦予一個關(guān)鍵字相關(guān)的權(quán)威值rw和一個全局的權(quán)威值rG：
rw=dArw+(1-d)s/｜S(w)｜
其中:d是一個調(diào)整因子；Aij=α(e)；S(w)是滿足搜索條件w的元組集；s是一個基本向量。1表示該節(jié)點屬于S(w)；0表示不屬于S(w)。
全局權(quán)威值是根據(jù)數(shù)據(jù)庫的語義來賦予的，在不同的應(yīng)用中具有不同的值，最后的結(jié)果為
rw，G(v)=rw(v)×(rG(v))g
其中:g是表示全局權(quán)威值在最終得分中所占的比重，可以由用戶或管理員來指定。
基于IR索引的排序算法[6]主要利用了現(xiàn)有的一些DBMS在單個文本屬性上對相關(guān)性排序的支持，將單個屬性上的相關(guān)性得分組合成為最終的得分。對于查詢Q，單個文本屬性的相關(guān)性得分是DBMS的IR引擎計算得出：
score(ai，Q)=∑w∈Q∩ai
[1+ln(1+ln(tf))]/[(1-s)+（sdl/avdl)]×ln (N+1)/(df)
其中:tf表示關(guān)鍵字w在屬性ai中出現(xiàn)的頻率；df是ai屬性值包含w的元組數(shù)目。每個文本屬性的值通過combine函數(shù)組合得到該元組數(shù)最終的分值：
combine(score(A，Q)，size(T))=(∑ai∈Ascore(ai，Q))/size(T)
其中:A是元組樹的所有文本屬性的向量表示；size(T)表示元組樹的大小。上述四種排序算法的優(yōu)缺點比較如表3所示。
表3排序算法比較
排序算法優(yōu)點缺點
基于連接數(shù)排序算法簡單直觀無法對相同連接數(shù)的元組排序
基于權(quán)重排序不同連接具有不同的權(quán)重符合數(shù)據(jù)庫的語義權(quán)重值不易確定需要領(lǐng)域知識
基于權(quán)威值排序邊和節(jié)點都有權(quán)威值節(jié)點具有特定的和全局的權(quán)威值；可以調(diào)整影響因子控制排序結(jié)果算法實現(xiàn)較復(fù)雜需要權(quán)威傳遞圖的支持
基于IR索引排序可利用DBMS的IR引擎的支持；算法在IR領(lǐng)域上已成熟應(yīng)用不能突出AND語義的優(yōu)先級；combine函數(shù)過于強調(diào)不同元組中同一關(guān)鍵字的貢獻(xiàn)
基于虛擬文檔的排序算法[13]是對傳統(tǒng)IR索引排序算法的一種改進(jìn)，它將每個元組連接樹（joined tuple tree）視為一個虛擬文檔(virtual document)。因此，一個候選網(wǎng)絡(luò)產(chǎn)生的所有結(jié)果將被建模為文檔的集合，虛擬文檔是與特定查詢相關(guān)的，且在運行時動態(tài)創(chuàng)建。基于這種模型，可以直接計算每個元組連接樹的相關(guān)性得分，而不必對每個文本屬性進(jìn)行評分再進(jìn)行累加，每個元組連接樹T的得分計算如下：
scorea(T，Q)=∑w∈Q∩Ti
[1+ln(1+ln(tfw(T)))]/[(1-s)+sdlT/(avdlCN×(T) )]×ln(idfw)
針對滿足所有關(guān)鍵字的元組樹具有比滿足部分關(guān)鍵字的元組樹更高的相關(guān)性得分這一要求，該算法引入完備性因子(completeness factor)：
scoreb(T，Q)=1-[(∑1≤i≤m(1-T.i)p)/m]1/p
其中：T.i是在元組連接樹中關(guān)鍵字kwi經(jīng)過規(guī)范后的頻率表示。
該算法還通過定義元組樹的大小因子（size normalization factor）來體現(xiàn)元組連接樹的大小對關(guān)鍵字出現(xiàn)幾率的影響，即元組連接樹越大，關(guān)鍵字出現(xiàn)幾率也越大，通過實驗得到較有效的大小因子計算公式如下：
scorec=(1+s1-s1×size(CN))×(1+s2-s2×size(CNnf))
基于虛擬文檔的排序算法對每一個元組連接樹的最終評分是上述三個評分函數(shù)的乘積：
score(T，Q)=scorea(T，Q)×scoreb(T，Q)×scorec(T，Q)
5結(jié)束語
數(shù)據(jù)庫關(guān)鍵字搜索作為一個新興的研究領(lǐng)域，在理論研究和應(yīng)用系統(tǒng)開發(fā)上均取得了很大的進(jìn)展，數(shù)據(jù)庫關(guān)鍵字搜索在研究上不僅繼承了互聯(lián)網(wǎng)搜索和信息檢索中的一些成熟技術(shù)，而且還根據(jù)關(guān)系數(shù)據(jù)庫自身的結(jié)構(gòu)化特點和語義信息，提出新的、更加適用于數(shù)據(jù)庫搜索的算法和相關(guān)性排序策略，并在實際應(yīng)用中取得了較好的效果。現(xiàn)有的數(shù)據(jù)庫關(guān)鍵字搜索研究正在朝搜索性能優(yōu)化以及與其他相關(guān)領(lǐng)域技術(shù)相結(jié)合的方向發(fā)展。然而，目前對數(shù)據(jù)庫關(guān)鍵字搜索的研究也并存在一些問題：a)現(xiàn)有研究僅僅是針對關(guān)系數(shù)據(jù)庫，而在互聯(lián)網(wǎng)上可能存在大量的非關(guān)系數(shù)據(jù)庫，這些數(shù)據(jù)庫也存儲了大量的有用信息，如何實現(xiàn)對非關(guān)系數(shù)據(jù)庫的關(guān)鍵字搜索將是未來的一個研究方向。b)現(xiàn)有的數(shù)據(jù)庫關(guān)鍵字搜索系統(tǒng)都是獨立的一個系統(tǒng)，與現(xiàn)存互聯(lián)網(wǎng)搜索系統(tǒng)沒有接口，而對于用戶的搜索需求，要求兩者能夠很好地結(jié)合起來。因此，實現(xiàn)非關(guān)系數(shù)據(jù)庫關(guān)鍵字搜索，以及數(shù)據(jù)庫關(guān)鍵字搜索和互聯(lián)網(wǎng)搜索引擎的無縫連接還有待進(jìn)一步的研究。同時，數(shù)據(jù)庫的語義搜索和分布式數(shù)據(jù)庫、異構(gòu)數(shù)據(jù)庫的搜索仍然是未來研究的熱點。
參考文獻(xiàn)：
［1］CAVERLEE J， LIU L， ROCCO D. Discovering interesting relationships among deep webdatabases:a source-biased approach[J].World Wide Web，2006，9(4):585-622.
[2]GOLDMAN R， SHIVAKUMAR N， VENKATASUBRAMANIAN S， et al. Proximity search in databases[C]//Proc ofVLDB’98. New York:[s.n.]， 1998.
[3]AGRAWAL S， CHAUDHURI S， DAS G. DBXplorer: a system for keyword-based search over relational databases[C]//Proc of ICDE’ 02. California:[s.n.]， 2002.
[4]BHALOTIA G， HULGERI A， NAKHEY C， et al. Keyword searching and browsing in databases using BANKS[C]//Proc of ICDE’02. California:[s.n.]， 2002.
[5]HRISTIDIS V， PAPAKONSTANTINOU Y. DISCOVER: keyword search in relational databases[C]//Proc of VLDB’02. Hong Kong:[s.n.]， 2002.
[6]HRISTIDIS V， GRAVANO L， PAPAKONSTANTINOU Y. Efficient IR-Style keyword search over relational databases[C]//Proc of VLDB’03. Berlin:[s.n.]， 2003.
[7]BALMIN A， HRISTIDIS V， LPAPAKONSTANTINOU Y. Authority based keyword queries in databases using ObjectRank[C]//Proc of VLDB’04. Toronto:[s.n.]， 2004.
[8]文繼軍，王珊. SEEKER:基于關(guān)鍵詞的關(guān)系數(shù)據(jù)庫信息檢索[J]. 軟件學(xué)報， 2005，16(7):1270-1279.
[9]LIU Fang， YU C T， MENG Wei-yi. Effective keyword search in relational databases[C]//Proc of SIGMOD’06. Chicago:[s.n.]， 2006.
[10]DING Bo-lin， YU J X， WANG Shan. Finding top-k min-cost connected trees in databases[C]//Proc of ICDE’07. Istanbul:[s.n.]， 2007.
[11]PENG Zhao-hai， ZHANG Jun， WANG Shan. TreeCluster:clustering results of keyword search over databases[C]//Proc of WAIM’06. Hong Kong:[s.n.]， 2006.
[12]HE Hao， WANG Hai-xun， YANG Jun， et al. BLINKS: ranked keyword searches on graphs[C]//Proc of SIGMOD’07. Beijing: [s.n.]， 2007.
[13]LUO Yi， LIN Xue-min， WANG Wei， et al. SPARK: top-k keyword query in relational databases[C]//Proc of SIGMOD’07.Beijing:[s.n.]， 2007.
[14]ZHANG Jun， PENG Zhao-hui， WANG Shan. Si-SEEKER: ontology-based semantic search over databases[C]//Proc of the 1st Conference on KSEM’06. 2006:599-611.
[15]YU Bei， LI Guo-liang， SOLINS K. Effective keyword-based selection of relational databases[C]//Proc of SIGMOD’07. Beijing:[s.n.]， 2007.
[16]SAYYADIAN M， LEKHAC H， DOAN A， et al. Efficient keyword search across heterogeneous relational databases[C]//Proc of ICDE’07. Istanbul: [s.n.]， 2007.
[17]KAUSHIK R， KRISHNAMURTHY R， RAMAKRISHNAN R. On the integration of structure indexes and inverted lists[C]//Proc of ICDE’04. Boston:[s.n.]， 2004.
[18]ZHANG Jun， PENG Zhao-hui， WANG Shan， et al. PreCN: preprocessing candidate networks for efficient keyword search over databases[C]//Proc of WISE’06. Wuhan:[s.n.]， 2006.
[19]ZHAN Jiang， WANG Shan. ITREKS: keyword search over relational database by indexing tuple relationship[C]//Proc of DASFAA’07. Bangkok: [s.n.] 2007.
[20]蔡宏艷， 姚佳麗， 王珊. DETECTOR: 基于關(guān)系數(shù)據(jù)庫通用的在線關(guān)鍵詞查詢系統(tǒng)[J]. 計算機研究與發(fā)展， 2007，44(1):119-125.
[21]WANG Shan， DU Xiao-yong， MENG Xiao-feng， et al. Database research: achievements and challenges[J]. Computer Science Technology，2006，21(5):823-837.
[22]SINGHAL A. Modern information retrieval: a brief overview[J].IEEE Data Eng Bull，2001，24(4):35-43.
[23]GROSSMAN D， FRIEDER O. Information retrieval: algorithms and heuristics[M]. 2nd ed. [S.l.]:Springer Publishers， 2004.
[24]MAMOULIS N， CHENG K H. Efficient aggregation of ranked inputs[C]//Proc of ICDE’06. Atlanta:[s.n.]， 2006.
[25]KIMELFELD B， SAGIV Y. Finding and approximating top-k answers in keyword proximity search[C]//Proc of PODS’06. 2006.
[26]KACHOLIA V， PANDIT S， CHAKRABARTI S. Bidirectional expansion for keyword search on graph databases[C]//Proc of VLDB’05. Trondheim:[s.n.]， 2005.
[27]LIU Zi-yang， CHEN Yi. Identifying meaningful return information for XML keyword search[C]//Proc of SIGMOD’07. Beijing:[s.n.]， 2007.
[28]DONG X， HALEVY A. Indexing dataspaces[C]//Proc of SIGMOD’07. Beijing: [s.n.]， 2007.
[29]WANG Shan， PENG Zhao-hui， ZHANG Jun. NUITS: a novel user interface for efficient keyword search over databases[C]//Proc of VLDB’06. Seoul:[s.n.]， 2006.
[30]王珊，文繼榮.數(shù)據(jù)庫和信息檢索技術(shù)的融合[J]. 中國計算機學(xué)會通訊，2006，2(4):18-24.
[31]王珊，張俊，彭朝暉，等. 基于本體的關(guān)系數(shù)據(jù)庫語義檢索[J]. 計算機科學(xué)與探索， 2007，1(1):59-78.
