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

李慶紅

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

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

李慶紅

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

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

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

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

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

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

1 元組信息存儲(chǔ)

在應(yīng)用Bootstrap方法進(jìn)行數(shù)據(jù)的近似查詢時(shí)，算法用到的大量再抽樣和重復(fù)查詢操作產(chǎn)生了大量的負(fù)載，為了降低查詢負(fù)載，設(shè)法避免運(yùn)行基本查詢?cè)谝淮我陨稀?duì)于大多數(shù)關(guān)系數(shù)據(jù)庫(kù)查詢來說，實(shí)際上有很多種方法可以實(shí)現(xiàn)這個(gè)目標(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è)基本查詢是直接對(duì)R1和Ry關(guān)系上進(jìn)行的查詢，則S是f運(yùn)行在這個(gè)查詢上的元組的集合，換句話說，如果聚集函數(shù)f被SELECT* 語(yǔ)句代替以后，S將僅僅是這個(gè)查詢結(jié)果的多集。假設(shè)基本查詢不是直接運(yùn)行于R1，R2，...，Rx，而是運(yùn)用對(duì) R1，R2，...，Rx再抽樣后的集合，那么S*就被定義為f要運(yùn)行元組的多集。由于R*中的元素R1*，R2*，...，Rx*分別是再抽樣集合 R中樣本R1，R2，...，Rx，因而 R* 必是 R 的一個(gè)元組集。因此，使 R*與任何其它的關(guān)系進(jìn)行連接產(chǎn)生的元組集決定是R與相同關(guān)系連接產(chǎn)生元組集的子集。即結(jié)果集S*刪除重復(fù)元組后必包含于刪除重復(fù)元組后的S集。表示為S*(刪除重復(fù)元組后)?S(刪除重復(fù)元組后)。

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

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

表1 關(guān)系表

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

SELECT AVG(AGE)

FROM SUPERVISES，AGE

WHERE BOSS=“Mr.Smith”AND

SUPERVISES.EMP=AGE.EMP

使用這個(gè)查詢，首先得到的用于計(jì)算平均年齡的S集是:

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

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

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

平均年齡的估計(jì)值為40.2。刪除了重復(fù)元組后，用于Bootstrap方法估算的元組集并未包含在取樣前的任何元組中。在基礎(chǔ)關(guān)系表上取樣的過程并不能創(chuàng)造新的元組，而只能改變S中元組在S*中出現(xiàn)的次數(shù)。如果關(guān)系R的一個(gè)元組t在R*中出現(xiàn)了n次，那么S中的任何一個(gè)依賴于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 再抽樣實(shí)現(xiàn)

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

算法1 對(duì)R進(jìn)行再抽樣

Vector temp=＜＞

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

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

從頭到尾對(duì)temp進(jìn)行瀏覽;對(duì)temp中的每一個(gè)i;

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

End for

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

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

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

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 再抽樣分析與實(shí)驗(yàn)

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

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

對(duì)所得的結(jié)果進(jìn)行分類并統(tǒng)計(jì)，即得出每次采樣過程中某個(gè)元組出現(xiàn)的次數(shù)，這個(gè)過程可通過下面的查詢過程得到，同時(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 累計(jì)每次抽樣相同元組數(shù)

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

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

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

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

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

4 結(jié)論

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

［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ù)庫(kù)。