啟發式資料方體挑選方法之分析比較

A Comparative Analysis of Data Cube Selection Heuristics

10.6382/JIM.200504.0201

林文揚(Wen-Yang Lin)；張耀升(Yao-Sheng Chang)

資料方體 ； 資料倉儲 ； 啟發式方法 ； 線上分析處理 ； data cubes ； data warehousing ； heuristic method ； OLAP

資訊管理學報

12卷2期（2005 / 04 / 01）

201 - 220

繁體中文

資料倉儲是針對決策支援系統的需求所發展出的新一代資料庫的觀念，其資料通常經由線上分析處理，提供管理者決策時的參考。為縮短查詢的時間，並提供使用者各個不同的觀察角度，這些資料通常在某一主題的關聯下，以多維度的資料型式儲存，稱為資料方體。資料方體選取的問題即是，給定一主題及相關的維度所組成的資料方體，考慮使用者欲進行的查詢問題，探討在有限的儲存空間限制下，如何選取適當的子方體（視域）加以實體化，以縮短查詢的時間，這個問題已知是屬於非多項式時間完成問題。因此，目前已知的資料方體實體化的選取方法大多屬於啟發式的方法。本論文旨在比較這些啟發式的挑選方法，分析其效率及求解的品質，以了解這些方法的優劣及適用性。

Data warehousing is a new database concept dedicated to supporting executive managers in decision-making through online analytical processing (OLAP). To decrease the query time and provide various viewpoints, these data usually are organized as a multiple dimensional data model, called data cubes. The data cube selection problem is, given the set of user queries and a storage space constraint, to select a set of materialized sub cubes from the data cubes to minimize the query cost, such as response time and/or the maintenance cost. This problem is known to be a NP-complete problem. Most of the existing algorithms are based on the greedy paradigm. In this paper, we compare and analyze the performance and quality of these greedy selection methods to rank their superiority and suitability.

1. Baralis, E.,Paraboschi, S.,Teniente, E.(1997).Materialized view selection in a multidimensional database.Proceedings of the 23rd VLDB Conference.
2. Chaudhuri, S.,Krishnamurthy, R.,Potamianos, S.,Shim, K.(1995).Optimizing queries with materialized views.Proceedings of International Conference on Data Engineering.
3. Ezeife, C. I.(1997).A uniform approach for selecting views and indexes in a data warehouse.Proceedings of International Database Engineering and Applications Symposium,151-160.
4. Gupta, H.(1997).Selection of views to materialize in a data warehouse.Proceedings of International Conference on Database Theory.
5. Gupta, H.,Harinarayan, V.,Rajaraman, A.,Ullman, J. D.(1997).Index Selection for OLAP.Proceedings of International Conference on Data Engineering.
6. Gupta, H.,Mumick, I. S.(1999).Selection of views to materialize under a maintenance cost constraint.Proceedings of International Conference on Database Theory.
7. Harinarayan, V.,Rajaraman, A.,Ullman, J. D.(1996).Implementing data cubes efficiently.Proceedings of ACM SIGMOD International Conference on Management of Data.
8. Horowitz, E.,Sahni, S.(1978).Fundamentals of Computer Algorithms.
9. Inmon, W. H.,Kelley, C.(1993).Rdb/VMS: Developing the Data Warehouse.
10. Jarke, M.(1984).Common subexpression isolation in multiple query optimization.Query Processing in Database Systems.
11. Karloff, H.,Mihail, M.(1999).On the complexity of the view-selection problem.Proceedings of the 8th ACM Symposium on Principles of Database Systems.
12. Larson, P.-A.,Yang, H.(1985).Computing queries from derived relations.Proceedings of the 1st VLDB Conference.
13. Levy, A.,Mendelson, A. O.,Sagiv, Y.,Srivastava, D.(1995).Answering queries using views.Proceedings of the 4th ACM Symposium on Principles of Database Systems.
14. Lin, W. Y.,Kuo, I. C.(2004).A genetic selection algorithm for OLAP data cube.Knowledge and Information Systems,6(1),83-102.
15. Quass, D.,Gupta, A.,Mumick, I. S.,Widom, J.(1996).Making views self-maintainable for data warehousing.Proceedings of Conference on Parallel and Distributed Information Systems.
16. Raab, F.(1995).TPC Benchmark(superscript TM) D (Decision Support).
17. Ross, K. A.,Srivastava, D.,Sudarshan, S.(1996).Materialized view maintenance and integrity constraint checking: trading space for time.Proceedings of ACM SIGMOD International Conference on Management of Data.
18. S. Chaudhuri,Dayal, U.(1997).An overview of data warehouse and OLAP technology.ACM SIGMOD Record,26,65-74.
19. Shukla, A.,Deshande, P. M.,Naughtion, J. F.(1998).Materialized view selection for multidimensional datasets.Proceedings of the 24th VLDB Conference.
20. Smith, J. R.(1998).Dynamic assembly of views in data cubes.Proceedings of the 7th ACM Symposium on Principles of Database Systems.
21. Theodoratos, D.,Sellis, T.(1997).Data warehouse configuration.Proceedings of the 23rd VLDB Conference.
22. Yang, J.,Karlapalem, K.,Li, Q.(1997).Algorithm for materialized view design in data warehousing environment.Proceedings of the 23rd VLDB Conference.
23. Yu, J. X.,Yao, X.,Choi C. H.,Gou, G.(2003).Materialized view selection as constrained evolutionary optimization.IEEE Transactions on Systems, Man and Cybernetics, Part C,33(4),458-467.
24. Zhang, C.,Yao, X.,Yang, J.(2001).An evolutionary approach to materialized views selection in a data warehouse environment.IEEE Transactions on Systems, Man and Cybernetics, Part C,31(3),282-294.
25. 林文揚、郭義中(2000)。應用於線上分析之資料方體的雙向貪婪桃選法。第五屆資訊管理實務研討會，高雄，臺灣:
26. 陳耀輝、劉宇昌、劉佳灝(1997)。在資料倉儲中選擇實體化視域之研究。八十六年全國計算機會議論文集

1. 張耀升、林文揚(2008)。線上關聯規則採掘之資料方體挑選。電子商務學報，10(4)，849-883。