Multidimensional access methods are considered to be a promising approach for providing acceptable performance to analysis-centric applications. However,despite the large body of research work in this field,the commercial support for multidimensional indexes is still very weak. The reason for this discrepancy is threefold: first, no standard multidimensional index like the B-Tree for one-dimensional data has emerged so far. Second, integrating a new access method into a database system kernel is usually a complex and expensive task. Third,current query optimizers still have problems in dealing with multidimensional data making it difficult to use multidimensional indexes efficiently. In this thesis, we address the above mentioned deficiencies and promote the universal B-Tree (UB-Tree)as a premier candidate for a general-purpose, multidimensional index. In an extensive theoretical and experimental comparison with R*-Trees we show that the UB-Tree can compete with other approaches in multidimensional indexing. The UB-Tree outperforms the R*-Tree not only w.r.to query performance but also considering the important properties of maintenance performance, index size and others. Addressing the kernel integration, we reveal another big advantage of UB-Trees: relying on the standard B-Tree as underlying structure the integration effort is reduced significantly. We further present optimizations of the basic algorithms, like the reduction of post-filtering for range query processing. To improve the support of query optimizers for multidimensional access methods, we propose a new type of multidimensional histograms based on UB-Tree concepts. At the same time, we point out general limitations of multidimensional synopses. Finally, we introduce the concept of weighted dimensions, which allows for tuning of the UB-Tree to application specific preferences among the dimensions. This makes the UB-Tree viable to a broader range of applications. The concept also leads to an improved range query processing for standard composite key indexes.     «

Multidimensional access methods are considered to be a promising approach for providing acceptable performance to analysis-centric applications. However,despite the large body of research work in this field,the commercial support for multidimensional indexes is still very weak. The reason for this discrepancy is threefold: first, no standard multidimensional index like the B-Tree for one-dimensional data has emerged so far. Second, integrating a new access method into a database system kernel is...     »

Mehrdimensionale Indexstrukturen gelten als vielversprechende Möglichkeit um akzeptierbare Performanz für analyse-orientierte Anwendungen zu erzielen. Trotz einer Vielzahl von vorgeschlagenen Datenstrukturen werden mehrdimensionale Indexe jedoch kaum in Datenbanksystemen eingesetzt. Dafür gibt es mehrere Gründe: zum ersten hat sich noch kein Standard, wie der B-Baum für ein-dimensionale Daten, für mehrdimensionale Indexierung herauskristallisiert. Zweitens, ist die Integration einer Indexstruktur in den Kern eines Datenbanksystems eine komplexe und damit kostenintensive Aufgabe. Drittens, haben heutige Anfrageoptimierer immer noch Probleme die Kosten für Anfragen auf mehrdimensionalen Daten abzuschätzen. In dieser Arbeit stellen wir den universellen B-Baum (UB-Baum) als einen Index vor der die genannten Nachteile überwindet und somit ein hervorragender Kandidat für einen universellen, mehrdimensionalen Index darstellt. In einem ausgiebigen theoretischen und praktischen Vergleich mit R*-Bäumen zeigen wir zum einen, dass der UB-Baum mit anderen mehrdimensionalen Zugriffsstrukturen konkurieren kann. Der UB-Baum ist nicht nur in Bezug auf die Anfrageperformanz besser als der R*-Baum, er schneidet auch bei den wichtigen Aspekten der Wartungsperformanz, Indexgrösse, u.a. besser ab. Die Diskussion der Integration des UB-Baums in den Datenbankkern macht einen weiteren Vorteil des UB-Baums deutlich: da er auf dem bekannten B-Baum beruht ist der Integrationsaufwand deutlich reduziert. Wir stellen verschiedene Optimierungen der grundlegenden Algorithmen, bspw. Reduzierung der Nachfilterung in der Bereichsanfrageverarbeitung, vor. Für die bessere Unterstützung von mehrdimensionalen Indexen durch die Anfrageoptimierung schlagen wir ein neues mehrdimensionales Histogramm, basierend auf UB-Baum Konzepten, vor und zeigen auch die Grenzen mehrdimensionaler Histogramme auf. Abschliessend führen wir das Konzept der gewichteten Dimensionen ein, das erlaubt den UB-Baum für anwendungsspezifische Preferenzen unter den Dimensionen zu optimieren. Dadurch ist der UB-Baum in einem größeren Bereich effizient anwendbar. Dieses Konzept liefert auch einen verbesserten Bereichsanfragealgorithmus für B-Bäume mit zusammengesetzten Schlüsseln.     «

Mehrdimensionale Indexstrukturen gelten als vielversprechende Möglichkeit um akzeptierbare Performanz für analyse-orientierte Anwendungen zu erzielen. Trotz einer Vielzahl von vorgeschlagenen Datenstrukturen werden mehrdimensionale Indexe jedoch kaum in Datenbanksystemen eingesetzt. Dafür gibt es mehrere Gründe: zum ersten hat sich noch kein Standard, wie der B-Baum für ein-dimensionale Daten, für mehrdimensionale Indexierung herauskristallisiert. Zweitens, ist die Integration einer Indexstruktu...     »