基于圖模型的Web數據庫取樣方法的解析

摘 要：由于在Web數據庫中存在著海量的信息，而這些信息隱藏在具有特定查詢能力的查詢接口后，從而為了解Web數據庫的分布、更新等內容特征帶來的困難，最終阻礙了Deep Web數據集成。文章基于這一問題提出了一種新的數據采樣方法，這種方法可以以增量的方式通過查詢接口從Web 數據庫中獲取近似隨機樣本，同時利用已經保存在本地的樣本記錄生成下次查詢。

關鍵詞：圖模型；Web；數據庫；取樣

隨著Web的迅速發展，當今的Web已經成為一個巨大的信息源，數據庫采樣是一個從數據庫隨機選取記錄的過程，可以獲得數據庫中有用的統計。文章提出的一種“Web數據庫取樣由于不受查詢接口屬性表現形式的限制，為此可以在本地模擬試驗中表現出優異的性質。

1 WDB-Sample基本思想

WDB-Sample的基本思想可以分為四大步：第一步是從一個任意的有效查詢開始進行查詢；第二步是從以上查詢所返回的結果中抽取記錄；第三步是將獲得的記錄放于本地樣本庫；最后是從樣本庫中選取一個記錄并將其作為Web數據庫的下一次查詢。然后轉入第二步。

對Web數據庫的采樣需要應對兩個挑戰，其一是所獲得的樣本的偏差，要求樣本的數據分布與Web數據庫保持一致；其二是獲得樣本的代價，要保證通過盡量少的查詢次數來獲得這些樣本。

2 一種基于Web數據庫的圖模型

2.1 Web數據庫模型概述

這里我們提出一種全新的基于Web數據庫圖模型，這一模型可以通過圖游歷的方式達到對于Web數據庫的采樣。這一模型中的每個頂點以及每個邊都附加了一個唯一的查詢，而對于每個頂點相當于記錄在集合R中的只有頂點對應的那個記錄。而對于每條邊相當于僅有記錄集合R中與該邊所連接的兩個頂點所對應的記錄。此外，WebData base graph （WG）與WDB所提供的查詢接口的查詢能力之間相關，因為所涉及到的所有的查詢均是查詢接口中可以表達的。從而導致兩個記錄在WG中是存在一條邊主要由是否存在一個查詢接口可表達的查詢可以滿足兩個記錄，換句話來講決定于頂點與邊上附加的查詢接口能力。為此即使是針對于具有相同內容的WDB，如果二者的查詢接口的能力不同也會導致查詢能力的差異。

2.2 基于WG的Web數據庫采樣方法思想

借助于圖模型可以將任意的一個WDB在記錄層上轉換為圖進行表達，從得到的圖模型可以得到支路之間的關聯關系。如果要對WDB增量式的采樣方法，正如上文所述的WDB-Sample思想，需要解決樣本的選取、查詢的選擇以及終止條件。但是下面我們主要對如何在WG中采用圖游歷的思想實現對WDB增量式的采樣。

鑒于我們難以越過查詢接口而直接獲得WDB的所有記錄，為此基于WG的Web的數據采樣思想如下所述：首先從任意的一個查詢Q0開始，并提交WDB；其次將查詢得到的結果記錄保存于本地RL，并對得到的記錄RL建立WGL；在此基礎上判定是否達到終止條件，如果是則停止，反之進入下一步；通過對建立的WGL的分析，從RL中選擇合適的記錄形成下一次查詢，轉入開始的第一步。

盡管在進行開始查詢中使用人工選擇的Q0點開始具有一定的主觀性，但是只要保證Q0的查詢結果足夠多就可以保證Q0是WG中度較大的一個，從而避免不同查詢帶來的采樣差異。同時隨著RL中的記錄數量不斷增加，WGL隨著擴大，為此我們僅需要將每次的查詢記錄添加到當前的WGL中，而不是重新構建WGL，其中WGL是WG的一個子圖。而采樣中最為關鍵的問題是第三步、第四步，其問題體現在：如何根據WGL從當前的記錄中選擇合適記錄、

2.3 WDB-Sampler算法

前面已經對WDB-Sampler算法的采樣思想進行了簡述，不再復述。這里指出一點：對于每次的查詢結果，我們僅獲取第一頁中的記錄。這樣做是基于以下兩個考慮：首先是要對這次查詢中更多次的記錄需要不斷地翻頁，而翻頁本身也是一種查詢操作。其二是由于所有的查詢結果均滿足此次查詢，為此會導致偏差的增加。

2.4 記錄的選擇

為了進行查詢操作需要從當前存儲的本地記錄中選擇一個個合適的記錄作為查詢，而這也正是record selector的功能。所選擇的的查詢記錄要可以獲得更多新的記錄。基于WG進行解釋，也就是從當前的WGL中選擇一個頂點v，然后通過v查詢到更多的尚不屬于WGL的頂點。為此查詢中我們將WGL中的頂點按其度進行從低到高的排列，并選擇度最小的頂點。度最小的頂點可能是在WG中的度較小，也可能是在WG中有很多與之相鄰的新頂點。為此如果發現獲得紀錄少于k則可以丟棄這一頂點并選擇其余頂點中度最小。

2.5 查詢的生成

選擇了WGL中的一個頂點后就可以從中選定一個記錄，然后利用queryGenerratot生成下一次查詢。由于一個記錄可以得到若干查詢，為此對于每一個記錄都要根據RL中的記錄建立相應的統計信息。

2.6 采樣過程終止

如果在圖模型數據取樣中不設置采樣終止條件，那么采樣過程就會一直進行下去，從而在理論上可以獲得WDB中的所有記錄，但是我們僅需要足夠的樣本記錄，而非全部。為此需要設定兩個常量nq與？啄，其中nq是一個大于1的自然數，而？啄介于0-1。其意義為：如果查詢中連續nq次的查詢結果有超過？啄的部分的重復記錄，那么就表明采樣結束。一般將nq設置為5-10，而？啄為5%-15%。

2.7 樣本偏差的修正

在實際的取樣中所獲得的RL作為樣本一般具有較大的偏差，為此需要采取措施對偏差加以修正。由于在WDB的結果頁面中會給出一個滿足當前記錄查詢的記錄數量的統計數字，為此我們記錄采樣中的所有的Q{Q1，Q2……，Qm}，同時為每個查詢記錄其結果數量。然后逐漸的對RL刪減，從而使得Q如果作為隨機查詢集合就會通過下面公示得到的偏差盡可能小。

當然，這一采樣方法并非完美，還需要后續工作者進一步的進行晚上、升級。首先采樣中設置的一系列參數僅僅是經驗性的，為此需要進行理論分析；其次上面對于采樣代價的評估僅僅是通過對Web數據庫的訪問次數來進行衡量，為此更為合理的評估方法有待進一步開發；最后這一采樣方法在多種數據庫的試驗還需要進行，從而不斷地完善、改進，進一步的降低樣本的偏差。

3 結束語

當下隨著Deep Web的快速發展，Deep Web已經逐漸成為數據集成領域的重要研究課題。鑒于Web數據庫僅能借助于特定的查詢方式進行接口訪問，而且數據庫數量巨大，為此需要通過對Web數據庫的采樣來了解其內容特征?；谝陨涎芯课恼绿岢隽艘环N增量式的Web數據庫采用方法，即WDB-Sample，這一采樣方法通過將上述的Web數據庫轉化為圖形來予以表示，從而達到了對增量的采樣。由于這種采樣方法在查詢中不受屬性表達形式的限制，為此在實際應用中可以在較小代價下得到高質量的樣本。

參考文獻

[1]Lawrence S，Giles C.Searching the World Wide Web.Science，1998，5360（280）：98.