關(guān)系數(shù)據(jù)庫(kù)對(duì)象級(jí)別檢索結(jié)果相關(guān)性排序算法研究

裴祥喜，李 珉，崔炳德，崔 晶，馮 濤，楊洪俠

（1.河北工程技術(shù)高等專(zhuān)科學(xué)校，河北 滄州 061001；2.滄州市產(chǎn)權(quán)交易中心，河北 滄州 061001）

近年來(lái)，由于關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞檢索可以大大提高關(guān)系數(shù)據(jù)庫(kù)的易用性，從而引起了國(guó)內(nèi)外專(zhuān)家學(xué)者的密切關(guān)注。然而關(guān)系數(shù)據(jù)庫(kù)與網(wǎng)絡(luò)不同，其有自身獨(dú)特的結(jié)構(gòu)特點(diǎn)，因此實(shí)現(xiàn)關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞檢索還有一定的難度。本文重點(diǎn)針對(duì)關(guān)系數(shù)據(jù)庫(kù)元組檢索、對(duì)象構(gòu)建以及相關(guān)性評(píng)估等，對(duì)相關(guān)性排序算法的實(shí)現(xiàn)進(jìn)行了簡(jiǎn)要說(shuō)明。

1 關(guān)系數(shù)據(jù)庫(kù)分析

關(guān)系數(shù)據(jù)庫(kù)是一種應(yīng)用數(shù)學(xué)集合概念的數(shù)據(jù)庫(kù)模型，并且用集合的方法來(lái)處理數(shù)據(jù)庫(kù)中的數(shù)據(jù)。從構(gòu)成結(jié)構(gòu)上看，可以將關(guān)系數(shù)據(jù)庫(kù)看成是一個(gè)具備描述性功能的表格，在這個(gè)表格中每一列代表一種數(shù)據(jù)種類(lèi)，而每一行則包含著這類(lèi)數(shù)據(jù)的唯一實(shí)體，總結(jié)起來(lái)關(guān)系數(shù)據(jù)庫(kù)就是由數(shù)據(jù)實(shí)體集合而構(gòu)成的一個(gè)應(yīng)用領(lǐng)域。與網(wǎng)絡(luò)相比關(guān)系數(shù)據(jù)庫(kù)有其獨(dú)特之處：

（1）關(guān)系數(shù)據(jù)庫(kù)中由數(shù)據(jù)實(shí)體組成的元組之間存在一定關(guān)系。

（2）數(shù)據(jù)庫(kù)中的文本少則是一個(gè)單詞、數(shù)字，多則是一句短語(yǔ)，與網(wǎng)絡(luò)文本相比關(guān)系數(shù)據(jù)庫(kù)中的文本多是短文本。由于短文本中單詞或者數(shù)據(jù)出現(xiàn)頻率很低，因此這種短文本并不適合關(guān)鍵詞頻率檢索，增加了關(guān)系數(shù)據(jù)庫(kù)信息檢索的難度。

（3）關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)屬性值之間隱藏有一定傳遞關(guān)系，同時(shí)數(shù)據(jù)屬性值的大小在很大程度上影響著相關(guān)性排序。

從以上分析中可以看出，依靠文本關(guān)鍵詞出現(xiàn)頻率對(duì)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行檢索是不現(xiàn)實(shí)的，因此借鑒短文本的分類(lèi)方法對(duì)關(guān)系數(shù)據(jù)數(shù)據(jù)庫(kù)中短文本進(jìn)行相關(guān)性排序，然后按照相關(guān)性的大小依照檢索要求選擇想要的文本。這種思路便是關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞檢索的核心思路，同時(shí)也是數(shù)據(jù)庫(kù)領(lǐng)域研究研究的熱點(diǎn)。然而，實(shí)現(xiàn)這一思路的關(guān)鍵在于設(shè)計(jì)一套適合關(guān)系數(shù)據(jù)庫(kù)特點(diǎn)的信息檢索相關(guān)性排序算法。

2 信息檢索的相關(guān)性排序

信息檢索是指通過(guò)一定的方法在指定數(shù)據(jù)庫(kù)或者其他數(shù)據(jù)集合中找出符合用戶要求數(shù)據(jù)資料的過(guò)程。通常情況下進(jìn)行信息檢索的方法是關(guān)鍵詞檢索，但是在實(shí)際中這種檢索方法并不精確且經(jīng)常出現(xiàn)疏漏，如何提高信息檢索方法的精確性一直都是相關(guān)研究學(xué)者關(guān)注的重點(diǎn)。

然而在實(shí)際信息檢索過(guò)程中只能找到與用戶要求文檔相關(guān)的資料，并且這些資料有很多，為確保資料能夠最大限度接近用戶要求，還需要對(duì)所檢索出的相關(guān)文檔進(jìn)行相關(guān)性排序，優(yōu)先將相關(guān)度最高的文檔提供給用戶。這里便涉及到相關(guān)性排序計(jì)算模型。

2.1 概率計(jì)算模型

計(jì)算一個(gè)關(guān)鍵詞在相關(guān)文檔和不相關(guān)文檔中出現(xiàn)的概率，對(duì)該詞的權(quán)重進(jìn)行估計(jì)，然后依據(jù)關(guān)鍵詞權(quán)重對(duì)文檔與查詢相關(guān)的概率進(jìn)行計(jì)算，最終對(duì)查詢文檔進(jìn)行相關(guān)性排序。概率計(jì)算模型是基于二元值與檢索詞獨(dú)立的假設(shè)，因而具有比較理想的調(diào)整權(quán)值，但這種模型沒(méi)有考慮采用查詢式擴(kuò)展、沒(méi)有考慮到文檔詞頻特性，同時(shí)也忽略了上次查詢對(duì)檢索詞概率的影響，因此該模型在實(shí)際中的應(yīng)用效果并不好。

2.2 向量空間模型

分別將文檔中的詞語(yǔ)以及查詢結(jié)果看成是一個(gè)向量，這樣對(duì)文檔詞語(yǔ)向量與查詢結(jié)果向量進(jìn)行相關(guān)度分析，從而對(duì)查詢結(jié)果進(jìn)行相關(guān)性排序。向量空間模型是一種經(jīng)典的相關(guān)性排序算法，并且其原理簡(jiǎn)單，直觀易懂，容易掌握，然而該模型難以確定標(biāo)引詞權(quán)值，并且需要計(jì)算大量相似度，導(dǎo)致系統(tǒng)運(yùn)行速度受到影響。

2.3 鏈接分析計(jì)算模型

鏈接分析是互聯(lián)網(wǎng)搜索依賴的重要計(jì)算模型，其理論依據(jù)是根據(jù)某一網(wǎng)頁(yè)被其它網(wǎng)頁(yè)所重視的程度來(lái)對(duì)查詢網(wǎng)頁(yè)進(jìn)行相關(guān)性排序。這種計(jì)算模型基于一個(gè)普遍的觀點(diǎn)：B網(wǎng)頁(yè)的超鏈接指向了A網(wǎng)頁(yè)，那么就認(rèn)為B網(wǎng)頁(yè)投了A網(wǎng)頁(yè)一票，即B網(wǎng)頁(yè)認(rèn)為A網(wǎng)頁(yè)比較重要。這種計(jì)算模型采用的算法主要是Page Rank算法。

3 對(duì)象級(jí)別關(guān)系數(shù)據(jù)庫(kù)信息檢索的相關(guān)性排序算法研究

3.1 關(guān)系數(shù)庫(kù)信息檢索相關(guān)性排序算法

隨著社會(huì)科技的發(fā)展，關(guān)系數(shù)據(jù)庫(kù)信息檢索相關(guān)性排序方面出現(xiàn)了一系列包括BANKS算法、RETLINE算法、Object Su mmary算法等在內(nèi)的排序算法，極大的推動(dòng)了關(guān)系數(shù)據(jù)庫(kù)的應(yīng)用普及。雖然這些算法只能進(jìn)行元組級(jí)別關(guān)系數(shù)據(jù)庫(kù)信息檢索相關(guān)性排序，但是研究這些算法對(duì)研究對(duì)象級(jí)別數(shù)據(jù)庫(kù)相關(guān)性排序算法有積極的借鑒意義。在這些關(guān)系數(shù)據(jù)信息檢索相關(guān)性排序算法中，尤其以BANKS算法最為經(jīng)典，再加上該算法結(jié)果更符合用戶要求，下面以BANKS算法為例進(jìn)行簡(jiǎn)單分析。

BANKS算法是一種典型的元組級(jí)相關(guān)性排序算法，用戶通過(guò)算法利用關(guān)鍵詞對(duì)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行檢索而不需要掌握關(guān)系數(shù)據(jù)庫(kù)知識(shí)以及相關(guān)查詢語(yǔ)句。這種算法的工作原理是：將元組看成一個(gè)個(gè)結(jié)點(diǎn)，通過(guò)對(duì)結(jié)點(diǎn)屬性值的分析查看結(jié)點(diǎn)是否符合搜索要求。若結(jié)點(diǎn)符合要求便將結(jié)點(diǎn)提取出來(lái)，由于提取包含關(guān)鍵詞的結(jié)點(diǎn)有很多，因此檢索結(jié)果就是眾多結(jié)點(diǎn)組成的集合。此時(shí)為使結(jié)果更加符合用戶要求，還需要對(duì)所提取的結(jié)點(diǎn)進(jìn)行相關(guān)性排序。

3.2 對(duì)象級(jí)別的關(guān)系數(shù)據(jù)庫(kù)信息檢索相關(guān)性排序方法

3.2.1 關(guān)系數(shù)據(jù)庫(kù)對(duì)象的構(gòu)建

對(duì)象級(jí)別的數(shù)據(jù)庫(kù)檢索要比元組級(jí)別的數(shù)據(jù)檢索更加詳細(xì)精確，因?yàn)樵M級(jí)別的數(shù)據(jù)檢索結(jié)果只是一個(gè)個(gè)單獨(dú)的包含關(guān)鍵詞的元組，元組之間的關(guān)系并沒(méi)有得到體現(xiàn)，從而導(dǎo)致信息過(guò)于分散，一些信息出現(xiàn)丟失，因此搜索結(jié)果的準(zhǔn)確性得不到保障。

進(jìn)行對(duì)象構(gòu)建的目的就是將各元組中的分散信息進(jìn)行整合，以對(duì)象為單位進(jìn)行數(shù)據(jù)搜索，從而使得關(guān)系數(shù)據(jù)庫(kù)的信息檢索更加符合其自身的結(jié)構(gòu)化特點(diǎn)。

在進(jìn)行對(duì)象構(gòu)建時(shí)，首先要做的是統(tǒng)計(jì)包含關(guān)鍵詞的元組所在的數(shù)據(jù)表，其次將數(shù)據(jù)表通過(guò)數(shù)據(jù)庫(kù)主外鍵聯(lián)系起來(lái)，從而明確數(shù)據(jù)表以及元組之間的關(guān)系，最后得到與搜索目標(biāo)相關(guān)的對(duì)象。

3.2.2 構(gòu)建對(duì)象規(guī)模以及重要性分析

通過(guò)對(duì)對(duì)象級(jí)別數(shù)據(jù)庫(kù)的分析發(fā)現(xiàn)，對(duì)象規(guī)模以及重要性在很大程度上影響著檢索結(jié)構(gòu)相關(guān)性排序結(jié)果，因此有必要分析數(shù)據(jù)庫(kù)對(duì)象的規(guī)模與重要性。由于元組的規(guī)模以及重要性是影響對(duì)象規(guī)模和重要性的關(guān)鍵因素，因此需要對(duì)元組數(shù)量規(guī)模以及結(jié)點(diǎn)間邊重要性進(jìn)行計(jì)算。

（1）元組數(shù)量規(guī)模的計(jì)算。在對(duì)象級(jí)別的數(shù)據(jù)庫(kù)檢索中元組數(shù)量規(guī)模會(huì)直接影響到對(duì)象規(guī)模。通常情況下元組規(guī)模越大對(duì)象規(guī)模越大，對(duì)象包含的信息越多，搜索結(jié)構(gòu)也就越準(zhǔn)確。但是，元組規(guī)模過(guò)大會(huì)造成對(duì)象中包含過(guò)多無(wú)用信息，從而干擾搜索結(jié)果的準(zhǔn)確性。因此相關(guān)性排序方法在計(jì)算元組數(shù)量規(guī)模時(shí)要將其控制在合適的范圍內(nèi)，計(jì)算公式為：

式中：nmax為最大規(guī)模的對(duì)象中包含的元組數(shù)量。

（2）元組結(jié)點(diǎn)重要性的計(jì)算。對(duì)象級(jí)別數(shù)據(jù)檢索相關(guān)排序算法更加注重分析相關(guān)元組內(nèi)部屬性之間的關(guān)系，從而對(duì)元組結(jié)點(diǎn)的重要性進(jìn)行重新計(jì)算。這樣計(jì)算重要性的方式可以避免因不含關(guān)鍵詞而遺漏的與搜索目標(biāo)相關(guān)的元組，從而提高搜索結(jié)果的準(zhǔn)確性。元組結(jié)點(diǎn)重要性的計(jì)算主要集中以下幾個(gè)方面：評(píng)估相關(guān)元組內(nèi)部屬性值與關(guān)鍵詞的聯(lián)系，而不是只注重元組之間的關(guān)系分析，并且通過(guò)分析可以推斷出元組內(nèi)部屬性值之間存在的傳遞關(guān)系。該算法不但評(píng)估屬性值與關(guān)鍵詞的相關(guān)性，而且還評(píng)估兩者之間的相似性，從而使搜索結(jié)果更加精確；通過(guò)信息熵分配元組屬性權(quán)值，從而計(jì)算出相關(guān)性最高以及相關(guān)性最低的元組屬性值。

（3）元組間邊計(jì)算。由于對(duì)象是由元組通過(guò)相關(guān)關(guān)系連接而成的，而元組之間的關(guān)系可以被看做是元組之間的有向邊，因此在計(jì)算對(duì)象的重要性時(shí)不能忽略元組間邊的重要性分析。在分析元組間邊重要性時(shí)，該算法主要集中計(jì)算分析間邊的類(lèi)型數(shù)量、間邊方向以及間邊兩端的結(jié)點(diǎn)等。

通過(guò)以上三點(diǎn)的分析可以總結(jié)出計(jì)算對(duì)象重要性的總公式：

式中：α作為調(diào)節(jié)因子負(fù)責(zé)控制元組與間邊的相對(duì)重要性。

4 結(jié)語(yǔ)

對(duì)象級(jí)別關(guān)系數(shù)據(jù)庫(kù)信息檢索相關(guān)排序算法的研究是現(xiàn)階段數(shù)據(jù)庫(kù)信息檢索研究的重點(diǎn)，受到眾多研究學(xué)者的關(guān)注并且取得了一定成就。本文率先對(duì)關(guān)系數(shù)據(jù)庫(kù)的定義、結(jié)構(gòu)特點(diǎn)以及信息檢索的相關(guān)排序進(jìn)行了詳細(xì)分析，然后在此基礎(chǔ)上對(duì)對(duì)象級(jí)關(guān)系數(shù)據(jù)庫(kù)信息檢索相關(guān)排序算法進(jìn)行了系統(tǒng)研究，為排序算法的實(shí)現(xiàn)提供了理論參考。

［1］ 張俊，邵仁俊，曾一鳴.對(duì)象級(jí)別的關(guān)系數(shù)據(jù)庫(kù)信息檢索技術(shù)研究［J］.計(jì)算機(jī)科學(xué)，2012，39（1）：142－145.

［2］ 鄧承剛，張俊，劉寧.基于屬性值分布的關(guān)系數(shù)據(jù)庫(kù)對(duì)象級(jí)別檢索結(jié)果排序算法［J］.計(jì)算機(jī)科學(xué)，2013，40（3）：219－223.

［3］ 邵仁俊，張俊，曾一鳴.DBORank：對(duì)象級(jí)別的關(guān)系數(shù)據(jù)庫(kù)信息檢索方法［J］.計(jì)算機(jī)科學(xué)與探索，2012，6（8）：742－744.