Search

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). Organizing fact tables with clustering multidimensional access methods (like the UB-Tree) are a promising approach to speed up star queries. However, the implementation into commercial products has not been done so far, since in addition to the clustering index organization, many parts of a database management system must be extended. For example, the query optimizer with corresponding cost model modifications must support the new organization and various optimization topics. In this thesis, we present EHC, the Encoding for Hierarchical Clustering in combination with UB-Trees. EHC enables the use of clustering index structures also for hierarchical data. EHC is extended to MHC, the multidimensional hierarchical clustering by combining multiple dimensions. Based on the concept of MHC, we develop a number of query optimization algorithms, in order to support hierarchical clustering with query processing. For this purpose, we present a complete abstract processing plan that captures all necessary steps in evaluating star queries in these environments. 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 data warehouse 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. Therefore, we suggest a combination of hierarchical clustering and pre-grouping. Exploiting hierarchy semantics for the pre-grouping of fact table result tuples is several time, In dieser Doktorarbeit wird die Implementierung vom MHC (multidimensionales hierarchisches Clustering) in das relationale Datenbanksystem Transbase Hypercube beschrieben. MHC wird notwendig, wenn Data Warehouse-Daten in einem clusternden multidimensionalen Index gespeichert werden sollen. Multidimensionales hierarchisches Clustering ist eine Technologie, um hierarchische Prädikate auf Dimensionstabellen auf Intervalle abzubilden, die über den multidimensionalen Index (UB-Tree in Transbase) optimal verarbeitet werden können. Hierarchie-Pfade werden durch Surrogate (numerische Codierung) abgebildet und in der Faktentabelle gespeichert. Ausgehend von einer allgemeinen Betrachtung von Hierarchien und Data Warehouse-Schemata wird die Integration der Surrogats-Berechnung für MHC in den Datenbankkern beschrieben. Interessante Aspekte zeigen sich beim Query-Processing von sog. Star Join Queries, wo durch die Hierarchie-Codierung in der Faktentabelle bereits sehr früh hierarchische Eigenschaften ausgenutzt werden können. Dies beschleunigt die Gruppierung und den Residual-Join erheblich. Weiterhin werden Konzepte beschrieben, die für eine allgemeine Verwendbarkeit der Technologie nötig sind, z.B. Multi-Query-Boxen auf UB-Trees oder Behandlung von Data Warehouse-Dimensionen, die nicht im Schlüssel des UB-Trees sind. Die theoretischen Überlegungen werden durch Messungen an einem Realdaten-Bestand verifiziert.

The Access Manager framework provides modular extensibility to a standard database management system (DBMS). Therefore it opens an operational DBMS in selected areas, by introducing a concise interface to the DBMS’s internal components. The DBMS functions as a host system for accommodating application domain-specific plug-ins, such as access modules for alternative primary and secondary access methods, custom algorithmic units implementing auxiliary transformations, and a potent data integration layer. The proposed interface particularly emphasizes full participation of extension modules in the host system’s intrinsic query optimization process. A prototype of the Access Manager framework was integrated into the relational DBMS Transbase of Transaction Software GmbH., Das Access Manager Framework erlaubt die modulare Erweiterung eines herkömmlichen Datenbank Management Systems (DBMS). Zu diesem Zweck wird ein voll einsatzfähiges DBMS mittels einer kompakten Schnittstelle geöffnet, die Zugriff auf interne Komponenten des Systems gewährt. Das DBMS fungiert dabei als Wirtssystems für Erweiterungen in Form von alternativen primären oder sekundären Zugriffsmethoden, die durch entsprechende Algorithmen für relationale Transformationen ergänzt werden können, und einer mächtigen Integrationsschicht für Zugriff auf externe Daten. Dabei wird insbesondere eine tiefgreifende Einbeziehung solcher Erweiterungen in die Anfrageoptimierung des Wirtssystems gewährleistet. Ein Prototyp wurde in das relationale DBMS Transbase der Firma Transaction Software GmbH integriert.

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). Organizing fact tables with clustering multidimensional access methods (like the UB-Tree) are a promising approach to speed up star queries. However, the implementation into commercial products has not been done so far, since in addition to the clustering index organization, many parts of a database management system must be extended. For example, the query optimizer with corresponding cost model modifications must support the new organization and various optimization topics. In this thesis, we present EHC, the Encoding for Hierarchical Clustering in combination with UB-Trees. EHC enables the use of clustering index structures also for hierarchical data. EHC is extended to MHC, the multidimensional hierarchical clustering by combining multiple dimensions. Based on the concept of MHC, we develop a number of query optimization algorithms, in order to support hierarchical clustering with query processing. For this purpose, we present a complete abstract processing plan that captures all necessary steps in evaluating star queries in these environments. 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 data warehouse 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. Therefore, we suggest a combination of hierarchical clustering and pre-grouping. Exploiting hierarchy semantics for the pre-grouping of fact table result tuples is several time, In dieser Doktorarbeit wird die Implementierung vom MHC (multidimensionales hierarchisches Clustering) in das relationale Datenbanksystem Transbase Hypercube beschrieben. MHC wird notwendig, wenn Data Warehouse-Daten in einem clusternden multidimensionalen Index gespeichert werden sollen. Multidimensionales hierarchisches Clustering ist eine Technologie, um hierarchische Prädikate auf Dimensionstabellen auf Intervalle abzubilden, die über den multidimensionalen Index (UB-Tree in Transbase) optimal verarbeitet werden können. Hierarchie-Pfade werden durch Surrogate (numerische Codierung) abgebildet und in der Faktentabelle gespeichert. Ausgehend von einer allgemeinen Betrachtung von Hierarchien und Data Warehouse-Schemata wird die Integration der Surrogats-Berechnung für MHC in den Datenbankkern beschrieben. Interessante Aspekte zeigen sich beim Query-Processing von sog. Star Join Queries, wo durch die Hierarchie-Codierung in der Faktentabelle bereits sehr früh hierarchische Eigenschaften ausgenutzt werden können. Dies beschleunigt die Gruppierung und den Residual-Join erheblich. Weiterhin werden Konzepte beschrieben, die für eine allgemeine Verwendbarkeit der Technologie nötig sind, z.B. Multi-Query-Boxen auf UB-Trees oder Behandlung von Data Warehouse-Dimensionen, die nicht im Schlüssel des UB-Trees sind. Die theoretischen Überlegungen werden durch Messungen an einem Realdaten-Bestand verifiziert.

This thesis introduces EOS, a new approach to knowledge representation and processing that is based on Concept Theory, a unicategorical formalism we developed for defining semanti-cally enriched formal ontologies. Generally, ontologies are a means for knowledge represen-tation and reuse. They provide a shared understanding about a knowledge domain. EOS ex-tends the scope of ontologies by offering means to also formalize epistemological processes, i.e. guidelines for knowledge processing that may be employed in knowledge acquisition, generation and retrieval tasks. This general idea is molded into an EOS framework for epis-temological ontology-driven systems for knowledge processing. On this formal basis we will show how an actual EOS system can be designed, implemented and successfully put to work., EOS ist ein Framework für ontologiegesteuerte Wissensrepräsentation und -verarbeitung. Als zentrales Element beinhaltet EOS einen neu entwickelten, mit "Concept Theory" bezeichneten, Formalismus für die Modellierung von EOS-Ontologien, welche sowohl ontologisches, als auch epistemologisches Domänenwissen in einer einheitlichen Darstellungsform vereinen. Concept Theory basiert auf dem Grundgedanken, daß Ontologien mittels Konstrukten einer einheitlichen Bauart, dem "Concept", definiert werden können. Es werden Syntax und Semantik für Concepts entwickelt und mit einer graphischen Notation veranschaulicht. Dem formalen Ansatz der Concept Theory wird dann eine entsprechende EOS-Systemarchitektur gegenübergestellt. EOS-Systeme sind in der Lage, Wissen in Form von Concepts zu verarbeiten. Bezogen auf diese Grundarchitektur wird abschließend die Funktionsweise von EOS-Systemen anhand eines praxisbezogenen Anwendungsbeispiels aus dem Bereich der Dokumentenverwaltung näher erläutert.

New application areas for databases like data warehousing and OLAP (Online Analytical Proc-essing) deploy the multidimensional data model in order to describe the application domain. Consequently, OLAP systems are represented by a multidimensional database schema to adequately reflect the application semantics. FIESTA presents a methodology for the evolution of such multidimensional schemas. Core of the thesis is a schema evolution algebra which comprehends a formal multidimensional data model together with corresponding schema evolution operations. Since OLAP systems are typically implemented as additional layer for relational database systems, the processing of sequences of schema evolution operations in a relational database system is presented. To this end, we formally describe how a multidimensional schema can be mapped to a corresponding relational database schema. In order to fully maintain the multidimensional semantics during this transformation, a corresponding meta schema is introduced as extension of the relational system catalogue. For a consistent processing of evolution operation sequences, a transformation to corresponding relational evolution commands is performed. These relational evolution commands adapt the relational database schema together with the instances and update the contents of the meta schema accordingly. A prototype for FIESTA has been implemented as part of a graphical design environment for data warehouses. In this environment, multidimensional schemas are presented at the user interface by means of a specialized graphical notation. This notation is an extension of the well-known Entity/Relationship approach. For internal processing the graphical representation is transformed to an algebraic description of the multidimensional schema., Neuartige Datenbank-Anwendungen wie Data Warehousing und OLAP (Online Analytical Processing) verwenden zur Beschreibung der Anwendungsdomäne das multidimensionale Datenmodell. OLAP Systeme weisen daher ein multidimensionales Datenbank-Schema auf, um die Anwendungs-Semantik adäquat darzustellen. Mit FIESTA wird eine Methodik zur Schema-Evolution solcher multidimensionaler Schemata vorgestellt. Kern der Arbeit ist eine Schema-Evolutions-Algebra, die eine Formalisierung des multidimensionalen Datenmodells zusammen mit darauf aufbauenden Schema-Evolutions-Operationen beinhaltet. Da OLAP-Systeme meist als Zusatzschichten-Architektur für relationale Datenbanksysteme implementiert werden, wird die Verarbeitung von Sequenzen solcher Schema-Evolutions-Operationen in einem relationalen Datenbanksystem vorgestellt. Dazu wird formal beschreiben, wie ein multidimensionales Schema auf ein entsprechendes relationales DB-Schema abgebildet werden kann. Damit bei dieser Transformation die volle multidimensionale Semantik erhalten bleibt, wird ein entsprechendes Metaschema als Erweiterung des relationalen Systemkatalogs eingeführt. Zur konsistenten Umsetzung von Evolutions-Operationen-Sequenzen erfolgt eine Transformation in entsprechende relationale Evolutions-Kommandos, die neben dem eigentlichen relationalen Datenbankschema auch die Instanzen und die Inhalte des Metaschemas anpassen. FIESTA wurde im Rahmen einer graphischen Data Warehouse-Entwurfsumgebung prototypisch implementiert. Dabei werden die multidimensionalen Schemata an der Benutzer-Schnittstelle mit einer speziellen grafischen Notation, die eine Erweiterung des bekannten E/R Ansatzes ist, dargestellt. Diese grafische Darstellung wird intern zur Verarbeitung in eine algebraische Beschreibung des multidimensionalen Schemas transformiert.

Suchmaschinen im WWW spielen heutzutage ein grosse Rolle um die vorhandene Masse der Informationen besser zugänglich zu machen. In dieser Arbeit wird anhand einer selbstkonstruierten Suchmaschine demonstriert, wie spezielle Informationen aus dem WWW automatisch gesammelt und halbautomatisch nach vorgegeben Kriterien bewertet werden können. Betrachtet wird dabei die Architektur von "Web-Crawlern" sowie Ranking- und Clustering-Verfahren für Dokumente im Allgemeinen. Entwickelt wurde ein Lernverfahren basierend auf einem neuronalen Netz zur Verknüpfung der heterogenen Informationen von Web-Seiten (Position im Graph und Inhalt), um Dokumente nach ihrem Inhalt genauer kategorisieren zu können. Der Ansatz verbessert die Bewertung von Dokumentmengen im WWW gegenüber bekannten Verfahren. Dabei wird auch ein neuer Ansatz vorgestellt, um die Qualität des Vergleichs von Dokumenten zu erhöhen., Today search engines of the WWW play an important role to work through the mass of information. For this thesis a search engine was built to demostrate how special information can be obtained from the web automatically and how data is classified using a given set of topics. Details on the architecture of "web crawlers" are described as well as common ranking and clusting methods for document sets. A learning method was created using a neural network to combine heterogenous information of web-pages (position in the graph / content info) to improve the classifaction process. As a result there is an advantage of this method over common well-known classification algorithms. Also a new algorithm is introduced to improve the quality of comparison of documents.

The workload that is generated by users of explorative navigational information systems typically contains characteristic patterns. If these task- respectively user-specific patterns are known to the system, they can be used to dynamically predict user interactions at runtime. These predictions enable the usage of predictive caching strategies and speculative execution strategies. Online analytical processing (OLAP) systems are database systems that are designed to interactively explore data that is structured according to the multidimensional data model. This thesis presents an approach (called PROMISE) to represent and acquire information about navigational patterns of OLAP systems and to use them in improving dynamic materialization (caching) strategies. To this end, the thesis contains a formal model to represent behavior of OLAP users taking into account the navigational and iterative query formulation via a graphical front-end tool. An according pattern model (based on the combination of different generalized Markov models) allows for representing navigational patterns. The PROMISE prediction algorithm uses these patterns in order to dynamically predict a set of queries at any point during a session. The prediction framework is completed by an algorithm that induces and updates the pattern information for the user's actual behavior online during the system's operation. In order to demonstrate the potentials of using prediction results for dynamic system optimization, we present two approaches improving the performance of semantic query level caches in OLAP system: through improved benefit estimation functions that allow more efficient admission and eviction algorithms and by means of speculative execution techniques. An empirical analysis of the characteristics of user behavior in a real-world data warehouse environment and performance measurements using simulated traces with data from a real world application demonstrate the usefulness of the approach., Interaktive Datenanalyse-Werkzeuge, welche die zu analysierenden Daten auf logischer Ebene anhand des multidimensionalen Datenmodells strukturieren und entsprechende mehrdimensionale Operationen unterstützen, werden als Online-Analytical-Processing-Systeme (OLAP-Systeme) bezeichnet. Die vorliegende Arbeit stützt sich auf die Beobachtung, dass das explorative Datenzugriffsverhalten, welches Benutzer dieser Systeme erzeugen, gewissen Regelmäßigkeiten folgt. Diese Muster spiegeln die Struktur des bearbeiteten Analyseproblems und/oder Eigenheiten der Arbeitsweise des einzelnen Benutzers wider. Kenntnisse über diese navigierenden Muster innerhalb der Anfragesequenzen können dazu benutzt werden, mittels Antizipationstechniken die Antwortzeiten des Systems dramatisch zu verkürzen. Der vorgestellte Ansatz PROMISE (Predicting User Behavior in Multidimensional Systems Environement) erlaubt es, Regelmäßigkeiten im Anfrageverhalten von interaktiven OLAP Benutzern automatisch zu erkennen und zur dynamischen Antizipation künftiger Anfragen zu nutzen. Den Kern des Ansatzes bildet der PROMISE Vorhersage-Algorithmus, welcher einen - auf Markov Modellen basierenden - Formalismus zur Muster-Repräsentation verwendet. Dieser berücksichtigt die speziellen Anforderungen von OLAP Systemen, insbesondere die iterative Anfrageformulierung mittels graphischer Werkzeuge. Als Anwendungsfall wird der Einsatz von Voraussage-Ergebnissen zur Steigerung der Effizienz von OLAP-Caching-Verfahren detailliert untersucht. Den Schwerpunkt bilden hierbei die Integration spekulativer Ausführungstechniken und die Verbesserung von Verdrängungsstrategien. Messungen der System-Performanz mittels Benutzersimulationen auf Datenbeständen eines realen Data Warehouse belegen die Anwendbarkeit und Leistungsfähigkeit des Verfahrens.

Das entwickelte System HEAVEN realisiert eine flexible und performante hierarchische Speicher- und Archivierungsumgebung für multidimensionale Array Datenbank Management Systeme. Viele Phänomene der Natur werden als Array-Daten mit entsprechender Dimensionalität modelliert. Als eine gemeinsame Charakteristik gilt das immense Datenvolumen (mehrere Petabyte). Gegenwärtig und in Zukunft sind Tertiärspeichersysteme der einzige praktikable Weg, diese Datenmengen zu speichern. Ein inhärentes Problem ist nicht das Speichern dieser großen Datenvolumina, sondern der effiziente und selektive Zugriff auf die gespeicherten Daten, sowie deren Analyse. Mit HEAVEN wird der Übergang von einer herkömmlichen, dateisystembasierten Datenhaltung auf eine datenbankbasierte Datenhaltung mit automatisierter und optimierter Tertiärspeicheranbindung vollzogen. Heute sind Gigabyte-Datenbanken üblich, Terabyte-Datenbanken die aktuelle Herausforderung und Petabyte-Datenbanken ein wichtiges Forschungsgebiet. HEAVEN realisiert ein hochgradig erweiterbares und skalierbares Datenmanagement, das durch eine optimierte Automatisierung der Datenauslagerung, Datenspeicherung und des Datenretrievals erreicht wird. So wurde mit HEAVEN eine hierarchische Speicher- und Archivierungsumgebung für multidimensionale Array Datenbank Management Systeme mit nahezu unlimitiertem Speichervolumen geschaffen. Nutzern und Applikationen wird eine transparente Sicht auf die gespeicherten Daten gegeben, unabhängig vom tatsächlichen, physikalischen Speicherort. Zur Steigerung der Performance des Retrievals und der Analyse multidimensionaler Array-Daten wurden spezielle Techniken entwickelt. Hierzu zählt das Super-Tile-Konzept, das Intra- und Inter-Super-Tile-Clustering, das Query-Scheduling und eine Caching-Hierarchie. Auch die Verwendung vorberechneter Operationsergebnisse und die erweiterte Analysemglichkeit durch das entwickelte Object-Framing tragen hierzu bei. Bei der Realisierung von HEAVEN wurde der Balanceakt zwisc, HEAVEN (Hierarchical Storage and Archive Environment for Multidimensional Array Database Management Systems) provides a solution for an intelligent management of large-scale datasets held on tertiary storage systems. Scientific large-scale experiments and corresponding simulation programs often generate large amounts of multidimensional array data. Data volume may reach hundreds of terabytes (up to petabytes). Presently and in the near future the only practicable way for storing such large volumes of multidimensional data are tertiary storage systems. An identified major bottleneck today is the fast and efficient access to and evaluation of high performance computing results. We address the necessity of developing techniques for efficient retrieval of requested subsets of large datasets from mass storage devices. Furthermore, we show the benefit of managing large spatio-temporal data sets with database management systems. But commercial (multidimensional) database systems are optimized for performance with primary and secondary memory access. So tertiary storage memory is only supported in an insufficient way for storage or retrieval of multidimensional array data. This means database systems need a smart connection to tertiary storage systems with optimized access strategies. HEAVEN combines the advantages of both techniques, storing large amounts of data on tertiary storage media and optimizing data access for retrieval with multidimensional database management systems. We present techniques like the Super-Tile-Concept, Intra- and Inter-Super-Tile-Clustering, Query-Scheduling and Caching, keeping our main focus on reducing tertiary storage access time for multidimensional array data. Additionally we extended the multidimensional query language of the database system using a new developed concept called Object Framing. With this extension, users will no longer be restricted to performing range queries in the shape of multidimensional hyper cubes. Now they will be a

The UB-Tree is an index structure for multidimensional point data. By name, it claims to be universal, but this imposes a huge burden, as there are few things which really prove to be universal. This thesis takes a closer look at aspects where the UB-Tree is not universal at a first glance. The first aspect is the discussion of space filling curves (SFCs), in particular comparing the Z-curve and the Hilbert-curve. The Z-curve is used to cluster data indexed by the UB-Tree and we highlight its advantages in comparison to other SFCs. While the Hilbert-curve provides better clustering, the Z-curve is superior w.r. to other metrics, i.e. it is significantly more efficient to calculate addresses and the mapping of queries to SFC-segments, and it is able to space efficiently index arbitrary universes. Thus the Z-curve is more universal here. The second aspect are bulk operations on UB-Trees. Especially for data warehousing the bulk insertion and deletion are crucial operations. We present efficient algorithms for incremental insertion and deletion. The third aspect is the comparison of the UB-Tree with bitmap indexes used for an example data warehousing application. We show how performance of bitmap indexes is increased by clustering the base table according to a SFC. Still the UB-Tree proves to be superior. The fourth aspect is the efficient management of data with skewed data distributions. The UB-Tree adapts its partitioning to the actual data distribution, but in comparison to the R-Tree, it suffers from being not able to prune search path leading to unpopulated space (= dead space). This is caused by partitioning the complete universe with separators. We present a novel index structure, the bounding UB-Tree (BUB-Tree), which is a variant of the UB-Tree inheriting its worst case guarantees for the basic operations while efficiently addressing queries on dead space. In comparison to R-Trees, its query performance is similar while offering superior maintenance performan, Um flexible Anfragen auf mehrdimensionale Daten effizient unterstützen zu können, ist eine optimierte Organisation der Daten nötig. Dabei müssen auch dynamische Daten und ungleichmäßige Datenverteilungen performant verwaltet werden. In dieser Arbeit wird daher neben der Anfragebearbeitung auch ein Schwerpunkt auf die flexible Verwaltung von mehrdimensionalen Daten mit dem UB-Baum gelegt. Dabei zeigt sich die Z-Kurve in Bezug auf Flexibilität und Effizienz als Gewinner gegenüber anderen bekannten raumfüllenden Kurven. Des Weiteren werden optimierte Algorithmen zum Laden und Löschen großer Mengen von Daten vorgestellt. Auch im Vergleich mit Bitmap-Indices am Beispiel eines Data Warehouse zeigt sich die Überlegenheit des UB-Baums. Für effiziente Bereichsanfragen auf leeren Räumen wurde die Variante "Bounding UB-Baum" entwickelt. Abschließend wurde die Indexierung ausgedehnter Objekte durch die Transformation der Objekt-Approximation und räumlicher Anfragen untersucht.

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 ra, 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 anwendungsspe

In this work, techniques for efficient operation execution on multidimensional arrays in database management systems are developed. All the techniques described here are implemented in the RasDaMan system, which provides a declarative query language on multidimensional arrays. The operations specified in this query language are executed using the operation execution engine developed here. Arrays of arbitrary base type, including user defined structures, are supported. This implies the use of a dynamic type system supporting definition of types at runtime of the server. The data can be of arbitrary dimensionality and size. Operation execution must be flexible enough to cope with this data. At the same time, efficiency is a key target, as the data volumes operated on are typically very big. Tiles are the basic unit of physical data storage for multidimensional arrays in the RasDaMan DBMS. All operations specified on arrays in queries are finally executed on tiles, so they form the basis for operation execution. A formalism defining semantics of operations on multidimensional tiles is developed. This formalism takes the basic properties of tiles into account: base type and spatial domain. Semantics of operations and the applicability of operations are defined on these properties. Based on the formalism, the design for an operation execution engine for multidimensional arrays is developed. This design has two major goals: Encapsulation of the actual implementation to present a clear interface to other modules of the system and efficiency when executing operations. An object-oriented model is developed to provide for encapsulation. This model provides efficiency by avoiding multiple iterations through cells when possible. Furthermore, the encapsulation enables the optimisation of algorithms for operation execution without affecting other modules. The efficiency of this implementation is evaluated using workloads from common application fields. A thorough performance anal, In dieser Arbeit werden Verfahren zur effizienten Operationsausführung auf multidimensionalen Feldern in Datenbanksystemen entwickelt. Felder beliebiger Dimensionalität und auf beliebigen, auch strukturierten, Basistypen werden unterstützt. Die Speicherung erfolgt in Kacheln, die als Grundeinheit für die Ausführung von Operationen dienen. Auf Basis eines Formalismus wird eine objektorientierte Implementierung beschrieben und deren Effizienz in Benchmark-Messungen analysiert. Die beschriebenen Techniken sind in dem multidimensionalen Rasterdatenbanksystem RasDaMan implementiert.

Der Internet-Mehrwertdienst World Wide Web hat in den letzten Jahren zunehmend an Bedeutung gewonnen. Die Einfachheit des zugrunde liegenden Hypertext-Modells und die mangelnde Trennung zwischen logischer und physischer Ebene im Web führen bei der Verwaltung komplexer Anwendungen und großer Informationsbestände zu verschiedenen Problemen. Um die riesigen Informationsmengen im Web effizienter verwalten zu können, werden deshalb zunehmend Datenbanken eingesetzt. In dieser Arbeit werden Verbesserungen zu Entwurf, Implementierung und Verwaltung großer Web-Anwendungen auf der Basis der entwickelten Modellierungsmethode HDBM (Hypermedia Database Methodology) beschrieben. Hierzu wird ein Meta-Schema vorgestellt, das die Verwaltung von Struktur, Layout und Navigation der Web-Anwendung in einer relationalen Datenbank gestattet. Der Einsatz von Meta-Daten gewährleistet die einfache Erstellung, Wartung und Skalierbarkeit von dynamisch generierten Web-Sites auf der Basis einer Datenbank. Realisiert wurden die Konzepte im Rahmen einer Implementierung mit dem relationalen Datenbanksystem Oracle., [Abstract only in German available.] Der Internet-Mehrwertdienst World Wide Web hat in den letzten Jahren zunehmend an Bedeutung gewonnen. Die Einfachheit des zugrunde liegenden Hypertext-Modells und die mangelnde Trennung zwischen logischer und physischer Ebene im Web führen bei der Verwaltung komplexer Anwendungen und großer Informationsbestände zu verschiedenen Problemen. Um die riesigen Informationsmengen im Web effizienter verwalten zu können, werden deshalb zunehmend Datenbanken eingesetzt. In dieser Arbeit werden Verbesserungen zu Entwurf, Implementierung und Verwaltung großer Web-Anwendungen auf der Basis der entwickelten Modellierungsmethode HDBM (Hypermedia Database Methodology) beschrieben. Hierzu wird ein Meta-Schema vorgestellt, das die Verwaltung von Struktur, Layout und Navigation der Web-Anwendung in einer relationalen Datenbank gestattet. Der Einsatz von Meta-Daten gewährleistet die einfache Erstellung, Wartung und Skalierbarkeit von dynamisch generierten Web-Sites auf der Basis einer Datenbank. Realisiert wurden die Konzepte im Rahmen einer Implementierung mit dem relationalen Datenbanksystem Oracle.

Arrays of arbitrary size and dimensionality appear in a large variety of database application fields, e.g., medical imaging, geographic information systems, scientific simulations, and also business-oriented applications like Online Analytical Processing (OLAP) and data mining. Recently, integration of an application domain-independent and dimensionality-independent type constructor for such Multi-dimensional Discrete Data (MDD) into Database Management Systems receives growing attention. Current scientific contributions in this area mainly focus on MDD algebra and specialized storage architectures. Since MDD values may occur in the scale of several megabytes and, compared to scalar values, operations on these values are very complex, their efficient evaluation becomes a critical factor for the overall query response time. Although the management of MDD values shifts the demands on query processing fundamentally, there has never been a systematic study on specific query optimization on both logical and physical level combined with efficient evaluation of MDD queries. In this thesis, we want to close this gap: We develop a generic Abstract Data Type (ADT) for MDD and integrate it into an adapted relational model by allowing the newly introduced MDD expressions in selection conditions and as parameters of the novel application operation which is an extension of relational projection. With this model serving as a formal base, a comprehensive list of algebraic transformation rules together with an optimization heuristics is provided. Specialized evaluation algorithms based on a tiled storage layout are presented which optimize array query processing both in terms of speed and memory usage. We proceed with an examination of the MDD specific cost structure for array query processing. The main responsible parameters are summarized in the Array Cost Model which, e.g., is used to make cost-based decisions for different alternative evaluation plans. The techniques presented a, Die Integration multidimensionaler Arrays in Datenbanksysteme gewinnt durch die Vielzahl ihrer Anwendungen wie 1D-Zeitreihen, 2D-Bilder, 3D-Volumendaten bis hin zu nD Simulations- und Wirtschaftsdaten zunehmend an Bedeutung. Diese Arbeit beschreibt die formale Integrationeines parametrisierten Array-Datentyps mit umfassender operationaler Unterstützung in das relationale Datenbankmodell, sowie die daraus resultierenden zusätzlichen Anforderungen an die Anfrageverarbeitung. Zur Optimierung sogenannter Array-Anfragen werden algebraische Optimierungsregeln und spezielle physische Ausführungsalgorithmen auf Basis einer gekachelten Speicherung erarbeitet. Ein Kostenmodell erlaubt die Vorhersage der Grösse des Anfrageresultats und der Anfragekosten. Der Nutzen der vorgestellten Konzepte wird durch ihre Implementierung und umfangreiche Performanzmessungen im Rahmen des FORWISS Projektes RasDaMan unter Beweis gestellt.

Der Einsatz der mehrdimensionalen Zugriffsstruktur UB-Baum in komplexen Geschäfts-Anwendungen (z.B. SAP R/3), statistischen Datenbanken, Data-Warehouse und Data-Mining haben gezeigt, dass Leistungssteigerungen bis zum Faktor 10 für die Verarbeitung von Bereichsanfragen möglich sind. Weitere Verbesserungen wurden durch die Integration in den Datenbankkern Transbase von TransAction erzielt. Diese Arbeit untersucht die Möglichkeit der Ausnutzung der Z-Partitionierung des UB-Baums für die Verwendung in der Anfrageverarbeitung und beim Massenladen. Hierzu entwickelte der Autor mehrere neue Algorithmen, die entweder aus der Z-Ordnung effizient eine Zielordnung oder aus einer 1-dimensionalen Quellordnung die Z-Ordnung erzeugen. Dies führt zu einem effizienten Massenlade-Algorithmus (TempTris-Alogrithmus) sowie zu einem Verbunds- und Gruppierungs-Operator (Tetris-Algorithmus, UBG-Algorithmus). Die Algorithmen reduzieren die E/A-Kosten in der Sortierphase um mindestens 50% gegenüber dem externen Sortieren. Für die einzelnen Algorithmen wurden Kostenmodelle entwickelt, die durch Leistungsmessungen auf künstlichen Datenverteilungen und durch Teile des TPC-H Benchmark belegt werden. Um die Anwendungstauglichkeit im realen Datenbankumfeld zu zeigen, wurden Messungen auf dem Data-Warehouse der Gesellschaft für Konsumforschung (GfK) gemacht. Die Arbeit schließt mit einer neuen Verarbeitungstechnik des CUBE-Operators und dem Einfluss der neuen Techniken auf die relationale Algebra. Der Autor erstellte die Ergebnisse dieser Arbeit als Mitglied der Mistralgruppe bei FORWISS., Complex business applications like SAP R/3, statistical databases, data warehousing and data mining have created a strong demand for efficiently processing complex queries on huge relational databases. By using the multidimensional index UB-tree as access structure to execute range queries a performance enhancement of factor 10 could be achieved. Additional improvements were carried out by integration in the database system Transbase of TransAction. This thesis analyses the usability of the Z-partitioning of the UB-Tree for query processing and bulk loading. The author of this thesis develops several algorithms that process efficiently a Z-order to a one dimensional order or reverse. The result is an efficient bulk load algorithm (TempTris-Algorithm) as well as a join and group algorithm (Tetris-Algorithm, UBG-Algorithm). These algorithms reduce the I/O-cost for the sort phase at least of 50% according to the external sorting. For each algorithm a cost model is presented. The author presents performance measurements that proved our predicted speed up factor. The performance measurements are conducted on artificial data as well as on the TPC-H benchmark. To show the potential impact on real database scenarios, measurements were performed on a real data warehouse from the Gesellschaft für Konsumforschung (GfK). This thesis concludes with a new processing technique of the CUBE-operator and the impact on the relational algebra. The author develops the results of this thesis as a member of the research group MISTRAL at FORWISS.

The paper discusses a way to deploy a given number of point light sources in the interior to provide required illuminance levels and uniformity of the working plane by using a genetic algorithm. Furthermore a genetic algorithm has been used to generate a proper luminous intensity distribution curve of multiple luminaires to meet the given criteria for the reference plane of the model room for predefined luminaire positions.