潘 林
(青島港灣職業(yè)技術學院 山東 266404)
數(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ù)與概率直接的關系。
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上一個查詢。
在進行模式的自動映射時,可能會產(chǎn)生幾種候選的模式對應關系,每一種都有其出現(xiàn)的概率,其元組的概率分布情況分為兩類:
(1)在所有的數(shù)據(jù)上會采用一種相同的映射關系,稱為by-table 映射,這是本文所關注的。
(2)在源數(shù)據(jù)的關系中,會出現(xiàn)多個元組的子集采用不同的映射關系 稱為by-tuple映射。
當從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 概率
以下是對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},其中
假定以得分函數(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)=
首先本文采用樹結構來闡述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.