李慶紅

(株洲職業(yè)技術(shù)學(xué)院信息工程系，湖南株洲412001)

關(guān)系數(shù)據(jù)庫中近似查詢的自動采樣改進方法研究

李慶紅

(株洲職業(yè)技術(shù)學(xué)院信息工程系，湖南株洲412001)

海量數(shù)據(jù)的傳統(tǒng)精確查詢易導(dǎo)致負載過大，而通過改進數(shù)據(jù)庫近似查詢自動采樣，預(yù)先運行樣本查詢，然后根據(jù)每一個元組在樣本關(guān)系表中出現(xiàn)的次數(shù)，將每個元組需要的存儲信息作為元組的屬性添加進數(shù)據(jù)表中，并通過DBMS在整個自動抽樣過程對它們進行管理，對所得的結(jié)果進行分類并統(tǒng)計，得出每次采樣過程中某個元組出現(xiàn)的次數(shù)，實驗表明方法是有效的。

關(guān)系數(shù)據(jù)庫;自動采樣;SQL

采用傳統(tǒng)精確查詢技術(shù)處理海量數(shù)據(jù)，查詢?nèi)蝿?wù)將顯得極其繁重，從而導(dǎo)致整個查詢的響應(yīng)時間超出用戶可以接受的限度。因而往往采用近似匹配，通過對部分或采樣數(shù)據(jù)的查詢，而不是整個數(shù)據(jù)集本身進行的查詢，此外，要完整地收集一個數(shù)據(jù)集往往不可能，現(xiàn)在的數(shù)據(jù)倉庫多是“普遍”數(shù)據(jù)的一個樣本，這在科學(xué)應(yīng)用領(lǐng)域是極其普遍的。為了讓用戶了解查詢結(jié)果的精度，確定正確的查詢結(jié)果在某個概率區(qū)間中，需要結(jié)合查詢結(jié)果的概率分布來給出置信區(qū)間，然后根據(jù)整體數(shù)據(jù)的分布情況計算出概率，對樣本數(shù)據(jù)估計匹配置信區(qū)間。通過分析樣本數(shù)據(jù)而推導(dǎo)出整個數(shù)據(jù)特征的概率分布，對數(shù)據(jù)集很可能不準(zhǔn)確。

在實際運用中通過樣本推斷出整個分布非常困難，不可能預(yù)先知道數(shù)據(jù)集的標(biāo)準(zhǔn)偏差和參數(shù)分布函數(shù)，或必須處理數(shù)據(jù)的概率分布，當(dāng)需要推導(dǎo)又推導(dǎo)不出產(chǎn)生置信區(qū)間的函數(shù)時，則需要考慮采用新的處理方法?；诜抡娴闹眯艆^(qū)間不需要單獨的分析推導(dǎo)［1－3］，使用簡單的計算能力避免分析推導(dǎo)和參數(shù)分析，提供了一個通用技術(shù)為大多數(shù)統(tǒng)計方法計算置信區(qū)間。統(tǒng)計估計中使用較廣泛的Bootstrap方法［4］能被大多數(shù)數(shù)據(jù)庫使用，能夠減小查詢數(shù)據(jù)的范圍，將查詢簡化到基礎(chǔ)數(shù)據(jù)上。置信區(qū)間在一個大容量的數(shù)據(jù)集上重復(fù)運行，反復(fù)抽樣基本數(shù)據(jù)庫表產(chǎn)生仿真數(shù)據(jù)集，每一次先對基本數(shù)據(jù)表進行再抽樣，再對每一個樣本進行基本查詢，最后再根據(jù)所有的查詢結(jié)果推導(dǎo)出整個數(shù)據(jù)的結(jié)果。但Bootstrap方法在對大型數(shù)據(jù)進行操作時速度將隨著數(shù)據(jù)量的增加而降低速度。

本文改進了數(shù)據(jù)庫近似查詢的自動采樣，通過確定在非采樣樣本上的基本查詢結(jié)果元組是第二次采樣形成的關(guān)系集上相同查詢結(jié)果的一個超元組集，預(yù)先運行樣本查詢，然后記住每一個元組在樣本關(guān)系表中出現(xiàn)的次數(shù)，將每個元組需要的存儲信息作為元組的屬性添加進數(shù)據(jù)表中，然后通過DBMS在整個Bootstrap過程對它們進行管理，對所得的結(jié)果進行分類并統(tǒng)計，得出每次采樣過程中某個元組出現(xiàn)的次數(shù)，提升了Bootstrap方法的采樣效率，或者減少執(zhí)行查詢的次數(shù)，加快獲取結(jié)果的時間，以最大限度地降低性能，使Bootstrap方法對海量數(shù)據(jù)數(shù)值類型的整個或者部分樣本進行基礎(chǔ)SQL查詢即完成對關(guān)系數(shù)據(jù)庫的近似查詢，得到符合用戶要求的近似結(jié)果信息。

1 元組信息存儲

在應(yīng)用Bootstrap方法進行數(shù)據(jù)的近似查詢時，算法用到的大量再抽樣和重復(fù)查詢操作產(chǎn)生了大量的負載，為了降低查詢負載，設(shè)法避免運行基本查詢在一次以上。對于大多數(shù)關(guān)系數(shù)據(jù)庫查詢來說，實際上有很多種方法可以實現(xiàn)這個目標(biāo)。考慮以下查詢:

SELECT BOOTSTRAP f(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

FROM Rx+1，Rx+2，...，Ry

INCOMPLETE R1，R2，...，Rx

WHERE expression(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

RESAMPLE b TIMES

WHERE expression(R1.att1，R1.att2，...，R2.att1，R2.att2，...)

RESAMPLE b TIMES

假設(shè)基本查詢是直接對R1和Ry關(guān)系上進行的查詢，則S是f運行在這個查詢上的元組的集合，換句話說，如果聚集函數(shù)f被SELECT* 語句代替以后，S將僅僅是這個查詢結(jié)果的多集。假設(shè)基本查詢不是直接運行于R1，R2，...，Rx，而是運用對 R1，R2，...，Rx再抽樣后的集合，那么S*就被定義為f要運行元組的多集。由于R*中的元素R1*，R2*，...，Rx*分別是再抽樣集合 R中樣本R1，R2，...，Rx，因而 R* 必是 R 的一個元組集。因此，使 R*與任何其它的關(guān)系進行連接產(chǎn)生的元組集決定是R與相同關(guān)系連接產(chǎn)生元組集的子集。即結(jié)果集S*刪除重復(fù)元組后必包含于刪除重復(fù)元組后的S集。表示為S*(刪除重復(fù)元組后)?S(刪除重復(fù)元組后)。

這樣可以保證在非采樣樣本上的基本查詢結(jié)果元組是第二次采樣形成的關(guān)系集上相同查詢結(jié)果的一個超元組集。如果對每一個原始關(guān)系 R1，R2，...，Rx僅運行一次基本查詢，那么將可以得到一個關(guān)系S，這個S包括所有在R1，R2，...，Rx的樣本集上運用同樣的查詢得到的一系列查詢結(jié)果。S的后處理將給予任何在樣本中執(zhí)行查詢時得到的任何結(jié)果。

假定兩個關(guān)系表:SUPERVISES(BOSS，EMP)和 AGE(EMP，YEARS)如下所示:

表1 關(guān)系表

使用下面的SQL查詢語句估計Mr.Smith管理員工的平均年齡:

SELECT AVG(AGE)

FROM SUPERVISES，AGE

WHERE BOSS=“Mr.Smith”AND

SUPERVISES.EMP=AGE.EMP

使用這個查詢，首先得到的用于計算平均年齡的S集是:

表2 基礎(chǔ)數(shù)據(jù)查詢結(jié)果

Mr.Smith管理員工的平均年齡估計結(jié)果為37.5。假設(shè)對兩個關(guān)系進行重采樣，如下表所示。對新生成的樣本進行前面一樣的查詢。用于計算平均年齡的S*集元組為:

表3 再采樣查詢結(jié)果

平均年齡的估計值為40.2。刪除了重復(fù)元組后，用于Bootstrap方法估算的元組集并未包含在取樣前的任何元組中。在基礎(chǔ)關(guān)系表上取樣的過程并不能創(chuàng)造新的元組，而只能改變S中元組在S*中出現(xiàn)的次數(shù)。如果關(guān)系R的一個元組t在R*中出現(xiàn)了n次，那么S中的任何一個依賴于t的元組將跟一些附加因素在S* 中出現(xiàn)n次。(“Mr.Smith”，“Joe”)在SUPERVISES關(guān)系表的樣本中出現(xiàn)了兩次，(“Joe”，42)在AGE關(guān)系表的樣本中出現(xiàn)2次。其結(jié)果是，元組(“Mr.Smith”，“Joe”，“Joe”，42)在 S* 中出現(xiàn)了4 次。

2 再抽樣實現(xiàn)

根據(jù)上面所舉的例子，就可以通過一個簡單的方法來模擬重復(fù)對每一個樣本表進行多次查詢的過程。通過預(yù)先運行樣本查詢，然后記住每一個元組在樣本關(guān)系表中出現(xiàn)的次數(shù)，這樣就可以達到預(yù)期。對于任何規(guī)模的關(guān)系R即使它有可能遠遠大過主存容量，也可以用一個簡單的算法來對其進行采樣(參見算法1)。

算法1 對R進行再抽樣

Vector temp=＜＞

For i=1 to|R|do產(chǎn)生一個1到|R|之間的隨機數(shù);將這個隨機數(shù)添加到temp;

對temp進行分類排序，如果本身很大，需要用到極限分類算法;

從頭到尾對temp進行瀏覽;對temp中的每一個i;

累計i在temp中出現(xiàn)的次數(shù);

End for

然后可以使用算法1求得的次數(shù)計算S中的每個元組在每一次Bootstrap方法查詢時重復(fù)出現(xiàn)的次數(shù)，如果運行完所有這些次數(shù)需要過多的主存空間作為緩存，而主存空間明顯不夠，那么就需要另外找一種比較好的的方法來處理這個問題了。目前處理該問題最簡單且最高效的辦法是運用一個I/O算法:將每個元組需要的存儲信息作為元組的屬性添加進數(shù)據(jù)表中，然后通過數(shù)據(jù)庫管理系統(tǒng)在整個Bootstrap過程對它們進行管理。對查詢結(jié)果的后期處理工作就是給出Bootstrap查詢的最終結(jié)果。

上例用到的數(shù)據(jù)表，要求所有元組進行b=10次采樣，且每個樣本的容量即每次采樣的次數(shù)n=10。運用算法1統(tǒng)計每一個元組在每一個樣本中重復(fù)出現(xiàn)的次數(shù)，并按樣本號進行GROUP BY分組。步驟如下:

創(chuàng)建 tuple_count(Tuple_id，Samp_id，Appear_count)和t_tuple(Tuple_id，Samp_id，num)，執(zhí)行下列SQL存儲過程:

CREATE PROCEDURE count_tuple_appear

AS

declare@i int

declare@j int

declare@samp int

set@i=1

while@i＜=10

begin

set@j=1;

while@j＜=8

begin

set@samp=1+abs(checksum(newid()))%(30)

insert into t_tuple select@samp，@i，1

set@j=@j+1

end

set@i=@i+1

end

3 再抽樣分析與實驗

通過上面的存儲過程，就將每次采樣的信息存入表t_tuple中。對t_tuple進行查詢就可以得到每一次抽樣過程的信息，結(jié)果如圖1所示:

圖1 隨機抽樣結(jié)果

對所得的結(jié)果進行分類并統(tǒng)計，即得出每次采樣過程中某個元組出現(xiàn)的次數(shù)，這個過程可通過下面的查詢過程得到，同時將結(jié)果存入到tuple_count表中，如圖2所示。

Insert into tuple_count

select tuple_id，samp_id，sum(num)as appear_count from t_tuple

group by tuple_id，samp_id

圖2 累計每次抽樣相同元組數(shù)

接下來，需要進行基礎(chǔ)查詢，并用查詢得到的結(jié)果產(chǎn)生一個S集，S中存儲的元組將用于f聚集函數(shù)的調(diào)節(jié)。這個任務(wù)是通過DBMS查詢引擎對存儲在數(shù)據(jù)庫中的所有數(shù)據(jù)執(zhí)行查詢來完成的，惟一的異常是因為numAppear數(shù)組的緣故，會增大所有不完整關(guān)系表的每個元組尺寸。這個數(shù)組被當(dāng)作是元組的附加屬性而貫穿于整個查詢的過程中。

最后，對S進行后處理以產(chǎn)生Si*(1≤i≤b)。當(dāng)所有的Si* 被計算出來后，就可以在所有的Si*上應(yīng)用f聚集函數(shù)，然后生成Bootstrap查詢的最終結(jié)果。注意到很多情況下，并不一定要將每一個Si*具體化。如果f可以計算(在許多使用普通聚集函數(shù)的情況下如AVG和SUM)，那么在計算Si*中的元組時，f的值將變化。

實驗使用傳統(tǒng)的DBMS進行查詢，采用TPC－H基準(zhǔn)［5］進行測試，DBGEN程序?qū)⒈壤蜃?SF)作為基準(zhǔn)參數(shù)生成TPC－H數(shù)據(jù)。使用比例因子SF=1來創(chuàng)建1GB數(shù)據(jù)集。選擇TPC－H基準(zhǔn)五個查詢Q1、Q2、Q6、Q12進行測試。采用C++和SQLSERVER2005實現(xiàn)，測試環(huán)境為XP 系統(tǒng)、Intel Xeon 2.4 GHz、4GB 內(nèi)存。

表4 查詢時間比較(單位:秒)

實驗得到的表4顯示改進方法最終產(chǎn)生的負載遠遠小于初始查詢所需抽樣次數(shù)，表明提升了Bootstrap方法的采樣效率，減少執(zhí)行查詢的次數(shù)，加快獲取結(jié)果的時間。

4 結(jié)論

本文改進了數(shù)據(jù)庫近似查詢的自動采樣，提升了Bootstrap方法的采樣效率，對海量數(shù)據(jù)數(shù)值類型的整個或者部分樣本進行基礎(chǔ)SQL查詢即完成對關(guān)系數(shù)據(jù)庫的近似查詢。雖然僅需要執(zhí)行一次基礎(chǔ)查詢就能利用Bootstrap方法，但對于整個查詢執(zhí)行過程，海量不完整數(shù)據(jù)樣本的所有元組仿真將造成巨大的性能負載。下一步的工作將進一步降低性能負載。

［1］HAAS P J，NAUGHTON J F，SESHADRI S，et al.Sampling-based estimation of the number of distinct values of an attribute［C］.Proceedings of the International Conference on Very Large Databases，1995:311－322.

［2］HASS P J，NAUGHTON J F，SESHADRI S，et al.Selectivity and cost estimation for joins based on random sampling［J］.Journal Compute System Science，1996，52(3):550 －569.

［3］ACHARTA S，GIBBONS P B，Poosala V，et al.The aqua approximate query answering system［C］.Proceedings of the ACM International Conference on Management of Data，2009:574 －576.

［4］HALL P.The bootstrap and edge worth expansion［M］.Berlin:Springer-Verlag，1995:56.

Research on Improved Method of Automatic Sampling of Approximate Question in Relational Databases

LI Qing-Hong
(Department of Information Engineering，Zhuzhou Professional and Technical College，Zhuzhou 41200，China)

Traditional accurate query of mass data is easy to lead to overload.This paper improves the bootstrap method for approximate queries.The sample query is executed in advance，according to the number of every tuple which appears in the sample relation，store information that these tuples need be added into a data table as store information，they are managed by DBMS in the whole bootstrap processing to classify and count obtained results to get the number of certain tuple which appears in every bootstrap processing.The experiment shows that the method is effective.

relational database;automatic sampling;SQL

(責(zé)任編校:光明)

TP392

A

1673－0712(2011)02－0087－04

2010－11－02.

李慶紅(1967—)，女，湖南株洲人，株洲職業(yè)技術(shù)學(xué)院信息工程系講師，碩士，研究方向:數(shù)據(jù)庫。