Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the “Cube” operator, which computes group-by aggregations over all possible subsets of the specified dimensions. The rapid acceptance of the importance of this operator has led to a variant of the Cube being proposed for the SQL standard. Several efficient algorithms for Relational OLAP (ROLAP) have been developed to compute the Cube. However, to our knowledge there is nothing in the literature on how to compute the Cube for Multidimensional OLAP (MOLAP) systems, which store their data in sparse arrays rather than in tables. In this paper, we present a MOLAP algorithm to compute the Cube, and compare it to a leading ROLAP algorithm. The comparison between the two is interesting, since although they are computing the same function, one is value-based (the ROLAP algorithm) whereas the other is position-based (the MOLAP algorithm). Our tests show that, given appropriate compression techniques, the MOLAP algorithm is significantly faster than the ROLAP algorithm. In fact, the difference is so pronounced that this MOLAP algorithm may be useful for ROLAP systems as well as MOLAP systems, since in many cases, instead of cubing a table directly, it is faster to first convert the table to an array, cube the array, then convert the result back to a table.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AADN96	Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
	AS	Arbor Software. "The Role of the Multidimensional Database in a Data Warehousing Solution". White Paper, Arbor Software. http://www.arborsoft.com/papers/wareWOC.html
	CCS93	E.F. Codd, S.B. Codd, and C.T. Salley. "Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate", White Paper, E.F. Codd and Associates. ht tp://w w w.arb orsoft .com/ papers / coddWO C. ht m 1
	DKOS84	David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	GBLP95	J. Gray, A. Bosworth, A.Layman, and H.Pirahesh. "Data Cube: A relational aggregation operator generalizing group-by, cross-tabs and sub-totals. Technical Report MSR-TR-95-22, Microsoft Research, Advance Technology Division, Microsoft Corporation, Redmond, 1995.
	GC96	George Colliat, OLAP, relational, and multidimensional database systems, ACM SIGMOD Record, v.25 n.3, p.64-69, Sept. 1996  [doi>10.1145/234889.234901]
	IA	Information Advantage. "OLAP- Scaling to the Masses". White Paper, Information Advantage. http: / / www. infoad van .com /
	MC	Stanford Technology Group, Inc. "INFORMIX- MetaCube". Product Brochure. http://www.in formlx.com/in formix/products / new.plo / stgbroch / brochure.html
	MS	MicroStrategy Incorporated. "The Case For Relational OLAP". White Paper, MicroStrategy Incorporated. htt p: / / www.strategy.com / dwf/wp.b_al .html
	OC	Oracle Corporation. "Oracle OLAP Products". White Paper, Oracle Corporation. htt p: / / w w w.o racle, corn / prod ucts / collat rl/olapwp.p d f
	PSW	Pilot Software. "An Introduction to OLAP'. White Paper, Pilot Software. http://w ww. pilotsw .corn/r .an d_t/wht paper/olap/olap, htm
	RJ	Arbor Software Corporation, Robert J. Earle, U.S.Patent # 5359724
	SM94	Sunita Sarawagi , Michael Stonebraker, Efficient Organization of Large Multidimensional Arrays, Proceedings of the Tenth International Conference on Data Engineering, p.328-336, February 14-18, 1994
	Wel84	T.A. Welch. "A Technique for High-Performance Data Compression". IEEE Computer, 17(6), 1984.
	ZTN	Y.H. Zhao, K. Tufte, and J.F. Naughton. "On the Performance of an Array-Based ADT for OLAP Workloads". Technical Report CS-TR-96- 1313, University of Wisconsin-Madison, CS Department, May 1996.

• Constructing reality Proceedings of the 11th annual international conference on Systems documentation
  Douglas A. Powell ,  Norman R. Ball ,  Mansel W. Griffiths
  
  
• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  

• ACM SIGMOD Record
  Volume 26 ,  Issue 2   June 1997