臺灣博碩士論文加值系統

資料倉儲通常儲存大量歷史性的資料，而使用者們所下的聚合查詢是為了分析這些在資料倉儲裡大量的資料，這些操作通常需要耗費大量的時間跟系統資源，而且所耗費的時間通常是一般線上處理資料庫系統的好幾倍，如何縮短這些聚合查詢的回應時間就變的相當重要。在資料倉儲的環境下很適合使用實體化視域來縮短這些聚合查詢的時間，我們提出一個可以根據這些聚合查詢間所互相衍生的情形建構有向無迴圈圖的方法，並修改深度優先搜尋演算法去走訪這個有向無迴圈圖，然後在系統所限制的空間限制下我們將找出一個可以有良好改善效能的執行序列，可以讓每一個查詢得到最合適的實體化視域，縮短這些聚合查詢所需要的回應時間。

Data Warehouse usually stores a large amount of historical data. User’s aggregate queries usually have to consume a large amount of time and system resources in order to analyze a large amount of data in data warehouse. The response time of these aggregate queries is typically several orders of magnitude higher than the response time of OLTP (Online Transaction Processing) queries. Because that, how to reduce their response time is becoming increasingly important. The concept of materialized view is well suited to the data warehouse environment. We offer a method to construct DAG (Directed Acyclic Graph) base on the derived situation between these aggregate queries. And then, we modify the depth-first search algorithm to travel this DAG. Finally, we will find out a queries execution order has well improve performance under the space constraint restricted by the data warehouse system.

中文摘要……………………………………………… i
英文摘要……………………………………………… ii
目錄………………………………………………… iii
圖目錄………………………………………………… v
表目錄 ………………………………………………… vi
一、序論 ……………………………………… 1
1-1 研究動機 …………………………………………………………………1
1-2研究目的………………………………………………………3
1-3論文架構………………………………………………………4
二、 研究背景與相關究……………………………………5
2-1 研究背景…………………………………………………………………5
2-1-1 資料倉儲………………………………………………………………5
2-1-2 資料方體跟格構………………………………………………………5
2-1-3 線上分析處理統………………………………………………………6
2-1-4 查詢改寫……………………………………………………………9
2-2 相關研究…………………………………………………………………10
三、描述問題與架構概觀…………………… 11
3-1 成本模式……………………………………………………………11
3-2 定義問題…………………………………………………………………12
3-2-1 初步準備………………………………………………………………12
3-2-2定義問題………………………………………………………14
3-3架構概觀…………………………………………………………15
四、 方法 …………………………………………… 17
4-1 工作量分析………………………………………………………………17
4-2 建構有向無迴圈圖………………………………………………………19
4-2-1 CASE 1…………………………………………………………………20
4-2-2 CASE 2…………………………………………………………………22
4-2-3 CASE 3…………………………………………………………………23
4-3 深度優先走訪…………………………………………………25
4-3-1 走訪CASE 1……………………………………………………………25
4-3-2 走訪CASE 2……………………………………………………………26
4-3-3 走訪CASE 3……………………………………………………………27
4-4 深度優先走訪演算法…………………………………………………30
五、 實驗數據……………………………………… 32
5-1 和傳統貪婪演算法的比較……………………………………………… 32
5-2 改變空間限制的比較……………………………………………………38
六、結論和未來研究方向………………………………… 40
參考文獻…………………………………………………… 41

[1] S. Agrawal, S. Chaudhuri, L. Kollar, A. Marathe, V. Narasayya, and M. Syamala “Database Tuning Advisor for Microsoft SQL Server 2005.” In Proceedings of VLDB (2004). 1110-1121.
[2] D. Zilio, J. Rao, S. Lightstone, G. Lohman, A. Storm, C. Garcia-Arellano, and S. Fadden “DB2 Design Advisor. Integrated Automatic Physical Database Design.” In Proceedings of VLDB (2004). 1087-1097.
[3] B. Dageville, D. Das, K. Dias, K. Yagoub, M. Zait, and M. Ziauddin “Automatic SQL Tuning in Oracle 10g.” In Proceedings of VLDB (2004).1098-1109.
[4] S. Agrawal, E. Chu, V. Narasayya “Automatic Design Tuning: Workload as a Sequence.” In Proceedings of ACM SIGMOD(2006).
[5] V. Harinarayan , A. Rajaraman and J. Ullman “Implementing data cubes efficiently[A].” In: Jagadish H V, Mumick I S, eds. Proc. of the 1996 ACM SIGMOD Int. Conf. on Management of Data[C]. Montreal, Canada, June 4-6, 1996. New York: ACM Press, 1996: 205-216.
[6] S. Agrawal, S. Chaudhuri and V.R. Narasayya. “Automated selection of materialized views and indexes in SQL databases.” In Proceedings of VLDB, pages 496–505, 2000.
[7] C.D.de Aguiar Ciferri and F.F.de Souza, “Materialized Views in Data Warehousing Environments,” in Proceedings of XXI International Conference of The Chilean Computer Science Society (SCCC), pp. 3-12, 2001.
[8] H. Gupta, V. Harinarayan, A. Rajaraman, and J.D. Ullman. “Index selection for OLAP.” In Proceedings of ICDE, pages 208–219, 1997.
[9] W.H. Inmon and C. Kelley, Rdb/VMS: Developing the Data Warehouse, QED Publishing Group, Boston, Massachussetts, 1993.
[10] J. Han and M. Kamber, Data Mining: Concepts and Techniques, MORGAN KAUFMANN PUBLISHERS, 2006.
[11] J. Gray, A. Bosworth, A. Layman, and H. Pirahesh, “Data cube: a relational aggregation operator generalizing group-by, cross-tabs and subtotals,” in Proceedings of International Conference on Data Engineering, pp. 152 -159, 1996
[12] S. Chaudhuri and U. Dayal, “An overview of data warehouse and OLAP technology,” ACM SIGMOD Record, Vol. 26, pp. 65-74, 1997.
[13] D. Srivastava, S. Dar, H.V. Jagadish, and A.Y. Levy. Answering queries with aggregation using views. In Proceedings of VLDB, pages 318–329, 1996.
[14] S. Cohen, W. Nutt, and A. Serebrenik. “Rewriting aggregate queries using views.” In Proceedings of PODS, pages 155–166, 1999.
[15] F. Afrati and R. Chirkova. “Selecting and using views to compute aggregate queries.” In Proc. of ICDT, 2005.
[16] TPC Benchmark H. Decision Support. http://www.tpc.org.
[17] http://www-306.ibm.com/software/data/informix/redbrick/