關(guān)鍵數(shù)據(jù)庫的關(guān)鍵詞查詢研究.pdf

1、隨著關(guān)系數(shù)據(jù)庫技術(shù)的發(fā)展，越來越多的數(shù)據(jù)存儲(chǔ)在關(guān)系數(shù)據(jù)庫中。關(guān)系數(shù)據(jù)庫已經(jīng)是當(dāng)前的數(shù)據(jù)庫主流形式，對關(guān)系數(shù)據(jù)庫的查詢技術(shù)也越來越重要。然而由于關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)化特點(diǎn)，對它的查詢需要采用結(jié)構(gòu)化查詢語言(SQL)，需要用戶學(xué)習(xí)復(fù)雜的結(jié)構(gòu)化查詢語言并且了解數(shù)據(jù)庫的模式。這對于一個(gè)沒有經(jīng)驗(yàn)的普通用戶來說顯然是一件困難的事情。因此，尋找一種新的關(guān)系數(shù)據(jù)庫信息查詢方式是近年來數(shù)據(jù)庫領(lǐng)域的研究熱點(diǎn)之一。
　　在關(guān)系數(shù)據(jù)庫關(guān)鍵詞查詢研究中，核心思

2、想大多是基于圖和簡化子樹的。根據(jù)簡化子樹的生成策略可以將關(guān)系數(shù)據(jù)庫關(guān)鍵詞查詢研究分為兩大類，即基于數(shù)據(jù)圖的方法和基于模式圖的方法，前者是直接對數(shù)據(jù)圖進(jìn)行處理，從數(shù)據(jù)圖中枚舉出簡化子樹，后者則是利用數(shù)據(jù)庫模式創(chuàng)建連接表達(dá)式，然后再在DBMS上執(zhí)行連接表達(dá)式所對應(yīng)的SQL語句得到簡化子樹。
　　本文研究中，采用了回溯法對數(shù)據(jù)圖進(jìn)行深度優(yōu)先搜索的方法來確定關(guān)鍵詞所對應(yīng)的元組信息。在基于數(shù)據(jù)庫的關(guān)鍵詞檢索中，將問題的解空間定義為數(shù)據(jù)庫的數(shù)

3、據(jù)圖結(jié)構(gòu)，由數(shù)據(jù)庫的元組構(gòu)成解空間圖的結(jié)點(diǎn)，元組間的主外鍵關(guān)系構(gòu)成圖中結(jié)點(diǎn)間的邊。用回溯法深度優(yōu)先搜索解空間得到問題的解，即與關(guān)鍵詞相關(guān)的查詢結(jié)果。回溯算法在搜索過程中并不在計(jì)算機(jī)中保存完整的解空間，而是同步地邊生成解答樹中的結(jié)點(diǎn)、邊檢查、邊丟棄結(jié)點(diǎn)，在搜索過程的任何時(shí)刻，僅保存從開始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)，從而減少了內(nèi)存的使用。同時(shí)，在結(jié)點(diǎn)上定義了剪枝函數(shù)，用以盡可能早的剪掉不可能包含問題解的結(jié)點(diǎn)，避免了搜索不必要的子空間，從而