基于關系數據庫的關鍵詞查詢研究

摘要:關系數據庫關鍵詞查詢技術是目前數據庫和信息檢索領域研究的熱點問題之一，它所研究的主要問題是根據用戶提交的若干個查詢關鍵詞，從數據庫中查詢出相關的信息，應用這種技術使得普通用戶或者Web用戶可以有效地訪問關系數據庫。

關鍵詞:關系數據庫;關鍵詞;查詢

一、關系數據庫關鍵詞查詢概述

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

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

二、相關定義

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

定義2:關系數據庫模式圖Gs(Relational Database Schema Graph)假設Gs=(V，E)表示模式Sdb=(R，FK)的關系數據庫對應的模式圖。Gs是一個有向圖，將關系數據庫中的每一個關系模式Rk(1≤k≤n)看作是Gs的一個節點，當且僅當關系模式Ri∈Gs，關系模式Rj∈Gs，(Ri→Rj)∈FK時，(Ri，Rj)∈E。

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

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

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

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

三、體系結構

(1)系統設置系統啟動模塊，做一些系統初始化工作，如系統的參數配置

(2)模式圖生成器從系統配置文件讀入數據庫模式圖的模式配置信息，生成數據庫模式圖。

(3)用戶查詢該模塊為用戶查詢接口，接受用戶輸入的查詢關鍵詞，

提交后續模塊處理。

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

(5)候選網絡生成器候選網絡生成器利用元組集生成器生成的非自由元組集擴展模式圖，形成元組集圖，然后對該元組集圖進行擴展，生成結點不超過預定最大允許結點數的候選網絡。所謂候選網絡，也稱元組集連接樹，也是可以看做是要用來產生關鍵詞查詢潛在結果的JOIN表達式。

(6)候選網絡執行器候選網絡執行器完全執行所有候選網絡得到全部結果，或者采用某種top-k算法執行候選網絡，以得到top-k查詢結果。

四、查詢處理

系統啟動時，首先會生成數據庫模式圖，這個過程非常短，然后系統接收到用戶提交的查詢關鍵詞。當用戶提交查詢關鍵詞時，元組集生成器利用IR引擎生成元組集，然后，候選網絡產生器利用非自由元組集擴展Gs生成元組集圖，廣度優先遍歷元組集圖生成候選網絡，最后，候選網絡執行器執行全部候選網絡。或者采用某種top-k查詢算法執行候選網絡，生成最終查詢結果返回給用戶。通過介紹SDSG系統，可以發現SDSG系統存在的優點:數據庫模式圖占用內存少;缺點:候選網絡產生器執行效率低、候選網絡執行效率低、缺少語義查詢。

參考文獻

[1] 施伯樂，丁寶康，汪衛.數據庫系統教程.第二版.高等教育出版社，2003:1-359

[2] 文繼軍，王珊.SEEKER:基于關鍵詞的關系數據庫信息檢索.軟件學報，2005， 16(7):1270-1281

[3] 許建軍.對結構化和半結構化數據的關鍵詞查詢研究.[復旦大學博士學位論文]，2007:22-37

[4] 張坤龍.數據庫關鍵詞搜索的預處理新技術研究.[中國人民大學博士論文]，2005:35-72，93-95