资料仓储系统中实体化视域选取之研究

逢甲大學資訊工程學系碩士班碩士論文資料倉儲系統中實體化視域選取之研究AStudyonSelectingMaterializedViewsofDataWarehouses指導教授：楊東麟研究生：黃曼玲中華民國九十年六月摘要資料倉儲（datawarehouse）是一種將資料聚集成資訊來源的場所，可以透過展示介面或線上 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 處理（OnlineAnalyticalProcessing,OLAP）的工具，提供給管理者作決策參考時使用。這些資料往往以多維度的（multi-dimensional）資料方格(datacubes)模式來組織和呈現，藉以提供多樣化的檢視觀點。在資料方格中，每個儲存格表示使用者所關心的聚集值。在關聯式資料庫（relationaldatabases）中，資料方格可視為某些視域（views）的集合。為了有效提昇倉儲系統的彙總查詢效能，將資料方格內相關的視域予以實體化（materialize）是常用的一種方式。然而一旦要把視域實體化，其建置與維護的成本就必須要加以考量。以往，選取實體化視域的方法大多採用貪心演算法（greedyalgorithm）。然而，此法並未考慮儲存空間的限制，也未刪除毋需存在的查詢視域，再加上考慮視域實體化個數限制，以致使用此法選擇的視域實體化後，查詢效能並不盡理想。雖然有人以兩階段演算法改進貪心演算法，但在倉儲空間遠大於可使用的最小空間時，選取效能上仍有待改進。我們調查了目前有關選取實體化視域的研究，針對彙總資料的選取設計及查詢轉換做探討。在資料倉儲的環境與儲存空間的限制下，如何有效地選擇資料方格內的視域予以實體化，以達到彙總查詢的最佳化是本研究的重點，這是屬於NP-complete的問題，至於應用Metadata來改善效能則不在本篇文章的討論範圍之內。因此，我們設計「候選視域中心點考量選取策略演算法」（MPLA-CV），在儲-I-存空間的限制下，解決視域選取的問題。有別於先前演算法的觀點，我們從候選視域中心點角度去評估實體化視域選取策略，除了比先前演算法有較好的整體成本（查詢與維護成本）表現外，在大部分情況下，MPLA-CV在建置成本方面，也有較佳的選取效能。視域如果被實體化，除了必須考慮整體成本與建置成本外，對於查詢轉換(queryrewrite)也必須加以考量。因此，我們提出向量資料結構，加快找尋查詢視域在倉儲系統中相依實體化視域。MPLA-CV演算法除了能夠在儲存空間的限制下，有效地選取實體化視域，以達到整體成本最佳化的目的外，亦可彌補原有兩階段演算法之不足。實驗結果顯示，在建置成本方面，如果不考慮維護成本，此方法有57.1%的平均改善率；當考慮維護成本時，則有47.4%的平均改善率。關鍵字：資料倉儲、線上分析處理、資料方格、查詢轉換、實體化視域-II-AbstractDatawarehouse(DW)isaninformationsourceofdataaggregation.IthelpsmanagersmakedecisionsbymeansofpresentationtoolslikeOn-LineAnalyticalProcessing(OLAP).Datacube(DC)presentedinmulti-dimensionalmodeloffersavarietyofdifferentviews.Thereareaggregatesofuser’sconcernimpliedineachcellofDCs.Inrelationaldatabases,DCisdeemedasetofviews.Toincreasequeryeffectivenessofaggregationinadatawarehouse,designerscanmaterializeviewsinDC.Nevertheless,therecomesanotherquestionaboutthecostsofimplementationandmaintenanceasviewsarematerialized.“Greedyalgorithm”wasapopularwayinselectingmaterializedviews.However,thegreedyalgorithmisnoteffectiveforitsneglectofstorageconstraint,itsretentionofredundantviews,anditslimitationonthenumberofmaterializedviews.Eventhough“two-phasealgorithm”wasproposedformodifyingthegreedyalgorithm,queryeffectivenessremaineddeficientinselectingmaterializedviewswhenwarehousestoragefarexceedsminimumavailablespace.Wesurveyedliteraturesonmaterializedviews,andreviewedseveraldesignsofselectionandqueryrewritesofdataaggregation.Themainpurposeofthisresearchistoselectthematerializedviewunderastorageconstraint,inordertoreachoptimizationofaggregatequeryandcontainmentofcosts.ThisisanNP-completeproblem.Regardingtheapplicationofmetadata,itisbeyondthescopeofourresearch.Inthispaper,weproposeaMid-PointLocatingAlgorithmwithCandidateView(MPLA-CV)forsolvingtheaboveproblemsofviewmaterializationunderastorageconstraint.MPLA-CVdeterminesmaterializedviewsfromthemid-pointsofcandidate-III-views.Ithaslowerqueryandmaintenancecoststhanpreviouslymentionedalgorithms.Inmostcases,MPLA-CVperformswellinselectioneffectivenesswithreducedbuild-upcost.Inadditiontoquery,maintenance,andbuild-upcosts,queryrewritemustbeconsideredaswellwhileviewsarematerialized.WeherebyproposeavectordatastructuretospeedupthesearchofqueryviewsrelatingtothematerializedviewsintheDW.Inthisresearch,MPLA-CVnotonlyselectsoptimalmaterializedviewswithminimumcostunderlimitedspace,butalsocompensatesfortheweaknessoftwo-phasealgorithm.TheresultsofourexperimentonMPLA-CVrevealthatbuild-upcostreductionhasanaverageimprovementrateof57.1%withoutconsideringthemaintenancecostand47.4%withthemaintenancecost.Keywords:datawarehouse,OLAP,datacube,queryrewrite,materializedview-IV-