基于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢研究

摘要:關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢技術(shù)是目前數(shù)據(jù)庫(kù)和信息檢索領(lǐng)域研究的熱點(diǎn)問題之一，它所研究的主要問題是根據(jù)用戶提交的若干個(gè)查詢關(guān)鍵詞，從數(shù)據(jù)庫(kù)中查詢出相關(guān)的信息，應(yīng)用這種技術(shù)使得普通用戶或者Web用戶可以有效地訪問關(guān)系數(shù)據(jù)庫(kù)。

關(guān)鍵詞:關(guān)系數(shù)據(jù)庫(kù);關(guān)鍵詞;查詢

一、關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢概述

關(guān)系數(shù)據(jù)庫(kù)通常通過結(jié)構(gòu)化查詢語言SQL來訪問。SQL訪問方式不但要求用戶知道并理解關(guān)系數(shù)據(jù)庫(kù)模式，也要懂得書寫復(fù)雜的SQL查詢語言，因此，它一般適合于專業(yè)用戶使用。普通用戶一般通過定制的關(guān)系數(shù)據(jù)庫(kù)查詢接口程序RQI(Relational databases Query Interface)或者關(guān)系數(shù)據(jù)庫(kù)應(yīng)用程序RAP(Relational databases Application Program)來訪問關(guān)系數(shù)據(jù)庫(kù)。RQI訪問方式雖然不要求用戶書寫復(fù)雜SQL查詢語言，但是要求用戶知道并理解關(guān)系數(shù)據(jù)庫(kù)模式，對(duì)于不同的關(guān)系數(shù)據(jù)庫(kù)需要使用不同的RQI，而且定制的RQI也往往不能滿足靈活多變的用戶查詢需求，當(dāng)RQI不能滿足用戶查詢需求時(shí)，就需要應(yīng)用開發(fā)人員來修改RQI，由此，使用RQI訪問方式則需要較高的開發(fā)費(fèi)用和維護(hù)費(fèi)用。

隨著Internet和Web技術(shù)的快速發(fā)展和應(yīng)用，一方面用戶越來越習(xí)慣于使用簡(jiǎn)單的查詢關(guān)鍵詞通過Web搜索引擎如Google，Baidu等來搜索信息;另一方面，越來越多的關(guān)系數(shù)據(jù)庫(kù)發(fā)布到Web上面向廣大普通用戶，形成所謂的“Deep Web”問題，使得普通用戶也期望能夠使用簡(jiǎn)單的關(guān)鍵詞來查詢關(guān)系數(shù)據(jù)庫(kù)數(shù)據(jù)。

二、相關(guān)定義

定義1:關(guān)系數(shù)據(jù)庫(kù)模式Sdb(Relational Database Schema)假設(shè)關(guān)系數(shù)據(jù)庫(kù)的模式，Sdb=(R，F(xiàn)K)，R={R1，R2，…，Rk}是一組關(guān)系模式，F(xiàn)K是R中關(guān)系模式間引用關(guān)系的映射，F(xiàn)K:R→R，如果FK(Ri)=Rj，記為Ri→Rj(1≤i，j≤n)，它表示Rj一個(gè)外鍵引用了Ri主鍵。

定義2:關(guān)系數(shù)據(jù)庫(kù)模式圖Gs(Relational Database Schema Graph)假設(shè)Gs=(V，E)表示模式Sdb=(R，F(xiàn)K)的關(guān)系數(shù)據(jù)庫(kù)對(duì)應(yīng)的模式圖。Gs是一個(gè)有向圖，將關(guān)系數(shù)據(jù)庫(kù)中的每一個(gè)關(guān)系模式Rk(1≤k≤n)看作是Gs的一個(gè)節(jié)點(diǎn)，當(dāng)且僅當(dāng)關(guān)系模式Ri∈Gs，關(guān)系模式Rj∈Gs，(Ri→Rj)∈FK時(shí)，(Ri，Rj)∈E。

定義3:連接元組樹Jt(Joning Tree of Tuples)給定一個(gè)關(guān)系數(shù)據(jù)庫(kù)的模式圖Gs=(V，E)，Jt是以數(shù)據(jù)庫(kù)中的元組tl為結(jié)點(diǎn)的一棵樹，其中tl(1≤l≤m)是關(guān)系rk(1≤k≤m)中元組，關(guān)系rk(1≤k≤m)是關(guān)系模式Rk(1≤k≤n)上的實(shí)例，如果(Ri，Rj)∈E且(ti tj)∈(ri rj)，那么，(ti，tj)是Jt的一條邊，其中ti∈ri，tj∈rj，(1≤i， j≤n)，稱Jt為一棵連接元組樹。

定義4:關(guān)鍵詞查詢Kq(Keyword Query)把關(guān)鍵詞查詢定義為查詢函數(shù)f:Kq→T，其中Kq是一個(gè)集合，其元素ki(1≤i≤m)為關(guān)鍵詞，T是一個(gè)集合，其元素Jti(1≤i≤n)為一個(gè)關(guān)鍵詞查詢結(jié)果。

定義5:關(guān)鍵詞查詢結(jié)果T(Keywords Qeury Results)關(guān)鍵詞查詢結(jié)果是OR語義，Kq是一個(gè)集合，其元素為ki(1≤i≤m)為關(guān)鍵詞，一個(gè)查詢結(jié)果是至少含有Kq中一個(gè)ki(1≤i≤m)且每個(gè)葉結(jié)點(diǎn)都至少含有Kq中一個(gè)ki(1≤i≤m) 的連接元組樹。

關(guān)鍵詞查詢結(jié)果是AND語義，Kq是一個(gè)集合，其元素為ki(1≤i≤m)為關(guān)鍵詞，一個(gè)查詢結(jié)果是Kq中的每一個(gè)的關(guān)鍵詞ki(1≤i≤m)都必須出現(xiàn)在結(jié)果中，并且每個(gè)葉子節(jié)點(diǎn)都至少含有一個(gè)Kq中的關(guān)鍵詞ki(1≤i≤m)的連接元組樹。

三、體系結(jié)構(gòu)

(1)系統(tǒng)設(shè)置系統(tǒng)啟動(dòng)模塊，做一些系統(tǒng)初始化工作，如系統(tǒng)的參數(shù)配置

(2)模式圖生成器從系統(tǒng)配置文件讀入數(shù)據(jù)庫(kù)模式圖的模式配置信息，生成數(shù)據(jù)庫(kù)模式圖。

(3)用戶查詢?cè)撃K為用戶查詢接口，接受用戶輸入的查詢關(guān)鍵詞，

提交后續(xù)模塊處理。

(4)元組集生成器該模塊利用由關(guān)系數(shù)據(jù)庫(kù)的全文檢索功能建立的IR引擎，將關(guān)系數(shù)據(jù)庫(kù)中具有文本屬性的每個(gè)關(guān)系生成元組集，只有那些與某個(gè)查詢關(guān)鍵詞或者查詢關(guān)鍵詞組合相關(guān)的非空的元組集保留下來，稱為非自由元組集，每個(gè)非自由元組集都是其源表(即生成該元組集的表)的一個(gè)子集，每個(gè)非自由元組集實(shí)際上也是一個(gè)臨時(shí)表，繼承其源表的主外鍵關(guān)系。

(5)候選網(wǎng)絡(luò)生成器候選網(wǎng)絡(luò)生成器利用元組集生成器生成的非自由元組集擴(kuò)展模式圖，形成元組集圖，然后對(duì)該元組集圖進(jìn)行擴(kuò)展，生成結(jié)點(diǎn)不超過預(yù)定最大允許結(jié)點(diǎn)數(shù)的候選網(wǎng)絡(luò)。所謂候選網(wǎng)絡(luò)，也稱元組集連接樹，也是可以看做是要用來產(chǎn)生關(guān)鍵詞查詢潛在結(jié)果的JOIN表達(dá)式。

(6)候選網(wǎng)絡(luò)執(zhí)行器候選網(wǎng)絡(luò)執(zhí)行器完全執(zhí)行所有候選網(wǎng)絡(luò)得到全部結(jié)果，或者采用某種top-k算法執(zhí)行候選網(wǎng)絡(luò)，以得到top-k查詢結(jié)果。

四、查詢處理

系統(tǒng)啟動(dòng)時(shí)，首先會(huì)生成數(shù)據(jù)庫(kù)模式圖，這個(gè)過程非常短，然后系統(tǒng)接收到用戶提交的查詢關(guān)鍵詞。當(dāng)用戶提交查詢關(guān)鍵詞時(shí)，元組集生成器利用IR引擎生成元組集，然后，候選網(wǎng)絡(luò)產(chǎn)生器利用非自由元組集擴(kuò)展Gs生成元組集圖，廣度優(yōu)先遍歷元組集圖生成候選網(wǎng)絡(luò)，最后，候選網(wǎng)絡(luò)執(zhí)行器執(zhí)行全部候選網(wǎng)絡(luò)。或者采用某種top-k查詢算法執(zhí)行候選網(wǎng)絡(luò)，生成最終查詢結(jié)果返回給用戶。通過介紹SDSG系統(tǒng)，可以發(fā)現(xiàn)SDSG系統(tǒng)存在的優(yōu)點(diǎn):數(shù)據(jù)庫(kù)模式圖占用內(nèi)存少;缺點(diǎn):候選網(wǎng)絡(luò)產(chǎn)生器執(zhí)行效率低、候選網(wǎng)絡(luò)執(zhí)行效率低、缺少語義查詢。

參考文獻(xiàn)

[1] 施伯樂，丁寶康，汪衛(wèi).數(shù)據(jù)庫(kù)系統(tǒng)教程.第二版.高等教育出版社，2003:1-359

[2] 文繼軍，王珊.SEEKER:基于關(guān)鍵詞的關(guān)系數(shù)據(jù)庫(kù)信息檢索.軟件學(xué)報(bào)，2005， 16(7):1270-1281

[3] 許建軍.對(duì)結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)的關(guān)鍵詞查詢研究.[復(fù)旦大學(xué)博士學(xué)位論文]，2007:22-37

[4] 張坤龍.數(shù)據(jù)庫(kù)關(guān)鍵詞搜索的預(yù)處理新技術(shù)研究.[中國(guó)人民大學(xué)博士論文]，2005:35-72，93-95