Efficient star query processing is crucial for a performant data warehouse (DW) implementation and much work is available on physical optimization (e.g., indexing and schema design) and logical optimization (e.g., pre-aggregated materialized views with query rewriting). One important step in the query processing phase is, however, still a bottleneck: the residual join of results from the fact table with the dimension tables in combination with grouping and aggregation. This phase typically consumes between 50% and 80% of the overall processing time. In typical DW scenarios pre-grouping methods only have a limited effect as the grouping is usually specified on the hierarchy levels of the dimension tables and not on the fact table itself. We suggest a combination of hierarchical clustering and pre-grouping as we have implemented in the relational DBMS Transbase. Exploiting hierarchy semantics for the pre-grouping of fact table result tuples is several times faster than conventional query processing. The reason for this is that hierarchical pre-grouping reduces the number of join operations significantly. With this method even queries covering a large part of the fact table can be executed within a time span acceptable for interactive query processing.

Advanced data warehouses and Web databases have set the demand for processing large sets of time ranges, quality classes, fuzzy data, personalized data and extended objects. Since, all of these data types can be mapped to intervals, interval indexing can dramatically speed up or even be an enabling technology for these new applications. We introduce a method for managing intervals by indexing the dual space with the UB-Tree. We show that our method is an effective and efficient solution, benefitting from all good characteristics of the UB-Tree, i.e., concurrency control, worst case guarantees for insertion, deletion and update as well as efficient query processing. Our technique can easily be integrated into an RDBMS engine providing the UB-Tree as access method. We also show that our technique is superior and more flexible to previously suggested techniques.

Online analytical processing (OLAP) requires query response times within the range of a few seconds in order to allow for interactive drilling, slicing, or dicing through an OLAP cube. While small OLAP applications use multidimensional database systems, large OLAP applications like the SAP BW rely on relational (ROLAP) databases for efficient data storage and retrieval. ROLAP databases use specialized data models like star or snowflake schemata for data storage and create a large set of indexes or materialized views in order to answer queries efficiently. In our case study, we show the performance benefits of TransBase HyperCube, a commercial RDBMS, whose kernel fully integrates the UB-Tree, a multi-dimensional extension of the B-Tree. With this newly developed access structure, TransBase HyperCube enables interactive OLAP without the need for storing a large set of materialized views or creating a large set of indexes. We compare not only the query performance, but also consider index size and maintenance costs. For the case study we use a 42 million record ROLAP database of GfK, the largest German market research company.

Bulk loading is used to efficiently build a table or access structure if a large data set is available at index time, e.g., the spool process of a data warehouse or the creation of intermediate results during query processing. The authors introduce the TempTris algorithm that creates a multidimensional partitioning from a one-dimensionally sorted stream of tuples. In order to achieve that, TempTris exploits the fact that a one-dimensional order can be used as a partial multidimensional order for the creation of a multidimensional partitioning. In this way, TempTris avoids external sorting for the creation of a multidimensional index. In combination with the Tetris sort algorithm, TempTris can be used to create intermediate query processing results that can (without external sorting), be reused to generate various sort orders. As an example of this new processing technique we propose an efficient algorithm for computing an aggregation lattice. Thus, TempTris can also be used to speed up the processing of CUBE operators that frequently occur in OLAP applications.

We consider the issue of bulk loading large data sets for the UB-Tree, a multidimensional index structure. Especially in data warehousing (DW), data mining and OLAP it is necessary to have efficient bulk loading techniques, because loading occurs not continuously, but only from time to time with usually large data sets. We propose two techniques, one for initial loading, which creates a new UB-Tree, and one for incremental loading, which adds data to an existing UB-Tree. Both techniques try to minimize I/O and CPU cost. Measurements with artificial data and data of a commercial data warehouse demonstrate that our algorithms are efficient and able to handle large data sets. As well as the UB-Tree, they are easily integrated into a RDBMS.

Most of the operations of the relational algebra or of SQL (such as projection with duplicate elimination, joins, ordering, group-by and aggregations) are efficiently processed using a sorted stream of tuples. Often, these operations are combined with restrictions in one or several attributes. Previous research has proposed algorithms for efficiently dealing with this kind of query pattern, which is highly relevant with respect to data warehousing, data mining and GIS (geographic information systems). In this paper, we present a cost model that enables a concise estimation of both memory costs and run-time costs for processing queries with restrictions in multiple attributes that may in addition involve a sort operation. Our cost model considers uniformly distributed UB-trees (universal B-trees) with independent dimensions, and it is derived analytically in three steps, starting with a very simple, perfectly idealized partitioning scheme, moving on to imperfect partitioning schemes, and finally evaluating a probabilistically partitioned UB-tree. We also reason to what extent our cost model might be taken into account if the data is not distributed uniformly, by investigating the connection between the cost model and selectivities.

Most operations of the relational algebra or SQL require a sorted stream of tuples for efficient processing. Therefore, processing complex relational queries relies on efficient access to a table in some sort order. In principle, indexes could be used, but they are superior to a full table scan only if the result set is sufficiently restricted in the index attribute. We present the Tetris algorithm, which utilizes restrictions to process a table in sort order of any attribute without the need for external sorting. The algorithm relies on the space partitioning of a multidimensional access method. A sweep line technique is used to read data in sort order of any attribute, while accessing each disk page of a table only once. Results are produced earlier than with traditional sorting techniques allowing better response times for interactive applications and pipelined processing of the result set. We describe a prototype implementation of the Tetris algorithm using UB-Trees on top of Oracle 8, define a cost model and present performance measurements for some queries of the TPC-D benchmark.

Data warehousing applications cope with enormous data sets in the range of Gigabytes and Terabytes. Queries usually either select a very small set of this data or perform aggregations on a fairly large data set. Materialized views storing pre-computed aggregates are used to efficiently process queries with aggregations. This approach increases resource requirements in disk space and slows down updates because of the view maintenance problem. Multidimensional hierarchical clustering (MHC) of OLAP data overcomes these problems while offering more flexibility for aggregation paths. Clustering is introduced as a way to speed up aggregation queries without additional storage cost for materialization. Performance and storage cost of our access method are investigated and compared to current query processing scenarios. In addition performance measurements on real world data for a typical star schema are presented.

Based on matured database technology the paper provides new insights into efficient ways to evaluate recursive deduction rules. We show how the forward-chaining approach to deduction can flexibly be married with goal-directed aspects of best/easiest-first strategies. From the natural fixpoint semantics of recursion we develop generally applicable differential iteration schemes that efficiently compute the fixpoint. Surprisingly the well-known Warshall-algorithm gets disclosed as a descendant of this class of algorithms. Performance measurements suggest the former as well as systolic Δ-algorithms with linear fixpoint equation as candidates for incorporating a transitive closure operator in databases. As a next important step towards integration of database technology and logic programming we suggest to profit from the standard features of concurrency control and transaction management by effectively using them for the synchronization of parallel deductions.

A synchronization technique and scheduling strategy is described, which allows us to run a batch process simultaneously with on-line transactions. The batch process and the transactions are serialized in such a way that consistency level 3 is achieved.

Performance in database systems is strongly influenced by buffer management and transaction recovery methods. This paper presents the principles of the database cache, which replaces the traditional buffer. In comparison to buffer management, cache management is more carefully coordinated with transaction management, and integrates transaction recovery. High throughput of small- and medium-sized transactions is achieved by fast commit processing and low database traffic. Very fast handling of transaction failures and short restart time after system failure are guaranteed in such an environment. Very long retrieval and update transactions are also supported.

In this paper a new method to increase parallelism in database systems is described. Use is made of the fact that for recovery reasons, we often have two values for one object in the database—the new one and the old one. Introduced and discussed in detail is a certain scheme by which readers and writers may work simultaneously on the same object. It is proved that transactions executed according to this scheme have the correct effect; i.e., consistency is preserved. Several variations of the basic scheme which are suitable depending on the degree of parallelism required, are described.

Two modifications of B -trees are described, simple prefix B -trees and prefix B -trees. Both store only parts of keys, namely prefixes, in the index part of a B * -tree. In simple prefix B -trees those prefixes are selected carefully to minimize their length. In prefix B -trees the prefixes need not be fully stored, but are reconstructed as the tree is searched. Prefix B -trees are designed to combine some of the advantages of B -trees, digital search trees, and key compression techniques while reducing the processing overhead of compression techniques.

The securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also threats to encipherment arising from updating and the file structure itself must be countered. A general encipherment scheme is proposed for files maintained in a paged structure in secondary storage. This is applied to the encipherment of indexes organized as B -trees; a B -tree is a particular type of multiway search tree. Threats to the encipherment of B -trees, especially relating to updating, are examined, and countermeasures are proposed for each. In addition, the effect of encipherment on file access and update, on paging mechanisms, and on files related to the enciphered index are discussed. Many of the concepts presented may be readily transferred to other forms of multiway index trees and to binary search trees.

The securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also must threats to encipherment arising from updating and the file structure itself be countered. A general encipherment scheme is proposed for files maintained in a paged structure on secondary storage. This is then applied to the encipherment of indexes organized as B-trees, a particular type of multiway search tree. Threats to the encipherment of B-trees, especially relating to updating, are examined, and counter-measures proposed for each. In addition, the effect of encipherment on file access and update, on paging mechanisms, and on files related to the enciphered index are discussed. Many of the concepts presented here may be readily transferred to other forms of multiway index trees and to binary search trees.