1、1在資料倉儲中提供一可動態調整的在資料倉儲中提供一可動態調整的總集範圍查詢資料方體架構之總集範圍查詢資料方體架構之設計與分析設計與分析 研究生：李育強研究生：李育強指導教授：李建億指導教授：李建億 博士博士國立台南師範學院資訊教育研究所碩士論文2大綱大綱n緒論n文獻探討n資料方體的適合建構時機分析n可動態轉換資料方體的機制n效能分析結果n結論與未來研究方向3一、緒論一、緒論n資料方體（Data Cube）被用在OLAP上對大型資料庫或資料倉儲（Data Warehouse）做互動式的分析，同時也被視為多維度資料庫（Multi-dimensional Database）n在一資料方體中，將我們所
2、感興趣的屬性設定為評估（measure）屬性，其餘屬性稱為之維度（dimension）或功能（functional）屬性n範圍總和查詢（Range Sum Query）是資料方體中很有用的工具之一，其目的是得知所查詢範圍內所有方格值的總和 研究背景研究背景4n評估屬性 銷售量n維度屬性 銷售年度及客戶年齡汽車公司的銷售為例：汽車公司的銷售為例：5n理想上，資料方體應支援快速查詢和快速更新且不需要用到額外的儲存空間 研究背景研究背景(續續)6研究動機研究動機n前置總集範圍查詢資料方體：nPS(Ho,Agrawal,Megiddo&Srikant,1997)nRPS(Geffer,Agrawal,
3、Abbadi&Smith,1999)nHC(Chan&Ioannidis,1999)nDDC(Geffer,Agrawal&Abbadi,1999)nSEDC(Riedewald,Agrawal,Abbadi&Pajarola,2000)n為加速資料方體的範圍查詢，事先計算和儲存範圍總和。雖有較快速的回應時間，但卻導至更高的更新成本或額外空間需求 nIDC(Riedewald,Agrawal&Abbadi,2000)n結合不需額外儲存空間的方法n使d 維問題，成為d 個一維問題7研究動機研究動機(續續)n在何種查詢/更新機率比的情形下，該使用何種資料方體？n當查詢/更新機率比隨時間變動的情形下
4、，除了重建資料方體外，並無法適時轉換資料方體以適應不同的情況，來提供最好的查詢/更新效能8研究動機研究動機(續續)n除了保有IDC法不需要額外儲存空間的優點外，本論文主要的研究動機有n提出一套機制來決定在何種查詢/更新機率比的情況下，應使用何種資料方體 n提出在同一維度內，綜合已知的方法，以獲得比現有方法更佳的資料方體 n提出一套可動態調整的資料方體建置機制，依據不同的查詢/更新機率比，動態地調整建構資料方體，來增進總集資料方體的效能，而不需重建整個資料方體 9二、文獻探討二、文獻探討n前置總集資料方體的演進nPrefix Sum(PS)方法nRelative Prefix Sum(RPS)方
5、法nHierarchical Cubes(HC)方法nDynamic Data Cube(DDC)方法nSpace-Efficient Data Cubes(SEDC)方法nIterative Data Cube(IDC)方法n綜合討論10前置總集資料方體的演進前置總集資料方體的演進11Prefix Sum(PS)Prefix Sum(PS)方法方法(Ho,Agrawal,Megiddo&Srikant,1997)12Prefix Sum(PS)Prefix Sum(PS)方法方法(續續)13Relative Prefix Sum(RPS)Relative Prefix Sum(RPS)方法方
6、法(Geffer,Agrawal,Abbadi&Smith,1999)14Relative Prefix Sum(RPS)Relative Prefix Sum(RPS)方法方法(續續)15Relative Prefix Sum(RPS)Relative Prefix Sum(RPS)方法方法(續續)1617Hierarchical Cubes(HC)Hierarchical Cubes(HC)方法方法(Chan&Ioannidis,1999)1819Dynamic Data Cube(DDC)Dynamic Data Cube(DDC)方法方法(Geffer,Agrawal&Abbadi,1
7、999)20Dynamic Data Cube(DDC)Dynamic Data Cube(DDC)方法方法(續續)21Space-Efficient Data Cubes(SEDC)Space-Efficient Data Cubes(SEDC)(Riedewald,Agrawal,Abbadi&Pajarola,2000)22Space-Efficient Data Cubes(SEDC)Space-Efficient Data Cubes(SEDC)(續續)23Iterative Data Cube(IDC)Iterative Data Cube(IDC)方法方法(Riedewald,A
8、grawal&Abbadi,2000)24綜合討論綜合討論nPS法有最快的查詢速度及最慢的更新速度n原始陣列則有最慢的查詢速度及最快的更新速度n其他方法的查詢及更新速度則在此二極端中25三、資料方體建構時機分析三、資料方體建構時機分析nHierarchical Local Prefix Sum(HLPS)方法n平均成本分析n資料方體建構成本分析nFlexible Data Cube(FDC)方法26加入加入HLPSHLPS法法27Hierarchical Local Prefix Sum(HLPS)Hierarchical Local Prefix Sum(HLPS)28Hierarchica
9、l Local Prefix Sum(HLPS)Hierarchical Local Prefix Sum(HLPS)(續續)29平均成本分析平均成本分析n為得知在不同的環境下該使用何種方法來建構資料方體，必須得知各個方法的平均查詢及更新成本 n存取資料方體的方格數與磁碟的分頁(pages)數成正比，相較於CPU的運算時間，磁碟的輸出入(I/O)時間佔了很大的瓶頸，因此成本分析皆以所需存取方格數做為單位n簡化分析起見，假設讀取與寫入一個方格有相同的成本n由IDC法得知，只要獲得一維的平均查詢及更新成本，將其連乘而得到d維的成本 30平均成本分析平均成本分析(續續)31平均成本分析平均成本分析(
10、續續)32LPS法法(k=2)平均成本分析平均成本分析n運用divide-and-conquer法來分析，將LPS方體由中間一分為二33平均成本分析平均成本分析(續續)34資料方體建構成本分析資料方體建構成本分析35Flexible Data Cube(FDC)方法方法n在所有可能的前置總集資料方體中，為因應不同的查詢/更新機率比而找出最佳資料方體是NP-Complete的問題，以一維來說就有n!種可能的資料方體，而d維則有(nd)!種可能的資料方體nFDC法在同一維度內結合原始陣列A、LPS、HLPS與PS等四法，運用heuristic法則，只需要線型時間O(n)，即可找出所要建構的最佳FD
11、C方體。36一維一維FDCFDC法的建構法的建構37Flexible Data Cube(FDC)方法方法(續續)n當k=0時，原始陣列A、LPS、HLPS及PS法，皆為FDC法的特例之一 n找出最佳FDC方體的時間複雜度 44n=16 n n二維以上的FDC方體建構同IDC法的建構方式 n平均查詢成本CaqFDC(n)=n平均更新成本=左右兩邊方體更新總成本/總更新數n建構成本=左右兩邊方體建構總成本38四、可動態轉換的資料方體機制四、可動態轉換的資料方體機制n資料方體架構的轉換成本nFDC資料方體架構的轉換成本n動態變換資料方體39資料方體架構的轉換成本資料方體架構的轉換成本40資料方體架
12、構的轉換成本資料方體架構的轉換成本(續續)n任一種資料方體的互換是可逆的 41FDC資料方體架構的轉換成本資料方體架構的轉換成本42FDC資料方體架構的轉換成本資料方體架構的轉換成本(續續)43動態變換資料方體動態變換資料方體n轉換前單一查詢/更新平均成本Ca1=qCaq+uCau n轉換後單一查詢/更新平均成本Ca2=qCaq+uCaun找出maxCa1-Ca2n轉換成本：Ct nN maxCa1-Ca2 Ct 表示轉換後所降低的總成本大於轉換成本，則轉換資料方體 44五、效能分析結果五、效能分析結果不同查詢不同查詢/更新機率更新機率45不同查詢不同查詢/更新機率更新機率(續續)46不同查詢
13、不同查詢/更新機率更新機率(續續)47不同維度邊長不同維度邊長48不同維度邊長不同維度邊長(續續)49不同維度邊長不同維度邊長(續續)50不同維度邊長不同維度邊長(續續)51六、結論與未來研究方向六、結論與未來研究方向n以資料方體的平均查詢及更新成本來決定在不同的查詢/更新機率比之下應使用何種資料方體n提出FDC法在同一維度內綜合已知的方法，建構出更佳資料方體的機制，並發現足以取代PS法的PS法n依據不同的查詢/更新機率比，動態地調整建構資料方體，來增進總集範圍資料方體的效能，而不需重建整個資料方體結論結論52未來研究方向未來研究方向n稀疏資料的支援n最佳總集範圍查詢資料方體n非均勻查詢及更新時的最佳資料方體 53謝謝蒞臨指導謝謝蒞臨指導
