The design of an OLAP system for supporting real-time queries is one of the major research issues．One approach is to use data cubes，which are pre-computed multidimensional views of data in the data warehouse．An initial set of data cubes can be derived．from which the answer to each frequently asked query can be retrieved directly．However，there are two practical problems concerning the design of a cube based system：1)the maintenance cost of the data cubes，and 2)the query cost to answer a selected set of frequently asked queries．Maintaining a data cube requires disk storage and CPU computation，So the maintenance cost is related to the total size of the data cubes materialized，and thus keeping all data cubes is impractical．The total size of cubes may be reduced by merging some cubes．However，the resulting larger cubes will increase the query cost of answering some queries．If the bounds on maintenance cost and query cost are strict．some of the queries need to be sacrificed．An optimization problem in data cube system design has been defined．With a maintenance-cost bound and a query-cost bound given by the user，it is necessary to opti-mize the initial set of data cubes such that the system can answer a maximum number of queries and satisfy the bounds．This is an NP-complete problem．Approximate algorithms Greedy Removing(GR)and 2-Greedy Merging with Multiple paths(2GGM)are proposed．Experiments have been done on a census database and the results show that our approach in both effbctive and efficient.
展开▼
