在查詢為隨機需求與回覆時間被限制的環境下同時決定資料倉儲所需儲存的資料與資料維護策略; Simultaneous Determination of View Selection and Update Policy with Stochastic Query and Response Time Constraints

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

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

題名:	在查詢為隨機需求與回覆時間被限制的環境下同時決定資料倉儲所需儲存的資料與資料維護策略;Simultaneous Determination of View Selection and Update Policy with Stochastic Query and Response Time Constraints
作者:	古傑煥;Chieh-Huan Ku
貢獻者:	工業管理研究所
關鍵詞:	再生理論;資料倉儲;資料維護策略;資料倉儲建置;卜瓦松分配;等候線;隨機模式;View selection;View maintenance policy;Poisson process;Renewal theory;M/G/1;AMPL/MINOS;MVPP;Data warehouse configuration
日期:	2004-06-14
上傳時間:	2009-09-22 14:13:03 (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, we simultaneously determine view selection and update policy in designing a data warehouse when the arrival of query follows a Poisson process and the response time of query is within a given threshold with a desired probability. In this research, we propose a mathematical model for determining optimal update policy when the set of materialized views are known. In the model, we adopt view maintenance policy for view update frequency, which does not change with the selected views in the former researches. Our model also incorporates the stochastic phenomenon to reflect the uncertain demand of query which is common in the real life. The mean system response time constrained by a specified time is formulated by a M/G/1 model. Furthermore, we develop a two-phase greedy algorithm for searching a better set of views to materialize. 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 solution running time between the greedy algorithm and exhaustive algorithm.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

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

社群 sharing

資料載入中.....