  In the past few years, the number of OLAP applications increased quickly.
These applications use two significantly different DB structures:
multidimensional (MD) and table-based. One can show that the traditional model
of relational databases cannot make difference between these two structures.
Another model is necessary to make the differences visible. One of these is the
speed of the system. It can be proven that the multidimensional DB organization
results in shorter response times. And it is crucial, since a manager may
become impatient, if he or she has to wait say more than 20 seconds for the
next screen. On the other hand, we have to pay for the speed with a bigger DB
size. Why does the size of MD databases grow so quickly? The reason is the
sparsity of data: The MD matrix contains many empty cells. Efficient handling
of sparse matrices is indispensable in an OLAP application. One way to handle
sparsity is to take the structure closer to the table-based one. Thus the DB
size decreases, while the application gets slower. Therefore, other methods are
needed. This paper deals with the comparison of the two DB structures and the
limits of their usage. The new results of the paper: (1) It gives a
constructive proof that all relations can be represented in MD arrays. (2) It
also shows when the MD array representation is quicker than the table-based
one. (3) The MD representation results in smaller DB size under some
conditions. One such sufficient condition is proved in the paper. (4) A
variation of the single count header compression scheme is described with an
algorithm, which creates the compressed array from the ordered table without
materializing the uncompressed array. (5) The speed of the two different
database organizations is tested with experiments, as well. The tests are done
on benchmark as well as real life data. The experiments support the theoretical
results.
