基于維層次的語義Ｃｕｂｅ存儲(chǔ)與增量更新技術(shù)研究

摘 要：利用維的層次性為每一個(gè)維建立一個(gè)索引，同時(shí)保存相應(yīng)的層次信息和預(yù)聚集數(shù)據(jù)，提出了基于維層次的語義Cube。在進(jìn)行數(shù)據(jù)更新時(shí)，使用更新前后的差值自下而上對(duì)受到更新單元影響的祖先節(jié)點(diǎn)進(jìn)行增量更新，在進(jìn)行模式更新時(shí)，無需重構(gòu)Cube，即可實(shí)現(xiàn)增量更新。由于其存儲(chǔ)結(jié)構(gòu)的靈活性，在高效完成增量更新的同時(shí)實(shí)現(xiàn)了Cube上進(jìn)行上探、下鉆等語義操作。理論分析和實(shí)驗(yàn)結(jié)果均表明，提出的基于維層次的語義Cube與傳統(tǒng)Cube相比，性能顯著提高。

關(guān)鍵詞：數(shù)據(jù)倉庫; 語義Cube; 增量更新

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0213-03

隨著數(shù)據(jù)倉庫逐漸成為企業(yè)決策支持的重要技術(shù)手段，如何有效地實(shí)現(xiàn)數(shù)據(jù)倉庫及其優(yōu)化問題日益成為人們重視和關(guān)注的焦點(diǎn)之一。數(shù)據(jù)倉庫及其分析工具——OLAP分析往往是基于多維數(shù)據(jù)模型，它由維和事實(shí)度量組成。在該模型中數(shù)據(jù)通常以數(shù)據(jù)立方體（Data Cube）形式進(jìn)行存儲(chǔ)［1］，通過數(shù)據(jù)聚集技術(shù)和高性能的多維存儲(chǔ)結(jié)構(gòu)組織和匯總了大量的聚集數(shù)據(jù)，為OLAP提供快速的多維信息分析。近年來，許多專家學(xué)者先后在Cube聚集計(jì)算［2，3］、Cube壓縮存儲(chǔ)［4－6］、Cube并行計(jì)算［7，8］等方面取得了一些成果，在一定程度上提高了Cube的數(shù)據(jù)查詢性能。但這些Cube在數(shù)據(jù)更新時(shí)，重構(gòu)開銷較大，且不能實(shí)現(xiàn)Cube增量更新；而且沒有保存維的層次及層次關(guān)系等語義信息，不能支持Cube在語義上的查詢操作；未充分利用維層次屬性對(duì)數(shù)據(jù)單元進(jìn)行簇集存放，在查詢和更新時(shí)，增加了I/O開銷，降低了Cube的查詢和更新效率。為此，本文提出了基于維層次的語義Cube，它的基本思想是：利用B+樹為Cube中的每一個(gè)維建立索引，同時(shí)保存相應(yīng)的層次信息和預(yù)聚集數(shù)據(jù)，實(shí)現(xiàn)了在Cube上進(jìn)行上探、下鉆等語義操作。由于數(shù)據(jù)倉庫系統(tǒng)是一種面向用戶的分析型應(yīng)用系統(tǒng)，必須根據(jù)用戶的需求不斷進(jìn)行完善和補(bǔ)充，數(shù)據(jù)倉庫的數(shù)據(jù)和模式要隨著分析任務(wù)的需要不斷更新。如何在基于維層次的語義Cube中高效實(shí)現(xiàn)增量更新是本文要討論的一個(gè)主要方面。

1 基于維層次的語義Cube

1.1 存儲(chǔ)結(jié)構(gòu)

例如表1是某賣場(chǎng)銷售情況的Cube二維表表示，它由地區(qū)維、產(chǎn)品維、時(shí)間維三個(gè)維和一個(gè)銷售量的度量值構(gòu)成。其中，地區(qū)、產(chǎn)品、時(shí)間均是由相應(yīng)維中的層次所組成的一個(gè)有序集。

表1 一個(gè)商品銷售情況的Cube二維表表示

定義3（基于維層次的語義Cube，DHSC） 對(duì)于維層次組合，通過B+樹的維層次屬性，對(duì)Cube按各個(gè)維層次進(jìn)行分割和分組聚集計(jì)算，即在第i維上依照hi進(jìn)行邏輯劃分，并且對(duì)于每個(gè)邏輯塊均進(jìn)行塊內(nèi)聚集并存儲(chǔ)到上一層次的聚集Cube中，則稱得到的Cube為維層次組合所對(duì)應(yīng)的基于維層次的語義Cube。

1.2 基于維層次的語義Cube的創(chuàng)建

基于維層次的語義Cube是通過數(shù)據(jù)倉庫的建模工具為其各個(gè)維創(chuàng)建層次樹，從維層次粒度最細(xì)的Cube開始，按各個(gè)B+樹中的維層次屬性，對(duì)Cube中粒度較細(xì)的各個(gè)數(shù)據(jù)單元（Cell）進(jìn)行劃分成若干個(gè)互不相交的分割子Cube，并對(duì)每一個(gè)分割子Cube的聚集值按維層次前綴進(jìn)行分組聚集計(jì)算，將計(jì)算得到的聚集值存儲(chǔ)到父Cube中，再對(duì)生成的父Cube按維層次粒度由細(xì)到粗進(jìn)行遞歸地分割和分組聚集計(jì)算，直至維層次粒度最粗時(shí)為止。其中每個(gè)節(jié)點(diǎn)包括兩個(gè)指針(childPtr為指向下一層子Cube的指針，parentPtr為指向上一層父Cube的指針)，一個(gè)標(biāo)志（flag，當(dāng)flag＝0時(shí)為葉子節(jié)點(diǎn)，flag＝1時(shí)為目錄節(jié)點(diǎn)），兩個(gè)存儲(chǔ)區(qū)域（MBBc表示該節(jié)點(diǎn)所包含的范圍，采用維層次編碼方式來表示，按維層次編碼組合的混合編碼的Hash函數(shù)來計(jì)算其存儲(chǔ)地址，作為Cube中數(shù)據(jù)單元的存取依據(jù)。chunk用于存儲(chǔ)具有相同維層次的多個(gè)數(shù)據(jù)單元cell，其大小以能裝入內(nèi)存為宜，各數(shù)據(jù)塊chunk可以按Cube中節(jié)點(diǎn)的層次次序和各個(gè)維相應(yīng)順序進(jìn)行簇集存儲(chǔ)）。

1.3 Cube語義操作

上探操作是指在某一維上將低層次的細(xì)節(jié)數(shù)據(jù)概括到高層次的匯總數(shù)據(jù)，或減少維數(shù)，而下鉆操作是從匯總數(shù)據(jù)深入到細(xì)節(jié)數(shù)據(jù)進(jìn)行觀察或增加新維。

在基于維層次的語義Cube中，假設(shè)數(shù)據(jù)已經(jīng)存放在內(nèi)存或緩存中，利用B+樹中保存的層次信息，上探時(shí)，就相當(dāng)于數(shù)據(jù)沿著B+樹往上聚集，即沿著parentPtr指針向上對(duì)所對(duì)應(yīng)的邏輯塊進(jìn)行聚集計(jì)算，下鉆時(shí)沿childPtr指針向下對(duì)所對(duì)應(yīng)的邏輯塊進(jìn)行訪問。

例如，在表1二維Cube所對(duì)應(yīng)的DHSC中，從<產(chǎn)品型號(hào)，月份>層次聚集Cube到<產(chǎn)品名，季度>層次聚集Cube進(jìn)行的聚集查詢過程就是Cube上探操作，可以沿<產(chǎn)品型號(hào)，月份>層次聚集Cube 相應(yīng)節(jié)點(diǎn)的parentPtr指針向上對(duì)所對(duì)應(yīng)的<產(chǎn)品名，季度>層次聚集Cube中的邏輯塊進(jìn)行訪問。

2 DHSC增量更新技術(shù)

2.1 模式更新

2.1.1 維的增刪

在對(duì)數(shù)據(jù)倉庫中的數(shù)據(jù)進(jìn)行OLAP分析時(shí)，預(yù)先假定度量值同a1、a2、a3三個(gè)屬性相關(guān)，因此建立了d1、d2、d3三個(gè)維，但在經(jīng)過數(shù)據(jù)分析后，可能發(fā)現(xiàn)屬性a4對(duì)度量值有影響，因此，就需增加d4維。首先要更新多維數(shù)據(jù)集的元組，即每一個(gè)元組均要按新屬性進(jìn)行拆分；其次修改層次組合，將新增維排在其他維之前，沒有拆分前的多維數(shù)據(jù)集元組可以看做是一個(gè)的層次聚集Cube。如果需要?jiǎng)h除一個(gè)維，那么對(duì)于所有的層次聚集Cube，如果對(duì)應(yīng)的層次組合在將刪除維上的值不是ALL，那么就需要在該維上聚集到ALL，并且不需要保存這一B+樹上的聚集信息；如果已經(jīng)聚集到了ALL層次，則只需要把B+樹上的聚集信息刪掉即可。然后從B+樹森林中刪去將刪除維對(duì)應(yīng)的B+樹。在維的增刪過程中，不會(huì)影響聚集查詢等操作。

2.1.2 維層次的增刪

在實(shí)際應(yīng)用中，可能會(huì)發(fā)現(xiàn)度量值與維中的某一層次有很大關(guān)系，但是在原始DHSC中并未包含這個(gè)層次，這時(shí)就需要增加一個(gè)層次，即在B+樹中新增一層，在DHSC中增加一個(gè)層次聚集Cube即可。如果新增加的層次是最低層次，需將多維數(shù)據(jù)集元組進(jìn)行拆分。如果層次是插在以前的層次當(dāng)中，則是一個(gè)數(shù)據(jù)向上聚集的過程，同時(shí)在相應(yīng)維的層次B+樹中插入新層次對(duì)應(yīng)的B+樹，并且需要修改層次聚集Cube中相對(duì)應(yīng)的層次組合值。刪除某個(gè)維層次時(shí)，需重新調(diào)整該維的B+樹結(jié)構(gòu)，即對(duì)要?jiǎng)h除層次的下一層次數(shù)據(jù)按上一層次進(jìn)行聚集。而層次聚集Cube對(duì)應(yīng)的層次組合中如果包括了將要?jiǎng)h除的層次，則可以采用向上聚集的策略來生成新的聚集Cube。維層次的增刪不會(huì)影響到聚集查詢。

算法1給出了在DHSC中插入新維的形式描述。

2.2 數(shù)據(jù)更新

在DHSC中，當(dāng)數(shù)據(jù)單元發(fā)生數(shù)據(jù)更新時(shí)，根據(jù)B+樹從根結(jié)點(diǎn)開始自上而下將各節(jié)點(diǎn)的范圍與更新數(shù)據(jù)單元所在的范圍依次進(jìn)行比較，找到覆蓋更新數(shù)據(jù)單元所在范圍的葉節(jié)點(diǎn)chunk，從該葉節(jié)點(diǎn)所指向的數(shù)據(jù)chunk用address選取相應(yīng)的更新單元進(jìn)行更新，然后再從更新的數(shù)據(jù)單元沿parentPtr指針向上對(duì)其所有受到更新影響的祖先節(jié)點(diǎn)的相應(yīng)數(shù)據(jù)單元進(jìn)行增量更新。增量更新算法如下所示。

3 算法性能分析

為便于進(jìn)行算法分析，首先假設(shè)維數(shù)為d，每個(gè)維的層次為h，在每個(gè)維上共有n個(gè)不同單元。在增量更新算法中，傳統(tǒng)聚集Cube如SDDC（SDDC是目前對(duì)PS改進(jìn)較好的存儲(chǔ)結(jié)構(gòu)），它的更新時(shí)間為O(log2dn)，而DHSC在增量更新時(shí)，只需對(duì)沿著更新單元所在Cuboid的parentPtr的指針自下而上，對(duì)所有層次粒度較粗且受到更新影響的高層次的聚集Cube中的數(shù)據(jù)單元進(jìn)行增量更新，則在聚集Cube中的每一層節(jié)點(diǎn)中只會(huì)有一個(gè)數(shù)據(jù)單元更新，增量更新算法的時(shí)間復(fù)雜度為O(logdh(huán)n)，可見其增量更新效率要比以往Cube均有大大地改善。

SDDC是目前性能較好的存儲(chǔ)結(jié)構(gòu)，下面給出實(shí)驗(yàn)檢驗(yàn)算法來比較DHSC與SDDC的優(yōu)劣。

第1組實(shí)驗(yàn)測(cè)試是不同維個(gè)數(shù)和數(shù)據(jù)量對(duì)Cube更新性能的影響。維數(shù)分別為3、4、5，并且假設(shè)維上的層次數(shù)為3。測(cè)試數(shù)據(jù)的大小分別為Ⅰ：64×64×64；Ⅱ：128×128×128；Ⅲ：512×512×512；Ⅳ：64×64×64×64；Ⅴ：128×128×128×128；Ⅵ：512×512×512×512；Ⅶ：64×64×64×64×64；Ⅷ：128×128×128×128×128；Ⅸ：256×256×256×256×256，實(shí)驗(yàn)結(jié)果如圖1－3所示。

由圖1－圖4可以得出，在維數(shù)固定時(shí)，隨著數(shù)據(jù)量的增長(zhǎng)，DHSC與SDDC變化趨勢(shì)基本一致，但DHSC比SDDC訪問的單元格個(gè)數(shù)要少，這種差別隨著維數(shù)的增加越來越明顯。由圖4可以得出，在層次數(shù)h=2時(shí)性能相差不大，但層次數(shù)h≥3時(shí)DHSC的性能優(yōu)于SDDC，隨著維數(shù)及數(shù)據(jù)量的增加，這種性能優(yōu)化就愈加明顯。綜上可知，DHSC與傳統(tǒng)的SDDC相比，綜合性能有所提高，尤其是在維度較高，維層次較多，維的基數(shù)也較大時(shí)，DHSC的綜合性能明顯優(yōu)于SDDC。

4 結(jié)束語

本文提出了基于維層次的語義Cube，它充分利用維層次屬性對(duì)數(shù)據(jù)單元進(jìn)行簇集存放。筆者將繼續(xù)對(duì)DHSC及其OLAP查詢進(jìn)行優(yōu)化，使它能夠更加有效地支持?jǐn)?shù)據(jù)倉庫上的查詢與更新。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。