在资料仓储中提供一可动态调整的总集范围查询资料方体架构之设课件

在資料倉儲中提供一可動態調整的總集範圍查詢資料方體架構之

設計與分析

研究生：李育強指導教授：李建億博士國立台南師範學院

資訊教育研究所碩士論文1在資料倉儲中提供一可動態調整的總集範圍查詢資料方體架構之

設大綱緒論文獻探討資料方體的適合建構時機分析可動態轉換資料方體的機制效能分析結果結論與未來研究方向2大綱緒論2一、緒論資料方體（DataCube）被用在OLAP上對大型資料庫或資料倉儲（DataWarehouse）做互動式的分析，同時也被視為多維度資料庫（Multi-dimensionalDatabase）在一資料方體中，將我們所感興趣的屬性設定為評估（measure）屬性，其餘屬性稱為之維度（dimension）或功能（functional）屬性範圍總和查詢（RangeSumQuery）是資料方體中很有用的工具之一，其目的是得知所查詢範圍內所有方格值的總和研究背景3一、緒論資料方體（DataCube）被用在OLAP上對大型評估屬性→銷售量維度屬性→銷售年度及客戶年齡汽車公司的銷售為例：4評估屬性→銷售量汽車公司的銷售為例：4理想上，資料方體應支援快速查詢和快速更新且不需要用到額外的儲存空間研究背景(續)5理想上，資料方體應支援快速查詢和快速更新且不需要用到額外的儲研究動機前置總集範圍查詢資料方體：PS(Ho,Agrawal,Megiddo&Srikant,1997)RPS(Geffer,Agrawal,Abbadi&Smith,1999)HC(Chan&Ioannidis,1999)DDC(Geffer,Agrawal&Abbadi,1999)SEDC(Riedewald,Agrawal,Abbadi&Pajarola,2000)為加速資料方體的範圍查詢，事先計算和儲存範圍總和。雖有較快速的回應時間，但卻導至更高的更新成本或額外空間需求

IDC(Riedewald,Agrawal&Abbadi,2000)結合不需額外儲存空間的方法使d維問題，成為d個一維問題6研究動機前置總集範圍查詢資料方體：6研究動機(續)在何種查詢/更新機率比的情形下，該使用何種資料方體？當查詢/更新機率比隨時間變動的情形下，除了重建資料方體外，並無法適時轉換資料方體以適應不同的情況，來提供最好的查詢/更新效能7研究動機(續)在何種查詢/更新機率比的情形下，該使用何種資料研究動機(續)除了保有IDC法不需要額外儲存空間的優點外，本論文主要的研究動機有提出一套機制來決定在何種查詢/更新機率比的情況下，應使用何種資料方體提出在同一維度內，綜合已知的方法，以獲得比現有方法更佳的資料方體提出一套可動態調整的資料方體建置機制，依據不同的查詢/更新機率比，動態地調整建構資料方體，來增進總集資料方體的效能，而不需重建整個資料方體8研究動機(續)除了保有IDC法不需要額外儲存空間的優點外，本二、文獻探討前置總集資料方體的演進PrefixSum(PS)方法RelativePrefixSum(RPS)方法HierarchicalCubes(HC)方法DynamicDataCube(DDC)方法Space-EfficientDataCubes(SEDC)方法IterativeDataCube(IDC)方法綜合討論9二、文獻探討前置總集資料方體的演進9前置總集資料方體的演進10前置總集資料方體的演進10PrefixSum(PS)方法

(Ho,Agrawal,Megiddo&Srikant,1997)11PrefixSum(PS)方法

(Ho,AgrawalPrefixSum(PS)方法(續)12PrefixSum(PS)方法(續)12RelativePrefixSum(RPS)方法

(Geffer,Agrawal,Abbadi&Smith,1999)13RelativePrefixSum(RPS)方法

(GRelativePrefixSum(RPS)方法(續)14RelativePrefixSum(RPS)方法(續)1RelativePrefixSum(RPS)方法(續)15RelativePrefixSum(RPS)方法(續)11616HierarchicalCubes(HC)方法

(Chan&Ioannidis,1999)17HierarchicalCubes(HC)方法

(Cha1818DynamicDataCube(DDC)方法

(Geffer,Agrawal&Abbadi,1999)19DynamicDataCube(DDC)方法

(GefDynamicDataCube(DDC)方法(續)20DynamicDataCube(DDC)方法(續)20Space-EfficientDataCubes(SEDC)

(Riedewald,Agrawal,Abbadi&Pajarola,2000)21Space-EfficientDataCubes(SEDSpace-EfficientDataCubes(SEDC)(續)22Space-EfficientDataCubes(SEDIterativeDataCube(IDC)方法

(Riedewald,Agrawal&Abbadi,2000)23IterativeDataCube(IDC)方法

(R綜合討論PS法有最快的查詢速度及最慢的更新速度原始陣列則有最慢的查詢速度及最快的更新速度其他方法的查詢及更新速度則在此二極端中24綜合討論PS法有最快的查詢速度及最慢的更新速度24三、資料方體建構時機分析HierarchicalLocalPrefixSum(HLPS)方法平均成本分析資料方體建構成本分析FlexibleDataCube(FDC)方法25三、資料方體建構時機分析HierarchicalLocal加入HLPS法26加入HLPS法26HierarchicalLocalPrefixSum(HLPS)27HierarchicalLocalPrefixSum(HierarchicalLocalPrefixSum(HLPS)(續)28HierarchicalLocalPrefixSum(平均成本分析為得知在不同的環境下該使用何種方法來建構資料方體，必須得知各個方法的平均查詢及更新成本

存取資料方體的方格數與磁碟的分頁(pages)數成正比，相較於CPU的運算時間，磁碟的輸出入(I/O)時間佔了很大的瓶頸，因此成本分析皆以所需存取方格數做為單位簡化分析起見，假設讀取與寫入一個方格有相同的成本由IDC法得知，只要獲得一維的平均查詢及更新成本，將其連乘而得到d維的成本

29平均成本分析為得知在不同的環境下該使用何種方法來建構資料方體平均成本分析(續)30平均成本分析(續)30平均成本分析(續)31平均成本分析(續)31LPS法(k=2)平均成本分析運用divide-and-conquer法來分析，將LPS方體由中間一分為二32LPS法(k=2)平均成本分析運用divide-and平均成本分析(續)33平均成本分析(續)33資料方體建構成本分析34資料方體建構成本分析34FlexibleDataCube(FDC)方法在所有可能的前置總集資料方體中，為因應不同的查詢/更新機率比而找出最佳資料方體是NP-Complete的問題，以一維來說就有n!種可能的資料方體，而d維則有(nd)!種可能的資料方體FDC法在同一維度內結合原始陣列A、LPS、HLPS與PS等四法，運用heuristic法則，只需要線型時間O(n)，即可找出所要建構的最佳FDC方體。35FlexibleDataCube(FDC)方法在所有可能一維FDC法的建構36一維FDC法的建構36FlexibleDataCube(FDC)方法(續)當k’=0時，原始陣列A、LPS、HLPS及PS法，皆為FDC法的特例之一

找出最佳FDC方體的時間複雜度

≦4×4×n=16n

二維以上的FDC方體建構同IDC法的建構方式

平均查詢成本CaqFDC(n)=平均更新成本=左右兩邊方體更新總成本/總更新數建構成本=左右兩邊方體建構總成本37FlexibleDataCube(FDC)方法(續)當k四、可動態轉換的資料方體機制資料方體架構的轉換成本FDC資料方體架構的轉換成本動態變換資料方體38四、可動態轉換的資料方體機制資料方體架構的轉換成本38資料方體架構的轉換成本39資料方體架構的轉換成本39資料方體架構的轉換成本(續)任一種資料方體的互換是可逆的

40資料方體架構的轉換成本(續)任一種資料方體的互換是可逆的4FDC資料方體架構的轉換成本各個FDC法之間的轉換成本，為個別方法的轉換成本之和

右邊方體的轉換則將表4.2的k’改成k’’即可

41FDC資料方體架構的轉換成本各個FDC法之間的轉換成本，為個FDC方體間的轉換只限制在其k’皆相同因k’不同時的轉換需重建整個資料方體FDC資料方體架構的轉換成本(續)42FDC方體間的轉換只限制在其k’皆相同FDC資料方體架構的轉動態變換資料方體轉換前單一查詢/更新平均成本Ca1=qCaq+

uCau

轉換後單一查詢/更新平均成本Ca2

=qCaq’+

uCau’找出max{Ca1-Ca2}轉換成本：Ct

N’×max{Ca1-Ca2}﹥Ct

表示轉換後所降低的總成本大於轉換成本，則轉換資料方體

43動態變換資料方體轉換前單一查詢/更新平均成本Ca1=qC五、效能分析結果不同查詢/更新機率44五、效能分析結果不同查詢/更新機率44不同查詢/更新機率(續)45不同查詢/更新機率(續)45不同查詢/更新機率(續)46不同查詢/更新機率(續)46不同維度邊長47不同維度邊長47不同維度邊長(續)48不同維度邊長(續)48不同維度邊長(續)49不同維度邊長(續)49不同維度邊長(續)50不同維度邊長(續)50六、結論與未來研究方向以資料方體的平均查詢及更新成本來決定在不同的查詢/