HKUST Library Institutional Repository Banner

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 SizeFormat
cikm99david.pdf221KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.