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

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/11193

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/11193

題名:	在查詢與更新為隨機需求與回覆時間被限制的環境下最小化資料倉儲系統之查詢與資料維護成本;Minimizing Query Processing and View Maintenance Cost with Stochastic Query and Update under a Response Time Constraints in a Data Warehouse System
作者:	張凱雯;Kai-Wen Chang
貢獻者:	工業管理研究所
關鍵詞:	普瓦松過程;資料倉儲;M/G/1 模型;AMPL/MINOS;MVPP;View selection;Poisson process;View maintenance;M/G/1
日期:	2006-06-28
上傳時間:	2009-09-22 14:16:06 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	資料倉儲被建立來有效地回答查詢。所謂的選擇先行作業結果即為透過選擇一個先行作業結果的組合，並且希望在最小化成本時，這個組合可以滿足模型的限制。而更新的策略則是談到應當在哪個時點重新更新作業結果中的資料。之前的研究將選擇作業結果與最小化成本兩個議題分開討論，但在實務上，這兩個問題是互相相關的。因此我們了解到同時解決這兩個問題對於資料倉儲設計上的重要性。除此之外，之前的研究都假設查詢頻率為固定，更新時間也為固定。這種作法並不能準確的反映出實際上使用者在查詢時的不確定性，也不能表現出即時更新的特性。因此，隨機的到達是要被考慮的。在查詢到達後，回覆的時間也是要被考慮的重要議題，回覆時間必須滿足使用者需求，因此回覆時間必須被考慮在議題的研究中。本研究提出了一個數學模型來最小化所有成本。並且在這個模型中，考慮了隨機的更新頻率，這點在之前的研究中是從來沒有被考慮過的。這個模型假設隨機的查詢到達率與更新頻率符合普瓦松分配，這個假設是很符合實際需求的。在建立回覆需求的限制模型上，我們採用一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.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....