|
|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/167
|
| Title: | Requirement-based data cube schema design |
| Authors: | Cheung, David W.
Zhou, Bo
Kao, Ben
Lu, Hongjun
Lam, Tak Wah
Ting, Hing Fung |
| Keywords: | Data cubes
Data cube schema design
OLAP
DSS |
| Issue Date: | 1999 |
| Citation: | Proceedings of the Eighth International Conference on Information and Knowledge Management : CIKM '99, Kansas City, MI, USA, 2-6 Nov. 1999, ACM, New York, USA, 1999, p. 162-169 |
| Abstract: | On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically. A very important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in pruning the search space for an optimal schema. This leads to a highly efficient algorithm. We report the efficiency and the effectiveness of cMP via an empirical study using the TPC-D benchmark. Our results show that the data cube schemas generated by cMP enable very efficient OLAP query processing. |
| Rights: | © ACM, 1999. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the Eighth International Conference on Information and Knowledge Management : CIKM '99, Kansas City, MI, USA, 2-6 Nov. 1999, ACM, New York, USA, 1999, p. 162-169 |
| URI: | http://hdl.handle.net/1783.1/167 |
| Appears in Collections: | CSE Conference Papers
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| cikm99david.pdf | | 221Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
