何康樂

摘要：在Web數(shù)據(jù)庫中，有著大量豐富的信息數(shù)據(jù)，這些信息并不能直接看到，只有進(jìn)行特定的查詢才能看到。由于這一特點，對Web數(shù)據(jù)庫的實時更新及其分布特征的了解成了一個問題，進(jìn)而也會阻礙到Deep Web數(shù)據(jù)庫的進(jìn)一步集成。針對這一困難，本文提出了一種新型的采樣方法，在查詢時能夠從Web數(shù)據(jù)庫獲取近似隨機(jī)的增量樣本并記錄，并在此基礎(chǔ)上進(jìn)行下一次查詢，并不會受到查詢接口的屬性限制，能夠在獲取高質(zhì)量樣本的同時降低代價。

關(guān)鍵詞：Web數(shù)據(jù)庫;采樣;圖模型

中圖分類號：G434 ? 文獻(xiàn)標(biāo)識碼：A ? 論文編號：1674-2117（2015）09-0076-02

伴隨著Web的飛速發(fā)展，其作為一個信息源覆蓋了越來越多的信息，根據(jù)其所蘊(yùn)含的具體信息深度，我們可以將整個Web分為兩大部分，包括Deep Web以及Surface Web。[1]所謂的Surface Web指的是能夠采用傳統(tǒng)的普通搜索引擎就能直接索引出的信息內(nèi)容。相對地，不能直接采用搜索引擎搜索到的信息數(shù)據(jù)內(nèi)容就被放在Deep Web中，其具體內(nèi)容被存儲在能夠進(jìn)行在線訪問的Web數(shù)據(jù)庫之中。由于Deep Web數(shù)據(jù)庫中存在著海量的信息，可以達(dá)到Surface Web的550倍[2]，想要從中快速獲取想要的信息也成了一個問題。

● Deep Web概述

網(wǎng)絡(luò)中諸多能夠進(jìn)行在線訪問的數(shù)據(jù)庫，統(tǒng)稱為Web數(shù)據(jù)庫，將全部Web數(shù)據(jù)庫整合到一起，就統(tǒng)一成了Deep Web，也被稱作是Hidden Web。[3]想要訪問Deep Web，就必須從查詢接口進(jìn)行訪問，在網(wǎng)頁上查詢接口是通過表單表現(xiàn)出來的，用戶具體需要做的就是輸入一定的條件在表單中，進(jìn)而便可以查詢相關(guān)信息。[4]

● Web數(shù)據(jù)庫采樣

Web數(shù)據(jù)庫中信息的質(zhì)量參差不齊，想要對其進(jìn)行有效研究，傳統(tǒng)做法通常是將全部數(shù)據(jù)庫進(jìn)行完全的統(tǒng)計分析。但，由于Web數(shù)據(jù)庫中的數(shù)據(jù)類型頗為廣泛，本地研究并不需要完整的數(shù)據(jù)庫，只需要構(gòu)建出一個具有針對性的本地數(shù)據(jù)庫即可。然而，本地數(shù)據(jù)庫構(gòu)建出來以后，由于網(wǎng)絡(luò)信息一直在實時更新，相應(yīng)地，本地數(shù)據(jù)庫中的信息也需要實時更新，同時，這會為本地儲存增加相當(dāng)大的負(fù)擔(dān)，進(jìn)而付出更多的代價。[5]針對這一問題，我們可以不將所有的信息都從Web數(shù)據(jù)庫中提取出來，僅從中抽取想要的數(shù)據(jù)樣本，通過具有代表性的樣本進(jìn)行數(shù)據(jù)庫研究。

傳統(tǒng)的采樣方法采集數(shù)據(jù)是通過數(shù)據(jù)庫直接獲取信息，進(jìn)行隨機(jī)采樣。隨機(jī)采樣技術(shù)有直方圖法和近似查詢法，但是這類方法都要求數(shù)據(jù)庫具備無限制訪問接口。所以，在Web數(shù)據(jù)庫采樣中，這種方法并不適用。參考搜索引擎，也有專家學(xué)者提出可以通過文檔進(jìn)行隨機(jī)采樣，可以從搜索引擎中隨機(jī)抽取樣本。但是，由于文檔并不能代替查詢表單，所以該方法也不適用于Web數(shù)據(jù)庫。綜合考慮Deep Web的特點，筆者提出了一種基于圖模型的數(shù)據(jù)采樣方法，該方法摒棄了查詢接口屬性的限制，能夠通過關(guān)鍵詞進(jìn)行快速查詢。

● 基于圖模型的Web數(shù)據(jù)庫采樣

1.基本思想

基于圖模型的Web數(shù)據(jù)庫采樣的基本思想主要可以分成四個環(huán)節(jié)，首先，從任意的有效查詢中查詢;其次，根據(jù)查詢到的結(jié)果抽取一些進(jìn)行記錄;再次，將記錄好的內(nèi)容放置到本地的樣本數(shù)據(jù)庫中;最后，根據(jù)樣本庫的信息，抽取一個記錄進(jìn)行下一次查詢，達(dá)成循環(huán)（如下頁圖）。

想要完成Web數(shù)據(jù)庫采樣，需要解決兩個問題。第一，采集到的樣本存在一定的偏差，必須進(jìn)行修正，保證數(shù)據(jù)分布能夠和Web數(shù)據(jù)庫相同;第二，獲取樣本相應(yīng)地需要付出一定的代價，要降低代價，可以通過減少查詢次數(shù)來達(dá)成這一目的。

2.圖模型WG概述

根據(jù)Web數(shù)據(jù)庫特征建立的一種全新模型，圖模型可以借由圖游歷的形式進(jìn)行采樣。在改樣過程中，模型中的各個頂點和邊都被定義了唯一的特征查詢，同時，查詢后的記錄集合中每個頂點都有其專門的對應(yīng)記錄，對于各個邊來說，也有著邊上自帶兩點的對應(yīng)集合記錄。WG能夠提供的具體能力與WDB中的具體查詢接口有關(guān)，因為只要是查詢，就必須有查詢接口。所以，要想判斷WG中的邊上兩個頂點是否存在兩個記錄，就要確定是否存在某個查詢接口能夠滿足邊上兩點的查詢記錄要求。

3.WG采樣方法

由圖可知，Web數(shù)據(jù)庫采樣需要解決的主要問題是：獲取樣本、選擇查詢以及終止條件。由于我們并不能調(diào)出所有的WDB記錄，那么也很難構(gòu)建出一個真正意義上的WG，所以，可以根據(jù)當(dāng)前的WG，隨機(jī)抽取一個點開始游歷，進(jìn)行采樣，基本過程為：①隨機(jī)抽取一個Q0，將其遞交給WDB;②將查詢后所得的具體結(jié)果記錄到RL中，并根據(jù)已有的RL建立起對應(yīng)的WGL;③判斷是否終止，若滿足終止條件，則終止，若不滿足，則繼續(xù)進(jìn)行下一步驟;④對構(gòu)建出WGL的進(jìn)行分析，然后在RL中找出合適的記錄繼續(xù)進(jìn)行查詢，回到第①步驟進(jìn)行。

（1）WDB-Sampler算法

WDB-Sampler算法主要對采樣的整體過程進(jìn)行具體的形式化描述。

（2）記錄選擇

想要進(jìn)行持續(xù)查詢，完成實時更新，必須在已經(jīng)基本形成的本地記錄合集中選出合適的某個記錄進(jìn)行下一步查詢，這就是記錄選擇這一環(huán)節(jié)需要完成的內(nèi)容。采樣WG進(jìn)行具體解釋，就是根據(jù)目前的WGL選出一個頂點v，根據(jù)v查詢之前沒有查詢到的其他頂點，豐富WGL。

（3）查詢生成

選擇好頂點以后，可以選出具體的某個記錄，然后完成下一環(huán)節(jié)的查詢。一個記錄可以獲得多個查詢，所以，針對每個RL中的記錄都要構(gòu)建出對應(yīng)的統(tǒng)計信息。

（4）采樣終止

圖模型若是沒有設(shè)計終止程序，可想而知，數(shù)據(jù)采樣將會持續(xù)進(jìn)行下去，雖然在理論上這樣做可以得到所有想要的記錄，但是我們事實上并不需要所有的信息，只是需要其中某些樣本。所以，應(yīng)該設(shè)計出常量nq>1、0<<1表示若是查詢中連續(xù)nq次的結(jié)果都超出了的重復(fù)記錄，就代表采樣結(jié)束。通常我們將nq值設(shè)計在5～10之間，設(shè)在5%～15%之間。

（5）偏差修正

因為查詢中我們是將RL當(dāng)做樣本進(jìn)行采樣的，那么采樣結(jié)束后往往會造成較大的偏差。針對這一問題，可以通過采樣中的查詢記錄數(shù)量和過程中的Q{}進(jìn)行樣本偏差修正。

● 結(jié)語

筆者提出的基于圖模型的WDB-Sample采樣方法，能夠?qū)eb數(shù)據(jù)庫轉(zhuǎn)變?yōu)閳D形進(jìn)行增量采樣，該方法能夠脫離屬性限制，保證高質(zhì)量采集樣本的同時降低代價，在教育領(lǐng)域中的應(yīng)用應(yīng)該有無限廣闊的前景。

參考文獻(xiàn)：

[1]劉偉，孟小峰，凌妍妍.一種基于圖模型的Web數(shù)據(jù)庫采樣方法[J].軟件學(xué)報，2008（02）.

[2]吳雨.基于圖模型的Web數(shù)據(jù)庫取樣方法的解析[J].科技創(chuàng)新與應(yīng)用，2013（20）.

[3]王曉玲.一種基于圖模型的Web數(shù)據(jù)庫采樣方法分析[J].計算機(jī)光盤軟件與應(yīng)用，2013（13）.

[4]趙琳.Web數(shù)據(jù)庫特征表示和抽取方法的研究[D].濟(jì)南：山東財經(jīng)大學(xué)，2012.

[5]董永權(quán).Deep Web數(shù)據(jù)集成關(guān)鍵問題研究[D].濟(jì)南：山東大學(xué)，2010.