數(shù)字圖書館聯(lián)盟中概率數(shù)據(jù)集成系統(tǒng)上的top-k查詢

潘 林

（青島港灣職業(yè)技術學院 山東 266404）

0 引言

數(shù)字圖書館是虛擬的圖書館，其目的是在網(wǎng)絡環(huán)境下構建共享的可擴展的知識網(wǎng)絡系統(tǒng)，提供超大規(guī)模的，分布式異構數(shù)字化信息的智能檢索和服務的知識中心[1]。

由于單一的數(shù)字圖書館提供的資源有限，不能滿足每個用戶的訪問需求，所以理想的方式是為用戶提供可以一次請求訪問多個數(shù)字圖書館資源的途徑。于是人們提出了聯(lián)盟數(shù)字圖書館（Digital Library Federation簡稱DLF）的概念[2]。

在一個數(shù)據(jù)集成的系統(tǒng)中，一個查詢在中介模式上提交后，查詢會產(chǎn)生若干帶有概率的重寫形式。這樣結果中的每個元組都會具有不同的概率，我們可以采用 top-k算法來獲得最近似的k個結果。在一個DLF中，最終用戶會希望獲得結果中最符合其偏好且概率最高的結果。這樣，在傳統(tǒng)的 top-k算法中，需要同時考慮依據(jù)偏好形成的得分函數(shù)與概率直接的關系。

1 數(shù)字圖書館聯(lián)盟DLF的概率的信息集成模型

Lenzerini 等[3]提出了一種數(shù)據(jù)集成的理論模型，基于該模型，本文定義了概率性的數(shù)據(jù)集成模型，其形式化描述如下：

一個數(shù)據(jù)集成系統(tǒng)Δ 是一個四元組 ，

其中G是全局模式，用使用了一組相關字母表Ag的邏輯理論來表達

S是源數(shù)據(jù)的模式，用使用了一組相關字母表As的邏輯理論來表達

對于映射mi∈M來說，我們可以定義為屬性的對應關系，一個屬性對應可表達為Cij=（Si，Ti），其中Si是模式S中一個源屬性，Ti是模式T中一個目標屬性。

在圖書館聯(lián)盟中，由于每個DL的自治性，適于利用LAV表達映射關系，其形式化描述為：

? x( s( x) → qg( x ))當qg?s時

? x( s( x) ≡ qg( x ))當 g≡qs

? x( q g( x) →s( x ))當s ? qg時

其中s是S的一個元素，gq 是在G上一個查詢。

2 模式映射的概率

2.1 映射的概率

在進行模式的自動映射時，可能會產(chǎn)生幾種候選的模式對應關系，每一種都有其出現(xiàn)的概率，其元組的概率分布情況分為兩類：

（1）在所有的數(shù)據(jù)上會采用一種相同的映射關系，稱為by-table 映射，這是本文所關注的。

（2）在源數(shù)據(jù)的關系中，會出現(xiàn)多個元組的子集采用不同的映射關系 稱為by-tuple映射。

2.2 查詢

當從G上提交查詢時，會按照各種映射形式形成多個查詢的重寫形式，對于每個返回的結果，其概率是不同的。

對于在G上的一個查詢Q，按照其與某個局部模式S可能會有的映射形式，可重寫成 Q….Q，對于 Q（ i ∈ [1,k]）中的元組 t∈ans（ Q），t有如下形式 t={t1，….tj}， t1∈ R，… t j ∈ R， R（ λ∈[1，j]）為與t相關的具有概率的關系模式，我們定義與t相關的布爾表達式：

即Q的查詢結果中每個元組的概率為包含該元組的查詢重寫的概率之和。

根據(jù)計算，我們得出如下的圖示：

圖1 概率

3 Top-k 查詢回答

3.1 U-kRanks查詢的定義

以下是對U-kRanks的定義：

D為一個具有可能的實例集I= {I1，I2，….In}的概率數(shù)據(jù)庫，且∑r(Ii)=1。對于i=1….k，讓{ t，… t}為一個元組集，其中每個元組會在一個非空的實例I（）中根據(jù)得分函數(shù)F出現(xiàn)在位置i。一個在F上的U-kRanks查詢，會返回結果{ t*； i=1….k}，其中

3.2 狀態(tài)的概率的定義

假定以得分函數(shù)F訪問一個數(shù)據(jù)庫D，在訪問了m個元組后，這些元組會形成若干個狀態(tài)，設sm，l為其某個狀態(tài)，其中l(wèi)（l<=m）個元組出現(xiàn)在該狀態(tài)中，表示為sl，未出現(xiàn)的（m-l）個元組表示為 Im，則狀態(tài) sm，l的概率為 ρ（sm，l）=Pr（sl∩ ls?），例如假若已經(jīng)檢索出的元組為{t1，t2，t3，t4}，對于其中某個狀態(tài)s（4，3）=，可計算其概率為ρ（s4，3）＝Pr（{t1，t2，t3，t4}∩?{t3}）= Pr（t1∧t2∧?t3∧t4）= Pr（t1）*Pr（t2）*Pr（?t3）*Pr（t4）.

3.3 利用狀態(tài)樹對opt_U-kRanks算法的討論

首先本文采用樹結構來闡述opt_U-kRanks查詢。假設得分排序的元組向量為（t1，t2....tn）（見圖1），每個節(jié)點代表一種具有一定概率的狀態(tài)，其值代表了該狀態(tài)的長度，即位次。節(jié)點i和j組成的邊表明通過添加一個新的元組狀態(tài)（出現(xiàn)或不出現(xiàn)），狀態(tài)i可以變成另一個狀態(tài)j。形如t1t2....ti的從根節(jié)點到一個非根節(jié)點i的路徑正好表達了狀態(tài)i。

圖2 狀態(tài)數(shù)

如圖1表示了位置（rank）為3，當前元組集為{t1，t2，t3，t4}時的狀態(tài)圖，根到虛線矩形內的元素形成的路徑為符合要求的狀態(tài)集即{t1，t2，?t3，t4}{t1，?t2，t3，t4}{?t1，t2，t3，t4}，新加入的元組可在剩余的路徑中形成符合要求的狀態(tài)集（即根到虛線橢圓內元素形成的路徑）

當新元組t5后，位置（rank）為3時符合要求的狀態(tài)都是從根到虛線橢圓內元素形成的路徑集合中選擇子集加入新元素（元組t5）后形成的

正如圖2描述，虛線矩形內的節(jié)點表示了排序元素個數(shù)為3的狀態(tài)，橢圓內節(jié)點表示了加入元組t4后排序元素個數(shù)小于3（包括0，1，2）的節(jié)點。從圖中可以看出，只有在長度為i-1的狀態(tài)上添加元組t才能保證其出現(xiàn)在排序i上。這時我們可以計算t4按照排序函數(shù)出現(xiàn)在位置3的概率為：

根據(jù)圖1，我們可以推到一個可使計算快速收斂的不等式。

對于位置k，由于任何一個事件的概率都不會大于1，所以在圖1中有 P5,3<= S= ∑ ρ(s4,2)。

不失一般性，對于任意元組 tm，不等式 Pm,k<= S=∑ρ(sm?1,k?1)（k is a rank position）都是成立的。如果我們要求tm為在排序位k時的概率，我們應該保證,mkP 是所有的里面最大者。從前面的討論，我們也可以推斷出即使用如所提出的Pm,k> S代替 Pm,k> Pm+1,k的方案，也不能保證 Pm,k比 Pm+2,k'or....or,nkP （n>i）大。下面，我們來簡化該不等式。

如圖1所描述的，我們有：

當k>=2時，我們有：

當k=1時，我們有：

綜上，我們可以得到一個近似的條件，即Pr（tm）>= 1/2，該條件可快速評估tm是否是在位置上的適合的解。

[1]E.A.Fox.Source Book on Digital Libraries.Technical Report TR-93-35 Virginia Polytechnic Institute and State University，1993.

[2]S.P.Harter.W hat is a Digital Library? Definitions，Content，and Issues.In KOLISS，1996.

[3]Birm ingham B.，et al.EU-NSF digital library working group on interoperability between digital libraries.http：//www.iei.pi.cnr.it/DELOS/NSF/interop.htm，2001-10-15.