Simultaneous determination of view selection and update policy with stochastic query and response time constraints

Yu Chin Liu, Ping Yu Hsu, Gwo Ji Sheen, Steve Ku, Kai Wen Chang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


Data warehouses are built to reply query searches efficiently from integrated data of various systems. To improve the performance of the system, the issue of materializing views within data warehouses must be explored. This involves to pre-compute a set of selected views which are fact and dimension tables, under given resource and quality constraints. The quality constraints include query processing time, data maintenance time and the freshness of data when queries are placed. Then there is the policy of updating, which treats the time issue of data reloading in data warehouses. A model is proposed to determine the view selection and update policy when the arrival of queries follows Poisson processes with the constraints of system response time, storage space and query dependent currency of data (on systems capable of periodic and query-triggered updates). To the best of the researchers' knowledge, no other research has considered all these factors in their models. A two-phase greedy algorithm was developed to determine the optimal update policy for the view selection problem. Numerous experiments were performed to explore the sensitivity of the proposed model under various constraints and system parameter settings. The results show that the model has reasonable responses to the tunings and that the proposed algorithm can rapidly find acceptable solutions.

Original languageEnglish
Pages (from-to)3491-3509
Number of pages19
JournalInformation Sciences
Issue number18
StatePublished - 15 Sep 2008


  • Data warehouse
  • M/G/1 queuing model
  • Multiple view processing plan
  • Poisson process
  • Renewal reward process
  • View maintenance policy
  • View selection


Dive into the research topics of 'Simultaneous determination of view selection and update policy with stochastic query and response time constraints'. Together they form a unique fingerprint.

Cite this