基于查詢和相對(duì)收益的物化視圖選擇算法

彭 成，佟秋利

（1.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京100084；2.清華大學(xué) 計(jì)算機(jī)與信息管理中心，北京100084）

0 引 言

在多維聯(lián)機(jī)分析系統(tǒng)中，將數(shù)據(jù)進(jìn)行聚集生成物化視圖預(yù)先存儲(chǔ)起來，對(duì)一些查詢可以直接給出結(jié)果，而不必進(jìn)行聚集計(jì)算，提高了查詢的效率。物化視圖需要占用空間，對(duì)于高維度的數(shù)據(jù)集來說，可以生成的物化視圖的總個(gè)數(shù)隨著維度上升成指數(shù)級(jí)增長，需要進(jìn)行物化視圖的選擇。

目前物化視圖選擇的策略較多，但是并沒有得到普遍的最優(yōu)算法，物化視圖選擇調(diào)整問題本身也被證明為NPHard問題［1］。在數(shù)據(jù)倉庫系統(tǒng)運(yùn)行過程中，對(duì)著用戶查詢的不斷變化，已有的選擇策略可能并不能滿足當(dāng)前的用戶查詢習(xí)慣，如何準(zhǔn)確地把握用戶查詢類型的分布，并選擇合適的時(shí)間段進(jìn)行調(diào)整，是當(dāng)前研究的重要問題。

Theodoratos D提出了對(duì)物化視圖定期地進(jìn)行動(dòng)態(tài)調(diào)整的方法，通過判斷用戶一段時(shí)間內(nèi)的查詢情況變化，結(jié)合物化視圖本身的查詢代價(jià)綜合考慮，選擇合適的時(shí)間進(jìn)行調(diào)整。除了這種階段性調(diào)整的方式之外還有實(shí)時(shí)動(dòng)態(tài)調(diào)整的方式，Cohen E提出了按照查詢請(qǐng)求的變化來實(shí)時(shí)改變每個(gè)物化視圖的優(yōu)先級(jí)，進(jìn)行實(shí)時(shí)調(diào)整。不過這種方式調(diào)整又過于頻繁，對(duì)于查詢請(qǐng)求比較多的情況下不適用，另外視圖集經(jīng)常變化，不夠穩(wěn)定，對(duì)于隨機(jī)性強(qiáng)的查詢并不是很實(shí)用。

本文提出了根據(jù)查詢進(jìn)行動(dòng)態(tài)調(diào)整的選擇算法，同時(shí)又考慮到視圖的收益和占用空間，而且可以由用戶自行設(shè)定維屬性權(quán)重，不斷調(diào)整出最適合的物化視圖選擇方案。

1 物化視圖概念介紹

為了能夠更快地得到查詢結(jié)果，在多維聯(lián)機(jī)分析系統(tǒng)中，也會(huì)采用類似于視圖的策略，將數(shù)據(jù)進(jìn)行聚集處理并預(yù)先存儲(chǔ)起來作為中間結(jié)果，當(dāng)查詢?cè)L問需要利用到其結(jié)果時(shí)可以直接給出，而不必進(jìn)行聚集計(jì)算，這個(gè)中間結(jié)果便是物化視圖。對(duì)于傳統(tǒng)的二維數(shù)據(jù)庫，視圖的存在方便了查詢，但是視圖本身是一個(gè)虛表，并不真實(shí)存在，只是方便用戶瀏覽的一種形態(tài)，在實(shí)際查詢時(shí)還是會(huì)調(diào)用原始數(shù)據(jù)庫進(jìn)行計(jì)算，在效率上并沒有提高，查詢時(shí)也需要重新進(jìn)行計(jì)算。而物化視圖則不同，它是真實(shí)存在的中間結(jié)果，可以提高查詢的效率。在OLAP查詢中，有時(shí)會(huì)遇到很復(fù)雜并且需要調(diào)用多個(gè)維度，涉及到多種數(shù)據(jù)的查詢，這個(gè)時(shí)候需要對(duì)數(shù)據(jù)進(jìn)行連接、投影等操作，其對(duì)時(shí)間的消耗是很大的，如果每次都需要進(jìn)行重新計(jì)算，則滿足不了聯(lián)機(jī)分析系統(tǒng)對(duì)查詢的快速響應(yīng)要求。物化視圖的出現(xiàn)解決了這一問題，它對(duì)可能需要調(diào)用到的結(jié)果事先進(jìn)行投影、連接、選擇等操作生成中間數(shù)據(jù)并存放起來，是真實(shí)地存放在數(shù)據(jù)倉庫中的，每次查詢時(shí)可以直接從物化視圖返回結(jié)果，提高了查詢的效率。

2 物化視圖的選擇及調(diào)整

物化視圖的存在使得數(shù)據(jù)倉庫獲得了較快的查詢速度，物化視圖的選擇策略對(duì)查詢速度有著決定性的影響。目前物化視圖選擇的策略較多，但是并沒有得到普遍的最優(yōu)算法。完全物化的數(shù)據(jù)集的數(shù)據(jù)量隨著維度數(shù)量而指數(shù)級(jí)增長，對(duì)于高維度的數(shù)據(jù)倉庫，完全物化并存儲(chǔ)是難以實(shí)現(xiàn)的。因此，就需要選擇其中部分的物化視圖來存放，即物化視圖的選擇策略問題，在特定的空間限制條件下，選擇出合適的物化視圖集，使得數(shù)據(jù)倉庫對(duì)用戶查詢有著最快的響應(yīng)。

物化視圖的選擇策略一般由3個(gè)方面因素決定：存儲(chǔ)空間占用，維護(hù)代價(jià)以及生成物化視圖帶來的收益。

（1）存儲(chǔ)空間占用：由于物化視圖的大小各不相同，維度包含的越多，數(shù)據(jù)劃分的越精細(xì)的物化視圖一般占用的空間較多，即使它可以為用戶節(jié)省很多的時(shí)間，但是有時(shí)將空間節(jié)省下來存放更多的占用空間較少的物化視圖更為劃算。從本質(zhì)上來說，物化視圖的存在是用空間交換時(shí)間的技術(shù)，物化視圖的個(gè)數(shù)是受到約束的。

（2）維護(hù)代價(jià)：即當(dāng)原始數(shù)據(jù)庫中的數(shù)據(jù)發(fā)生變化時(shí)，物化視圖作為實(shí)際存在的數(shù)據(jù)，也是需要同步更新來保持?jǐn)?shù)據(jù)一致。對(duì)于較大的數(shù)據(jù)倉庫來說，更新數(shù)據(jù)的耗時(shí)會(huì)比較長，如果與之相關(guān)的物化視圖比較多，那么更新的代價(jià)就很大，這時(shí)需要減少物化視圖的數(shù)量以得到平衡。對(duì)于空間限制比較寬松的情況，物化視圖過多的話會(huì)影響到更新時(shí)的速度，所以如何尋找平衡點(diǎn)也是物化視圖選擇中一個(gè)重要的考慮因素。

（3）物化視圖帶來的收益：指不生成某個(gè)物化視圖和生成此物化視圖對(duì)查詢速度的貢獻(xiàn)，對(duì)于生成了物化視圖的情況，相應(yīng)的查詢可以直接得到結(jié)果，未生成物化視圖的查詢時(shí)間計(jì)算需要考慮到選擇、連接、聚集等幾個(gè)方面的運(yùn)算速度。收益分為相對(duì)收益和絕對(duì)收益，相對(duì)收益是生成物化視圖對(duì)現(xiàn)有視圖集的效率改進(jìn)。而絕對(duì)收益就是物化視圖對(duì)原始數(shù)據(jù)集的效率改進(jìn)。一般進(jìn)行收益計(jì)算時(shí)，采用的是相對(duì)收益，其更能反映實(shí)際的收益效果。

本文采用的方式是定期更新與根據(jù)查詢效率更新相結(jié)合的方式，一方面對(duì)每次查詢請(qǐng)求判斷是否生成相應(yīng)的物化視圖，通過一個(gè)閾值來作為是否生成的評(píng)判標(biāo)準(zhǔn)；另一方面設(shè)定一個(gè)固定時(shí)間進(jìn)行全局性的物化視圖集的更新，主要是按照每個(gè)物化視圖集的權(quán)重進(jìn)行排序并將靠前的物化視圖生成。當(dāng)然已經(jīng)存在的不需要生成，只需要生成那些新出現(xiàn)的物化視圖。

3 數(shù)據(jù)立方體格結(jié)構(gòu)圖

對(duì)于物化視圖，每種維度有聚集和不聚集兩種選擇，共有2＾n個(gè)可能的物化視圖。如果一個(gè)物化視圖A的所有維度都在另一個(gè)物化視圖B中出現(xiàn)，即B將數(shù)據(jù)集劃分得更為精細(xì)，同時(shí)劃分方式是包括A的所有劃分方式的，此時(shí)B和A是一種偏序關(guān)系，記做A≦B，所有的可以由A計(jì)算的查詢都可以由B來計(jì)算得到。對(duì)于物化視圖的集合｛V1，V2，V3……Vn｝，它們之間以視圖之間的偏序關(guān)系作為箭頭，視圖本身作為結(jié)點(diǎn)形成的圖就叫做數(shù)據(jù)立方體的格圖。

例如，對(duì)一個(gè)有4個(gè)維度的數(shù)據(jù)集，4個(gè)維度分別為部門（A），科目（B），項(xiàng)目（C），年份（D），那么其可能的物化視圖共有2＾4＝16個(gè)，按照維度數(shù)量可以分組如下：

（1）（A，B，C，D），即數(shù)據(jù)集本身

（2）（A，B，C），（A，B，D），（A，C，D），（B，C，D）

（3）（A，B），（A，C），（A，D），（B，C），（B，D），（C，D）

（4）（A），（B），（C），（D）

（5）none，即不劃分的數(shù)據(jù)

這些物化視圖按照維度的包含關(guān)系可以生成格結(jié)構(gòu)圖，維度的包含關(guān)系也表明了對(duì)于相應(yīng)查詢的包含關(guān)系，即若一個(gè)物化視圖是包含另一個(gè)的，那么它可以進(jìn)行另一個(gè)物化視圖能夠進(jìn)行的所有查詢。上面的物化視圖集能夠形成的數(shù)據(jù)立方體格結(jié)構(gòu)圖如圖1所示。

其中的邊是從上往下的單向邊，上面是父結(jié)點(diǎn)，下面是子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)表示一個(gè)物化視圖，結(jié)點(diǎn)的內(nèi)容即物化視圖中包含的維度。例如（A，B）表示按照部門和科目分類形成的物化視圖。（A，B，C，D），（A，B，C），（A，B，D）都存在流向（A，B）的通路，表明（A，B）這一物化視圖可以被它們生成，能從（A，B）得到結(jié)果的查詢都可以從上面3個(gè)物化視圖中任意一個(gè)通過聚集計(jì)算得到。

圖1 數(shù)據(jù)立方體格結(jié)構(gòu)

4 BWCC權(quán)重及相對(duì)收益計(jì)算模型

本文采用基于用戶查詢習(xí)慣和物化視圖加權(quán)相對(duì)收益的動(dòng)態(tài)選擇算法。其考慮了視圖的大小，視圖的相對(duì)收益，另外還考慮了物化視圖所包含的每項(xiàng)屬性的權(quán)重，即特定的某項(xiàng)維度被查詢的可能性，另外系統(tǒng)根據(jù)用戶的查詢輸入進(jìn)行學(xué)習(xí)，根據(jù)查詢頻率動(dòng)態(tài)調(diào)整，保持提供最適合的物化視圖選擇方案。

影響選擇方案的核心因素有幾個(gè)：查詢頻率，特定維度的權(quán)重，視圖大小以及物化視圖帶來的相對(duì)收益。用Vq來表示視圖q的價(jià)值，并采用查詢驅(qū)動(dòng)機(jī)制，每次查詢涉及到的視圖的價(jià)值相應(yīng)增大，不定期地更新物化視圖以滿足不斷變化的查詢需求。

（1）維度權(quán)重用來表示每項(xiàng)維度被查詢到的可能性的大小，初始化均為1，可由用戶自行定義更改，對(duì)于特定的物化視圖q，其維度權(quán)重Weight（q）為所有維度項(xiàng)權(quán)重的平均值。

（2）物化視圖q的相對(duì)收益Ben（q）表示物化視圖q給已有的物化視圖集帶來的查詢效率的改進(jìn)，B（q，s）＝∑v≤qBv，其中v為在格結(jié)構(gòu)圖中q的子結(jié)點(diǎn)，Bv為q對(duì)于v帶來的查詢效率的改進(jìn)。定義w為v的父結(jié)點(diǎn)中已經(jīng)生成物化視圖并且具有最少的元組數(shù)的節(jié)點(diǎn)，如果C（v）＜C（w），則Bv＝C（w）－C（v），否則Bv＝0。

（3）查詢頻率Count（q）表示視圖q被查詢到的次數(shù)，每個(gè)查詢都可以對(duì)應(yīng)到與查詢條件含有同樣維度條件的物化視圖q。

（4）物化視圖q的占用空間的大小是衡量其價(jià)值的另一因素，其與物化視圖包含的元組數(shù)C（q）成正比，在計(jì)算價(jià)值時(shí)可以直接用C（q）表示。對(duì)于具有一定稀疏度的多維數(shù)據(jù)集，實(shí)際生成的物化視圖尺寸往往會(huì)小一些。假定原始多維數(shù)據(jù)集的稀疏度為k，物化視圖較原數(shù)據(jù)集對(duì)n個(gè)維度進(jìn)行了聚集，每個(gè)維度包含的屬性項(xiàng)數(shù)為d1，d2，……dn，原始數(shù)據(jù)集元組數(shù)量為a，則新物化視圖的元組數(shù)量C（q）估計(jì)值為

本文采用的算法對(duì)物化視圖價(jià)值Value（q）計(jì)算的公式 為Value（q）＝Ben（q）＊Weight（q）＊Count（q）2／C（q）。從上式可以看出，本文的算法中物化視圖q的價(jià)值Value（q）與其相對(duì)收益Ben（q）和視圖權(quán)重Weight（q）成正比，收益和維度權(quán)重越大，視圖價(jià)值越高；Value（q）與查詢到的次數(shù)Count（q）的平方成正比，查詢到的次數(shù)越多，視圖價(jià)值越高，同時(shí)在一段時(shí)間內(nèi)查詢到的次數(shù)越多，價(jià)值增長越快；Value（q）與視圖的元組數(shù)個(gè)數(shù)成反比，表示視圖越大，占用空間越多，其價(jià)值越低。

5 BWCC算法實(shí)現(xiàn)

在借鑒已有的算法基礎(chǔ)上，本文給出了基于查詢習(xí)慣和加權(quán)相對(duì)收益的動(dòng)態(tài)選擇及調(diào)整算法，算法的流程圖如圖2所示。

圖2 BWCC算法流程

對(duì)于物化視圖的初始選擇，可以由用戶指定，也可以由系統(tǒng)根據(jù)設(shè)置的維度權(quán)重和視圖占用空間大小進(jìn)行自行選擇，算法具體描述如下：

算法1：初始選擇物化視圖集算法

輸入：空間限制S，視圖集V

輸出：物化視圖集MV

／／初始化視圖集V中每個(gè)視圖q的價(jià)值Value＿begin（q）

for each q in V

Value＿begin（q）＝Weight（q）／Size（q）；

對(duì)所有q按照Value＿begin（q）從大到小進(jìn)行排序；

while（S＞0）｛

for each q in V｛／／遍歷視圖集

／／選擇視圖加入物化視圖集

if（S－Size（q）＞0）｛

MV＝MV＋ ｛q｝；／／將視圖q加入物化視圖集

S＝S－Size（q）；／／減少剩余空間

｝｝｝

return MV；

對(duì)于物化視圖的初始選擇，可以由用戶指定，也可以由系統(tǒng)根據(jù)設(shè)置的維度權(quán)重和視圖占用空間大小進(jìn)行自行選擇，Size（q）表示物化視圖q占用的空間大小，初始時(shí)的視圖價(jià)值是通過該視圖所包含的維度權(quán)重的平均數(shù)以及視圖大小綜合考慮的。維度權(quán)重的平均數(shù)越大，視圖包含的維度越容易被查詢到，其價(jià)值就越高，而視圖的占用空間越大，其價(jià)值就越低。

隨著用戶查詢的輸入，算法會(huì)根據(jù)查詢的頻率調(diào)整各個(gè)視圖的價(jià)值，并判斷是否需要進(jìn)行物化視圖集的局部更新和全局更新。對(duì)于查詢輸入a，視圖調(diào)整的算法步驟如下：

算法2：物化視圖集調(diào)整算法

輸入：查詢a，物化視圖集MV

輸出：物化視圖集MV

if（MV中存在視圖q，a對(duì)應(yīng)的視圖＜＝q，且C（q）最?。?/p>

由q來回答a；

｝

else從原始多維數(shù)據(jù)集聚集計(jì)算回答a；

Count（q）＋＋；／／a對(duì)應(yīng)的視圖計(jì)數(shù)增加

Value（q）＝Ben（q）＊ Weight（q）＊ Count（q）＊Count（q）／C（q）；／／更新視圖q的價(jià)值

Count＿all＋＋；／／全局更新計(jì)數(shù)增加

／／當(dāng)查詢未命中而且q價(jià)值增加較多時(shí)，調(diào)用局部更新的算法

if（Count＿all＜time ＆ ＆ 查詢未命中 ＆ ＆ Value（q）－Value＿old（q）＞val）｛

調(diào)用局部更新的算法；

｝

else｛調(diào)用全局更新算法；｝

Return MV；

每次查詢時(shí)，都會(huì)對(duì)相對(duì)應(yīng)的視圖的計(jì)數(shù)進(jìn)行增加，不斷更新視圖的價(jià)值。更新后會(huì)計(jì)算視圖新的價(jià)值與舊的價(jià)值之差，當(dāng)差值高于一定值時(shí)，說明此視圖最近比較常用，并且在這段時(shí)間內(nèi)可能會(huì)經(jīng)常用到，需要進(jìn)行物化，以便提高之后的查詢效率和命中率。視圖局部更新的方法為先判斷當(dāng)前空間限制是否足夠容納q，如果不足，則刪去價(jià)值最小的視圖，直到空間足夠，最后將q加入物化視圖集。

算法3：物化視圖集局部更新算法

輸入：查詢對(duì)應(yīng)的視圖q，物化視圖集MV，空間限制S

輸出：物化視圖集MV

if（S－Size（q）＞0）｛／／剩余空間滿足條件時(shí)，直接添加q進(jìn)入物化視圖集

MV＝MV＋ ｛q｝；／／添加q到物化視圖集

S＝S－Size（q）；／／更新空間限制

｝else｛

／／空間不夠時(shí)，刪除物化視圖以騰出空間

while（S－Size（q）＜0）｛

獲得價(jià)值最小的物化視圖q′

MV＝MV－q′；／／將其刪除

S＝S＋Size（q′）；／／更新空間限制

｝

MV＝MV＋ ｛q｝；／／添加q到物化視圖集

S＝S－Size（q）；／／更新空間限制

｝

return MV；

當(dāng)過了一定長度的時(shí)間后，用戶的習(xí)慣可能已經(jīng)發(fā)生了變化，此時(shí)需要對(duì)物化視圖進(jìn)行全局的更新，利用歷史價(jià)值信息以及視圖本身的價(jià)值進(jìn)行綜合判斷，選擇合適的視圖進(jìn)行物化完成全局更新的操作。全局更新的方法與初始選擇類似，不同的是對(duì)于視圖價(jià)值的計(jì)算，全局更新是對(duì)當(dāng)前視圖價(jià)值乘以歷史系數(shù)Value（q）＝Value（q）＊v＿h(yuǎn)is，其值在0到1之間，可以參考用戶習(xí)慣的延續(xù)性進(jìn)行設(shè)定。

算法4：物化視圖集全局更新算法

輸入：物化視圖集MV，空間限制S，歷史系數(shù)v＿h(yuǎn)is

輸出：物化視圖集MV

／／對(duì)V中每個(gè)視圖q計(jì)算價(jià)值

for each q in V｛

Value（q）＝Value（q）＊v＿h(yuǎn)is；／／計(jì)算時(shí)乘以歷史系數(shù)v＿h(yuǎn)is

Value＿old（q）＝Value（q）；／／更新 Value＿old的值

Count（q）＝0；／／清零查詢計(jì)數(shù)

｝

對(duì)V中的所有視圖按照價(jià)值從大到小進(jìn)行排序；

／／從大到小加入物化視圖集

While（S＞0）｛

for（each q in V）｛

if（S－Size（q）＞0）｛／／空間足夠時(shí)添加q到物化視圖集

MV＝MV＋ ｛q｝；／／加入物化視圖集

S＝S－Size（q）；／／更新空間限制

｝｝｝

return MV；

本文中的BWCC算法的在初始選擇時(shí)的復(fù)雜度是O（nlogn），與排序算法相同。在系統(tǒng)運(yùn)行過程中，隨著用戶查詢的到來，還會(huì)進(jìn)行局部更新和全局更新，局部更新的時(shí)間復(fù)雜度與視圖數(shù)量無關(guān)，耗時(shí)較少；全局更新的時(shí)間復(fù)雜度和初始選擇相同，也是O（nlogn）。

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

本文將BWCC算法與貪心算法和排序算法進(jìn)行對(duì)比，分析了其時(shí)間復(fù)雜度，測(cè)試了其查詢命中率和總體收益。本文在CPU 類型為 Genuine Intel（R）T2050 1.60GHz，1.60GHz的計(jì)算機(jī)中進(jìn)行測(cè)試，測(cè)試對(duì)象為一個(gè)維度層次項(xiàng)個(gè)數(shù)為10，每項(xiàng)對(duì)應(yīng)的屬性值個(gè)數(shù)為5，事實(shí)項(xiàng)個(gè)數(shù)為2的多維數(shù)據(jù)集，空間限制為10%。

測(cè)試分為兩組數(shù)據(jù)進(jìn)行，第一組數(shù)據(jù)為完全隨機(jī)生成的1000個(gè)查詢，每個(gè)維度屬性在查詢中出現(xiàn)的概率相同，均為0.5。第二組分為3個(gè)階段，每階段1000個(gè)查詢，并讓其中指定的10個(gè)維度屬性在查詢中出現(xiàn)的概率增至0.8，其余40個(gè)維度屬性的出現(xiàn)概率更改為0.2。對(duì)于不同的階段，更換指定的10個(gè)維度，用以表現(xiàn)用戶習(xí)慣的歷史延續(xù)性。

第一組查詢命中率比較如圖3所示。

圖3 第一組查詢命中率比較

對(duì)于第一組查詢，由于查詢是完全隨機(jī)的，所以3種算法在命中率上差別并不大。對(duì)于靜態(tài)的貪心算法和排序算法來講，在初始選擇物化視圖集后就不作變化，其命中率也只和初始的選擇有關(guān)。對(duì)于BWCC算法，它的動(dòng)態(tài)調(diào)整機(jī)制對(duì)于完全隨機(jī)的查詢沒有意義，其初始選擇算法和排序算法相同，也是按照尺寸大小進(jìn)行排序，因此其命中率也和排序算法接近?？傮w來講，3種算法在對(duì)于完全隨機(jī)的用戶查詢，其命中率是大體接近的。

第二組查詢命中率比較如圖4所示。

對(duì)于具有一定規(guī)律的用戶查詢，查詢的結(jié)果走勢(shì)大致分為三段，每段對(duì)應(yīng)1000個(gè)查詢。對(duì)于貪心算法和排序算法來說，物化視圖在初始確定之后就不變了，命中率取決于被賦予高出現(xiàn)概率的維度屬性是否有其物化視圖在初始時(shí)被生成。排序算法和貪心算法的命中率隨著維度屬性出現(xiàn)概率的分布變化而變化，時(shí)高時(shí)低，呈現(xiàn)隨波逐流的態(tài)勢(shì)，而不能保持一個(gè)相對(duì)穩(wěn)定的命中率。

圖4 第二組查詢命中率比較

對(duì)于BWCC算法，在上面的實(shí)驗(yàn)中，大體分為3個(gè)階段。每個(gè)階段的命中率都是開始較低，而后逐漸升高。逐漸升高的原因是它隨著用戶查詢不斷調(diào)整自己的物化視圖集。而每當(dāng)查詢偏好變化時(shí)，由于其之前生成的物化視圖集與新的查詢習(xí)慣不一定匹配，所以命中率會(huì)出現(xiàn)一定的下降，隨著時(shí)間的推移，其自我調(diào)整的機(jī)制又將命中率不斷提高。可以看出，針對(duì)這種有一定側(cè)重的查詢集合，BWCC算法的命中率要高于貪心算法和排序算法，對(duì)于查詢偏好的變更也有較好的處理能力，本文中的BWCC算法在命中率上具有較大優(yōu)勢(shì)。

7 結(jié)束語

本文對(duì)數(shù)據(jù)倉庫系統(tǒng)中的物化視圖選擇問題進(jìn)行了研究，提出了基于習(xí)慣和加權(quán)相對(duì)收益的動(dòng)態(tài)選擇及調(diào)整算法BWCC，此算法考慮了視圖的相對(duì)收益、視圖尺寸、維屬性權(quán)重以及用戶查詢習(xí)慣，可以根據(jù)查詢的偏好進(jìn)行動(dòng)態(tài)的調(diào)整，提高了命中率。另外用戶也可以給不同的維度屬性賦予不同的權(quán)重來表示其被查詢到的可能性大小，權(quán)重也會(huì)影響到系統(tǒng)對(duì)于物化視圖集的選擇，可以更好地對(duì)用戶偏好做出改變。總體來說，這一算法的命中率高于傳統(tǒng)選擇算法，還可以根據(jù)用戶習(xí)慣進(jìn)行動(dòng)態(tài)調(diào)整，時(shí)間復(fù)雜度與傳統(tǒng)選擇算法差別不大，相對(duì)于傳統(tǒng)算法有較大的優(yōu)勢(shì)。

［1］PMark Whitehorn，PRobert Zare，Mosha Pazusmansky.Problem solving for MDX for SQL Server 2005［M］.New York：Springer－Verlag，2007：105－131.

［2］LI Caihua.Application of OLAP technology in production evaluation［J］.Computing Technology and Automation，2009，28（4）：133－137（in Chinese）.［李才華.OLAP技術(shù)在生產(chǎn)評(píng)價(jià)中的應(yīng)用［J］.計(jì)算技術(shù)與自動(dòng)化，2009，28（4）：133－137.］

［3］LAN Jian，JIN Hongmei.The design and realization of OLAP based data warehouse analysis model in enterprises［J］.Process Automation Instrumentation，2006，27（5）：9－12（in Chinese）.［藍(lán)箭，金紅梅.基于OLAP的企業(yè)數(shù)據(jù)倉庫分析模型設(shè)計(jì)與實(shí)現(xiàn)［J］.自動(dòng)化儀表，2006，27（5）：9－12.］

［4］CHEN Qimai，HE Chaobo，LIU Hai.OLAP－based collaborative educational decision［J］.Computer Applications，2009，29（1）：304－305（in Chinese）.［陳啟買，賀超波，劉海.基于OLAP的高校教學(xué)協(xié)同決策［J］.計(jì)算機(jī)應(yīng)用，2009，29（1）：304－305.］

［5］Themis Palpanas，Nick Koudas，Alberto O Mendelzon.On space constrained set selection problems［M］.England：Data Knowl，2008：200－218.

［6］JIANG Nan，GAO Wei，ZHANG Liqiu.Research and application of data mining model based on analysis services［J］.Machinery Design ＆ Manufacture，2007（4）：83－85（in Chi－nese）.［姜楠，高巍，張麗秋.基于Analysis Services的數(shù)據(jù)挖掘模型的研究與應(yīng)用［J］.機(jī)械設(shè)計(jì)與制造，2007（4）：83－85.］

［7］Kobra Etminani，Prof M Naghibzadeh.A min－min max－min selective algorithm for grid task scheduling［C］／／Uzbekistan：3rd IEEE／IFIP International Conference in Central Asia，2007：1－7.

［8］Dong F，Akl S G.Scheduling algorithms for grid computing：state of the art and open problems［R］.Technical Report，2006.

［9］Tang Zhaohui，Jamie MacLennan.Data mining with SQL server 2005［M］.Beijing：Tsinghua University Press，2007：45－53（in Chinese）.［Tang Zhaohui，Jamie MacLennan.Data mining with SQL server 2005［M］.北京：清華大學(xué)出版社，2007：45－53.］

［10］Gupta H，Mumick I S.Selection of views to materialize under a maintenance cost constraint［C］／／ICDT，1999：453－470.