MISTRAL: Processing relational queries using a multidimensional acces technique (Diss., TU München) (Q2726358)

Preface: Classical one-dimensional B-trees have been the standard access method of all commercial database systems for many years. This dissertation is a very promising effort to introduce Universal B-trees (UB-trees), the multidimensional variant of B-trees, as a basic access method into the core of fundamental DB-technology. The universal relevance of UB-trees is a consequence of the fact, that every relation can be considered as a set of points in multidimensional space. UB-trees organize this space for efficient processing of the data, resulting for many types of queries in orders of magnitude improvement over classical methods.NEWLINENEWLINENEWLINEThe thesis lays the theoretical foundations of UB-tress, predicts their performance by analytical models and validates these models by experiments using large real world databases and real life applications and queries from the field of datawarehousing. The need to sort data and intermediate results frequently is an annoying drawback of today's query processing methods. In combination with the Tetris algorithm UB-trees allow to avoid sorting in most cases, leading to dramatic improvements of response time, storage requirement and overall query processing time.NEWLINENEWLINENEWLINEAdding a new access method requires to consider all aspects of database systems: architecture of subsystems, query optimization, query processing, multiuser operation and synchronization, bulk loading, storage requirement, parallelism, etc.NEWLINENEWLINENEWLINESince UB-trees rely on classical B-trees for their implementation, all of these issues can be solved in a satisfactory way and can be dealt with elegantly.NEWLINENEWLINENEWLINEThe performance experiments reported in this thesis were carried out with an implementation of UB-trees as a middleware layer on top of SQL. Additional performance improvements can be gained by integrating the UB-tree technology in the kernel of database systems.NEWLINENEWLINENEWLINEThis thesis is a cornerstone of the MISTRAL project. MISTRAL has the goal to introduce UB-trees as a new access method into database systems with the fascinating vision, to extend fundamental database technology in an essential way. MISTRAL is financially supported by SAP, Teijin, NEC, Hitachi, the European Commission, Project MDA, TAS, Gfk and Microsoft.