基于維層次的語義Ｃｕｂｅ存儲與增量更新技術研究
2007-01-01 00:00:00顧頎胡孔法陳崚唐曉麗劉海東
計算機應用研究 2007年6期
摘 要：利用維的層次性為每一個維建立一個索引，同時保存相應的層次信息和預聚集數據，提出了基于維層次的語義Cube。在進行數據更新時，使用更新前后的差值自下而上對受到更新單元影響的祖先節(jié)點進行增量更新，在進行模式更新時，無需重構Cube，即可實現(xiàn)增量更新。由于其存儲結構的靈活性，在高效完成增量更新的同時實現(xiàn)了Cube上進行上探、下鉆等語義操作。理論分析和實驗結果均表明，提出的基于維層次的語義Cube與傳統(tǒng)Cube相比，性能顯著提高。
關鍵詞：數據倉庫; 語義Cube; 增量更新
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2007)06-0213-03
隨著數據倉庫逐漸成為企業(yè)決策支持的重要技術手段，如何有效地實現(xiàn)數據倉庫及其優(yōu)化問題日益成為人們重視和關注的焦點之一。數據倉庫及其分析工具——OLAP分析往往是基于多維數據模型，它由維和事實度量組成。在該模型中數據通常以數據立方體（Data Cube）形式進行存儲［1］，通過數據聚集技術和高性能的多維存儲結構組織和匯總了大量的聚集數據，為OLAP提供快速的多維信息分析。近年來，許多專家學者先后在Cube聚集計算［2，3］、Cube壓縮存儲［4－6］、Cube并行計算［7，8］等方面取得了一些成果，在一定程度上提高了Cube的數據查詢性能。但這些Cube在數據更新時，重構開銷較大，且不能實現(xiàn)Cube增量更新；而且沒有保存維的層次及層次關系等語義信息，不能支持Cube在語義上的查詢操作；未充分利用維層次屬性對數據單元進行簇集存放，在查詢和更新時，增加了I/O開銷，降低了Cube的查詢和更新效率。為此，本文提出了基于維層次的語義Cube，它的基本思想是：利用B+樹為Cube中的每一個維建立索引，同時保存相應的層次信息和預聚集數據，實現(xiàn)了在Cube上進行上探、下鉆等語義操作。由于數據倉庫系統(tǒng)是一種面向用戶的分析型應用系統(tǒng)，必須根據用戶的需求不斷進行完善和補充，數據倉庫的數據和模式要隨著分析任務的需要不斷更新。如何在基于維層次的語義Cube中高效實現(xiàn)增量更新是本文要討論的一個主要方面。
1 基于維層次的語義Cube
1.1 存儲結構
例如表1是某賣場銷售情況的Cube二維表表示，它由地區(qū)維、產品維、時間維三個維和一個銷售量的度量值構成。其中，地區(qū)、產品、時間均是由相應維中的層次所組成的一個有序集。
表1 一個商品銷售情況的Cube二維表表示
定義3（基于維層次的語義Cube，DHSC） 對于維層次組合
1.2 基于維層次的語義Cube的創(chuàng)建
基于維層次的語義Cube是通過數據倉庫的建模工具為其各個維創(chuàng)建層次樹，從維層次粒度最細的Cube開始，按各個B+樹中的維層次屬性，對Cube中粒度較細的各個數據單元（Cell）進行劃分成若干個互不相交的分割子Cube，并對每一個分割子Cube的聚集值按維層次前綴進行分組聚集計算，將計算得到的聚集值存儲到父Cube中，再對生成的父Cube按維層次粒度由細到粗進行遞歸地分割和分組聚集計算，直至維層次粒度最粗時為止。其中每個節(jié)點包括兩個指針(childPtr為指向下一層子Cube的指針，parentPtr為指向上一層父Cube的指針)，一個標志（flag，當flag＝0時為葉子節(jié)點，flag＝1時為目錄節(jié)點），兩個存儲區(qū)域（MBBc表示該節(jié)點所包含的范圍，采用維層次編碼方式來表示，按維層次編碼組合的混合編碼的Hash函數來計算其存儲地址，作為Cube中數據單元的存取依據。chunk用于存儲具有相同維層次的多個數據單元cell
1.3 Cube語義操作
上探操作是指在某一維上將低層次的細節(jié)數據概括到高層次的匯總數據，或減少維數，而下鉆操作是從匯總數據深入到細節(jié)數據進行觀察或增加新維。
在基于維層次的語義Cube中，假設數據已經存放在內存或緩存中，利用B+樹中保存的層次信息，上探時，就相當于數據沿著B+樹往上聚集，即沿著parentPtr指針向上對所對應的邏輯塊進行聚集計算，下鉆時沿childPtr指針向下對所對應的邏輯塊進行訪問。
例如，在表1二維Cube所對應的DHSC中，從<產品型號，月份>層次聚集Cube到<產品名，季度>層次聚集Cube進行的聚集查詢過程就是Cube上探操作，可以沿<產品型號，月份>層次聚集Cube 相應節(jié)點的parentPtr指針向上對所對應的<產品名，季度>層次聚集Cube中的邏輯塊進行訪問。
2 DHSC增量更新技術
2.1 模式更新
2.1.1 維的增刪
在對數據倉庫中的數據進行OLAP分析時，預先假定度量值同a1、a2、a3三個屬性相關，因此建立了d1、d2、d3三個維，但在經過數據分析后，可能發(fā)現(xiàn)屬性a4對度量值有影響，因此，就需增加d4維。首先要更新多維數據集的元組，即每一個元組均要按新屬性進行拆分；其次修改層次組合，將新增維排在其他維之前，沒有拆分前的多維數據集元組可以看做是一個
2.1.2 維層次的增刪
在實際應用中，可能會發(fā)現(xiàn)度量值與維中的某一層次有很大關系，但是在原始DHSC中并未包含這個層次，這時就需要增加一個層次，即在B+樹中新增一層，在DHSC中增加一個層次聚集Cube即可。如果新增加的層次是最低層次，需將多維數據集元組進行拆分。如果層次是插在以前的層次當中，則是一個數據向上聚集的過程，同時在相應維的層次B+樹中插入新層次對應的B+樹，并且需要修改層次聚集Cube中相對應的層次組合值。刪除某個維層次時，需重新調整該維的B+樹結構，即對要刪除層次的下一層次數據按上一層次進行聚集。而層次聚集Cube對應的層次組合中如果包括了將要刪除的層次，則可以采用向上聚集的策略來生成新的聚集Cube。維層次的增刪不會影響到聚集查詢。
算法1給出了在DHSC中插入新維的形式描述。
2.2 數據更新
在DHSC中，當數據單元發(fā)生數據更新時，根據B+樹從根結點開始自上而下將各節(jié)點的范圍與更新數據單元所在的范圍依次進行比較，找到覆蓋更新數據單元所在范圍的葉節(jié)點chunk，從該葉節(jié)點所指向的數據chunk用address選取相應的更新單元進行更新，然后再從更新的數據單元沿parentPtr指針向上對其所有受到更新影響的祖先節(jié)點的相應數據單元進行增量更新。增量更新算法如下所示。
3 算法性能分析
為便于進行算法分析，首先假設維數為d，每個維的層次為h，在每個維上共有n個不同單元。在增量更新算法中，傳統(tǒng)聚集Cube如SDDC（SDDC是目前對PS改進較好的存儲結構），它的更新時間為O(log2dn)，而DHSC在增量更新時，只需對沿著更新單元所在Cuboid的parentPtr的指針自下而上，對所有層次粒度較粗且受到更新影響的高層次的聚集Cube中的數據單元進行增量更新，則在聚集Cube中的每一層節(jié)點中只會有一個數據單元更新，增量更新算法的時間復雜度為O(logdh(huán)n)，可見其增量更新效率要比以往Cube均有大大地改善。
SDDC是目前性能較好的存儲結構，下面給出實驗檢驗算法來比較DHSC與SDDC的優(yōu)劣。
第1組實驗測試是不同維個數和數據量對Cube更新性能的影響。維數分別為3、4、5，并且假設維上的層次數為3。測試數據的大小分別為Ⅰ：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，實驗結果如圖1－3所示。
由圖1－圖4可以得出，在維數固定時，隨著數據量的增長，DHSC與SDDC變化趨勢基本一致，但DHSC比SDDC訪問的單元格個數要少，這種差別隨著維數的增加越來越明顯。由圖4可以得出，在層次數h=2時性能相差不大，但層次數h≥3時DHSC的性能優(yōu)于SDDC，隨著維數及數據量的增加，這種性能優(yōu)化就愈加明顯。綜上可知，DHSC與傳統(tǒng)的SDDC相比，綜合性能有所提高，尤其是在維度較高，維層次較多，維的基數也較大時，DHSC的綜合性能明顯優(yōu)于SDDC。
4 結束語
本文提出了基于維層次的語義Cube，它充分利用維層次屬性對數據單元進行簇集存放。筆者將繼續(xù)對DHSC及其OLAP查詢進行優(yōu)化，使它能夠更加有效地支持數據倉庫上的查詢與更新。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
