Introduction

The area of statistical analysis of empiric or business data has been boosted significantly in recent years by the concepts of data warehousing and online analytical processing (OLAP, See CoCS93 ). This paper focuses on the concepts of the experimental OLAP server CubeStar , which differs essentially in two aspects from commercial systems and research prototypes. First, the used multidimensional data model provides a more very flexible modeling of classification hierarchies resulting in an extended star schema on the relational side. Second, the system implements a dynamic and adaptive aggregate cache which allows much more efficient multidimensional query processing.

The structure of the paper is as follows: The next section gives a short introduction to the multidimensional data model and the query language. Section three outlines the fundamental ideas of the dynamic and partition-oriented aggregation cache. The fourth section explains the relational representation of the multidimensional structures and queries. The general architecture of CubeStar is outlined in section five. The last section illustrates the performance potential of the aggregate cache by some simulation results. The paper concludes with a summary and an outlook of the current research activities.

Data Model and Query Language

A structural deficiency of many multidimensional modeling approaches like See AgGS97 , See CaTo97 or See LiWa96 is the missing distinction of classifying and characterizing information. Consider the following SQL statement for the statistical table in figure 1 assuming a two-dimensional scenario:

SELECT Product_Family, Product_Brand,
Shop_Region, Shop_Type,
SUM(Sales)
FROM ...
WHERE Product_Group = `Video' AND
Shop_Country = `Germany'
GROUP BY Product_Family, Product_Brand,
Shop_Region, Shop_Type

Both the relational mapping and the multidimensional equivalent know only grouping attributes resulting in an actually four-dimensional output table, respectively data cube. However, like the prefixes of the attributes demonstrate, the example is about a two dimensional problem where Product_Family is a classification attribute ( CA ) in a hierarchical classification structure of the product dimension (figure 2). The attribute Brand however is not part of the classification but serves as a property attribute for an additional characterization of single items. These in turn - generally called dimensional elements - are instances of the primary attribute ( PA=CA0 ) of a dimension, which functionally determines all other attributes.

At the instance level, each class of dimensional elements inherits some property attributes from its parent class where others are specific to that node ( See SmSm77 ). For example, only Video products show a property attribute VideoSystem . A property VideoSystem for the product group Washers , which is also element of the product dimension, would result in a structural schema defect ( See LeAW98 ). Other multidimensional data models are not able to express this fact. The modeling paradigm of CubeStar distinguishes between classification attributes (figure 2, upper part) and property attributes (figure 2, lower part). The classification hierarchy defines the overall framework for the analysis, specific property attributes are used for detailed evaluations.

Processing Multidimensional Aggregates

In the application domain of OLAP/data warehousing an adequate and very common optimization method is the use of summary tables thus pre-aggregating the enormous quantity of data. One way to do so, is the a-priori-approach, where aggregates are precalculated for all possible aggregation levels, so that queries may easily be answered during run-time through a simple lookup operation. Some commercial products use this strategy ( See Cogn98 , See Hype98 ). However, since the number of possible aggregates grows exponentially with the number of grouping attributes, this method is not feasible in application scenarios where there are 20 or more property attributes describing a product or a customer.

The only alternative is to select some of the most beneficial aggregates for materialization. Some queries then may be derived from the aggregates where others need to access the raw data. The problem is to select those aggregates which give the highest overall speed-up by allocating the least amount of disk space. Based on the relational data model See Gupt97 and See YaKL97 proposed algorithms to select views in a data warehouse. Of fundamental importance in the multidimensional context was the work See HaRU96 where a greedy algorithm based on an aggregation lattice was presented. The work was later extended by See GHRU97 and See BaPT97 .

The fundamental lack of this technique is the missing support of analysis hot spots. The algorithm only investigates aggregates at different granularities but does not include the scope. For example it is not possible to pre-aggregate only the sales for the actual month; each aggregate contains data for all months.

Another central criticism of this method is that it does not adapt to the dynamics of the interactive query behavior ( See ThSe97 ). The selected set of aggregates is statically materialized after each data warehouse refresh and does not adapt the actual query set during the analysis phase. In order to overcome this problem, See ScSV96 presented a rather restrictive data warehouse cache based on the relational data model. Recently, See DRSN98 implemented a more flexible caching method for partitions of multidimensional aggregates. They address the same problem as the CubeStar approach. In contrast to CubeStar , their solution is based on aggregate partitions of a fixed size, like buffer pages.

The strategy of CubeStar is to store precalculated queries for reuse in an aggregate cache. The typical draw back of query caching is that a new query must be contained in the old one in order to utilize it. In CubeStar a patch working algorithm is used to combine cached multidimensional objects. The result of this algorithm in combination with a sophisticated cache strategy are substantial performance gains even for very small cache sizes ( See Experimental Results ). For a detailed description of the algorithms see See LeAl99 .

Relational Mapping of Multidimensional Structures

Of fundamental importance for the structured and efficient relational processing of multidimensional operators is a suitable relational representation of multidimensional objects. Today, most relational data warehouses are based on the star schema ( See Sample Star Schema ), where the data cube containing the measures is represented by a central fact table. Its primary key is a composition of foreign keys to the according dimension tables. The dimension tables contain - in a denormalized fashion - the classification structures as well as the property attributes for each dimension.

The use of a single dimension table for each dimension turns out to be problematic in the context of class-specific property attributes since different classes, like Camcorder and Washers , have also different schemata with regard to their properties (e.g. attributes VideoSystem and MaxLoad ). In order to cope with these problems, the global dimension tables of the traditional star schema are replaced (basically partitioned) by class-specific dimension tables (scope tables), each of which having a possibly different schema.

The following example illustrates this method for the product dimension. Foundation for the hierarchy are the base classes, i.e. the classes of the lowest level in the hierarchy like Camcorder and HomeVCR , with their specific property schemata:

Products_Camcorder ( ArticleId, Brand, VideoSystem, AccuType)
TR-75 Sony HI8 Li
TS-78 Sony HI8 NiCd
A200 JVC N8 NiCd

Products_HomeVCR  ( ArticleId, Brand, VideoSystem, RemoteControl)
V-201 JVC VHS Yes
ClassicI Grundig VHS-C No

All classes at higher levels are then recursively defined as views to the lower classes. The names of the child classes as well as all common attributes are propagated to the parent. For the product group Video the resulting scope table (view) is defined as follows:

create view Products_Video (ArticleId, Brand, VideoSystem, Family) as
select ArticleId, Brand, VideoSystem, ` Camcorder '
from Products_Camcorder
union all
select ArticleId, Brand, VideoSystem, ` HomeVCR '
from Products_HomeVCR

Products_Video    ( ArticleId, Brand, VideoSystem, Family)
TR-75 Sony HI8 Camcorder
TS-78 Sony HI8 Camcorder
A200 JVC N8 Camcorder
V-201 JVC VHS HomeVCR
ClassicI Grundig VHS-C HomeVCR

Hence, the information for each class node of a dimension is stored in a class-specific relation or view, containing all dimensional elements below that class node with information about their parents in the classification hierarchy and the subset of property attributes visible at that node ( See LeTW97 ).

This construction has a positive side effect. Since the scope of a MO is defined by a classification node ( See Multidimensional Objects ) which is represented by a specific scope table, the SQL queries for the computation of a multidimensional object do not need any restrictions beside the join conditions. The following example illustrates this approach. Suppose for the computation of the multidimensional object M from section 2, the patch worker picks up the following aggregates from the cache:

M 1 = ( [ Sales, FLOW, NONE ],
(Products.Group = `Video', Shops.Country = `Germany'),
[ (Products.ArticleId, Shops.ShopId), {} ] ) // raw data

M 2 = ( [ Sales, FLOW, SUM ],
(Products.Group = `Video', Shops.Region = `South'),
[ (Products.Family, Shops.State), { Brand, ShopType} ] )

M 3 = ( [ Sales, FLOW, SUM ],
(Products.Family = `Camcorder', Shops.Country = `Germany'),
[ (Produkte.Family, Shops.Region), { Brand , VideoSystem , ShopType } ] )

In order to compose M based on these MOs CubeStar generates the following SQL query:

CREATE TABLE M AS
SELECT Family, Region, Brand, ShopType, SUM(Sales) AS Sales
FROM M 1, Products_HomeVCR P, Shops_North S
WHERE M 1.ArticleId = P.ArticleId AND M 1.ShopId = S.ShopId
GROUP BY Family, Region, Brand, ShopType
UNION ALL
SELECT Family, Region, Brand, ShopType, SUM(Sales) AS Sales
FROM M 2,
(SELECT DISTINCT(State, Region) FROM Shops_Germany) S
WHERE M 2.State = S.State
GROUP BY Family, S.Region, Brand, ShopType
UNION ALL
SELECT Family, Region, Brand, ShopType, Sales
FROM M 3
WHERE Family = `HomeVCR'

The example clearly shows that in the context of multidimensional objects all restrictions are implicitly applied by joins with the according scope tables. The view mechanism selects with the scope tables Products_HomeVCR and Shops_North in the case of MO M 1 only those elements which are requested in the query avoiding to scan a possibly large dimension table (like customer). In the case of using the cached aggregate MO M 2 , the summary data must be further aggregated from the state to the regional level. Therefore, the according scope table containing only the State-Region relationships must be dynamically generated by a SELECT DISTINCT statement applied to scope table Shops_Germany . No aggregation is necessary for the MO M 3 , because its granularity is already at the requested level. Moreover no join with a scope table is needed, because the selection attribute corresponds to the group-by attribute.

The Architecture of CubeStar

Like typical ROLAP-systems, the CubeStar prototype is designed according to a three-tier-architecture. CubeStar consists of a client tier, the multidimensional Cube­Star server and a relational backend (figure 5).

All query processing and aggregate management is based on the data model introduced in See Multidimensional Objects , i.e. queries as well as aggregates are internally represented by multidimensional objects. The task of the CubeStar server is twofold: On the one hand, based on the patch-working algorithm a set of cached MOs to accelerate the execution of the query must be determined and reflected in an SQL statement. On the other hand, these MOs must be created and maintained by the server as well. Therefore, the CubeStar server itself has a three-layer architecture consisting of the query processor, the aggregate cache management and the partition directory service.

Another component which is used by all three layers is the classification information service. Basically, the classification information service is an API providing easy access to the dimensions and classification hierarchies. Calls to the classification directory request for example the children or properties of a certain class node or relationships between class nodes in the hierarchy.

The task of the multidimensional query optimizer is to find for each leaf of the tree of a set of physically existing MOs. All relevant informations about materialized multidimensional objects are stored and managed by the partition directory. Based on the decision of the patch-worker, in the first phase, an SQL query is generated and executed for each leaf of the query tree. The intermediate result, a newly materialized MO, is added to a temporary storage area. In a second phase, an SQL statement is generated recursively for the whole query tree in a bottom up manner. The intermediate results for inner nodes are not materialized, because the operators applied during the computation of a nested query may become very complex. Thus, the compatibility checks necessary to determine the reusability of such an aggregate are very complicated. The final result, however, is materialized and asynchronously delivered to the client.

After the complete computation of the query, each of the newly materialized MOs for the leaves is handed over to the aggregate cache. Based on the replacement strategy ( See The Replacement Strategy ) one or more cached MOs might be chosen for replacement. Depending on the outcome of the benefit computation, either the new multidimensional object or one of those in the cache might be deleted in order to satisfy the space constraint.

Experimental Results

In order to simulate a typical OLAP query behavior we implemented a query generator, which constructs a new query in modifying the previous one based on the decision path in See Query generation . Each alternative can be parametrized with a certain probability. Since it is very hard to get actual query statistics from real world OLAP applications, we experimented with different parametrizations and got very good results for most of the query sequences. For simplicity, all simulations in this chapter are based on query sequences generated with the annotated probabilities.

The scenario consists of three dimensions with a four-, five- and six-level hierarchy, respectively. Each class at the base level of the hierarchies had between 10 and 15 property attributes. With a sparsity of 3% the data cube consisted of approximately 250.000 tuples.

The relational database management system used for the physical storage of the multidimensional objects was Oracle Enterprise Server 8.0.4. on a DEC Alpha 3000/800 server (1 CPU, 192 MByte RAM). The average query execution time for queries which could not utilize the cache was between 10 and 20 seconds. Therefore, the time for multidimensional processing can be neglected.

The following figures show the cost saving ratio (CSR; See LeAl99 , See ScSV96 , See DRSN98 ), i.e. the relative savings resulting from accessing the cache instead of raw data, for a set of simulations. The values of the abscissa are determined by the step counter.

See Development of the cost saving ratio (CSR) for 1.000 simulated single user queries; Comparison of the the dynamic aggregate and static preaggregation compares the dynamic aggregate cache as explained in See Processing Multidimensional Aggregates to the static preaggregation strategy from See HaRU96 . The different graphs in each diagram show the cost saving ratio for a number of different cache sizes. With the dynamic caching method cost reductions of more than 50% are possible with a cache size of only 10.000 tuples ( See Development of the cost saving ratio (CSR) for 1.000 simulated single user queries; Comparison of the the dynamic aggregate and static preaggregation a). Note, that this is only about 4% of the fact table size, i.e. much less than a simple B-Tree index on the fact table would require. With a cache size of 25.000 tuples the speed up can be increased to about 60%. Adding more space does not yield any benefit, since there are always queries which can not be answered using the cache.

Summary and Conclusion

This article introduces the general concepts of the multidimensional OLAP server CubeStar . Both, the multidimensional data model and the dynamic management and composition of aggregates based on the patch-working algorithm are an extension of previously published work. It was demonstrated that an adaptive strategy for preaggregation in general yields much better results than static algorithms. It was shown that performance increases of up to 60% are possible with cache sizes of only 5-10% of the size of the fact table. Except for the patch working, no additional pre- or post-processing is necessary. The cache can be used in conjunction with other optimizations like indexes or also static aggregates. In order to make the results comparable to other systems we will adapt the data of the APB-1 Benchmark of the OLAP Council ( See OLAP98 ).

All components of the CubeStar server are completely implemented in Java. Current work is focussed on good parametrizations of the replacement strategy and an extension according to of the dynamic creation of index structures supporting access to multidimensional aggregates. This can be seen as the dynamic adaption of See GHRU97 . Other research activities involves the exploitation of parallelization and distribution ( See AlLe98 , See AlGL98 ). On the data modeling side we are currently exploring object relational techniques in order to reflect the classification structures, or classes, in a more natural manner.

References