\documentstyle[psfig, 11pt]{article}
\input{defpaper.sty}
\newcommand{\comment}[1]{}
\setnormaldefaults
\newcommand{\OneandHalfSpace}{\edef\baselinestretch{1.05}\Huge\normalsize}
\newcommand{\DoubleSpace}{\edef\baselinestretch{1.2}\Huge\normalsize}
\newcommand{\TwoandHalfSpace}{\edef\baselinestretch{1.4}\Huge\normalsize}
\newcommand{\SingleSpace}{\edef\baselinestretch{1.0}\Huge\normalsize}
\newcommand{\TripleSpace}{\edef\baselinestretch{1.5}\Huge\normalsize}
\newcommand{\CrunchPreSecSpace}   {\vspace{-1em}}
\newcommand{\CrunchSecSpace}   {\vspace{-1em}}
\newcommand{\SpaceItem}   {\vspace{-1em}}
\newcommand{\CrunchParaSpace}  {\vspace{-1em}}
\newcommand{\AddSpaceAfterFigure}  {\vspace*{2ex}}
\newcommand{\AddSpace} {\vspace*{2ex}}
\newcommand{\EatSpace}  {\vspace*{-1ex}}
\enableSQL

%\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{9.3in} %was 8.75
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in} %was 6.8
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.00in} %was 0.25
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}
%\setlength{\parskip}{-0.005cm}

%\newlength{\tightlinespace}
%\newlength{\oldbaselineskip}
%\addtolength{\oldbaselineskip}{\baselineskip}
%\addtolength{\tightlinespace}{0.8\baselineskip}
%\setlength{\baselineskip}{\tightlinespace}       % to obtain single spacing

% Before title
\def\papernumber #1 raised #2 {
\vspace{-#2}
\vbox to 0pt{\hfill
\framebox{\bf Paper Number: #1}}
\vspace{#2}
}



\title{Aggregate Aware Caching for Multi-Dimensional Queries}
\author{{\bf Prasad M. Deshpande}{\thanks{Currently at NCR Corp.}}\\
	\and
	{\bf Jeffrey F. Naughton}\\
}
\CrunchParaSpace
\date{
	{\small {\sl \{pmd, naughton\}@cs.wisc.edu}}\\
	{\small Computer Sciences Department}\\
	{\small University of Wisconsin, Madison, WI 53706}\\
}


\begin{document}
%\TripleSpace
%\DoubleSpace
\OneandHalfSpace
%\SingleSpace
\maketitle
% After \maketitle
\papernumber AMERICA140 raised 3.2in
\input epsf
\vspace{-1cm}
\begin{abstract}
To date, work on caching for OLAP workloads has focussed
on using cached results from a previous query as the answer to 
another query.  This strategy is effective when the query stream exhibits
a high degree of locality. It unfortunately misses
the dramatic performance improvements obtainable when the answer
to a query, while not immediately available in the cache, can
be computed from data in the cache.  In this paper, we consider
the common subcase of answering queries by aggregating 
data in the cache.  In order to use aggregation in the cache, one must solve
two subproblems: (1) determining when it is possible to answer
a query by aggregating data in the cache, and (2) determining the
fastest path for this aggregation, since there can be many.
We present two strategies -- a naive one and a  {\it Virtual Count} based strategy. The virtual count based method finds if a 
query is computable from the cache almost instantaneously, with a small
overhead of maintaining the summary state of the cache. The algorithm
 also maintains
cost-based information that can be used to figure out the
best possible option for computing a query result from the cache. 
Experiments with our implementation show that aggregation in the cache
leads to substantial performance improvement. The virtual
count based methods further improve the performance compared to the naive
approaches, in terms of cache lookup and aggregation times.

\end{abstract}
\CrunchParaSpace
\section{Introduction}
\CrunchParaSpace
On-Line Analytical Processing (OLAP) systems provide tools for
analysis of multi-dimensional data. Most systems are built using a
three tier architecture. The first tier provides a GUI and the middle
tier provides a multi-dimensional view of the data stored in the final
tier, which can be a RDBMS. Most of the queries are complex,
requiring the aggregation of large amounts of data. However, decision
support applications need to be interactive and demand fast response
times. Different techniques to speed up a query have been studied and
implemented, both in research and industrial systems.  These include
precomputation of aggregates in the database, having specialized index
structures, and caching in the middle tier.

While a great deal of work has been published on these issues,
to our knowledge the published literature has not addressed
the important issue of building an ``active cache'', one that can not only
speed queries that ``match'' data in the cache, but can also answer
queries that require aggregation of data in the cache.   We
show that a cache with such an ability is much more effective than
a cache without such a capability.  Intuitively, this is straightforward:
aggregating cache-resident data is much faster than issuing a SQL
query to a remote data source.  However, in practice making this work
is non-trivial.

The first issue to be dealt with is that in such an active cache the
lookup process is considerably more complex than it is in an ordinary
cache, because it is not sufficient to see if the query result is in
the cache. One must determine if the data in the cache is a
sufficient basis from which to compute the answer to the query.  This
problem is especially difficult with fine granularity caching schemes
such as chunk-based caching~\cite{drsn98}, query
caching~\cite{sdjl96:views}, and semantic caching~\cite{dfjst96}.
Obviously, this lookup must be fast --- it is infeasible to spend a
substantial amount of time deciding if a query can be computed from
the cache, because it is possible that the lookup cost itself could
exceed the time required to bypass the cache and execute the query at
the remote backend database.

The second issue to be dealt with is that in such an active cache, there
can be multiple ways in which to perform the aggregation required to answer
the query.  This situation arises due to the hierarchical nature of
OLAP multidimensional data models --- in general there are multiple
aggregation paths for any query.  The multiple aggregation paths
complicate the cache lookup problem even further, since now not only
is it necessary to determine if a query is computable from the cache,
one must also find the best way of doing this computation.

In this paper, we propose solutions to both the cache lookup problem and
the optimal aggregation path problem.  Our implementation shows that
with a small space overhead, we can perform much better than naive approaches.
Overall, an active cache substantially outperforms a conventional cache
(which does not use aggregation) for the representative OLAP workloads  
we studied.

\CrunchParaSpace
\subsection{Related Work}
OLAP has received extensive attention from the research
community. Most of the work can be classified into pre-computing
aggregates, indexing mechanisms or caching. The problem of computing
the cube has been studied in \cite{Prasad}, \cite{zhao},
\cite{ross:cube}. \cite{sdnr96} deals with the issue of the space required for
precomputation. Picking group-bys to precompute has been studied in
\cite{hru96:cube} and \cite{sdn98}. \cite{cubetree} and \cite{kotidis}
consider the problem of efficient organization of the cube data. 
In the field of caching,
\cite{ssv} presents replacement and admission schemes specific to
warehousing. The problem of answering queries with aggregation using
views has been studied extensively in \cite{sdjl96:views}. Semantic
query caching for client-server systems has been studied in
\cite{dfjst96}. \cite{slcj98} presents a method for dynamically
assembling views based on granular view elements which form the
building blocks. Another kind of caching is chunk-based caching 
which is a semantic caching method optimized for the OLAP domain. Our previous
paper~\cite{drsn98} describes chunk based caching in detail. The
different methods of implementing aggregations compared in this paper
are based on a chunk caching scheme.
\CrunchParaSpace
\subsection{Paper Organization}
The remainder of the paper is organized as follows:
Section~\ref{chunk-caching} gives a brief description of the chunk
based scheme, on which our experiments are based.
Section~\ref{problem-defn} defines the problem formally, and presents a
exhaustive search method for implementing aggregations.  The virtual
count based strategy is described in
Section~\ref{VCM-description}. These methods are extended to
incorporate costs in Section~\ref{cost-optimization}. A discussion
of some replacement policies is
presented in Section~\ref{rep-policy}. 
Section~\ref{experiments}
describes our experiments and results.  The conclusions are presented
in Section~\ref{conclusions}.

\CrunchParaSpace
\section{Chunk based caching}
\label{chunk-caching}
\CrunchParaSpace
Chunk-based caching was proposed in~\cite{drsn98}.  In
this section, we review chunk-based caching in order to make 
this paper self-contained.
The motivation of chunk based caching is to allow a query to take advantage
of overlap with previous queries, even if the later queries are not totally
contained in the previous queries.

Chunk based caching takes advantage of the multi-dimensional nature of
OLAP data. The dimensions form a multi-dimensional space and data
values are points in that space. The distinct values for each
dimension are divided into ranges, thus dividing the multi-dimensional
space into chunks.  Figure~\ref{chunkcomp} shows a multidimensional
space formed by two dimensions $Product$ and $Time$ and the chunks at
levels $(Product, Time)$ and $(Time)$. The caching scheme uses chunks
as a unit of caching. This works well since chunks capture the notion
of semantic regions. Note that there can be chunks at any
level of aggregation.


\begin{figure*}	
\parbox[t]{3in}
{
\centerline{
  \epsfysize=2.0in
  \epsffile{fig/chunkcomp.eps}
}
\caption{\label{chunkcomp} Chunks at different levels.}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
\centerline{
  \epsfysize=2.0in
  \epsffile{fig/query.eps}
}
  \caption{\label{query-fig} Reusing cached chunks.}
}
  \vspace{-0.1in}
\end{figure*}


In the chunk-based caching scheme, query results to be stored in the
cache are broken up into chunks and the chunks are cached. When a new
query is issued, the query is analyzed to determine what chunks are
needed to answer it. The cache is probed to find these chunks. 
Depending on what chunks are present in the cache, the
list of chunks is partitioned into two. One part is answered from the
cache. The other part consists of the missing chunks which have to be
computed from the backend. To compute the missing chunks, a single SQL
statement is issued to the backend translating the missing chunk numbers into
the selection predicate of the SQL query.

\begin{example}
Figure~\ref{query-fig} shows three queries Q1, Q2 and Q3 which are issued in
that order. Q3 can use some of the cached chunks it has in common with Q1 and 
Q2. Only the missing chunks (marked by the shaded area) have to be
computed from the backend.
\end{example}
\CrunchParaSpace

An important property we use later is the closure property of chunks
described in~\cite{drsn98}. This means that there is a simple correspondence
between chunks at different levels of aggregation. A set of chunks at
a detailed level can be aggregated to get a chunk at higher level of
aggregation. For example, Figure~\ref{chunkcomp} shows that chunk $0$
of $(Time)$ can be computed from chunks $(0, 1, 2, 3)$ of $(Product,
Time)$.

In~\cite{drsn98}, we show that chunk based caching performs better than complete query
caching. The main reasons for this are that chunking achieves fine granularity
of caching and allows for partial reuse of results. The query need not be
completely contained in the cache. Chunks which are present can be reused and
only the missing chunks are computed at the backend. Performance can be further
improved by having a chunk based file organization in the backend. Further
details are available in~\cite{drsn98}.
\CrunchParaSpace
\section{Aggregations in the Cache}
\label{problem-defn}   
\CrunchParaSpace
We now consider the problem of aggregation in more detail. In a
multi-dimensional schema, there are many possible levels of
aggregation, each of which corresponds to a different group-by
operation. These group-bys can be arranged in the form of a lattice
using the "can be computed by" relationship. This kind of structure has been
extensively used in previous work~\cite{Prasad, hru96:cube, sdn98}.

\begin{example}
Consider a schema with three dimensions $A$, $B$ and $C$. Dimension
$B$ has a two level hierarchy defined on it, whereas $A$ and $C$ have a
single level hierarchy as shown in Figure~\ref{simple-schema}.
Figure~\ref{lattice} shows the lattice formed by these
dimensions. $(x, y, z)$ denotes the level on each of the
dimensions. $(1, 2, 1)$ is the most detail level $(A_1B_2C_1)$
whereas $(0, 0, 0)$ is the most aggregated level $(A_0B_0C_0)$.
\end{example}
\CrunchParaSpace

\begin{figure*}
\parbox[b]{3in}
{
\centerline{
\begin{tabular}{|c|c|}
\hline
Dimension&Levels \\
\hline
A& $A_1$, $A_0$ = ALL \\
B& $B_2$, $B_1$, $B_0$ = ALL \\
C& $C_1$, $C_0$ = ALL \\
\hline
\end{tabular}
}
\caption{Schema \label{simple-schema}}
}
\makebox[0.5in]{}
\parbox[b]{3in}
{
\centerline{
  \epsfysize=2.0in
  \epsffile{fig/lattice.eps},
}
\caption{\label{lattice} Lattice of group-bys.}
}
  \vspace{-0.1in}
\end{figure*}

For any group-by there are many group-bys from which it can be
computed. In general, a group-by $(x_1,y_1,z_1)$ can be computed from
$(x_2, y_2, z_2)$ if $x_1 \le x_2$, $y_1 \le y_2$ and $z_1 \le
z_2$. For example, group-by $(0, 2, 0)$ can be computed from $(0, 2,
1)$ or $(1, 2, 0)$. Thus we need to consider all the
ancestors to determine if a particular group-by query can be answered
from the cache.

The problem becomes more complex when using the chunk-based caching
scheme. Due to the closure property, there is a simple correspondence
between chunks at different levels of aggregation. For example, a
chunk at level $(0, 2, 0)$, say chunk 0, will map to a set of chunks
at level $(1, 2, 0)$, say chunks 0 and 1. To compute chunk 0 of $(0,
2, 0)$ from $(1, 2, 0)$, we need both chunks 0 and 1 of $(1, 2,
0)$. It may happen that only chunk 0 of $(1, 2, 0)$ is present in the
cache whereas chunk 1 is computable from other chunks. This implies
that chunk 0 of $(0, 2, 0)$ is still computable from the cache. Thus
to determine if a chunk of a particular group-by is computable from
the cache, it is necessary to explore all paths in the lattice from
that group-by to the base group-by. Figure~\ref{lattice} shows the
different paths possible for computation of a chunk of $(0,2,0)$. Let
us first examine a naive method of finding if a chunk is computable 
from the cache.
\CrunchParaSpace
\subsection{Exhaustive Search Method}
\CrunchParaSpace
The Exhaustive Search Method (ESM) is a naive implementation of
finding if a chunk is computable from the cache. If a chunk is
missing from the cache, it searches along all paths to the base
group-by, to check if it can be computed from the cache. The algorithm
is listed below: 
\algorithm{
\>{\bf Algorithm : ESM(Level, ChunkNumber) }\\
\> {\it Inputs:} \>\>\>Level -- Indicates the group-by level \\
\>\>\>\>ChunkNumber -- Identifies chunk that needs to be computed \\
\> {\it Outputs:} \>\>\> success -- to indicate if the chunk is computable \\
\>\>\>\> path -- path for a successful computation \\
\>if (CacheLookup(Level, ChunkNumber))		// Lookup in the cache \\
\>\>  return true; \\
\>For each Parent Group-by in the lattice \\
\>\>  ParentLevel = level of the Parent Group-by \\
\>\>  ParentChunkNumbersList = GetParentChunkNumbers(ChunkNumber, Level, ParentLevel)\\
\>\>  success = true;	\\
\>\>  For each chunk number CNum in ParentChunkNumbersList \\
\>\>\>	if (!ESM(ParentLevel, CNum))	\\
\>\>\>\>	   success = false		\\
\>\>\>\>	   break		\\
\>\>if (success)	\\
\>\>\>	return true	\\
\>return false	
}
In the above algorithm, {\it GetParentChunkNumbers()} is a function which maps a
chunk at one level to a set of chunks at a more detailed level. This
algorithm searches different paths and quits as
soon as it finds a successful path. We have skipped some details
here in order to keep the algorithm concise and readable. As it explores
the different paths, it has to keep track of what chunks have been
found at what level. This is required so that if a search is successful, all the chunks
found during the search can be aggregated to give the required chunk.

\begin{lemma}
\label{ESMComplexity}
Consider a schema having $n$ dimensions, with hierarchies of size $h_i$ 
on dimension $d_i$. Let $(l_1, l_2, \ldots l_n)$ denote the level
of a group-by. Note that $(0, 0, \ldots 0)$ is the most aggregated
level and $(h_1, h_2, \ldots h_n)$ is the
base level. The maximum number of paths in the lattice searched by ESM for a group-by at
level $(l_1, l_2, \ldots l_n)$ is given by: 
\[\frac{(\Sigma_{i=1}^{n}(h_i - l_i))!}{\Pi_{i=1}^{n}(h_i - l_i)!}\]
\end{lemma}
\begin{proof}
This comes from the observation as we go along any path from $(l_1,
l_2, \ldots l_n)$ to the base node $(h_1, h_2, \ldots h_n)$, the level
in one of the dimension is increasing by one for each step in the
path. Each different order of this increase leads to a new path. This
leads to the factorial number of possible combinations in the numerator. The
denominator is due to the fact that the order within each dimension is
not important. The actual number of
recursive calls to ESM is much higher than this because a single aggregate 
chunk maps to multiple chunks at a detailed level (through the {\it MapChunkNumbers()}
function) and ESM has to be called on each of those chunks, i.e. there
is a fanout along each step of the path. This fanout is quite
expensive, but due to space limitations we will omit the detailed analysis here.
\end{proof}

Lemma~\ref{ESMComplexity} suggests that the complexity of determining
if a chunk can be computed from the cache depends on the level of
aggregation of the chunk. For highly aggregated chunks, the number of paths
searched is higher since there are many ways to compute them. For example, for
the most aggregated level $(0,0, \ldots 0)$, it is $(h_1 + h_2 \ldots
+ h_n)!/(h_1!*h_2!*\ldots h_n!)$. Note that this is the worst case complexity. The
algorithm will complete as soon as it finds one way to compute the
chunk. For example, if the chunk is already present in the cache, ESM
quits immediately. The average complexity depends on the actual
contents of the cache. We experimentally demonstrate this in
Section~\ref{experiments} for different cases.

\CrunchParaSpace
\section{Virtual Count Based Method}
\label{VCM-description}
\CrunchParaSpace
There is a lot of room for improvement in the naive ESM method. Our
strategy, the {\em Virtual Count} based method (VCM) is 
motivated by two observations:
\begin{enumerate}
\CrunchParaSpace
\item
As ESM searches along different paths, a lot of vertices are visited
multiple times. This
is because of the lattice structure, where the paths are not disjoint,
and will have multiple common vertices.

\begin{example}
Consider a small sub-section of a lattice as shown in
Figure~\ref{lattice-section}. Suppose ESM is searching for chunk 0 at
level $(0,0)$. Two of the paths from $(0,0)$ intersect at $(1,1)$. As
ESM searches these two paths, it will search for each of chunks 0, 1,
2 and 3 at level $(1,1)$ two times -- once for each path. It does not
reuse the work done previously.
\end{example}
\item
A lot of the work can be reused by maintaining some summary of the
state of the cache in terms of some meta-information
about each chunk. \comment{As we will show in our implementation results, since
the number of chunks is quite small compared to the total size of the
data, the overhead for this information is reasonable.}
\end{enumerate}
\CrunchParaSpace
\begin{figure*}
\parbox[t]{3in}
{
\centerline{
  \epsfysize=2in
  \epsffile{fig/latticepaths.eps}
}
\caption{\label{lattice-section} Searching along Paths}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
\centerline{
  \epsfysize=2.0in
  \epsffile{fig/virtualcounts.eps}
}
\caption{\label{chunk-counts} Virtual counts.}
}
\end{figure*}

In accordance with these observations, VCM maintains a count for each chunk 
at each group-by level. A chunk may be either directly present in the cache 
or may be computable through some path. Each path has to pass through some
parent of that node in the lattice. Thus, the virtual count 
for a chunk is defined as:
\begin{nameddefinition}{Virtual Count}
The virtual count for a chunk indicates the 
number of parents of that node through which there is a successful 
computation path. The count is incremented by one if the chunk is directly
present in the cache.
\end{nameddefinition}

\begin{example}
Figure~\ref{chunk-counts} shows a very simple lattice with two dimensions
having hierarchy size of 1 each. Level $(1,1)$ has 4 chunks, levels $(1,0)$ and
$(0,1)$ have 2 chunks each and level $(0,0)$ has only 1 chunk. The figure shows
the chunks that are present in the cache and the counts maintained by the VCM.
Chunk 0 at level $(1,1)$ has count 1 since it is present in the cache and that
is the only way to compute it. Chunk 1 at level $(1,1)$ is not computable,
nor is it present in the cache, thus giving a count of 0. Chunk 0 at level
$(0,1)$ has a count of 1 even though it is not present in the cache. This is
because there is a successful computation path through 1 of its parents, i.e.
level $(1,1)$. Chunk 0 at level (0,0) is present in the cache. Also, there are
successful computation paths through two of its parents. Thus the count for 
chunk 0 at level (0,0) is 3.
\end{example}
\CrunchParaSpace
Note that the count is not equal to the total number of ways of
computing a chunk, but is just indicative of whether a chunk is
computable. If a node has $k$ parents in the lattice, a chunk of that node
cannot have a count greater than $k + 1$. There is a subtle reason for defining
the count in this way rather than as the total number of successful paths. The
reason is explained in the proof of Lemma~\ref{UpdateComplexity}.
Once these counts are maintained, determining if a chunk is computable from the
cache is trivial due to the following property, upon which the next
algorithm is based. 
\begin{property}The virtual count of a chunk is non-zero if and only if it is
computable from the cache.
\end{property}
\begin{proof}
The proof of the above follows from the definition of virtual count and the
observation that any path of computation must pass through some parent node.
\end{proof}

\algorithm{
\>{\bf Algorithm : VCM(Level, ChunkNumber) }\\
\> {\it Inputs:} \>\>\>Level -- Indicates the group-by level \\
\>\>\>\>ChunkNumber -- Identifies chunk that needs to be computed \\
\> {\it Outputs:} \>\>\> success -- to indicate if the chunk is computable \\
\>\>\>\> path -- path for a successful computation \\
\>if (Count(Level, ChunkNumber) == 0)	 // Count is the array of counts	 \\
\>\>  return false; \hspace{2in}\ldots\hspace{2.5in}(I)\\
\>if (CacheLookup(Level, ChunkNumber)) \\
\>\>  return true; \\
\>For each Parent Group-by in the lattice \\
\>\>  ParentLevel = level of the Parent Group-by \\
\>\>  ParentChunkNumbersList = GetParentChunkNumbers(ChunkNumber, Level, ParentLevel)\\
\>\>  success = true;	\\
\>\>  For each chunk number CNum in ParentChunkNumbersList \\
\>\>\>	if (!VCM(ParentLevel, CNum))	\\
\>\>\>\>	   success = false		\\
\>\>\>\>	   break		\\
\>\>if (success)	\\
\>\>\>	return true	\\
\>assert(false)   // control should never reach here	
}

Again, some details have been omitted from the algorithm, which
includes maintaining information about the chunks found on the
successful path, so that they can 
be aggregated.  This algorithm looks similar to ESM in structure. However,
the check for Count to be non-zero in statement (I) acts as a short
circuit to reduce the complexity. If a chunk is not
computable from the cache, VCM returns in constant time (just a single count
lookup). If a chunk is indeed computable, VCM explores exactly one path (the
one which is successful). Unsuccessful paths are rejected immediately
without exploring completely. Compare this with the factorial number of paths for
ESM. The complexity of VCM is constant in the number of paths making it much
faster than the ESM.
\CrunchParaSpace
\subsection{Maintaining the Counts}
\CrunchParaSpace
Maintenance of the virtual counts makes lookups instantaneous. However, it
adds an overhead when chunks are inserted or deleted from the cache. The counts
will get updated at that time. The update algorithm while adding a chunk is 
listed below:

\algorithm{
\>{\bf Algorithm : VCM\_InsertUpdateCount(Level, ChunkNumber) }\\
\> {\it Inputs:} \>\>\>Level -- Indicates the group-by level \\
\>\>\>\>ChunkNumber -- Identifies chunk whose count needs to be incremented\\
\> {\it Outputs:} \>\>\>none\\
\>Count(Level, ChunkNumber) = Count(Level, ChunkNumber) + 1		\\
\>if (Count(Level, ChunkNumber) $>$ 1)   // Chunk was previously computable	\\
\>\>  return \\
\>For each Child Group-by in the lattice \\
\>\>   ChildLevel = level of the Child Group-by \\
\>\>   ChildChunkNumber = GetChildChunkNumber(ChunkNumber, Level, ChildLevel) \\
\>\>   ChunkNumbersList = GetParentChunkNumbers(ChildChunkNumber, ChildLevel, Level)\\
\>\>  flag = true;	\\
\>\>  For each chunk number CNum in ChunkNumbersList \\
\>\>\>	if (Count(Level, CNum) == 0)	\\
\>\>\>\>   flag = false		\\
\>\>\>\>   break		\\
\>\>if (flag)	\\
\>\>\>	VCM\_InsertUpdateCount(ChildLevel, ChildChunkNumber)
}

\noindent We will not go into formal proof of the correctness of the
above update  
algorithm in maintaining virtual counts. However, we do comment on its
complexity.
\begin{lemma}
\label{UpdateComplexity}
Suppose we are inserting a new chunk in the cache at level $(l_1, l_2, \ldots
l_n)$. The number of counts updated is bounded by $n*\Pi_{i=1}^{n}(l_i +
1)$.
\end{lemma}
\begin{proof}
The proof follows from a
observation that for any new chunk inserted in the cache, a recursive call to
{\it VCM\_InsertUpdateCount()} occurs only on aggregated chunks to which 
the new chunk
contributes. A chunk can contribute to only one chunk at each node in
the sub-lattice below. The number of nodes in the sub-lattice below 
$(l_1, l_2, \ldots l_n)$ is given by $\Pi_{i=1}^{n}(l_i + 1)$. Also, whenever
update is called on a chunk, its virtual count is incremented by 1. By the
definition of virtual count, contribution to the virtual count of any chunk 
from 
parent nodes cannot exceed $n$ (since there are at most $n$ parents for each
node). Thus the number of calls during the update recursion is bounded by
$n*\Pi_{i=1}^{n}(l_i + 1)$. 

Note that the definition of virtual count plays a crucial part here. If virtual
count had been defined as the total number of successful paths to a chunk, the
bound would have been much larger (since the factor $n$ gets replaced by a
factorial number of paths). The trick of the VCM algorithm is to maintain just
sufficient information to determine if a chunk is computable, keeping the
update cost minimal at the same time.
\end{proof}

The exact complexity of a single insert depends on the cache contents. 
The amortized complexity over all the inserts is much lesser than
this worst case complexity. This is because, the updates are propagated only
when a chunk becomes newly computable. A chunk can become newly computable only
once. It could be more if there are deletes also since a chunk can keep
switching between computable and non-computable state. However we don't expect
this to happen very often for each chunk. Typically a chunk insert will cause
update to propagate to only one level. This is similar to B-Tree splits, where
most page splits do not propagate more than one level. 
The counts have to be updated even when a chunk is thrown out of the cache. The
algorithm for that is similar to the {\it VCM\_InsertUpdateCount()} method 
both in implementation and complexity, so we will omit the details in 
this paper.

It can be shown from Lemma~\ref{ESMComplexity}
and~\ref{UpdateComplexity} that the worst case complexity of the ESM
find is much higher compared to the update complexity of the VCM
update. Again, due to space constraints we will skip the proof. 
\CrunchParaSpace
\subsection{Space Overhead}
\CrunchParaSpace
The improved performance of VCM comes at the expense of additional memory
required to store the counts. The number of counts maintained is
equal to total number of chunks at all possible levels. This might seem large,
but it is feasible due to the following reasons:
\begin{enumerate}
\CrunchParaSpace
\item
If a chunk is not computable, its count is 0. If we use a sparse array
representation, the amount
of storage becomes proportional to the number of chunks computable from the
cache rather than the total number of possible chunks. In our
implementation, we use a dynamic representation, that switches between
a sparse and a dense representation. 
\item
The number of chunks is much smaller than the actual number of tuples
in the base 
table. For example, in the schema used for our experiments, the base
table had a size of 20 MB (million tuples of 20 bytes each). The total number of
chunks over all the levels is 32256. Assuming 4
bytes per chunk for its count (actually 1 byte would suffice here), we
need only 32256*4 = 129 KB for the entire schema. 
This is quite small (about 0.6\%) compared to the base table size. We
can expect space overhead also to scale linearly with 
the database size, since the number of chunks typically increases
linearly assuming the average chunk size is maintained.
\item
Active caches make it feasible not to cache chunks at certain levels
in the lattice. This is particularly attractive if the group-by size
of a node in the lattice is about the same as that of its parent
(i.e. the group-by does not cause any compression). Pruning out such nodes
from the lattice leads to fewer counts to be stored.
We will not go into the details of this optimization, due to space constraints.
\end{enumerate}
\CrunchParaSpace
\CrunchParaSpace
\section{Cost Based Strategies}
\label{cost-optimization}
\CrunchParaSpace
The ESM and the VCM algorithms find just one path for the
computation of a chunk. The cost to compute a chunk from the
cache depends on the cost of aggregation. We assume a linear cost of
aggregation, i.e. the cost is proportional to the number of tuples
aggregated. This assumption has been used previously, for solving the
precomputation problem~\cite{hru96:cube, sdn98}. 
There may be multiple successful paths through
which a chunk could be computed. Each path will have different cost of computation
depending on what chunks are being aggregated along that path. Both
ESM and VCM can be extended to find the least cost path.  

\begin{example}
Consider the simple lattice shown in Figure~\ref{cost-lattice}. There are two
paths for computation of chunk 0 at level $(0,0)$. One way is to aggregate
chunk 1 at level $(1,0)$ and chunks 0 and 2 at level $(1,1)$. Another way is to
aggregate chunks 0 and 1 at level $(0,1)$. The costs for these two options are
different since the number of tuples being aggregated is different. In
general, it is better to compute from a more immediate ancestor in the lattice,
since group-by sizes keep reducing as we move down the lattice. 
\end{example}
\CrunchParaSpace
\begin{figure}[htb]
\centerline{
  %\psfig{file=fig/differentcosts.ps1,height=2.5in,bbllx=125pt,bblly=185pt,bburx=340pt,bbury=475pt,angle=-90,clip=}
  \epsfysize=2.0in
  \epsffile{fig/differentcosts.eps}
}
  \vspace{-0.1in}
\caption{\label{cost-lattice} Different costs of computation.}
\end{figure}

\comment{
An important question is whether the difference in costs is justifiable enough
to try to find the best path. There could be orders of magnitude difference
between the best and the worst path. However, we found that the cost of main memory
aggregation, when a chunk is computed from the cache, is very small compared to
the time to issue query and get results from the backend database. Queries can
hit in the cache either completely or partially (only a fraction of chunks
needed for the query are computable from the cache). For partial hit queries,
optimizing the aggregation times for chunks found in the cache
does not affect the total performance much, since anyway some results need to
be fetched from the backend. For complete queries,
the aggregation time becomes a significant percentage of the total
time. With bigger caches and more locality we can expect many queries to hit
completely in the cache thus making it important to optimize for the
aggregation cost. 
}
\CrunchParaSpace
\subsection{Cost Based ESM}
\CrunchParaSpace
\algorithm{
\>{\bf Algorithm : ESMC(Level, ChunkNumber) }\\
\> {\it Inputs:} \>\>\>Level -- Indicates the group-by level \\
\>\>\>\>ChunkNumber -- Identifies chunk that needs to be computed \\
\> {\it Outputs:} \>\>\> cost -- cost of the best path to compute the chunk \\
\>\>\>\> path -- least cost path for computation \\
\>if (CacheLookup(Level, ChunkNumber))		// Lookup in the cache \\
\>\>  return size of the chunk; \\
\>  mincost = INF				// INF = infinity  \\
\>For each Parent Group-by in the lattice \\
\>\>  ParentLevel = level of the Parent Group-by \\
\>\>  ParentChunkNumbersList = GetParentChunkNumbers(ChunkNumber, Level, ParentLevel)\\
\>\>  success = true;	\\
\>\> totalcost = 0; \\
\>\>  For each chunk number CNum in ParentChunkNumbersList \\
\>\>\>	cost = ESMC(ParentLevel, CNum); \\
\>\>\>	if (cost == INF)	\\
\>\>\>\>	   success = false		\\
\>\>\>\>	   break		\\
\>\>\>    else \\
\>\>\>\>     totalcost += cost; \\
\>\>if ((success) \&\& (totalcost $<$ mincost))	\\
\>\>\>	mincost = totalcost	\\
\>return mincost	
}

The Cost based ESM (ESMC), instead of quitting after finding the first path,
continues to search for more paths which might be of lesser cost.
The worst case complexity of ESMC is same as ESM. However, its average
case complexity is much higher since it always explores all paths to
find the minimum cost path. Whether this extra time is worth it
depends on the time saved in aggregation. We present some experimental
results which examine this in Section~\ref{experiments}.
\CrunchParaSpace
\subsection{Cost Based VCM}
\CrunchParaSpace
The cost based VCM (VCMC) finds the best path for computing a chunk by
maintaining cost information in addition to the count information. For
each computable chunk, it stores the cost of the least cost path to
compute it and the parent through which the least cost path
passes. There are two additional arrays for each level, the {\tt Cost} array
that stores the least cost and the {\tt BestParent} array that stores the
parent through which the least cost path passes. The find complexity is
still constant time, which makes this method very attractive.

\algorithm{
\>{\bf Algorithm : VCMC(Level, ChunkNumber) }\\
\> {\it Inputs:} \>\>\>Level -- Indicates the group-by level \\
\>\>\>\>ChunkNumber -- Identifies chunk that needs to be computed \\
\> {\it Outputs:} \>\>\> cost -- cost of the best path to compute the chunk \\
\>\>\>\> path -- least cost path for computation \\
\>if (Count(Level, ChunkNumber) == 0)	 \\
\>\>  return INF; \\
\>if (CacheLookup(Level, ChunkNumber))	\\
\>\>  return size of the chunk;	\\
\>parent = BestParent(Level, ChunkNumber)   \\
\>ParentLevel = level of parent \\
\>ParentChunkNumbersList = GetParentChunkNumbers(ChunkNumber, Level, ParentLevel)\\
\>totalcost = 0 \\
\>For each chunk number CNum in ParentChunkNumbersList \\
\>\>cost = VCMC(ParentLevel, CNum)	\\
\>\>assert(cost != INF) \\
\>\>totalcost += cost \\
\>return totalcost
}

The {\tt Cost} array is not being used by the VCMC method. It is used by the
update algorithm, when inserting and deleting chunks. The update
algorithm is similar to the one used by VCM. The only difference is that
in VCMC a update is propagated in two cases -- when a chunk becomes
newly computable and when the least cost of computing a chunk
changes. When the least cost changes, the costs of the children chunks
are updated using the {\tt Cost} array. We are not listing the update
algorithm here since it is similar to VCM update, but a little more
complex. The worst case complexity of update remains the same, but
the average complexity is slightly higher since an update is now
propagated even when the least cost of a chunk changes.

Another advantage to maintaining the costs for the VCMC method is that
it can return the least cost of computing a chunk instantaneously (without
actually doing the aggregation). This is very useful for a cost-based 
optimizer, which
can then decide whether to aggregate in the cache or go to the backend
database. In our
experiments, we did not use precomputed tables in the backend, so aggregating
in the cache was always faster. But in the presence of precomputed aggregate
tables, executing query at the backend might sometimes be faster. It is
necessary to have a cost-based optimizer to make runtime decisions.
\CrunchParaSpace
\section{Replacement Policies}
\label{rep-policy}
\CrunchParaSpace
The possibility of aggregating the cache contents to answer queries
leads to interesting options for effectively using the cache
space. In~\cite{drsn98}, we showed that a benefit based replacement policy
works very well for chunks. Highly aggregated chunks have a greater
value, since they are expensive to compute and thus are given a higher
weightage while caching. Finding an optimal replacement policy is much
more difficult for aggregate
aware caching schemes. There are two reasons:
\begin{enumerate}
\CrunchParaSpace
\item Other than being used to answer queries at the same level, a
chunk can potentially be used to answer queries at a more aggregated
level. 
\item Whether a chunk can be used to answer a query at a more
aggregated level depends on the presence of other chunks in the
cache. This is because an aggregated chunk maps to a set of chunks at
a more detailed level and all those chunks need to be present in order
to compute the aggregated chunk. This also means that the benefit of a
chunk depends on what chunks are inserted in the future, which is
impossible to predict. A replacement policy should try to form groups
of useful chunks.
\end{enumerate}

\begin{example}
In Figure~\ref{benefit-lattice}(a), chunk 0 at level (1,1) has a lower
benefit than chunk 0 at level (1,1) in
Figure~\ref{benefit-lattice}(b). The presence of chunk 1 at level (1,1)
in Figure~\ref{benefit-lattice}(a) leads to a higher benefit to both
chunks 0 and 1, since they can now be used to compute chunk 0 at level
(0,1). 
\end{example}
\CrunchParaSpace
\begin{figure}[htb]
\centerline{
  \epsfysize=2.0in
  \epsffile{fig/benefits.eps}
}
  \vspace{-0.1in}
\caption{\label{benefit-lattice} Benefits.}
\end{figure}

The actual benefit of aggregating a set of chunks into another chunk
may be because of two things:
\CrunchParaSpace
\begin{enumerate}
\item this aggregation provides a cheaper way to compute the chunk --
in this case benefit is equal to savings in aggregation cost
\item this aggregation is the only way to compute the chunk -- in this
case benefit is equal to the saving in the overhead of connecting to the backend,
issuing query and fetching results.
\end{enumerate}
\CrunchParaSpace
Typically, the overhead of issuing a SQL query to
the backend and fetching the results over the network can be quite
high compared to the cost of aggregating from the cache. A query will
run much faster if it can be completely answered by aggregating from
the cache. This motivates us to try and answer as many queries from
the cache as possible.
\CrunchParaSpace
\subsection{Preloading the Cache}
\CrunchParaSpace
\label{pre-loading}
Commercial systems have taken various approaches to loading and
pre-computing data. Some like Oracle Express and Arbor Essbase try to precompute
virtually everything~\cite{apb-bench}. These leads to long precomputation times, and
huge memory requirements in the middle tier.
Other systems such as Applix TM1 keep only the base data in main memory~\cite{tm1-ref},
always pre-computing from this.  This approach requires less memory,
and dramatically decreases precomputation time. Thus they can start
answering queries before others have even finished loading. However,
since even in-memory computation is not free, once the precomputation
is finished Oracle and Essbase are substantially faster.

We are looking at a hybrid, in which we load a part of the base data in
memory, then dynamically cache higher-level chunks.  The goal
is to get the best of both worlds: limited precompute time,
lowered memory requirements, and faster query execution time.
An important factor is the cache size relative to the base
data size.  Note that both the definition of ``base data''   and
``active 
portion''  will vary from application to application.  With respect to
`` base data'' , in many OLAP applications the ``base data'' is already
aggregated to some degree - for example, in a sales application for a
large retailer, the customer dimension is often rolled up into some
higher level segments.  With respect to the "active portion" of base
data, in many cases an application will be concerned primarily with a
given time window (e.g., last 12 months) or with a given scenario
(e.g., actual.)  The overall point is that in practice, for
OLAP applications the ``active portion of the base data''
is much smaller than the biggest fact table in a large data
warehouse.  One can see that this is true by examining the
OLAP marketplace - currently MOLAP dominates ROLAP by a wide
margin, and no currently deployed MOLAP application will run
on data sets the size of large warehouse fact tables.


If the cache can hold all the base level chunks, all the queries can
be answered from the cache and there is no 
need to go to the backend at all. \comment{ This might seem against the
intuition of keeping highly aggregated chunks in the cache. However,
once the base chunks are cached, highly aggregated chunks become more 
important like before since they save a lot on aggregation cost. }
However, if the cache is not big enough to hold all of the ``active
portion'' of the base level chunks,
it becomes important what chunks we cache. It is not of
much use if the cached chunks are distributed all over the
multi-dimensional space. For example, in Figure~\ref{benefit-lattice},
at level $(1,1)$ it is much better to cache chunks $0$ and $1$ rather
than chunks $0$ and $3$. Chunks $0$ and $1$ can be used to compute
chunk $0$ at level $(0,1)$ whereas chunks $0$ and $3$ cannot be
aggregated to give any higher level chunk. In general it is beneficial if
a set of chunks cached form a packed region of the multi-dimensional
space. We experimented with different options and found that loading an
entire group-by with the maximum number of descendents in the lattice and
which fits in the cache works well.

The area of cache replacement policies for active caches as
an interesting open area for future research.The focus of this paper
is not on cache replacement policies. However, we propose the following 
policy in accordance with our observations:
\begin{namedproposition}{Two Level Policy}
\begin{itemize}
\item Chunks are classified into two types -- those that are fetched
from the backend (called {\em backend chunks}) and those that are computed
from other chunks in the cache (called {\em computed chunks}). Backend
chunks have higher priority and can replace computed chunks, but not
the other way around. This policy tries minimize accesses to the
backend since they are expensive. Replacement within each group is
according to the normal benefit policy (i.e. highly aggregated chunks
have higher benefit -- same as that used in~\cite{drsn98}).
\item Whenever a group of chunks is used to compute another chunk, the
clock value (we approximate LRU with CLOCK) of all the chunks in the
group is incremented by an amount 
equal to the benefit of the aggregated chunk. This tries to identify
and maintain groups of useful aggregatable chunks in the cache.
\item To help in the formation of useful groups, we pre-load the cache
with a group-by that fits in the cache and has the maximum number of
descendents in the lattice. Picking such a group-by will enable
answering queries on any of its descendents.
\end{itemize}
\end{namedproposition}
Clearly this replacement policy is not optimal, and
        improving on it is fertile ground for future
        work.  But as our experiments show, this policy
        provides substantial benefits over such policies as 
        simple benefit based LRU.

%\section{Important Issues}
%\label{imp-issues}
\comment{
\section{Other Caching Schemes}
\label{other-schemes}
Even though the methods we have proposed seem specific to the chunk
based caching scheme, similar problems arise when using other caching
schemes also. The main distinction is whether we cache entire tables
or at a finer granularity (of either a query, chunk or a semantic
region). 
\begin{itemize}
\CrunchParaSpace
\item
Table level caching means that we cache entire group-bys rather than
just parts of it. For table level caching, the problem of finding the best
solution is easier. There is no need to explore all possible paths to compute a
query at a particular level. It is enough to consider all possible
ancestor nodes in the lattice. A table cached at any of the ancestor
nodes can be used to answer the query. The smallest size ancestor will
be the best choice. Thus ``find'' complexity is lesser than that of
ESM for chunk based scheme. However, table level caching wastes a
lot of valuable cache space since it caches entire tables rather than
just the hot portions of it.  For this reason table level caching
has been rejected by most previous studies on caching for multidimensional
workloads.
\item
For finer granularity caching schemes, the problem is as difficult as
for the chunk based scheme. To compute any query we may need to
aggregate different parts of group-bys at different levels. This makes it
necessary to explore all paths, thus increasing the complexity.
\end{itemize}
\CrunchParaSpace
}
\CrunchParaSpace
\section{Experiments}
\label{experiments} 
\CrunchParaSpace
In this section, we describe the experiments used to evaluate the performance
of the different schemes. We have a three tier system. The client issues
queries to the middle tier which does caching of results. Both the client and
the middle tier were running on a dual processor Pentium 90 MHz machine with 
128 MB of main
memory running SunOS 5.5.1. The backend database used was a commercial database
system,
running on a separate machine (a Sun UltraSparc 200 MHz with 256 MB of main memory
running SunOS 5.5.1). A buffer pool size of 30 MB was used at the backend. The
chunked file organization was achieved by building a clustered index
on the chunk number for the fact file. The query execution
times reported are the execution times at the middle tier. \comment{It does not
include the time for shipping the tuples back to the client, since that time is
very much dependent on the network speed.}

All experiments were run on the APB-1 Schema~\cite{apb}. APB-1 is an
analytical processing benchmark developed by the OLAP Council. The
APB-1 schema, like any 
OLAP schema, consists of a set of dimensions and measures.\comment{ The
dimensions have hierarchies defined on them. Data can be aggregated
along different dimensions to different levels in the hierarchy. This
leads to many possible aggregate queries.} APB has five dimensions
with hierarchies.
Also, there is a 
measure {\it UnitSales} associated with the dimensions {\it Product}, {\it
Customer}, {\it Time} and {\it Channel}. This mapping is stored in a fact
table $HistSale$. The schema is described below:

\noindent$Product = (PCode, PClass, PGroup, PFamily, PLine, PDivision)$ \\
\noindent$Customer = (CStore, CRetailor)$\\
\noindent$Time = (TMon, TQtr, TYr)$\\
\noindent$Channel = (ChBase)$\\
\noindent$Scenario = (Scenario)$

\noindent$HistSale = (CStore, PCode, ChBase, TMon, UnitSales)$


All queries were on the fact table {\it HistSale}, and asked for sum of 
{\it UnitSales} at different levels of aggregation. 
The number of nodes in the APB lattice is
$(6+1)*(2+1)*(3+1)*(1+1)*(1+1) = 336$, because the hierarchy sizes
are 6, 2, 3, 1 and 1 respectively. The data was generated using the APB data
generator~\cite{apb}, with the following parameters: number of
channels = 10 and data density = 0.7. The table HistSale had about a
million tuples, each of 20 bytes. Adding some page overhead the base table 
size comes to about 22MB. The estimated size of the full cube for this
schema is 902 MB. We experimented with cache sizes of 10 MB to 25 MB
which is quite small compared to the size of the full cube.
The number of distinct values and number of chunk ranges at
different levels of the dimensions are listed in
Table~\ref{apb-table}. The total number of chunks at the base level is
$8*10*4*2*1 = 640$.

\begin{table}
\centerline{
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
Level & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
Product & 1 (1) & 2 (1) & 7 (2) & 20 (4) & 100 (8) & 870 (8) & 9000 (8)\\
Customer & 1 (1) & 99 (10) & 900 (10) & -- & -- & -- & -- \\
Time & 1 (1) & 2 (1) & 8 (2) & 24 (4) & -- & -- & -- \\
Channel & 1 (1) & 9 (2) & -- & -- & -- & -- & -- \\
Scenario & 1 (1) & 3 (1) & -- & -- & -- & -- & -- \\
\hline
\end{tabular}
}
\caption{Distinct values and number of chunk ranges.}
\label{apb-table}
\end{table}

We performed two kinds of experiments. \comment{In caching experiments, the results
depends very much on the query stream being used.} In order to evaluate a
concept by itself, independent of the query stream generation method, we
performed a set of unit experiments. For these experiments we used a
very precise set of input queries, which were designed to bring out the 
best case, worst case and the average behavior.
The other set of experiments involved artificially generating a query stream
and comparing the performance of the different methods.
\CrunchParaSpace
\subsection{Unit Experiments}
\CrunchParaSpace
\label{UnitExpts}
\subsubsection{Benefit of Aggregation}
\CrunchParaSpace
This experiment demonstrates the benefit of implementing aggregations in the
cache. The query stream consists of one query at each level of aggregation.
Each query accesses one chunk at the corresponding level. The cache was
pre-loaded so that all the base table chunks are cached - level
$(6,3,2,1,0)$. \comment{The cache was big enough to hold the base level
chunks.} In one case, aggregation in the
cache was not used and all the queries had to be executed at the backend. In
the other case, the queries were answered by aggregating from the base table
chunks. The query execution times both at the backend or in the cache depends
on the level of aggregation. Table~\ref{AggrBenefit} shows the execution times
for two extremes : the most aggregated group by - level $(0, 0, 0, 0, 0)$ and a
very detailed group-by - level $(6,2,3,0,0)$. It also gives the average time
over all the group-bys. The Scenario dimension is always
at level 0 in all queries, since this dimension is missing from the HistSale
table. \comment{All execution times are in milliseconds. }
Aggregating in the cache is several times faster than executing the query in
the backend database for all the group-bys. This is due to the large overhead 
of issuing a SQL query to the backend database and
fetching results. Also, the backend database may not be optimized for
performing 
star joins, which are essential when rolling up along the hierarchies. On the
average, aggregating in cache is about 8 times faster. Note that this factor,
is highly dependent on the network and the backend database being
used. The presence of pre-computed aggregates at the backend would
also affect the results. In our experiments, there were no
pre-computed tables. Pre-computed tables at the backend might make it
necessary to have a simple optimizer which decides whether to
aggregate in the cache or fetch from the backend.
\CrunchParaSpace
\begin{table*}
\parbox[t]{3in}
{
\centerline{
\begin{tabular}{|c|c|c|c|}
\hline
Level & GB (0,0,0,0,0) & GB (6,2,3,0,0) & Average \\
\hline
Backend & 16255 & 1181 & 10720.8  \\
Cache & 6414 &  88 & 1301.46 \\
\hline
\end{tabular}
}
\caption{\label{AggrBenefit} Aggregating times in cache vs the backend (ms).}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
\centerline{
\begin{tabular}{|c|c|c|c|}
\hline
Level & GB (0,0,0,0,0) & GB (6,2,3,0,0) & Average \\
\hline
Best Path & 6 & 88 & 133.51  \\
Worst Path & 6414 & 88 & 1301.46 \\
\hline
\end{tabular}
}
\caption{\label{CostBenefit} Variation in aggregation costs (ms).}
}
\end{table*}
\CrunchParaSpace
\subsubsection{Aggregation Cost Optimization}
\CrunchParaSpace
This experiment aims to show how aggregation costs can vary along
different paths. For each group-by we compute one chunk in two ways:
in one case it is aggregated from chunks at the base level
and in the second case it is aggregated using the least cost method
(from its smallest parent). The difference in these times gives an
idea of the potential savings due to cost based optimization.
Table~\ref{CostBenefit} shows the execution times
for two extremes: the most aggregated group by -- level $(0, 0, 0, 0, 0)$ and a
very detailed group-by -- level $(6,2,3,0,0)$ and also the average time
over all the group-bys. For the most aggregated level $(0, 0, 0, 0, 0)$, the
ratio of the worst path to best path is the largest. A single tuple at that 
level
results from aggregating a large number of base tuples, so computing it from
base level is quite expensive. On the other hand, if it is computed from its
immediate parent (which itself is highly aggregated), the cost is smaller since
a smaller number tuples are aggregated. For a very detailed level like
(6,2,3,0,0), there 
is not much difference between the best and the worst paths. However, the
average speedup does suggest that cost based optimization is important.

\CrunchParaSpace
\subsubsection{Lookup Times}
\CrunchParaSpace
The complexity of the lookup algorithm to determine how to compute a
chunk is different for ESM and VCM. ESM explores all paths, whereas
VCM explores just a single path. In this  
experiment we measured the 
lookup times for all four algorithms ESM, ESMC, VCM and VCMC.  We
measured the lookup time for one chunk at each level of
aggregation. The lookup time depends on the level of aggregation
as well as on the cache
contents. Table~\ref{lookup} lists the minimum, 
maximum and the average lookup times over all the group-bys for two
cases: one where the experiment was run with an empty cache
and the other where the cache was warmed up with all
the base table chunks. 

In both cases, the cache lookup times for VCM and VCMC are negligible. 
These methods explore a maximum of one path. The times for
the ESM and ESMC are more interesting. When the cache is empty, none of the
paths will be successful. However, both these methods have to explore all the
paths. Lemma~\ref{ESMComplexity} suggests that the time depends on the level
of aggregation of the group-by. For detailed level group-bys the lookup time is
low since very few paths of computations exist. For aggregated group-bys the
time is much higher due to explosion in the number of paths. This variation is
one of the drawbacks of the exhaustive methods since query response time will
no longer be consistent. VCM and VCMC do not have these
problems. 

When all the
base table chunks are in the cache, lookup times for ESM becomes
negligible, since the very first path it explores becomes successful (base
table makes all paths successful). However, it is very likely that
the first path (from the base table) is not the best path. For ESMC,
the lookup time is just unreasonable when all the base level chunks are
cached, since ESMC has to explore all the paths, to find the 
best cost path. 
The cost of each path itself becomes much higher, since each chunk on
each path is computable and the ESMC is called recursively on it. We have
ignored this fanout factor (one chunk at a particular level maps to a set of
chunks at a more detail level) in estimating the complexity of the lookup. Even
a savings in aggregation costs cannot justify such high lookup times. So we do
not consider the ESMC method in any further experiments.
There is a small difference in the find times for ESM, VCM and VCMC
methods even though all three explore only one path. The time for VCM
and VCMC are slightly higher because of the overhead of additional array
lookups. 
\begin{table}
\centerline{
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
& \multicolumn{3}{c|}{Cache Empty} & \multicolumn{3}{c|}{Cache Preloaded} \\
\cline{2-7}
 & Min & Max & Average & Min & Max & Average \\
\hline
ESM & 0 & 106826 & 1896.1  & 0 & 44 & 4.54 \\
ESMC & 0 & 134490 & 2390 & 0 & 19826592 & 272598 \\
VCM & 0 & 0 & 0 & 0 & 62 & 6.32 \\
VCMC & 0 & 0  & 0 & 0 & 149 & 13.15 \\
\hline
\end{tabular}
}
\caption{Lookup times (ms).}
\vspace{-1em}
\label{lookup}
\end{table}
\CrunchParaSpace
\subsubsection{Update Times}
\CrunchParaSpace
The VCM and VCMC method incur an update cost while inserting and
deleting chunks, since they have to maintain count and cost
information. ESM and ESMC do not have any update
cost. Lemma~\ref{UpdateComplexity} suggests that update complexity is
higher for more detail level chunks. To look at the worst case
behavior we loaded all chunks of the base table -- level (6,2,3,1,0)
followed by all chunks at level (6,2,3,0,0). The update times vary
while inserting different chunks, since how far an update propagates
depends on what has been inserted in the cache previously. For
example, while inserting the last chunk at level (6,2,3,1,0), update
propagates all the way, since a lot of aggregate chunks become
computable because of it. Table~\ref{update} shows the maximum,
minimum and the average update time for the VCM and VCMC method.
Even the maximum update time is quite feasible and on an average the cost is
negligible. We can observe an interesting difference between VCM and VCMC.
When inserting chunks at level (6,2,3,0,0), the update times for VCM are 0.
All the chunks are already computable due to previous loading of level
(6,3,3,1,0), so the updates do not propagate at all. However, for VCMC,
insertion of chunks of (6,2,3,0,0) changes the cost of computation for all its
descendents in the lattice. The cost information needs to be changed and the 
update costs reflects this.

\begin{table}
\centerline{
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
 & \multicolumn{3}{c|}{Loading (6,2,3,1,0)} & \multicolumn{3}{c|}{Loading
(6,2,3,0,0)} \\
\cline{2-7}
 & Min & Max & Average & Min & Max & Average \\
\hline
VCM & 0 & 19 & 1.797 & 0 & 0 & 0 \\
VCMC & 1 & 36 & 5.427 & 0 & 15 & 10.09 \\
\hline
\end{tabular}
}
\caption{Update times (ms).}
\vspace{-1em}
\label{update}
\end{table}
\CrunchParaSpace
\subsection{Query Stream Experiments}
\CrunchParaSpace
For these experiments, we generated a stream of queries using different parameters.
These were similar to the ones used in~\cite{drsn98}. \comment{ and are described
in the following section.} For each experiment the cache was pre-loaded
with a group-by as our ``two-level policy''. Performance is measured
as an average over 100 queries. The cache 
sizes used ranged from 10 MB to 25 MB. This might seem high compared
to a base table size of 22 MB. But as noted earlier
(section~\ref{pre-loading}), very often in OLAP applications, the
``active portion'' of the base table is not as large as the biggest
table in the data warehouse. Besides the total cube size is 902 MB and this is 
what we are trying to cache. 
\CrunchParaSpace
\subsubsection{Generating a Query Stream}
\CrunchParaSpace
The query stream is a mix of four kinds of queries:
\begin{enumerate}
\CrunchParaSpace
\item {\bf Random Queries:} This query is generated by choosing a aggregation
level (group-by) randomly over the lattice with uniform distribution. Similarly
the selection predicate is chosen uniformly and randomly for each dimension.
\item {\bf Drill Down Queries:} The query generated a drill-down over the
previous query, i.e. we increase the level of detail in one of the dimensions.
The selection predicate is adjusted accordingly.
\item {\bf Roll Up Queries:} This is complement of drill down query, in which
the new query rolls up on one of the dimensions to a greater level of
aggregation.
\item {\bf Overlap queries:} The query generated is at the same level as the
previous query. The selection predicate is changed and it may partially overlap
with the previous selection range.
\end{enumerate}
\CrunchParaSpace

Roll-up, drill-down and overlap queries give rise to some locality in the query
stream. While traditional caching can exploit overlap locality, we need active
caches with aggregation to improve performance of roll-up queries. The query
stream we used had a mix of 30\% each of drill-down, roll-up and overlap queries.
The rest of them (10\%) were random queries. 

\comment {
{\bf Data Locality :} \\
Here we consider the situation where we have ``active'' regions of the
base data. Very often, the analyst is interested in only a portion of the entire
data. For example, he might only be interested in data for the current
year. Similar situation exists for an analyst in Wisconsin who might
only be interested in data for Wisconsin. This can be modeled
 by generating queries which have an implicit dimension for group-by and an
implicit selection on that dimension. For example, when analyzing data
for the current year, there is an implicit group-by on $Time$
dimension, with the selection $Year=1999$. The selection condition
leads to data locality since all queries access only a portion of the
data. We characterize this locality in terms of the percentage of the
base data referred to by the queries. We experimented with data
localities ranging from 25\% (high locality) to 100\% (no locality --
all data important).
}
\CrunchParaSpace
\subsubsection{Replacement Policies}
\CrunchParaSpace
This experiment was designed to compare the  ``two level policy''
described in Section~\ref{rep-policy} with the plain benefit based
policy. The plain benefit based policy does not classify chunks into
two types. Also, no attempt is made to identify groups of chunks. 
\comment {We experimented with data locality of
25 \%, 50\% and 100\%.} Figure~\ref{rep-hitratio-100}
\comment{,~\ref{rep-hitratio-50} and~\ref{rep-hitratio-25}} plots the percentage
of queries which  
are complete hits in the cache for different cache sizes. By complete hits we
mean queries which are completely answered from the cache, either directly or by
aggregating other chunks. The average query execution times are plotted in 
Figure~\ref{rep-times-100} \comment{,~\ref{rep-times-50}
and~\ref{rep-times-25}} . As the cache size 
increases, the percentage of 
complete hits increases. There are two reasons: the cache can be
pre-loaded with a larger group-by 
(so more queries can be answered by aggregating
) and just more chunks are cached leading to better hit ratio in general.
The results show that the ``two level policy'' performs better because
it has a better complete hit ratio. Also, 
for queries which are not complete hits, a larger 
portion of the results are found in the cache
leading to a smaller query being issued to the backend. This translates 
into improved average response time. For example, consider the case
when the 
cache is large enough (25 MB) to hold the entire base table. The ``two level
policy'' caches the the entire base table, leading to 100\% complete
hit ratio. The ratio is lower for the other case (since it throws away
useful base chunks in favor of computed chunks), causing it to go to the
backend for some queries. \comment{ This effect is observed earlier when there
is a data locality of 50\% since only 50\% of the data is accessed and
a cache size of 15 MB is enough to hold all the hot base data
chunks. For the case of 25\% locality, a cache size of 10 MB holds all
the relevant base data chunks leading to 100\% complete hit ratio.
}
\begin{figure}	
\parbox[t]{3in}
{
\centerline{\psfig{file=graphs2/rep-hits.ps,height=2.0in}}
\caption{ Complete hit ratios. \comment{Data locality 100\%.} \label{rep-hitratio-100}}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
\centerline{\psfig{file=graphs2/rep-times.ps,height=2.0in}}
\caption{ Average execution times. \comment{Data locality 100\%.}\label{rep-times-100}}
}
  \vspace{-0.1in}
\end{figure}

\comment {
\begin{figure}	
\parbox[t]{3in}
{
%\centerline{\psfig{file=graphs2/rep-hits.ps,height=2.5in}}
\caption{ Complete hit ratios. Data locality 50\%.\label{rep-hitratio-50}}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
%\centerline{\psfig{file=graphs2/rep-times.ps,height=2.5in}}
\caption{ Average execution times. Data locality 50\%.\label{rep-times-50}}
}
  \vspace{-0.1in}
\end{figure}

\begin{figure}	
\parbox[t]{3in}
{
%\centerline{\psfig{file=graphs2/rep-hits.ps,height=2.5in}}
\caption{ Complete hit ratios. Data locality 25\%.\label{rep-hitratio-25}}
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
%\centerline{\psfig{file=graphs2/rep-times.ps,height=2.5in}}
\caption{ Average execution times. Data locality 25\%.\label{rep-times-25}}
}
  \vspace{-0.1in}
\end{figure}
}
\CrunchParaSpace
\subsubsection{Comparison of Different Schemes}
\CrunchParaSpace
In this experiment, we compared the different approaches to caching: no
aggregation, exhaustive search based methods and virtual count based methods.
Experiments in Section~\ref{UnitExpts} showed that the lookup times for ESMC
are unreasonable. Also, the lookup and update costs of VCMC are comparable to
that of VCM. So we consider only ESM and VCMC. The case with no aggregations in
the cache is considered to demonstrate the benefit of having an active cache.
Fig~\ref{Comp-Times} shows the average execution times for running the query
stream described earlier.\comment{ with a data locality of 100\%. }The ``two
level policy'' was used for replacement for the ESM and VCMC
methods. However, for the no aggregation case, the simple benefit
based policy was used since  
detail chunks don't have any higher benefit in the absence of
aggregation. Both ESM and VCMC outperform the no aggregation case by a huge
margin. This is expected, since, without aggregation, the number of cache
misses are large. In fact only 31 out of the 100 queries are complete hits in
the cache. For ESM and VCMC, the number of complete hits are much more. \comment{They
are same as that shown in Figure~\ref{rep-hitratio}.} 

VCMC outperforms ESM, with the difference being more for lower cache 
sizes. It might seem that the difference is
not large. However, this is because of the fact that we are plotting the
average execution times over all the queries. The queries which have to go the
backend take disproportionately larger time and that affects the
average.  The
difference between VCMC and ESM is more pronounced for queries which are
complete hits. 
When the query stream has lot of locality we can expect to get many complete
hits. So speeding up complete hit queries is critical for increased system
throughput. Table~\ref{speedup-table} shows the percentage of queries that
are complete hits and the speedup factor for these queries. 

To further analyze the speedup, Figure~\ref{Split-Times} shows the
average execution times for queries 
that hit completely in the cache. We
split the total cost for each query into three parts: cache lookup time,
aggregation time and update time (to add the newly computed chunks). The bars
on the left are for the ESM method and those on the right are for VCMC method.
Even though it seems that the execution times are increasing for larger caches,
note that the times cannot be compared across different cache sizes. This is
because the set of queries which are complete hits is different for different
cache sizes.
At lower cache
sizes, the speedup is more. This is because for smaller caches, the cache
cannot hold a lot of chunks. So ESM has to spend a lot 
of time in finding a
successful path of computation. This is reflected in very high lookup times.
There is also a difference in the aggregation costs for ESM and VCMC, since
VCMC considers costs to find the best path of computation. As the cache size is
increased, the lookup time for ESM reduces, since there are more successful
paths. In fact, for a cache size of 25 MB, the entire base table fits in memory
and the first path it searches is a successful path. So the find time becomes
negligible. The performance difference is now only due to the difference in the
aggregation cost. We can also observe that the update times for VCMC method are
very small. The update times, for a cache size of 25 MB, are slightly higher
since it holds all the base level chunks. Whenever a new aggregated
chunk is added or removed, it changes the costs of computation for its descendent chunks 
and these costs have to be updated. The find times for VCMC are negligible.

\begin{figure*}	
\parbox[t]{3in}
{
\centerline{\psfig{file=graphs2/comp-times.ps,height=2.0in}}
%\label{Comp-Times}
\caption{Comparison of ESM and VCMC with No aggregation \label{Comp-Times} }
}
\makebox[0.5in]{}
\parbox[t]{3in}
{
\centerline{\psfig{file=graphs2/split-times.ps,height=2.0in}}
%\label{Split-Times}
\caption{Comparison of ESM and VCMC for queries which are complete
hits. The bars to the left are for ESM and those on the right are for
VCMC. \label{Split-Times}}
}
  \vspace{-0.1in}
\end{figure*}
\begin{table}
\centerline{
\begin{tabular}{|c|c|c|}
\hline
Cache Size (MB) & \% of Complete Hits & Speedup factor (VCMC over ESM) \\
\hline
\comment{
10 & 53 & 8.84 \\
15 & 61 &  2.33\\
20 & 66 & 2.19 \\
25 & 100 &  1.11 \\
}
10 & 66 & 5.8 \\
15 & 74 &  4.11\\
20 & 77 & 3.17 \\
25 & 100 &  1.11 \\
\hline
\end{tabular}
}
\caption{Speedup of VCMC over ESM.}
\vspace{-1em}
\label{speedup-table}
\end{table}

\CrunchParaSpace
\subsection{Results}
\CrunchParaSpace
Our experiments have shown that aggregation in the cache is a good
idea and leads to a dramatic improvement in performance over the no
aggregation case. The ``two-level'' policy works better than the simple
benefit policy since it maintains useful groups of chunks and reduces
accesses to backend. VCMC always performs better than ESM. When the
cache size is small compared to the base (or ``active'' data
size), the win of VCMC over ESM is more. A large part of this gain is
due to savings in the find time and a smaller one due to aggregation
time. 
When the cache is big enough to hold all base data and some more
aggregated chunks, the gain in the find time is lost (since the first
path
chosen by ESM is successful). The improvement is now only due to the
aggregation cost. Even though we have shown that the potential savings
in aggregation
cost could be high (by our unit experiments), it turns out that on average
over
all the group-bys and for the queries we generated the savings in
aggregation cost is not that high. So, in this case, we have a choice
of using either ESM or VCMC depending on the locality in the query
stream and the implementation effort one is willing to put in.
Even though the methods we have proposed seem specific to the chunk
based caching scheme, similar problems arise when using other
fine-grained caching schemes also.

\CrunchParaSpace
\section{Conclusions}
\label{conclusions}
\CrunchParaSpace
Providing a cache with the ``active'' capability of computing
aggregates from cached data allows the cache to satisfy queries that
would otherwise result in cache misses.  Results from our
implementation show that this can yield a substantial performance
improvement over traditional caching strategies.  Providing this
improvement required the development of fast mechanisms for
determining when a query can be computed from the cache. Also,
given that a query can in fact be computed from the cache, fast
mechanisms are required for determining the optimal aggregation path given the
current state of the cache and the current query.  

The area of active caching opens up a lot of opportunities for future
work.  One direction for such work would be to investigate the
efficacy of such active caching approaches in workloads more general
than those typically encountered in OLAP applications.  Our solution
in this paper takes advantage of the clean hierarchical structure of
multidimensional data models and queries; it may be a challenging task
to develop similar techniques for less structured workloads.

There are also many interesting open issues for active caching for
multidimensional workloads.  One of the most interesting is that of
cache replacement policies, since the utility of a piece of
information in a cache now varies dramatically depending upon (a)
where it is in the hierarchy, and (b) what other pieces of
information are currently in the cache.  

As we travel further down the path toward active caches, at some point
the cache itself begins to resemble a database system, with its own
query processor and optimizer.  There are interesting tradeoffs to be
made here.  For example, the more complex the active cache becomes,
the higher the overhead it is likely to impose.  Replacing a cache
with a middle tier DBMS is likely to give rise to the need for yet
another cache to speed up access to this middle tier DBMS, which begs
the question once again of how complex that cache should be!  Ignoring
the issue of overhead, another difference between a middle tier DBMS
and an active cache is that the cache contains a workload-sensitive
dynamically varying subset of the data set being accessed.  This can
be a significant benefit, allowing, for example, a hot segment of
detailed data to be cached in the middle tier even when the entire
detailed data set is far too large to be loaded into the middle tier.



\begin{thebibliography}{10}

\bibitem[AAD+96]{Prasad} S. Agarwal, R. Agrawal, P.M. Deshpande,
A. Gupta, J.F. Naughton, R. Ramakrishnan, S. Sarawagi.
On the Computation of Multidimensional Aggregates,
{\em Proc. of the 22nd Int. VLDB Conf.}, 506--521, 1996.

\bibitem[APB]{apb} The Analytical Processing Benchmark available at
{\em \mbox{http://www.olapcouncil.org/research/bmarkly.htm}}

\bibitem[APB-BENCH]{apb-bench}
APB benchmark performance results available at {\em
\mbox{http://www.oracle.com/olap/html/bnchmark.html},
\mbox{http://www.hyperion.com/unix\_bench.cfm}}. 

\bibitem[BPT97]{italy} E. Baralis, S. Paraboschi, E. Teniente.
Materialized View Selection in a Multidimensional Database,
{\em Proc. of the 23rd Int. VLDB Conf.}, 1997.

\bibitem[DFJST]{dfjst96}
S. Dar, M. J. Franklin, B. T. Jonsson, D. Srivastava, M. Tan.
\newblock Semantic Data Caching and Replacement,
\newblock {\em Proc. of the 22nd Int. VLDB Conf.}, 1996.

\bibitem[DRSN98]{drsn98}
P. M. Deshpande, K. Ramasamy, A. Shukla, J. F. Naughton.
\newblock Caching Multidimensional Queries Using Chunks,
\newblock {\em Proc of ACM SIGMOD Int. Conf. on Mgmt. of Data},
259--270, 1998.

\bibitem[GBLP96]{gray} J. Gray, A. Bosworth, A. Layman, H. Pirahesh.
Data Cube: A Relational Aggregation Operator Generalizing Group-By,
Cross-Tab, and Sub-Totals, {\em Proc. of the 12th Int. Conf. on Data Engg.},
pp 152-159, 1996.

\bibitem[GHRU97]{ghru97:cube} H. Gupta, V. Harinarayan, A. Rajaraman, 
J.D. Ullman. Index Selection for OLAP, {\em Proc. of the 13th ICDE},
208--219, 1997.

\bibitem[G97]{gupt97} H. Gupta. Selection of Views to Materialize in
a Data Warehouse, {\em Proc. of the Sixth ICDT}, 98--112, 1997.

\bibitem[HRU96]{hru96:cube} V. Harinarayanan, A. Rajaraman, J.D. Ullman.
Implementing Data Cubes Efficiently,
{\em Proc. ACM SIGMOD Int. Conf. on Management of Data}, 205--227, 1996.

\bibitem[KR98]{kotidis} Y. Kotidis, N. Roussopoulos.
An Alternative Storage Organization for ROLAP Aggregate Views Based on
Cubetrees,
{\em Proc. ACM SIGMOD Int. Conf. on Management of Data}, 249--258, 1998.

\bibitem[RKR97]{cubetree} N. Roussopoulos, Y. Kotidis, M. Roussopoulos.
Cubetree: Organization of and Bulk Updates on the Data Cube,
{\em Proc. ACM SIGMOD Int. Conf. on Management of Data}, 89--99, 1997.

\bibitem[RK96]{kimball} R. Kimball. {\em The Data Warehouse Toolkit},
John Wiley \& Sons, 1996.

\bibitem[RSC98]{ross:multicube} K. A. Ross, D. Srivastava, D. Chatziantoniou.
Complex Aggregation at Multiple Granularities,
{\em Int. Conf. on Extending Database Technology}, 263-277, 1998.

\bibitem[RS97]{ross:cube} K. A. Ross, D. Srivastava.
Fast Computation of Sparse Datacubes,
{\em Proc. of the 23rd Intl. VLDB Conf.}, 116-125, 1997.

\bibitem[SDJL96]{sdjl96:views}
D. Srivastava, S. Dar, H. V. Jagadish and A. Y. Levy.
\newblock Answering Queries with Aggregation Using Views,
\newblock {\em Proc. of the 22nd Int. VLDB Conf.}, 1996.

\bibitem[SDNR96]{sdnr96} A. Shukla, P.M. Deshpande, J.F. Naughton.
K. Ramasamy, Storage Estimation for Multidimensional Aggregates in
the Presence of Hierarchies, {\em Proc. of the 22nd Int. VLDB Conf.},
522--531, 1996.

\bibitem[SDN98]{sdn98} A. Shukla, P.M. Deshpande, J.F. Naughton.
Materialized View Selection for Multidimensional Datasets,
{\em Proc. of the 24th Int. VLDB Conf.}, 488--499, 1998.

\bibitem[SLCJ98]{slcj98} J. R. Smith, C. Li, V. Castelli, A. Jhingran.
Dynamic Assembly of Views in Data Cubes,
{\em Proc. of the 17th Sym. on PODS}, 274--283, 1998.

\bibitem[SSV]{ssv}
P. Scheuermann, J. Shim and R. Vingralek.
\newblock WATCHMAN : A Data Warehouse Intelligent Cache Manager,
\newblock {\em Proc. of the 22nd Int. VLDB Conf.}, 1996.

\bibitem[SS94]{ss94:mdarray}
S. Sarawagi and M. Stonebraker.
\newblock Efficient Organization of Large Multidimensional Arrays,
\newblock {\em Proc. of the 11th Int. Conf. on Data Engg.}, 1994.

\bibitem[TM1]{tm1-ref}
TM1 technology papers available at {\em 
\mbox{http://www.applix.com/tm1/tm\_tech.html},
\mbox{http://www.applix.com/tm1/rescentr/tm1wppr.htm}}.

\bibitem[U96]{ullman-survey} J.D. Ullman. 
Efficient Implementation of Data Cubes Via Materialized Views,
{\em The 2nd Int. Conf. on Knowledge Discovery and Data Mining}, 386--388,
1996. 

\bibitem[ZDN97]{zhao} Y. Zhao, P.M. Deshpande, J.F. Naughton.
An Array--Based Algorithm for Simultaneous Multidimensional Aggregates,
{\em Proc. ACM SIGMOD Int. Conf. on Management of Data}, 159--170, 1997.

\end{thebibliography}

\end{document}

   

