遺傳演算法於資料倉儲中構建資料方體之應用

Abstract

資料倉儲是針對決策支援系統的需求所發展出的新一代資料庫的觀念，黃資料通常經由線上分析處理，提供管理者決策時的參考。為縮短查詢的時間，並提供使用者各個不同的觀察角度，這些資料通常在某一主題的關聯下，以多維度的資料型式儲存，稱為資料方體。資料方體中的每一方格代表使用者所關心的，某一經合計後的視域。資料方體構建的問題即是，給定一主題及相關的維度所組成的資料方體，考慮使用者欲進行的查詢問題，探討在有限的儲存空間限制下，如何選取適點的子方體(視域)加以實體化，以縮短查詢的時間。這個問題已知是屬於NP完全問題。 本論文針對此問題，嘗試以遺傳演算法建立一子方體實體化選擇的模式，以建立資料倉儲中的資料方體。我們提出一貪婪式的遺傳演算法，稱為遺傳貪婪法。根據實驗的結果，由貴傳貪婪演算法所找到的解遠優於過去廣為採用的貪婪方法；在相同的儲存空間限制下，能大幅地減少處理查詢所需的成本。