数据方体系统设计中的优化问题

支持实时查询的联机分析处理系统的设计是当前一个很重要的研究问题。其中常用的方法是使用数据方体来实现。对于出现频率较高的查询,可以给出对应的数据方体集,使得每个查询都可以直接得到回答。但是在设计基于方体的系统时,需要考虑以下两个问题:(1)数据方体的维护成本,(2)回答频繁查询的响应时间。在用户给出了维护成本上限和响应时间上限后,需要对数据方体集进行优化,使得系统能够满足用户的要求,并回答尽可能多的查询。文章给出了数据方体系统设计优化问题的定义,这是一个NP完全问题,并提出了贪心删除和贪心合并的近似算法。实验表明了算法的有效性。

An Optimization Problem in Data Cube System Design

The design of an OLAP system for supporting real -t ime queries is one of the major research issues.One approach is to use data cu bes.A set of data cubes can be derived,from which the answer to each frequentl y asked query can be retrieved directly.However,there are two practical probl ems concerning the design of a cube -based system:(1)the maintenance cost of the data cubes,and(2)the response time to answer a selected set of frequ ently asked queries.With a maintenance bound and a response time bound given b y the user,it is necessary to optimize the set of data cubes such that the syst em can answer a maximum number of queries and satisfy the bounds.An optimizatio n problem in data cube system design has been defined.This is a NP -complete p roblem.Approximate algorithms Greedy Removing and Greedy Merging are proposed .Experiments have been done and the results show that our approach is both eff ective and efficient.