楊書新，徐慧琴，譚 偉

（江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000）

0 引 言

關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢旨在為用戶提供類搜索引擎的方法實(shí)現(xiàn)基于關(guān)鍵詞的數(shù)據(jù)庫(kù)內(nèi)容查詢，它不要求用戶熟悉復(fù)雜的結(jié)構(gòu)化查詢語(yǔ)言 （如SQL，SPARQL等）和底層數(shù)據(jù)庫(kù)模式的知識(shí)。關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢枚舉所有查詢結(jié)果的方法主要由兩部分組成：根據(jù)用戶給定的關(guān)鍵詞集合Q，產(chǎn)生一系列候選結(jié)果集合；對(duì)候選結(jié)果集進(jìn)行相關(guān)度降序排序。一個(gè)優(yōu)秀的關(guān)鍵詞查詢系統(tǒng)必需滿足以下三點(diǎn)要求：①查詢效率高；②能枚舉所有與查詢相關(guān)的結(jié)果；③一個(gè)滿足用戶需求的相關(guān)性評(píng)分函數(shù)。然而，要很好的滿足以上三點(diǎn)要求依然存在很大的挑戰(zhàn)，因此，關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢方法的研究依然是數(shù)據(jù)庫(kù)研究領(lǐng)域的一個(gè)重點(diǎn)。

文中針對(duì)要求③中的排序問(wèn)題研究如何有效的對(duì)結(jié)果進(jìn)行排序，目前已有的排序方法通?？紤]的影響因素比較單一，因此，文中提出結(jié)合結(jié)果樹(shù)結(jié)構(gòu)權(quán)重和關(guān)鍵詞與包含關(guān)鍵詞元組之間的相關(guān)性對(duì)結(jié)果進(jìn)行排序的方法。在基于結(jié)構(gòu)權(quán)重的排序方法基礎(chǔ)上引入相關(guān)性權(quán)重，可以使排列在前面的結(jié)果樹(shù)不僅結(jié)構(gòu)緊湊而且與查詢條件高度相關(guān)。

1 相關(guān)工作

目前，已有的研究通常將關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢轉(zhuǎn)換為對(duì)圖的查詢，基于圖關(guān)鍵詞查詢的結(jié)果排序主要有兩種：基于圖結(jié)構(gòu)權(quán)重的方法和基于IR式排序的方法。

文獻(xiàn) ［1－2］采用路徑代價(jià)來(lái)衡量結(jié)果的質(zhì)量，當(dāng)所有關(guān)鍵詞節(jié)點(diǎn)到中心節(jié)點(diǎn)的總路徑權(quán)重越小，查詢到的結(jié)果樹(shù)就越緊湊，結(jié)果質(zhì)量也就越高。

不同于以上采用基于圖結(jié)構(gòu)權(quán)重的排序方法，文獻(xiàn)［3－4］采用IR式排序方法，為結(jié)果中的每個(gè)元組附一個(gè)IR分值，結(jié)果樹(shù)的IR分值取結(jié)果樹(shù)中所有元組IR分值的平均值。F.Liu等人在文獻(xiàn) ［3］中對(duì)KQORD和傳統(tǒng)的IR排序方法進(jìn)行分析，將一種結(jié)合了規(guī)范化因子的IR評(píng)分方法應(yīng)用于結(jié)果排序中。在IR式結(jié)果排序的基礎(chǔ)上，Y.Luo等人在文獻(xiàn) ［4］的排序方法中引入虛擬文檔模型的概念，計(jì)算查詢結(jié)果與關(guān)鍵詞的相關(guān)度。

文獻(xiàn) ［5－7］為了完整表達(dá)關(guān)鍵詞之間的語(yǔ)義關(guān)系，受Steiner樹(shù)的啟發(fā)提出了Steiner圖問(wèn)題。

由上述可知，很多研究在結(jié)果排序方面考慮的元素比較單一，因此，在接下來(lái)的篇幅中，文中將在查詢結(jié)果的呈現(xiàn)方面聯(lián)合基于圖結(jié)構(gòu)權(quán)重和基于IR式排序方法的優(yōu)點(diǎn)，提出一種新的排序方法，采用結(jié)合結(jié)果樹(shù)的結(jié)構(gòu)權(quán)重和查詢相關(guān)性的方法對(duì)結(jié)果進(jìn)行排序。

2 數(shù)據(jù)模型

許多領(lǐng)域中的大量數(shù)據(jù) （例如生物網(wǎng)絡(luò)，社會(huì)網(wǎng)絡(luò)等）都可以建模成圖的結(jié)構(gòu)。基于圖數(shù)據(jù)結(jié)構(gòu)的關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢方法可以根據(jù)用戶給定的一組查詢關(guān)鍵詞Q產(chǎn)生由核心節(jié)點(diǎn) （所有關(guān)鍵詞節(jié)點(diǎn)所能到達(dá)的節(jié)點(diǎn)），信息節(jié)點(diǎn)（關(guān)鍵詞節(jié)點(diǎn)），路徑節(jié)點(diǎn)和相關(guān)邊構(gòu)成的一系列子樹(shù)作為查詢結(jié)果。查詢結(jié)果必須滿足如下兩個(gè)約束：①完全性約束：結(jié)果中必須包含用戶給定的所有關(guān)鍵詞；②非冗余性約束：當(dāng)結(jié)果子樹(shù)的子樹(shù)依然包含所有的關(guān)鍵詞，或者一個(gè)結(jié)果包含于另一個(gè)查詢結(jié)果時(shí)，都屬于冗余結(jié)果，必須進(jìn)行剪枝。

現(xiàn)有方法中的數(shù)據(jù)模型主要可分為兩大類：模式圖和數(shù)據(jù)圖。在模式圖中，節(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)庫(kù)中的關(guān)系表，邊對(duì)應(yīng)表與表之間的主外碼引用關(guān)系；在數(shù)據(jù)圖中，節(jié)點(diǎn)表示關(guān)系表中元組記錄，邊表示元組與元組之間的主外碼關(guān)系。數(shù)據(jù)圖可表示非結(jié)構(gòu)化數(shù)據(jù)，半結(jié)構(gòu)化數(shù)據(jù)和結(jié)構(gòu)化數(shù)據(jù)。由于數(shù)據(jù)圖廣泛的應(yīng)用性，基于數(shù)據(jù)圖的關(guān)鍵詞查詢方法備受關(guān)注，基于數(shù)據(jù)圖的查詢系統(tǒng)有BANKS－Ⅰ，BANK－Ⅱ，EASE［5］等。

定義1 數(shù)據(jù)圖：假設(shè)G＝（V，E）是關(guān)系數(shù)據(jù)庫(kù)對(duì)應(yīng)的數(shù)據(jù)圖，G表示一個(gè)有向帶權(quán)圖，V為圖中節(jié)點(diǎn)集合，E為圖中邊的集合，數(shù)據(jù)庫(kù)中的每條元組記錄看作是圖中的節(jié)點(diǎn)，如果存在表中任意兩個(gè)元組ti，tj存在主外碼引用關(guān)系，則有 ＜ti，tj＞∈E或 ＜tj，ti＞∈E。

關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢中，給定一組查詢條件Q＝（q1，q2，…qn），系統(tǒng)找到包含關(guān)鍵詞的信息碎片 （包含關(guān)鍵詞的元組記錄），合理的組織這些信息碎片，構(gòu)成非冗余的結(jié)果組Steiner樹(shù)，一個(gè)查詢條件通常會(huì)產(chǎn)生大量結(jié)果，隨機(jī)排列結(jié)果顯然不符合用戶的需求，因此，定義一個(gè)相關(guān)性評(píng)分函數(shù)很有必要，使結(jié)果集按照某種特定的順序呈現(xiàn)在客戶端，將用戶感興趣的結(jié)果靠前排列。

3 結(jié)果排序方法

到目前為止，一些基于最小Steiner樹(shù)問(wèn)題以及它的變型通常只考慮邊的權(quán)重而忽視了節(jié)點(diǎn)權(quán)重或者考慮了節(jié)點(diǎn)權(quán)重也只是假設(shè)它們的權(quán)重是相等的，但實(shí)際上，包含關(guān)鍵詞節(jié)點(diǎn)和關(guān)鍵詞可達(dá)節(jié)點(diǎn)的重要性并不是等同的，因此，在本節(jié)中，結(jié)果樹(shù)評(píng)分函數(shù)將結(jié)合結(jié)構(gòu)權(quán)重和節(jié)點(diǎn)的相關(guān)性權(quán)重。

3.1 基于結(jié)構(gòu)的權(quán)重計(jì)算

根據(jù)權(quán)威度的定義，當(dāng)一個(gè)參與者有許多的鏈入鏈接時(shí)，它就是權(quán)威的。對(duì)于數(shù)據(jù)圖而言，一個(gè)節(jié)點(diǎn)的入度越大，它的權(quán)威度就越高。因此，用節(jié)點(diǎn)權(quán)威度可以很理想的表示節(jié)點(diǎn)的權(quán)重，式 （1）給出單個(gè)節(jié)點(diǎn)的權(quán)重計(jì)算公式，用平均節(jié)點(diǎn)權(quán)重表示結(jié)果樹(shù)的節(jié)點(diǎn)權(quán)重，如式 （2）所示

式中：incom（v）——節(jié)點(diǎn)v的入度，incommax——數(shù)據(jù)圖中的節(jié)點(diǎn)最大入度，｜T｜——結(jié)果子樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。

以往的一些研究對(duì)有向圖G的正反向邊的權(quán)值并未給予區(qū)分，這顯然不符合實(shí)際應(yīng)用，文中在對(duì)數(shù)據(jù)進(jìn)行預(yù)處理時(shí)，為正向邊和反向邊設(shè)定不同的權(quán)值，如式 （3）所示，正向邊設(shè)權(quán)值為1，式 （4）給出結(jié)果樹(shù)中邊權(quán)重分量的計(jì)算方法，邊權(quán)重越小，結(jié)果樹(shù)分?jǐn)?shù)越大，采用log函數(shù)求邊權(quán)重和可以有效減小結(jié)果樹(shù)評(píng)分函數(shù)中邊權(quán)重部分的變化幅度，其中Wmin（e）為圖中最小邊權(quán)重

3.2 基于相關(guān)性的權(quán)重計(jì)算

（1）關(guān)鍵詞重要性分析

TF－IDF作為一種用于資訊探勘和資訊檢索的常用加權(quán)技術(shù)，可用于評(píng)估一個(gè)詞對(duì)于一個(gè)文件集 （語(yǔ)料庫(kù)）中一個(gè)文件的重要程度。一個(gè)詞的重要性與它在文件中出現(xiàn)的次數(shù)成正比，但同時(shí)與它在語(yǔ)料庫(kù)中出現(xiàn)的頻率成反比。

采用基于TF－IDF的方法計(jì)算關(guān)鍵詞的重要性［8］，元組與給定的查詢關(guān)鍵詞的相關(guān)性與輸入的關(guān)鍵詞集合緊密聯(lián)系，因此該值是動(dòng)態(tài)的，隨著給定的關(guān)鍵詞變化而變化。

文中將每個(gè)元組單元建模成一個(gè)虛擬文檔d，式 （5）給出求文檔d中關(guān)鍵詞qi的重要性標(biāo)準(zhǔn)化公式

ntf（qi，d）（標(biāo)準(zhǔn)詞頻），ndl（標(biāo)準(zhǔn)文檔長(zhǎng)度）和nidfqi（標(biāo)準(zhǔn)逆文檔頻率）［8］3個(gè)因子的計(jì)算公式如下

其中，tf（qi，d）為詞頻，表示關(guān)鍵詞qi在文檔 （元組）d中出現(xiàn)的次數(shù)，一個(gè)詞在文檔中出現(xiàn)得越頻繁，重要性越大。dl表示文檔長(zhǎng)度，即元組中包含術(shù)語(yǔ)的個(gè)數(shù)，dl的出現(xiàn)可以有效降低長(zhǎng)文本中關(guān)鍵詞qi的重要性。avgdl表示文檔的平均長(zhǎng)度，s為0～1的平滑參數(shù)，通常取值為0.2。idfqi為逆文檔頻率，用文檔頻率的倒數(shù)表示，文檔頻率為包含某特定關(guān)鍵詞的文檔在總的文檔集中出現(xiàn)次數(shù)，式 （8）給出了逆文檔頻率的標(biāo)準(zhǔn)化計(jì)算公式，D為文檔d的集合，｜D｜表示總的文檔數(shù)量，｜dfqi｜為包含關(guān)鍵詞qi的元組數(shù)量。這里文檔進(jìn)行了分類，針對(duì)DBLP數(shù)據(jù)集而言，文檔有author和paper兩個(gè)類，如果關(guān)鍵詞qi屬于anthor類，那么｜D｜就為author元組的數(shù)量，否則就為paper元組的數(shù)量。

以圖1中的數(shù)據(jù)子圖為例，當(dāng)查詢條件Q＝ ｛Keyword，Relational｝時(shí)，包含關(guān)鍵詞的節(jié)點(diǎn)為p1，p2和p3，下面分別給出這3個(gè)節(jié)點(diǎn)與查詢條件相關(guān)性的計(jì)算過(guò)程。

圖1 數(shù)據(jù)圖子樣

詞頻tf（qi，d）見(jiàn)表1。

表1 詞頻tf（qi，d）

逆文檔頻率idfqi見(jiàn)表2。

表2 逆文檔頻率idfqi

標(biāo)準(zhǔn)文檔長(zhǎng)度ndl見(jiàn)表3。

表3 標(biāo)準(zhǔn)文檔長(zhǎng)度ndl

節(jié)點(diǎn)與查詢條件的相關(guān)性分?jǐn)?shù)見(jiàn)表4。

表4 節(jié)點(diǎn)與查詢條件的相關(guān)性分?jǐn)?shù)

（2）節(jié)點(diǎn)與關(guān)鍵詞相關(guān)性分析

為了描述元組與關(guān)鍵詞的相關(guān)性，用RE（t，Q）表示元組t與查詢條件Q的相關(guān)度，式 （9）分別給出包含關(guān)鍵詞和不包含關(guān)鍵詞的元組相關(guān)度計(jì)算方法，當(dāng)元組不包含關(guān)鍵詞時(shí)，相關(guān)度值為0

其中，包含給定關(guān)鍵詞元組的相關(guān)性計(jì)算如式 （10）所示。假設(shè)t是關(guān)系數(shù)據(jù)庫(kù)中基本數(shù)據(jù)表中的元組，對(duì)于DBLP數(shù)據(jù)集來(lái)講，它們是來(lái)自表Author和Pape

式 （11）為基于節(jié)點(diǎn)相關(guān)性的權(quán)重分量計(jì)算方法

3.3 線性結(jié)合

下式給出結(jié)果樹(shù)的相關(guān)性評(píng)分函數(shù)計(jì)算公式，其中0＜λ，β＜1，通常λ取值0.2，分?jǐn)?shù)越高，表明結(jié)果與查詢相關(guān)性就越大，越符合用戶查詢要求。

在實(shí)際應(yīng)用中，關(guān)鍵詞表示的語(yǔ)義可能不同，例如關(guān)鍵詞 “于丹”，它可以是一個(gè)作者名，也可是一本書名中的術(shù)語(yǔ)。為了提高查詢靈活性，確定關(guān)鍵詞所屬類型，可將關(guān)鍵詞表示成 “作者：于丹”，說(shuō)明查詢的關(guān)鍵詞類型為作者。關(guān)鍵詞類型的設(shè)置對(duì)于不熟悉系統(tǒng)的用戶來(lái)說(shuō)會(huì)存在一定偏差，作者可能被描述成作家，寫書人等，系統(tǒng)應(yīng)結(jié)合這種情況將這一類描述智能統(tǒng)一成作者。雖然該種表示方式包含兩個(gè)術(shù)語(yǔ)，但由于冒號(hào)前面用于標(biāo)注關(guān)鍵詞類型，因而冒號(hào)前后做一個(gè)關(guān)鍵詞看待，只有當(dāng)元組與關(guān)鍵詞內(nèi)容和類型屬性完全匹配的時(shí)候，相關(guān)度的值為一個(gè)非零實(shí)數(shù)。

當(dāng)輸入查詢關(guān)鍵詞時(shí)，只找到包含關(guān)鍵詞的元組遠(yuǎn)不能滿足用戶的信息需求，表5定義了幾種針對(duì)DBLP數(shù)據(jù)集設(shè)置查詢條件的方式供用戶選擇。＜＃style＞表示附加條件，＃后面標(biāo)注的是要查找的信息類型，只有當(dāng)輸入的關(guān)鍵詞出現(xiàn)在同一個(gè)元組中時(shí)才考慮該附加條件。

表5 查詢條件的設(shè)置

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證文中提出的結(jié)果評(píng)分函數(shù)的有效性，做了一系列的實(shí)驗(yàn)數(shù)據(jù)分析，本次實(shí)驗(yàn)開(kāi)發(fā)環(huán)境為Myeclipse＋jdk1.6＋tomcat6.0，基于postgreSQL數(shù)據(jù)庫(kù)用java語(yǔ)言實(shí)現(xiàn)功能，為了避免查詢過(guò)程中出現(xiàn)內(nèi)存溢出的問(wèn)題，在Myeclipse平臺(tái)下設(shè)置java虛擬機(jī)參數(shù)為 “－Xms256MXmx512M”，實(shí)驗(yàn)設(shè)備為一臺(tái)內(nèi)存為2G，CPU為酷睿雙核2.1GHz，操作系統(tǒng)為 Windows XP的PC機(jī)。

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 查詢結(jié)果的產(chǎn)生

查詢結(jié)果的獲取采用圖遍歷和位標(biāo)記的方法，首先根據(jù)用戶輸入的關(guān)鍵詞找到包含關(guān)鍵詞的節(jié)點(diǎn)并采用n位二進(jìn)制數(shù)對(duì)其進(jìn)行位標(biāo)記 （n值為關(guān)鍵詞個(gè)數(shù)），其它不包含關(guān)鍵詞節(jié)點(diǎn)的位標(biāo)記值初始化為0，然后對(duì)圖遍歷并更新節(jié)點(diǎn)位標(biāo)記值，遍歷過(guò)的節(jié)點(diǎn)位標(biāo)記值更新為其可達(dá)關(guān)鍵詞節(jié)點(diǎn)的位標(biāo)記值求或運(yùn)算后的值，當(dāng)節(jié)點(diǎn)的位標(biāo)記值為所有關(guān)鍵詞節(jié)點(diǎn)位標(biāo)記的或運(yùn)算結(jié)果時(shí)，則稱該節(jié)點(diǎn)為能連接所有關(guān)鍵詞節(jié)點(diǎn)的中心節(jié)點(diǎn)，由中心節(jié)點(diǎn)，關(guān)鍵詞節(jié)點(diǎn)和它們之間的路徑便能得到一個(gè)結(jié)果組stenier樹(shù)。圖2為結(jié)果獲取的一個(gè)簡(jiǎn)單實(shí)例。

圖2 查詢結(jié)果樹(shù)的獲取

圖2中黑色節(jié)點(diǎn)為關(guān)鍵詞節(jié)點(diǎn)，灰色節(jié)點(diǎn)為可達(dá)所有關(guān)鍵詞節(jié)點(diǎn)的中心節(jié)點(diǎn)，虛線為節(jié)點(diǎn)之間的路徑。

4.2.2 實(shí)驗(yàn)結(jié)果及分析

系統(tǒng)以文獻(xiàn)索引數(shù)據(jù)庫(kù)DBLP （digital bibliography ＆library project）作為實(shí)驗(yàn)數(shù)據(jù)集對(duì)評(píng)分函數(shù)進(jìn)行評(píng)估。實(shí)驗(yàn)采用標(biāo)準(zhǔn)的IR評(píng)價(jià)指標(biāo) MRR （mean reciprocal rank），RR定義為1／rbest，即把最符合查詢條件的答案在被評(píng)價(jià)系統(tǒng)給出結(jié)果中的排序取倒數(shù)作為它的準(zhǔn)確度，MRR則為多次求得RR的平均值。為了說(shuō)明文中提出的結(jié)果評(píng)估函數(shù)（search EValution，SEV）的有效性，將在結(jié)果評(píng)分函數(shù)中參數(shù)值的估計(jì)和結(jié)果查準(zhǔn)率兩個(gè)方面進(jìn)行實(shí)驗(yàn)。

（1）參數(shù)值的估算

評(píng)分函數(shù)中參數(shù)λ取值為0.2，該值參考經(jīng)典的BANKS系統(tǒng)中的值，設(shè)置參數(shù)β值分別為0，0.002，0.004，0.006，0.008和0.01進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)每次輸入兩個(gè)關(guān)鍵詞，使用系統(tǒng)進(jìn)行查詢操作并記錄最符合查詢條件的結(jié)果排序序號(hào)，對(duì)應(yīng)不同的參數(shù)β，進(jìn)行20組實(shí)驗(yàn)，分別在系統(tǒng)查詢到的結(jié)果集中找到與輸入關(guān)鍵詞最相關(guān)的結(jié)果和它所排在的位置，通過(guò)最佳結(jié)果排序序號(hào)的倒數(shù)計(jì)算得到MRR值，實(shí)驗(yàn)結(jié)果如圖3所示，從實(shí)驗(yàn)結(jié)果可以看出，β最好的取值在0.002～0.006之間，因此，為了方便實(shí)驗(yàn)數(shù)據(jù)的比較，后期將β參數(shù)值設(shè)為0.005。

（2）結(jié)果查準(zhǔn)率

SEV評(píng)分函數(shù)的有效性采用信息檢索領(lǐng)域的查準(zhǔn)率（precision）來(lái)評(píng)估，計(jì)算方法如下

圖3 參數(shù)β取值0～0.01時(shí)的查詢結(jié)果MRR值

式中：rs （relevant results）——查詢到的與關(guān)鍵詞相關(guān)的結(jié)果數(shù)，is（irrelevant results）——查詢到的與關(guān)鍵詞不相關(guān)的結(jié)果數(shù)。

參數(shù)λ為0.2，β為0.005，當(dāng)輸入關(guān)鍵詞個(gè)數(shù)分別為1，2和3時(shí)，計(jì)算top－k個(gè)查詢結(jié)果的查準(zhǔn)率，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 top－k結(jié)果查準(zhǔn)率

實(shí)驗(yàn)結(jié)果表明，當(dāng)輸入關(guān)鍵詞個(gè)數(shù)為1時(shí)，輸出的top－k個(gè)結(jié)果幾乎都是與查詢相關(guān)的結(jié)果，當(dāng)輸入多個(gè)關(guān)鍵詞時(shí)，輸出的結(jié)果有高度相似和冗余情況，使得結(jié)果查準(zhǔn)率略微下降。

運(yùn)行實(shí)驗(yàn)系統(tǒng)，當(dāng)輸入關(guān)鍵詞為2，3，4和5時(shí)，分別進(jìn)行20次查詢，并求得平均查準(zhǔn)率，將求得的平均查準(zhǔn)率和SPARK［4］，BLINKS［9］方法的平均查準(zhǔn)率進(jìn)行比較，SPARK和BLINKS方法的查準(zhǔn)率參考文獻(xiàn) ［10］。比較結(jié)果如圖5所示，實(shí)驗(yàn)結(jié)果表明文中所提方法的平均查準(zhǔn)率比SPARK和BLINKS有所提高。

圖5 查詢結(jié)果在DBLP數(shù)據(jù)集中的平均查準(zhǔn)率

5 結(jié)束語(yǔ)

SEV排序方法不僅考慮結(jié)果的結(jié)構(gòu)權(quán)重，而且結(jié)合了查詢相關(guān)性的元組IR式權(quán)重，當(dāng)元組同時(shí)包含多個(gè)關(guān)鍵詞時(shí)，元組權(quán)重明顯增加，相關(guān)的結(jié)果排序越靠前。該方法相比于BANKS系統(tǒng)中的排序方法，在輸入若干個(gè)查詢關(guān)鍵詞并且其中的兩個(gè)或兩個(gè)以上的關(guān)鍵詞出現(xiàn)在同一個(gè)元組的情況下，文中提出的方法能更有效的對(duì)結(jié)果進(jìn)行排序。由于關(guān)鍵詞的選取對(duì)于用戶來(lái)說(shuō)有一定的難度，因此，關(guān)鍵詞查詢過(guò)程的研究還有一定的空間，今后的工作將從查詢重寫和查詢提示方面開(kāi)展。

［1］Wang Meirong，Jiang Lijun，Zhang Liru，et al.Exact top－k keyword search on graph databases ［C］／／Taichung，Taiwan：SAC，2011：985－986.

［2］Ding Bolin，Jeffrey Xu Yu，Wang Shan，et al.Finding top－k min－cost connected trees in databases ［C］／／Istanbul：Data Engineering，2007：836－845.

［3］Liu F，Yu C，Meng W.Effective keyword search in relational databases［C］／／Chicago，Illinois，USA：The ACM SIGMOD International Conference on Manament of Data，2006：563－574.

［4］Luo Y，Lin X，Wang W.SPARK：Top－k keyword query in relational databases ［C］／／Cancun：ICDE，2007：115－126.

［5］Li G，Ooi B C，F(xiàn)eng J.EASE：An effective 3－in－1keyword search method for unstructured，semi－structured and structured data ［C］／／New York，NY，USA：SIGMOD，2008：903－914.

［6］Kasneci G，Ramanath M，Sozio M.STAR：Steiner－tree approximation in relationship graphs ［C］／／Shanghai，China：ICDE，2009：868－879.

［7］Günter Ladwig，Thanh Tran.Index structures and top－k join algorithms for native keyword search databases ［C］／／New York，NY，USA：ACM，2011：1505－1514.

［8］WANG Jiayi，YANG Luming，XIE Dong，et al.Ranking strategy of keyword search over relational databases ［J］.Computer Engineering and Design，2008，29 （10）：2566－2569 （in Chinese）.［王佳宜，楊路明，謝東，等.基于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查找排序策略 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（10）：2566－2569.］

［9］He H，Wang H，Yang J.BLINKS：Ranked keyword searches on graphs ［C］／／New York，NY，USA：Proceedings of the ACM SIGMOD International Conference on Management of Data，2007：305－316.

［10］Feng Jianhua，Guoliang L，Wang Jianyong.Finding top－k answers in keyword search over relational databases using tuple units ［J］.Knowledge and Data Engineering，2011，23（12）：1781－1794.