在查詢與更新為隨機需求與回覆時間被限制的環境下最小化資料倉儲系統之查詢與資料維護成本

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：103

、訪客IP：18.118.163.176

姓名

張凱雯(Kai-Wen Chang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

在查詢與更新為隨機需求與回覆時間被限制的環境下最小化資料倉儲系統之查詢與資料維護成本
(Minimizing Query Processing and View Maintenance Cost with Stochastic Query and Update under a Response Time Constraints in a Data Warehouse System)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

資料倉儲被建立來有效地回答查詢。所謂的選擇先行作業結果即為透過選擇一個先行作業結果的組合，並且希望在最小化成本時，這個組合可以滿足模型的限制。而更新的策略則是談到應當在哪個時點重新更新作業結果中的資料。之前的研究將選擇作業結果與最小化成本兩個議題分開討論，但在實務上，這兩個問題是互相相關的。因此我們了解到同時解決這兩個問題對於資料倉儲設計上的重要性。除此之外，之前的研究都假設查詢頻率為固定，更新時間也為固定。這種作法並不能準確的反映出實際上使用者在查詢時的不確定性，也不能表現出即時更新的特性。因此，隨機的到達是要被考慮的。在查詢到達後，回覆的時間也是要被考慮的重要議題，回覆時間必須滿足使用者需求，因此回覆時間必須被考慮在議題的研究中。
本研究提出了一個數學模型來最小化所有成本。並且在這個模型中，考慮了隨機的更新頻率，這點在之前的研究中是從來沒有被考慮過的。這個模型假設隨機的查詢到達率與更新頻率符合普瓦松分配，這個假設是很符合實際需求的。在建立回覆需求的限制模型上，我們採用一M / G / 1個模型闡述可以在指定時間內回覆查詢的機率為何。
在實驗階段，我們考慮了不同狀況去應用所提出的模型與貪婪演算法。並且在實驗後分析不同情況下參數間的影響，以及最終結果選擇的改變。最後，我們經過實驗結果到我們在這裡提出的數學模型和算法透過這些實驗是正確和可靠的。

摘要(英)

Data warehouse is built up to reply queries efficiently. The view selection is to select a set of views to materialize under constraints, when minimizing the total of query processing cost and view maintenance cost. The update policy decides when to refresh the data in a data warehouse. Previous researches dealt with these two problems independently, however under the real situation, they are correlated with each other. Therefore, simultaneously determining view selection and update policy in designing a data warehouse is important. Besides, as to previous researches, they assume that query arrival rates and update frequency are deterministic which can’t reflect uncertain demand of query in real situation, that will lead to a incorrect outcome. Therefore, the stochastic arrival should be considered.
In this research, we propose a mathematical model to minimize the total cost when the set of materialized views are known. In the model, we adopt stochastic view maintenance frequency, which does not be considered in the former researches. Our model also incorporates the stochastic phenomenon to reflect the uncertain query and uncertain update with Poisson process, which is common in the real life. The mean system response time constrained by a specified time is formulated by an M/G/1 model, which is within a given threshold with a desired probability.
As to application, we consider different special cases to implement the mathematical model and the greedy algorithm. A computational analysis is conducted to explore the impact of different constraints and system parameters on view selection. In addition, we also design some experiments to evaluate the difference of view selection and its solution. Finally, we recognize the mathematical model and algorithm we propose here are correct and reliable via these experiments.

關鍵字(中)

★ 普瓦松過程
★ 資料倉儲
★ M/G/1 模型

關鍵字(英)

★ AMPL/MINOS
★ MVPP
★ View selection
★ Poisson process
★ View maintenance
★ M/G/1

論文目次

Abstract I
摘要 II
Contents III
List of Figures V
List of Tables VIII
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem description 3
1.3 Research objectives 4
1.4 Research methodology and procedure 4
Chapter 2 Literature Review 6
2.1 Frameworks 6
2.2 View selection 10
2.3 View maintenance 11
Chapter 3 Mathematical Model 13
3.1 Definitions and assumptions 13
3.1.1 Definitions 13
3.1.2 Assumptions 14
3.2 Notations 15
3.3 Mathematical model 16
3.3.1 Objective function 19
3.3.2 The response time constraint 23
3.3.3 Modeling the other constraint 28
3.4 Greedy algorithm 30
Chapter 4 Model Application 33
4.1 Validation 33
4.1.1 A MVPP case to validate the mathematical model 33
4.1.2 Experiments of Validation 35
4.2 Evaluation 40
4.2.1 The MVPP case for evaluation 40
4.2.2 Experiments of Evaluation 41
Chapter 5 Conclusion 48
5.1 Research Contribution 48
5.2 Further Research 48
Appendix A. Mathematical model in AMPL format 53
Appendix B. Greedy Algorithm in AMPL format 57
Appendix C. Additional cases 60

參考文獻

Allen, A. O., Probability, Statistics, and Queuing Theory with computer science applications, Academic Press, 1990
Baralis, E., S. Paraboschi, E. Teniente, “Materialized view selection in a multidimensional database”, 23rd VLDB Conference, pp. 156-165, 1997
Colby, L. S., A. Kawaguchi, D. F. Lieuwen, I. S. Mumick, K. A. Ross, “Supporting Multiple View Maintenance Policies”, ACM SIGMOD Conference, pp. 405-416, May 1997.
Fourer, R., D. M. Gay, B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, The Scientific Press Series, 1993.
Fourer, R., D. M. Gay, B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming with AMPL Plus Student Edition for Microsoft Windows, Duxbury Press, 1997.
Gupta, A., J. A. Blakeley, “Using partial information to update materialized views” Information Systems Vol. 20, No. 8 pp. 641-662, 1995
Gupta, H., V. Harinarayan, A. Rajaraman, J. D. Ullman, “Index Selection for OLAP”, In Proc. Of the Intl. Conf. on Data Engineering, 1997
Gupta, H. “Selections of views to materialize in a data warehouse”, in ICDT, 1997
Gupta, H., I. S. Mumick, “Selections of views to materialize under a maintenance cost constraint”, Proceedings of the International Conference on Data Engineering, 1998
Harinarayan, V., A. Rajaraman, J. D.Ullman, “Implementing data cubes efficiently”, ACM Sigmod, June 1996
Horng, J. T., Y. J. Chang, B. J. Lin, C. Y. Kao, “Materialized View Selection Using Genetic Algorithms in a Data Warehouse System”, IEEE, pp. 2221-2227, 1999
Inmon, W. H., Building the Data Warehouse, John Wiley & Sons, Inc., 3rd edition
Ku, J. H., “Simultaneous Determination of View Selection and Update Policy with Stochastic Query and Response Time Constraints”, Master thesis, National Central University, 2004
Kuno, H. A., E. A. Rundensteiner, “Incremental maintenance of materialized views in multiview: Strategies and performance evaluation”, IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No.5, pp. 768-792, September/October 1998
Liang, W., H. Wang, M. E. Orlowska, “Materialized view selection under the maintenance time constraint“, Data and Knowledge Engineering Vol. 37, No.2 pp. 230-216, 2001
Martin, J., System Analysis for Data Transmission, Prentice-Hall, Englewood Cliffs, New Jersey, 1972
Mistry, H., P. Roy, S. Sudarshan, K. Ramamritham, “Materialized view selection and maintenance using multi-query optimization”, http://www.cse.iitb.ac.in/~krithi/papers/ sigmod2001_viewmaint.pdf, 2000
Patel, J. K., C. B. Read, Handbook of the Normal Distribution, Marcel Dekker, 1996
Ross, S. M., Introduction to Probability Models, 8th edition, Academic Press, 2003.
Rajagopalan, S., “Make to Order or Make to Stock: Model and Application”, Management Science Vol. 48, No. 2, pp. 241–256, February 2002
Segev, A., W. Fang, “Currency based updates to distributed materialized views”, IEEE, pp.512-520, 1990
Segev, A., W. Fang, “Optimal update policies for distributed materialized views”, Management Science Vol.37, No7, pp. 851-870, July 1991
Theodoratos, D., T. Sellis, “Data warehouse configuration”, Proceedings of the 23rd VLDB Conference, pp. 126-135, 1997
Theodoratos, D., M. Bouzeghoub, “Data Currency Quality Satisfaction in the Design of Data Warehouse”, International Journal of Cooperative Information Systems Vol.10, No.3 pp. 299-326, 2001
Vassiliadis, P., “Data Warehouse Modeling and Quality Issues”, Department of Electrical and Computer Engineering National Technical University of Athens, Ph.D. Thesis, June 2000
Yang, J., K. Karlapalem, Q. Li, “A framework for designing materialized views in data warehousing environment”, Technical Report HKUST-CS96-35, October 1996
Yang, J., K. Karlapalem, Q. Li, “Algorithms for Materialized View Design in Data Warehouse Environment”, Proceedings of the 23rd VLDB Conference, pp. 136-145, 1997
Yu, X. J., C. H. Choi, G. Gou, H. Lu, “Selecting views with maintenance cost constraints: Issues, Heuristics and Performance”, Journal of Research and Practice in Information Technology, Vol.36, No.2, pp. 89-120, 2004
Zhang, C., X. Yao, J. Yang, “An Evolutionary Approach to Materialized Views Selection in a Data Warehouse Environment”, IEEE Transactions on Systems, Man, and Cybernetics-Part C: Application and Reviews, Vol. 31, No. 3, pp. 282-294, August 2001
Zhuge, Y., G. M. Hector, J. Hammer, J. Widom, “View Maintenance in a Warehousing Environment”, Technical Report, Stanford University, 1995

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2006-7-10

推文