Web 大數(shù)據(jù)系統(tǒng)數(shù)據(jù)源選擇*

劉正濤，王建東

1.三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210012

2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

1 引言

在Web大數(shù)據(jù)系統(tǒng)中，一般包含大量的異構(gòu)數(shù)據(jù)源，這些數(shù)據(jù)源將形成Web大數(shù)據(jù)系統(tǒng)的多個(gè)參與者，這些參與者在數(shù)據(jù)類型、數(shù)據(jù)元素的命名、數(shù)據(jù)的約束與限制等方面都是獨(dú)立的，并且在操作執(zhí)行與通信時(shí)，這些參與者也是獨(dú)立的。為了能夠同時(shí)訪問多個(gè)Web數(shù)據(jù)源，Web數(shù)據(jù)集成系統(tǒng)必須對(duì)查詢接口進(jìn)行集成。當(dāng)有了統(tǒng)一的訪問接口后，如果只是把集成接口上的用戶提交查詢簡單地轉(zhuǎn)換成一個(gè)領(lǐng)域的每個(gè)Web數(shù)據(jù)源上的查詢，顯然是不可行的。因?yàn)檫@樣操作存在以下問題：（1）查詢花費(fèi)的代價(jià)太高；（2）不是Web上每個(gè)數(shù)據(jù)源都能提供高質(zhì)量的查詢結(jié)果；（3）由于Web數(shù)據(jù)源返回結(jié)果之間存在大量冗余，查詢的數(shù)據(jù)源數(shù)量越多，冗余度也會(huì)越大。基于以上原因，Web數(shù)據(jù)源選擇成為Web大數(shù)據(jù)系統(tǒng)集成中的一個(gè)關(guān)鍵問題。把查詢提交給很少量的數(shù)據(jù)源，但又要求返回的結(jié)果能夠很好地滿足用戶的特定需求，是數(shù)據(jù)源選擇的理想目標(biāo)。針對(duì)不同的用戶集成需求，Web數(shù)據(jù)源的選擇方法各異。由于Web大數(shù)據(jù)集成系統(tǒng)需提供與查詢相關(guān)且高質(zhì)量的檢索結(jié)果給用戶，從而研究人員主要依據(jù)數(shù)據(jù)源與查詢的相關(guān)性以及數(shù)據(jù)源本身質(zhì)量來進(jìn)行Web數(shù)據(jù)源選擇的相關(guān)研究。

傳統(tǒng)數(shù)據(jù)集成系統(tǒng)一般假定需要集成的數(shù)據(jù)源之間是相互獨(dú)立的。然而，在處理一個(gè)查詢所需要的大量Web數(shù)據(jù)源中，不同Web數(shù)據(jù)源中的數(shù)據(jù)存在著大量的重復(fù)記錄，同時(shí)還存在著一些數(shù)據(jù)源從其他數(shù)據(jù)源拷貝了部分或全部數(shù)據(jù)的現(xiàn)象。數(shù)據(jù)源之間的數(shù)據(jù)相互覆蓋與數(shù)據(jù)依賴將對(duì)數(shù)據(jù)源數(shù)據(jù)質(zhì)量的評(píng)估、數(shù)據(jù)源排序及不同數(shù)據(jù)源的數(shù)據(jù)融合產(chǎn)生重要的影響。

本文主要目標(biāo)是根據(jù)Web數(shù)據(jù)源的一些特征，從大量的數(shù)據(jù)源中選擇k個(gè)質(zhì)量適合并且與用戶查詢相關(guān)的數(shù)據(jù)源，以最少的時(shí)間代價(jià)滿足用戶的查詢需求。本文的創(chuàng)新與貢獻(xiàn)如下：

（1）提出了一個(gè)兩階段數(shù)據(jù)源選擇方案。第一階段通過各個(gè)數(shù)據(jù)源模式與中間模式的相似度選擇與查詢相關(guān)度高的數(shù)據(jù)源，通過計(jì)算依賴數(shù)據(jù)源的質(zhì)量來選取質(zhì)量較好的數(shù)據(jù)源；第二階段基于最大熵理論計(jì)算數(shù)據(jù)源之間的重復(fù)率，選擇查詢效率最高的數(shù)據(jù)源。

（2）改進(jìn)了ACCUNOD（accuracy of node）算法，在算法中加入了數(shù)據(jù)源之間依賴關(guān)系的考量，提出了一個(gè)新算法定義數(shù)據(jù)源的可信度。

（3）提出了最小代價(jià)查詢模型，運(yùn)用最大熵原理計(jì)算不同數(shù)據(jù)源之間的重復(fù)率，定義了一個(gè)最小代價(jià)查詢優(yōu)化算法。實(shí)驗(yàn)表明，與相關(guān)算法相比，該算法可以提高查詢效率，具有一定的可擴(kuò)展性。

本文組織結(jié)構(gòu)如下：第2章對(duì)Web數(shù)據(jù)源選擇與有數(shù)據(jù)重復(fù)的數(shù)據(jù)源的處理進(jìn)行了分析與總結(jié)；第3章給出了Web大數(shù)據(jù)系統(tǒng)集成相關(guān)問題的一些基本定義；第4章給出了數(shù)據(jù)源模式與中間模式相似度的計(jì)算方法；第5章提出了有依賴關(guān)系的數(shù)據(jù)源可信度的計(jì)算方法；第6章提出了最小代價(jià)查詢模型，并給出了運(yùn)用最大熵原理計(jì)算數(shù)據(jù)源之間重復(fù)率的最小代價(jià)查詢優(yōu)化算法；第7章介紹了本文采用的實(shí)驗(yàn)方案，通過實(shí)驗(yàn)對(duì)提出的最小代價(jià)查詢算法進(jìn)行了評(píng)估，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析；最后對(duì)全文進(jìn)行總結(jié)，并給出今后的研究方向。

2 相關(guān)工作

Yu等人[1]提出了一種基于直方圖的topN選擇方法。該方法分為兩步：第一步是判斷數(shù)據(jù)庫與特定查詢之間的相關(guān)性；第二步是確定最適合提交查詢的數(shù)據(jù)庫和從返回的結(jié)果中選擇最合適的記錄。算法實(shí)驗(yàn)表明，這種計(jì)算topN查詢的方法是非常有效的?？梢允褂帽倔w技術(shù)對(duì)數(shù)據(jù)源的特征進(jìn)行概念描述，同時(shí)提取查詢的概念描述，計(jì)算相關(guān)性，進(jìn)行數(shù)據(jù)源的選擇。在Web數(shù)據(jù)源選擇時(shí)，與用戶查詢相關(guān)的數(shù)據(jù)源質(zhì)量參差不齊，數(shù)據(jù)源的質(zhì)量是數(shù)據(jù)源選取的一個(gè)重要方面。Aboulnaga等人[2]設(shè)計(jì)了一個(gè)μBE（matching by example）數(shù)據(jù)集成系統(tǒng)，系統(tǒng)中使用了基于集成效用數(shù)據(jù)源選擇方法。μBE系統(tǒng)根據(jù)三方面評(píng)價(jià)Web數(shù)據(jù)源質(zhì)量：數(shù)據(jù)源模式在受約束條件下相互匹配程度、數(shù)據(jù)源中數(shù)據(jù)特征（覆蓋度、冗余度、數(shù)據(jù)量）以及數(shù)據(jù)源自身的特征（延時(shí)、可靠性、費(fèi)用、權(quán)威性）。μBE通過迭代一系列的受限優(yōu)化問題來找出適合集成的數(shù)據(jù)源。Xian等人[3]提出了基于迭代的Web數(shù)據(jù)源選取和集成方法，該方法通過評(píng)價(jià)一個(gè)新加入數(shù)據(jù)源可能帶來的增益來決定是否選取該數(shù)據(jù)源，其核心在于增益函數(shù)的設(shè)計(jì)。為了解決面向混合類型關(guān)鍵詞查詢的非合作結(jié)構(gòu)化Deep Web數(shù)據(jù)源的選擇問題，萬常選等人[4]提出了一種屬性與關(guān)鍵詞結(jié)合的Deep Web數(shù)據(jù)源選擇方法。該方法建立了特征詞與主題詞之間的關(guān)聯(lián)性，特征詞在約束型屬性離散值上的記錄分布直方圖，以及兩個(gè)特征詞在同一約束型屬性上直方圖之間的約束相關(guān)性，對(duì)非合作結(jié)構(gòu)化Deep Web數(shù)據(jù)源的約束型屬性與檢索型屬性進(jìn)行了有效的特征概括。Dong等人[5]平衡質(zhì)量與花費(fèi)，基于邊際主義理論進(jìn)行數(shù)據(jù)源選擇。Rekatsinas等人[6]研究了動(dòng)態(tài)數(shù)據(jù)源選擇問題，基于數(shù)據(jù)源內(nèi)容是隨著時(shí)間而改變的，并定義了一組基于時(shí)效的評(píng)價(jià)集成數(shù)據(jù)質(zhì)量的指標(biāo)，如覆蓋度、新鮮性、準(zhǔn)確性等，因此數(shù)據(jù)源選擇成為一個(gè)NP難問題，基于人工學(xué)習(xí)策略，給出了對(duì)應(yīng)的近似解決策略。

在Web數(shù)據(jù)源選取時(shí)，數(shù)據(jù)源之間的數(shù)據(jù)重復(fù)是一個(gè)核心的問題。目前，有很多文獻(xiàn)在數(shù)據(jù)選取時(shí)考慮了數(shù)據(jù)之間的重復(fù)或相交問題。Florescu等人[7]首先將數(shù)據(jù)源按照不同的領(lǐng)域進(jìn)行分類，將每個(gè)數(shù)據(jù)源分成一個(gè)或多個(gè)領(lǐng)域中，然后利用概率信息來計(jì)算領(lǐng)域間的數(shù)據(jù)重復(fù)問題，并最終選擇Top-k個(gè)數(shù)據(jù)源。StatMiner系統(tǒng)[8]在數(shù)據(jù)源排序時(shí)考慮了數(shù)據(jù)的重復(fù)問題。系統(tǒng)假定數(shù)據(jù)源與查詢都可以標(biāo)記為類層次，通過一些樣本數(shù)據(jù)，計(jì)算不同類之間的重復(fù)問題，形成最佳的查詢方案。文獻(xiàn)[9-10]討論了依賴數(shù)據(jù)源中的最小代價(jià)、最大覆蓋率與數(shù)據(jù)源排序問題。Salloum等人[11]提出了一個(gè)OASIS（online query answering system for overlapping sources）系統(tǒng)，該系統(tǒng)使用最大熵原理動(dòng)態(tài)統(tǒng)計(jì)數(shù)據(jù)源之間的重復(fù)率，實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)的在線數(shù)據(jù)源排序算法。

本文目標(biāo)與以上文獻(xiàn)的不同在于：

（1）對(duì)于一個(gè)查詢q，本文目標(biāo)是查詢Top-k個(gè)元組，而不是全部元組；

（2）所選擇的數(shù)據(jù)源必須滿足一定的相關(guān)性與數(shù)據(jù)源質(zhì)量要求；

（3）聚焦于能夠獲得最小查詢代價(jià)。

3 相關(guān)定義

為了定義一個(gè)有依賴關(guān)系的Web大數(shù)據(jù)集成系統(tǒng)，給出了有關(guān)數(shù)據(jù)源、數(shù)據(jù)源的依賴關(guān)系等問題的形式化定義。

定義1（Web數(shù)據(jù)源）數(shù)據(jù)源為提供系統(tǒng)集成數(shù)據(jù)的來源，例如Deep Web數(shù)據(jù)站點(diǎn)、XML數(shù)據(jù)文件、關(guān)系數(shù)據(jù)庫等。一組數(shù)據(jù)源可以表示為S={s1,s2,…,sn}，其中si(1≤i≤n)是第i個(gè)數(shù)據(jù)源。

定義2（實(shí)體）客觀世界中一個(gè)獨(dú)立存在事物的總稱為一個(gè)實(shí)體。每個(gè)實(shí)體具有唯一的標(biāo)識(shí)符。

定義3（實(shí)體屬性）實(shí)體屬性表示一個(gè)客觀世界實(shí)體的特征的描述。一個(gè)實(shí)體的屬性可以表示為A={a1,a2,…,an}，其中ai(1≤i≤n)為實(shí)體的第i個(gè)屬性。實(shí)體的屬性集合也被稱為該實(shí)體的模式。例如，一本書的屬性有ISBN號(hào)碼、價(jià)格、作者等。

定義4（數(shù)據(jù)源依賴性DAG）通過一個(gè)DAG來表示W(wǎng)eb數(shù)據(jù)源集合S={s1,s2,…,sn}之間的依賴性，其中對(duì)于每個(gè)數(shù)據(jù)源si∈S，對(duì)應(yīng)著DAG中的每一個(gè)節(jié)點(diǎn)v；如果si依賴于sj，即si從sj拷貝了數(shù)據(jù)，則有一條有向邊來表示二者的依賴狀況，記作si→sj。

4 數(shù)據(jù)源模式匹配

在一個(gè)Web大數(shù)據(jù)系統(tǒng)中，一項(xiàng)重要的工作就是創(chuàng)建一個(gè)中間模式和建立中間模式與源數(shù)據(jù)模式之間的映射關(guān)系。這項(xiàng)工作需要理解數(shù)據(jù)源的數(shù)據(jù)結(jié)構(gòu)，并了解用戶將如何對(duì)數(shù)據(jù)進(jìn)行查詢。但這對(duì)于Web大數(shù)據(jù)系統(tǒng)來說是不可能實(shí)現(xiàn)的，必須通過自動(dòng)的集成方法來實(shí)現(xiàn)模式集成。該全局集成模式包括來自不同數(shù)據(jù)源模式的屬性集合，將該屬性集合定義為全局屬性（global attribute，GA）。同時(shí)，將所有數(shù)據(jù)源的模式與該全局屬性集合建立屬性之間的映射關(guān)系。一個(gè)良好的GA不能同時(shí)包含概念相同的兩個(gè)屬性。其定義如下：

定義5（良好GA）g是一個(gè)屬性集合，g∈GA，{aij}是數(shù)據(jù)源模式屬性與GA之間的映射，g是良好的當(dāng)且僅當(dāng)g≠?并且

定義6（中間模式）中間模式M={g1,g2,…,gn}，其中g(shù)i∈M是良好的當(dāng)且僅當(dāng)

定義7（模式包含）中間模式M1包含中間模式

在模式映射相似度計(jì)算過程中，使用了多策略信息決策方法。使用的策略包括屬性名稱、實(shí)例與數(shù)據(jù)類型約束。對(duì)于以上3個(gè)決策預(yù)測結(jié)果采取了組合的方法進(jìn)行合并[12]。

5 數(shù)據(jù)源可信度

數(shù)據(jù)源的可信度影響著數(shù)據(jù)值的準(zhǔn)確程度，通常人們更愿意相信那些可信度比較高的數(shù)據(jù)源，就好像人們?cè)谙騽e人咨詢消息一樣，某些人可信程度較高，其提供的消息可信度就會(huì)很高，相反，有些人經(jīng)常說一些謊言，可信程度比較低，其提供的信息可信度就會(huì)很低。數(shù)據(jù)源也一樣，可信度越高的數(shù)據(jù)源它所提供的數(shù)據(jù)值的可信度也就越高。依據(jù)這一理論，數(shù)據(jù)源可信度將對(duì)數(shù)據(jù)值的正確性產(chǎn)生影響。因此，在選擇數(shù)據(jù)源時(shí)，數(shù)據(jù)源的可信度是一個(gè)重要的指標(biāo)。

針對(duì)數(shù)據(jù)源的可信度的求解，Yin等人[13]提出的ACCUNOD算法，該算法的基本思想是每一個(gè)數(shù)據(jù)源都有一個(gè)可信度，數(shù)據(jù)源的可信度影響數(shù)據(jù)信息可信度，而數(shù)據(jù)源的可信度又是根據(jù)它所提供的數(shù)據(jù)值的可信度決定的，因此數(shù)據(jù)源的可信度與數(shù)據(jù)值的可信度是相互影響的，利用迭代算法的思想去計(jì)算數(shù)據(jù)源的可信度和數(shù)據(jù)值的可信度。該算法沒有考慮數(shù)據(jù)源相互依賴的情況。Dong等人[14-15]進(jìn)一步考慮了數(shù)據(jù)源的準(zhǔn)確性因素，并將其與數(shù)據(jù)源的依賴關(guān)系結(jié)合起來，獲得了較好的效果。以上文獻(xiàn)的出發(fā)點(diǎn)是通過計(jì)算數(shù)據(jù)源的可信度與依賴度來發(fā)現(xiàn)數(shù)據(jù)的可信度，本文的出發(fā)點(diǎn)主要是發(fā)現(xiàn)高可信度的數(shù)據(jù)源。

ACCU（accuracy）算法是在BENE（beneficial）算法和MAL（malice）算法的基礎(chǔ)上提出的，該方法既考慮了數(shù)據(jù)源的依賴關(guān)系，也考慮了數(shù)據(jù)源的可信度。其基本計(jì)算方法如下。

當(dāng)兩個(gè)數(shù)據(jù)源si與sj相互獨(dú)立時(shí)，即si⊥sj，根據(jù)概率公式有：

當(dāng)數(shù)據(jù)源sj拷貝si時(shí)，即sj→si，根據(jù)概率公式有：

其中，Ot為數(shù)據(jù)源si與sj提供相同正確值的實(shí)體集合；Of為數(shù)據(jù)源si與sj提供不相同錯(cuò)誤值的實(shí)體集合；Od為數(shù)據(jù)源si與sj提供不相同值的實(shí)體集合；ε(s)為數(shù)據(jù)源s提供錯(cuò)誤值的概率；c為拷貝數(shù)據(jù)源拷貝數(shù)據(jù)比例。

對(duì)于數(shù)據(jù)源的可信度，可以使用以下公式來計(jì)算：

其中，m是數(shù)據(jù)源s提供的值的個(gè)數(shù)；V(s)是數(shù)據(jù)源s提供的數(shù)據(jù)值的集合；P(v)表示數(shù)據(jù)值v正確的概率。

P(v)可以通過以下公式來計(jì)算：

每個(gè)數(shù)據(jù)值的可信度C(v)為：

其中，I(s)為數(shù)據(jù)源s的選票數(shù)。

通過以上分析可以得知：數(shù)據(jù)源的可信度依賴于每個(gè)數(shù)據(jù)源中數(shù)據(jù)值的準(zhǔn)確度；數(shù)據(jù)源之間的依賴性依賴于數(shù)據(jù)源中數(shù)據(jù)值的準(zhǔn)確度與數(shù)據(jù)源的可信度；而數(shù)據(jù)值的準(zhǔn)確度依賴于數(shù)據(jù)源的準(zhǔn)確度以及與其他數(shù)據(jù)源之間的依賴關(guān)系。下面通過算法1的迭代得出各個(gè)數(shù)據(jù)源的準(zhǔn)確度。

算法1給出了每個(gè)數(shù)據(jù)源可信度的計(jì)算方法，其基本思想為：首先給定每個(gè)數(shù)據(jù)源s的初始可信度為1-ε，然后通過迭代的方法求出每個(gè)數(shù)據(jù)源的可信度A(s)。其基本方法為：計(jì)算數(shù)據(jù)源相互之間的依賴概率，按照依賴概率對(duì)數(shù)據(jù)源進(jìn)行排序，計(jì)算每個(gè)數(shù)據(jù)對(duì)象各屬性的可信度，計(jì)算數(shù)據(jù)源的可信度。直到每個(gè)數(shù)據(jù)源s的準(zhǔn)確度A(s)變化小于某個(gè)值，并且需要確定的正確值集合無振蕩時(shí)結(jié)束循環(huán)。

算法1ACCU_VOTE

輸入：數(shù)據(jù)源集合S，數(shù)據(jù)源數(shù)據(jù)的值集合O。

輸出：每個(gè)數(shù)據(jù)源的可信度。

//每個(gè)數(shù)據(jù)源s的準(zhǔn)確度A(s)變化小于某個(gè)值，并且需要確定的正確值集合無振蕩時(shí)結(jié)束循環(huán)

6 最小代價(jià)查詢算法

在Web大數(shù)據(jù)系統(tǒng)中，各數(shù)據(jù)源的訪問時(shí)間各異，數(shù)據(jù)源之間的重復(fù)情況不同，為了減少訪問時(shí)間，其關(guān)鍵問題在于各數(shù)據(jù)源的訪問順序。

定義8（代價(jià)）s為一個(gè)數(shù)據(jù)源，q是一個(gè)查詢。查詢數(shù)據(jù)源s的代價(jià)為C(s)=CC(s)+TC(s)×|q(s)|。其中，CC(s)為數(shù)據(jù)源s的連接時(shí)間；TC(s)為數(shù)據(jù)源s每個(gè)元組的傳輸時(shí)間；|q(s)|為查詢返回的元組總數(shù)。

定義9（查詢效率）一個(gè)數(shù)據(jù)源的查詢效率為vi=C(s)/|q(s)|，即查詢總體代價(jià)與所查詢的元組總數(shù)之比。

定義10（最小代價(jià)模型（time-cost minimization model，TMM））給定一個(gè)查詢qi，一個(gè)數(shù)據(jù)源集合S={s1,s2,…,sn}，需要查詢k個(gè)元組，找到一個(gè)數(shù)據(jù)源的排列序列Πopt{1,2,…,k}，使得其他任何排列Π都有C(qi(Πopt(S)))≤C(qi(Π(S)))。

例1不存在交叉。給定3個(gè)數(shù)據(jù)源s1、s2、s3，為簡便起見，CC(s1)=CC(s2)=CC(s3)=0，3個(gè)數(shù)據(jù)源的每個(gè)元組傳輸時(shí)間分別為TC(s1)=0.8 ms，TC(s2)=1.0 ms，TC(s3)=1.6 ms。對(duì)于一個(gè)查詢q，通過統(tǒng)計(jì)得知|q(s1)|=50，|q(s2)|=150，|q(s3)|=80，3個(gè)數(shù)據(jù)源的元組交叉情況為|q(s1)∩q(s2)|=0，|q(s1)∩q(s3)|=0，|q(s2)∩q(s3)|=0，|q(s1)∩q(s2)∩q(s3)|=0。也就是說，3個(gè)數(shù)據(jù)源相互獨(dú)立并且不存在交叉情況?？梢缘贸鲆韵陆Y(jié)論：

例2存在交叉。給定3個(gè)數(shù)據(jù)源s1、s2、s3，為簡便起見，CC(s1)=CC(s2)=CC(s3)=0，3個(gè)數(shù)據(jù)源的每個(gè)元組傳輸時(shí)間分別為TC(s1)=0.8 ms，TC(s2)=1.0 ms，TC(s3)=1.6 ms。對(duì)于一個(gè)查詢q，通過統(tǒng)計(jì)得知|q(s1)|=50，|q(s2)|=150，|q(s3)|=80，3個(gè)數(shù)據(jù)源的元組交叉情況為|q(s1)∩q(s2)|=25，|q(s1)∩q(s3)|=10，|q(s2)∩q(s3)|=15，|q(s1)∩q(s2)∩q(s3)|=0。也就是說，3個(gè)數(shù)據(jù)源互相之間存在交叉情況?？梢缘贸鲆韵陆Y(jié)論：

通過兩個(gè)例子，可以得出以下兩個(gè)觀察：

觀察1如果所選擇的數(shù)據(jù)源中不存在查詢結(jié)果交叉問題，則最小查詢代價(jià)模型可以得到查詢的最優(yōu)結(jié)果。

觀察2如果所選擇的數(shù)據(jù)源中存在查詢結(jié)果交叉問題，則最小查詢代價(jià)模型需要考慮查詢數(shù)據(jù)源的查詢效率與數(shù)據(jù)源之間的數(shù)據(jù)重復(fù)情況。

在實(shí)踐中，可以觀察到一些小型網(wǎng)站經(jīng)常引用或拷貝大型網(wǎng)站的數(shù)據(jù)，與大型網(wǎng)站的數(shù)據(jù)重復(fù)率很高，因此可以得到以下觀察。

觀察3數(shù)據(jù)數(shù)量少的數(shù)據(jù)源經(jīng)?？截惢蛞脭?shù)據(jù)數(shù)量比較大的數(shù)據(jù)源，在查詢時(shí)，數(shù)據(jù)數(shù)量較大的數(shù)據(jù)源應(yīng)賦予更高的優(yōu)先級(jí)。

查詢效率貪婪算法（MinC）的核心思想：每次在待查詢的數(shù)據(jù)源集合中尋找一個(gè)最大效率的，直到查詢的元組大于等于k個(gè)元組或者所有的數(shù)據(jù)源都已經(jīng)查詢完畢。該算法對(duì)于沒有重復(fù)的數(shù)據(jù)源可以得到最高的查詢效率。

算法2查詢效率貪婪算法（MinC）

輸入：一個(gè)查詢q，所需要查詢的元組數(shù)k，一個(gè)待查詢的數(shù)據(jù)源集合S，數(shù)據(jù)源集合的查詢效率V。

輸出：數(shù)據(jù)源優(yōu)化序列Πopt。

數(shù)據(jù)源最大數(shù)量貪婪算法（MaxT）的核心思想是：每次在待查詢的數(shù)據(jù)源集合中尋找一個(gè)最大數(shù)據(jù)量的數(shù)據(jù)源，直到查詢的元組大于等于k個(gè)元組或者所有的數(shù)據(jù)源都已經(jīng)查詢完畢。MaxT算法與MinC算法的步驟基本一致，MaxT算法優(yōu)先選擇元組數(shù)目大的數(shù)據(jù)源。

算法3數(shù)據(jù)源最大數(shù)量貪婪算法（MaxT）

輸入：一個(gè)查詢q，所需要查詢的元組數(shù)k，一個(gè)待查詢的數(shù)據(jù)源集合S，數(shù)據(jù)源集合的元組數(shù)集合|S|。

輸出：數(shù)據(jù)源優(yōu)化序列Πopt。

根據(jù)觀察2，優(yōu)化排序算法（Optimization）優(yōu)先選擇一個(gè)數(shù)據(jù)數(shù)量最大的數(shù)據(jù)源作為第一個(gè)數(shù)據(jù)源，然后根據(jù)已選擇數(shù)據(jù)源Πopt與待選數(shù)據(jù)源集合S的重復(fù)情況，優(yōu)先選擇最大效率的數(shù)據(jù)源加入到Πopt隊(duì)列中，直到查詢的元組大于等于k個(gè)元組或者所有的數(shù)據(jù)源都已經(jīng)查詢完畢。

為了估算Πopt隊(duì)列集合與剩余數(shù)據(jù)源集合S中的每個(gè)數(shù)據(jù)源s的重復(fù)率，應(yīng)用最大熵原理來實(shí)現(xiàn)重復(fù)率的估算問題。

其中，V(Ω)為重復(fù)估計(jì)時(shí)的可能變量，使用了文獻(xiàn)[11]中的重復(fù)估計(jì)算法。

算法4優(yōu)化排序算法（Optimization）

輸入：一個(gè)查詢q，所需要查詢的元組數(shù)k，一個(gè)待查詢的數(shù)據(jù)源集合S，數(shù)據(jù)源集合的查詢效率V。輸出：優(yōu)化序列Πopt。

在實(shí)際的Web大數(shù)據(jù)集成系統(tǒng)中，數(shù)據(jù)源的選擇通常需要兩個(gè)階段：第一個(gè)階段是數(shù)據(jù)質(zhì)量的評(píng)估以及查詢與數(shù)據(jù)源的相關(guān)性計(jì)算，選擇合適質(zhì)量與一定查詢相關(guān)性的數(shù)據(jù)源；第二階段使用最小查詢代價(jià)模型算法給數(shù)據(jù)源進(jìn)行排序。在排序時(shí)，如果用戶對(duì)查詢的相關(guān)性與質(zhì)量有特殊需求，可以在第二階段算法中加入模式相關(guān)性與質(zhì)量的影響因子。

7 實(shí)驗(yàn)評(píng)估

7.1 實(shí)驗(yàn)設(shè)計(jì)

為了評(píng)估算法的執(zhí)行情況，本文搭建了一個(gè)模擬實(shí)驗(yàn)平臺(tái)。首先，使用網(wǎng)絡(luò)爬蟲從不同的Web站點(diǎn)尋找了1 500個(gè)有關(guān)書籍的站點(diǎn)，然后通過算法1對(duì)每一個(gè)數(shù)據(jù)源的總體質(zhì)量進(jìn)行計(jì)算。1 500個(gè)網(wǎng)站的數(shù)據(jù)總共記錄數(shù)為241 660條，在這些記錄中，總共有25 320條不同的書目。為了簡化計(jì)算以及減少網(wǎng)絡(luò)因素的影響，首先對(duì)各個(gè)站點(diǎn)的訪問代價(jià)CC(s)、每個(gè)元組的傳輸時(shí)間TC(s)進(jìn)行統(tǒng)計(jì)，然后收集每個(gè)站點(diǎn)的所有元組，經(jīng)過一定的語義轉(zhuǎn)換，放到一個(gè)MySQL關(guān)系數(shù)據(jù)庫里面。為了進(jìn)行評(píng)估，實(shí)現(xiàn)了4個(gè)算法。

（1）隨機(jī)算法（Random）：通過隨機(jī)方法，任意選擇下一個(gè)數(shù)據(jù)源進(jìn)行排序；

（2）最大元組法（MaxT）：不考慮數(shù)據(jù)源之間的覆蓋問題，每次直接選擇當(dāng)前隊(duì)列中的最大|q(s)|數(shù)的數(shù)據(jù)源s，進(jìn)行數(shù)據(jù)源排序；

（3）最小代價(jià)算法（MinC）：不考慮數(shù)據(jù)源之間的覆蓋問題，每次直接選擇每個(gè)元組最小代價(jià)的數(shù)據(jù)源s，進(jìn)行數(shù)據(jù)源排序；

（4）優(yōu)化算法（Optimization）：根據(jù)算法4，在選擇數(shù)據(jù)源時(shí)，應(yīng)用最大熵原理，動(dòng)態(tài)計(jì)算待選數(shù)據(jù)源s與已經(jīng)建立的隊(duì)列的重復(fù)情況，選擇最佳的數(shù)據(jù)源。

系統(tǒng)原型：使用Java語言實(shí)現(xiàn)了一個(gè)包括以上4個(gè)算法的數(shù)據(jù)集成系統(tǒng)實(shí)驗(yàn)平臺(tái)。實(shí)驗(yàn)平臺(tái)的操作系統(tǒng)為MS-Windows7，CPU為i54460，8 GB內(nèi)存，所有的查詢都在同一個(gè)網(wǎng)絡(luò)中進(jìn)行，實(shí)驗(yàn)共使用了兩臺(tái)計(jì)算機(jī)，一臺(tái)用于數(shù)據(jù)存儲(chǔ)，一臺(tái)用于計(jì)算數(shù)據(jù)。

實(shí)驗(yàn)參數(shù)設(shè)計(jì)：

（1）第一組實(shí)驗(yàn)主要針對(duì)本文提出的4個(gè)算法進(jìn)行了比較，共完成了3個(gè)實(shí)驗(yàn)。第一個(gè)實(shí)驗(yàn)測試4個(gè)算法在不同Top-k下的性能表現(xiàn)，分別將k的取值設(shè)為數(shù)據(jù)源不同數(shù)據(jù)總數(shù)的0.1、0.2、0.5、0.8。該實(shí)驗(yàn)?zāi)康氖菧y試不同算法在用戶需求數(shù)據(jù)數(shù)量不同時(shí)的表現(xiàn)。第二個(gè)實(shí)驗(yàn)測試4個(gè)算法在不同數(shù)據(jù)源數(shù)目情況下的執(zhí)行效率，該實(shí)驗(yàn)k的取值為0.3，數(shù)據(jù)源的數(shù)據(jù)各選取500個(gè)、1 000個(gè)、1 500個(gè)，其中數(shù)據(jù)源的選擇采取了隨機(jī)選取的辦法。第三個(gè)實(shí)驗(yàn)測試優(yōu)化算法在使用多線程技術(shù)情況下的執(zhí)行效率，該實(shí)驗(yàn)中k的取值為0.3。

（2）第二組實(shí)驗(yàn)主要對(duì)優(yōu)化算法與文獻(xiàn)[11]中的DYNAMIC+算法進(jìn)行比較，共完成了兩個(gè)實(shí)驗(yàn)。第一個(gè)實(shí)驗(yàn)測試完整優(yōu)化算法與DYNAMIC+算法的性能，實(shí)驗(yàn)中k的取值為0.3（共計(jì)7 600條不同記錄）、0.6（共計(jì)14 200條不同記錄）。第二個(gè)實(shí)驗(yàn)兩個(gè)算法使用的數(shù)據(jù)源相同，都是經(jīng)過第一階段預(yù)處理過的數(shù)據(jù)源，數(shù)據(jù)源總數(shù)為1 000個(gè)，實(shí)驗(yàn)中k的取值為0.3（共計(jì)7 600條不同記錄）、0.5（共計(jì)10 400條不同記錄）。在兩組實(shí)驗(yàn)中，各種算法都分別執(zhí)行了100次，最后的取值為100次實(shí)驗(yàn)結(jié)果的平均值。

7.2 實(shí)驗(yàn)分析

7.2.1 第一組實(shí)驗(yàn)

Fig.1 Response time of algorithms with different proportion of tuple圖1 不同返回元組數(shù)的查詢響應(yīng)時(shí)間

第一個(gè)實(shí)驗(yàn)的結(jié)果如圖1所示。通過實(shí)驗(yàn)可以得知：不管k的取值大小，總體來說，Random算法的執(zhí)行時(shí)間最長，效率最低，MaxT算法的執(zhí)行時(shí)間比Random算法要少，MinC算法相對(duì)MaxT算法的效率有所提升，Optimization算法執(zhí)行時(shí)間最少，相對(duì)其他算法有較大的提升；當(dāng)k=0.1時(shí)，Random算法、MaxT算法、MinC算法、Optimization算法的執(zhí)行時(shí)間分別為16.3、14.2、7.1、5.1 s；當(dāng)k=0.8時(shí)，4個(gè)算法的執(zhí)行時(shí)間分別為241.5、211.3、114.5、86.1 s。由圖1可以明顯看出，當(dāng)k值增加時(shí)，Random算法增加的幅度最大，Optimization算法增加的幅度最小。

第二個(gè)實(shí)驗(yàn)的結(jié)果如圖2所示。通過實(shí)驗(yàn)可以得知：（1）隨著數(shù)據(jù)源數(shù)目的增多，各個(gè)算法的時(shí)間都有增加，但不管|S|取值大小，Optimization算法都是同等條件下最優(yōu)的。（2）當(dāng)數(shù)據(jù)源數(shù)目增加時(shí)，不同算法時(shí)間增加的幅度不同，其中Random算法增加的比例最大，當(dāng)|S|=500時(shí)，CRandom=15.8 s；當(dāng)|S|=1 000時(shí)，CRandom=71.4 s；時(shí)間增加了452%，與此同時(shí)，Optimization算法的訪問時(shí)間增加了252%。（3）Optimization算法隨著數(shù)據(jù)源的增加，訪問時(shí)間線性增加，算法具有一定的擴(kuò)展性。

Fig.2 Response time of algorithms with different number of sources圖2 不同數(shù)據(jù)源個(gè)數(shù)的查詢響應(yīng)時(shí)間

第三個(gè)實(shí)驗(yàn)主要測試在多線程并行計(jì)算下4個(gè)算法的執(zhí)行效率，實(shí)驗(yàn)中k的取值為0.3，數(shù)據(jù)源數(shù)量為1 000個(gè)，實(shí)驗(yàn)分別測試了1～12個(gè)線程的執(zhí)行效率。實(shí)驗(yàn)結(jié)果如圖3所示。通過實(shí)驗(yàn)可以得知：（1）線程數(shù)量越多，各種算法的查詢執(zhí)行時(shí)間都在減少，線程增加時(shí)，執(zhí)行時(shí)間的降低并非線性降低。（2）當(dāng)線程數(shù)量小于5開始，時(shí)間的減少比較明顯；當(dāng)線程數(shù)量大于5時(shí)，時(shí)間減少速度開始明顯趨緩。

Fig.3 Response time of algorithms with Parallel query answering圖3 并行查詢各算法查詢時(shí)間

7.2.2 第二組實(shí)驗(yàn)

第二組實(shí)驗(yàn)主要比較Optimization算法與文獻(xiàn)[11]DYNAMIC+算法性能，測試中分別使用了單線程模式與并行模式。

在第一個(gè)實(shí)驗(yàn)中，Optimization算法使用的數(shù)據(jù)源是經(jīng)過第一階段排序過的數(shù)據(jù)源，DYNAMIC+算法使用的是隨機(jī)選擇的數(shù)據(jù)源。測試結(jié)果如圖4所示。通過實(shí)驗(yàn)結(jié)果可以得知：（1）數(shù)據(jù)源數(shù)量越少，Optimization算法相對(duì)DYNAMIC+算法的性能越好。（2）Optimization算法總體來說性能比DYNAMIC+算法要好一些。（3）采用單線程模式與多線程模式對(duì)于趨勢的影響不大，主要原因就是Optimization算法使用的數(shù)據(jù)源經(jīng)過了第一階段數(shù)據(jù)質(zhì)量的評(píng)估。經(jīng)過統(tǒng)計(jì)表明，質(zhì)量高的數(shù)據(jù)源的響應(yīng)時(shí)間往往比較小。當(dāng)數(shù)據(jù)源數(shù)量較少時(shí)，根據(jù)第一階段的數(shù)據(jù)源選擇策略，從總體的數(shù)據(jù)源中選取了比較好的一些數(shù)據(jù)源，相應(yīng)的執(zhí)行效率就比較高；當(dāng)數(shù)據(jù)源數(shù)量增多時(shí)，這種優(yōu)勢就會(huì)降低，兩個(gè)算法的性能就會(huì)慢慢接近。

Fig.4 Performance comparison of optimization algorithm and DYNAMIC+algorithm圖4 覆蓋優(yōu)化算法與DYNAMIC+性能比較

圖5給出第二個(gè)實(shí)驗(yàn)的測試結(jié)果。通過實(shí)驗(yàn)結(jié)果可以得知：（1）兩個(gè)算法的性能基本相當(dāng)。（2）當(dāng)查詢數(shù)據(jù)數(shù)量比較少時(shí)，DYNAMIC+算法性能更好一些；當(dāng)查詢數(shù)據(jù)數(shù)量較多時(shí)，Optimization算法性能更好一些。

Fig.5 Performance comparison of optimization algorithm and DYNAMIC+algorithm圖5 覆蓋優(yōu)化算法與DYNAMIC+性能比較

實(shí)驗(yàn)小結(jié)：（1）第一組實(shí)驗(yàn)表明，在同等條件下，Optimization算法比其他算法的性能更好；同時(shí)，Optimization算法具有一定的擴(kuò)展性。（2）第二組實(shí)驗(yàn)表明，與相關(guān)算法DYNAMIC+相比，Optimization算法總體上來說性能更優(yōu)。

8 結(jié)束語

數(shù)據(jù)源的選擇與排序是Web大數(shù)據(jù)系統(tǒng)的關(guān)鍵問題之一。數(shù)據(jù)源之間的重復(fù)是選擇數(shù)據(jù)源的關(guān)鍵問題。本文提出了一個(gè)兩階段數(shù)據(jù)源選擇排序方法：第一階段通過組合的方法計(jì)算查詢與數(shù)據(jù)源之間的相關(guān)性，通過計(jì)算數(shù)據(jù)源的可信度計(jì)算數(shù)據(jù)源的質(zhì)量，在計(jì)算數(shù)據(jù)源質(zhì)量時(shí)考慮了數(shù)據(jù)源之間的重復(fù)情況。在第一階段選擇了與查詢具有一定相關(guān)度與質(zhì)量標(biāo)準(zhǔn)的數(shù)據(jù)源。第二階段設(shè)計(jì)了4個(gè)算法，隨機(jī)算法、最大元組法、最小查詢代價(jià)算法、優(yōu)化算法。4個(gè)算法各有不同的應(yīng)用場景，通過該系列算法對(duì)第一階段選擇的數(shù)據(jù)源進(jìn)行排序。實(shí)驗(yàn)結(jié)果表明，與相關(guān)算法相比，Optimization算法可以減少系統(tǒng)查詢時(shí)間，具有一定的擴(kuò)展性。下一步的工作是結(jié)合并行算法對(duì)目前的最小代價(jià)查詢算法進(jìn)行進(jìn)一步的優(yōu)化。

[1]Yu C,Philip G,Meng Weiyi.Distributed top-Nquery processing with possibly uncooperative local systems[C]//Proceedings of the 29th International Conference on Very Large Data Bases,Berlin,Sep 9-12,2003.San Mateo:Morgan Kaufmann,2003:117-128.

[2]Aboulnaga A,El Gebaly K.μBE:user guided source selection and schema mediation for internet scale data integration[C]//Proceedings of the 23rd International Conference on Data Engineering,Istanbul,Apr 15-20,2007.Washington:IEEE Computer Society,2007:186-195.

[3]Xian Xuefeng,Zhao Pengpeng,Yang Yuanfeng,et al.Efficient selection and integration of hidden Web database[J].Journal of Computers,2010,5(4):500-507.

[4]Wan Changxuan,Deng Song,Liu Dexi,et al.Non-cooperative structured deep Web selection based on hybrid type keyword retrieval[J].Journal of Computer Research and Development,2014,51(4):905-917.

[5]Dong X L,Saha B,Srivastava D.Less is more:selecting sources wisely for integration[J].Proceedings of the VLDB Endowment,2012,6(2):37-48.

[6]Rekatsinas T,Dong X L,Srivastava D.Characterizing and selecting fresh data sources[C]//Proceedings of the 2014 International Conference on Management of Data,Snowbird,Jun 22-27,2014.New York:ACM,2014:919-930.

[7]Florescu D,Koller D,Levy A Y.Using probabilistic information in data integration[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,Athens,Aug 25-29,1997.San Francisco:Morgan Kaufmann Publishers Inc,1997:216-225.

[8]Nie Zaiqing,Kambhampati S,Nambiar U.Effectively mining and using coverage and overlap statistics for data integra-tion[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(5):638-651.

[9]Sarma A D,Dong X L,Halevy A Y.Data integration with dependent sources[C]//Proceedings of the 14th International Conference on Extending Database Technology,Uppsala,Mar 21-24,2011.New York:ACM,2011:401-412.

[10]Liu Xuan,Dong X L,Ooi B C,et al.Online data fusion[J].Proceedings of the VLDB Endowment,2011,4(11):932-943.

[11]Salloum M,Dong X L,Srivastava D,et al.Online ordering of overlapping data sources[J].Proceedings of the VLDB Endowment,2013,7(3):133-144.

[12]Liu Zhengtao,Wang Jiandong.Pay-as-you-go schema integration in Web dataspace[J].Journal of Frontiers of Computer Science and Technology,2011,5(1):87-96.

[13]Yin Xiaoxin,Han Jiawei,Yu P S.Truth discovery with multiple conflicting information providers on the Web[J].IEEE Transactions on Knowledge&Data Engineering,2008,20(6):796-808.

[14]Dong X L,Berti-Equille L,Srivastava D.Integrating conflicting data:the role of source dependence[J].Proceedings of the VLDB Endowment,2009,2(1):550-561.

[15]Dong X L,Berti-Equille L,Srivastava D.Truth discovery and copying detection in a dynamic world[J].Proceedings of the VLDB Endowment,2009,2(1):562-573.

附中文參考文獻(xiàn)：

[4]萬常選,鄧松,劉德喜,等.面向混合類型關(guān)鍵詞查詢的非合作結(jié)構(gòu)化深網(wǎng)數(shù)據(jù)源選擇[J].計(jì)算機(jī)研究與發(fā)展,2014,51(4):905-917.

[12]劉正濤,王建東.Web數(shù)據(jù)空間邊建邊用模式集成[J].計(jì)算機(jī)科學(xué)與探索,2011,5(1):87-96.