In a traditional relational database management system, queries can only be defined over attributes defined in the schema, but are guaranteed to give single, definitive answer structured exactly as specified in the query. In contrast, an information retrieval system allows the user to pose queries without knowledge of a schema, but the result will be a top-k list of possible answers, with no guarantees about the structure or content of the retrieved documents. In this chapter, we present Drill Beyond, a novel IR/RDBMS hybrid system, in which the user seamlessly queries a relational database together with a large corpus of tables extracted from a web crawl. The system allows full SQL queries over a relational database, but additionally enables the user to use arbitrary additional attributes in the query that need not to be defined in the schema. The system then processes this semi-specified query by computing a top-k list of possible query evaluations, each based on different candidate web data sources, thus mixing properties of two worlds RDBMS and IR systems.

Materialized summary tables and cached query results are frequently used for the optimization of aggregate queries in a data warehouse. Query rewriting techniques are incorporated into database systems to use those materialized views and thus avoid the access of the possibly huge raw data. A rewriting is only possible if the query is derivable from these views. Several approaches can be found in the literature to check the derivability and find query rewritings. The specific application scenario of a data warehouse with its multidimensional perspective allows the consideration of much more semantic information, e.g. structural dependencies within the dimension hierarchies and different characteristics of measures. The motivation of this article is to use this information to present conditions for derivability in a large number of relevant cases which go beyond previous approaches.

Data processing on a continuously growing amount of information and the increasing power restrictions have become an ubiquitous challenge in our world today. Besides parallel computing, a promising approach to improve the energy efficiency of current systems is to integrate specialized hardware. This paper presents a Tensilica RISC processor extended with an instruction set to accelerate basic database operators frequently used in modern database systems. The core was taped out in a 28 nm SLP CMOS technology and allows energy-efficient query processing as well as query optimization by applying selectivity estimation techniques. Our chip measurements show an 1000x energy improvement on selected database operators compared to state-of-the-art systems.

In this demo, we present MorphStore, an in-memory column store with a novel compression-aware query processing concept. Basically, compression using lightweight integer compression algorithms already plays an important role in existing in-memory column stores, but mainly for base data. The continuous handling of compression from the base data to the intermediate results during query processing has already been discussed, but not investigated in detail since the computational effort for compression as well as decompression is often assumed to exceed the benefits of a reduced transfer cost between CPU and main memory. However, this argument increasingly loses its validity as we are going to show in our demo. Generally, our novel compression-aware query processing concept is characterized by the fact that we are able to speed up the query execution by morphing compressed intermediate results from one scheme to another scheme to dynamically adapt to the changing data characteristics during query processing. Our morphing decisions are made using a cost-based approach.

Databases as a service (DBaaS) transfer the advantages of cloud computing to data management systems, which is important for the big data era. The allocation in a DBaaS system, i.e., the mapping from databases to nodes of the infrastructure, influences performance, utilization, and cost-effectiveness of the system. Modeling databases and the underlying infrastructure as weighted graphs and using graph partitioning and mapping algorithms yields an allocation strategy. However, graph partitioning assumes that individual vertex weights add up (linearly) to partition weights. In reality, performance does usually not scale linearly with the amount of work due to contention on the hardware, on operating system resources, or on DBMS components. To overcome this issue, we propose an allocation strategy based on penalized graph partitioning in this paper. We show how existing algorithms can be modified for graphs with non-linear partition weights, i.e., vertex weights that do not sum up linearly to partition weights. We experimentally evaluate our allocation strategy in a DBaaS system with 1,000 databases on 32 nodes.

The development of in-memory query engines is constantly adapting to evolving hardware features to maintain high performance for modern data analytics. To achieve this, parallelizing query processing is crucial for leveraging the full potential of modern hardware. While traditional parallelization techniques like multi-threading and distributed computing are well-established, the increasing availability and continuous advancements of data-level parallelism, known as Single Instruction Multiple Data (SIMD), have made SIMD a cutting-edge approach for improving single-query performance. Three general trends can be identified in the evolution of SIMD hardware: (i) continual increase in the available degree of data-level parallelism through wider SIMD registers, (ii) ongoing expansion of functional capabilities, and (iii) notable heterogeneity of the SIMD hardware landscape. The increasing width of SIMD registers, ranging from 128-bit to 512-bit for Intel and ARM platforms and up to 16 Kb on the NEC SX-Aurora TSUBASA vector engine, provides significant potential for data-level parallelism. This trend benefits query operators with linear access patterns, such as simple scans or arithmetic operations. However, it can negatively impact operators that rely on random access patterns or introduce loop-carried dependencies, such as sorting or a Hash-Join. With the introduction of novel instruction set extensions, like Intel's AVX-512, the functional capabilities of SIMD hardware have been continuously extended, allowing more complex operations to be efficiently executed in parallel. Consequently, this thesis outlines the opportunities and challenges of wider SIMD registers for in-memory query processing and how novel instruction set extensions can be used to mitigate some challenges. Additionally, the SIMD hardware landscape has become increasingly heterogeneous, with different architectures available. This diversity poses a significant challenge for academia and industry, as it requires constant adaptation and re-evaluation of SIMD-based algorithms and data structures. To address this challenge, we implemented a SIMD hardware abstraction library called Template SIMD Library (TSL), which provides a unified interface to different architectures. In this thesis, we present the design and implementation of TSL, demonstrating its capabilities by implementing a set of SIMD-based algorithms for in-memory query processing. We also show that even modern FPGAs benefit from the SIMD paradigm and can be programmed using high-level synthesis tools, such as Intel's oneAPI. Moreover, we demonstrate the potential of SIMD-based FPGA programming by implementing SIMD-based algorithms for in-memory query processing on different FPGA cards and integrating the necessary functionality into the TSL. Finally, we propose a novel workload-aware SIMD query processing approach called SIMQ. This approach leverages SIMD registers to share data access and SIMD instructions to share computation across queries.:1 Introduction 1.1 Single Instruction Multiple Data (SIMD) 1.1.1 Utilizing SIMD 1.1.2 SIMD in OLAP Query Processing 1.2 Thesis Goals and Contributions 1.2.1 Implications of SIMD Advancements on Analytical Query Processing 1.2.2 Leveraging SIMD to Optimize OLAP Query Throughput 1.2.3 Embracing the Heterogeneity of SIMD-aware Hardware 1.3 Impact of Thesis Contributions 1.3.1 Publications of Thesis Contribution 1.3.2 Open Source Contributions 1.3.3 Further Publications 1.4 Structure of the Thesis 2 Evaluating the Vector Supercomputer SX-Aurora TSUBASA 2.1 Problem Statement 2.2 Hardware System SX-Aurora TSUBASA 2.2.1 Overall Architecture 2.2.2 Vector Processing and Specific Systems 2.2.3 Execution Model and Programming Approach 2.3 MorphStore — In-Memory Database System 2.4 Comparative Evaluation 2.4.1 Selected Investigated Operations 2.4.2 Experimental Setup and Methodology 2.4.3 Single-Thread Evaluation Results 2.4.4 Multi-Thread Evaluation Results 2.4.5 Summary 2.5 Future Work 2.6 Conclusion 3 Fighting Duplicates in Hashing 3.1 Problem Statement 3.2 Background 3.2.1 Linear Probing 3.2.2 State-of-the-Art Vectorized Implementation of Linear Probing 3.2.3 Novel SIMD Instructions 3.3 CD-aware Vectorized Implementation of Linear Probing 3.3.1 CD-aware Hash Table Data Structures 3.3.2 Handling of Bucket Duplicates 3.3.3 Handling of Key Duplicates 3.4 Experimental Evaluation 3.4.1 Evaluation Result for Hashing without Value Handling 3.4.2 Evaluation Results for Hashing with Value Handling 3.5 Related Work 3.6 Conclusion and Future Work 4 Leveraging SIMD to Optimize OLAP Query Throughput 4.1 Problem Statement 4.2 Background and Related Work 4.2.1 Vectorization in General 4.2.2 Vectorization in Database Systems 4.2.3 Work Sharing in Database Systems 4.3 Sharing Vector Registers 4.3.1 SISQ: Single Instruction Single Query 4.3.2 SIMQ: Single Instruction Multiple Queries 4.4 Evaluation 4.4.1 Single-Threaded Evaluation 4.4.2 Multi-Threaded Evaluation 4.5 Discussion 4.6 Conclusion 5 Program your (custom) SIMD instruction set on FPGA in C++ 5.1 Problem Statement 5.2 FPGA Programming in C++ 5.2.1 Naïve C++ programming 5.2.2 Data Parallel C++ programming. 5.2.3 Using specialized data types 5.2.4 Analyzing FPGA resources 5.2.5 Summary 5.3 Programming SIMD instruction set 5.3.1 Register Definition 5.3.2 Instruction Definition 5.3.3 Comparing with RTL kernels 5.4 Use Case Studies 5.4.1 FilterCount 5.4.2 Binary Packing 5.5 Custom SIMD instructions 5.6 DPC++ Best practices 5.7 Related Work 5.8 Conclusion 6 Mastering the SIMD Heterogeneity 6.1 Problem Statement 6.2 Background 6.2.1 Applicability 6.2.2 Evolving API 6.3 TSLGen - Generative Framework 6.3.1 General Concepts 6.3.2 Framework Description 6.4 Advanced Features 6.4.1 Test Generation 6.4.2 Build Environment Files Generation 6.4.3 Further Extensions 6.4.4 Toolsupport 6.5 Use-Case Studies 6.5.1 Case Studies Description 6.5.2 Applicability 6.5.3 Extensibility 6.6 Discussion 6.7 Related Work 6.8 Conclusion 7 Tutorial on SIMD - Foundations, Abstraction, and Advanced Techniques 7.1 Problem Statement 7.2 Foundations 7.3 Abstraction 7.4 Advanced Techniques 7.4.1 Wider SIMD Registers 7.4.2 Flexibly-Sized SIMD Registers 7.4.3 Partition-based SIMD Processing 7.4.4 Increasing Heterogeneity 7.5 Summary / Kontinuierlich wachsende Mengen an zu verwaltenden Daten und komplexer werdende analytische Anfragen erfordern eine stetige Weiterentwicklung und Verbesserung von In-Memory Query Engines. Die effiziente Ausnutzung sich ständig weiterentwickelnder Hardware-Features fällt dabei eine entscheidende Rolle zu. Ein grundlegender Ansatz zur Beschleunigung von Algorithmen besteht in der Parallelisierung der Verarbeitung. Neben Scale-up und Scale-out Ansätzen, wie Multi-Thread beziehungsweiße Distributed Computing, existiert die Möglichkeit der Datenlevel parallelen (Single Instruction Multiple Data (SIMD)) Verarbeitung. Durch die zunehmende Verfügbarkeit und kontinuierliche Weiterentwicklung ist vorallem SIMD eine häufig eingesetzte Technik zur Beschleunigung verschiedenster Algorithmen in Forschung und Industrie geworden. Drei allgemeine Trends lassen sich im Bezug auf die Entwicklung von SIMD-Hardware identifizieren: (i) eine kontinuierliche Zunahme des verfügbaren Grades an Datenparallelismus durch breitere SIMD-Register, (ii) eine kontinuierliche Erweiterung des Funktionsumfangs und (iii) eine große Heterogenität der SIMD-Hardware-Landschaft. Die zunehmende Breite der verfügbaren SIMD-Register, die von 128 bit bis 512 bit für Inel und ARM Plattformen und bis zu 16 Kb auf der NEC SX-Aurora TSUBASA reicht, nützt vorallem Algorithmen mit linearem Zugriffsmuster ohne relevante Abhängigkeiten zwischen den einzelnen zu verarbeitenden Daten. Algorithmen welche auf nicht-lineare Zugriffsmuster angewiesen sind oder deren Verhalten stark von den zu Grunde liegenden Daten abhängig ist, können jedoch häufig nicht von einem höheren Grad an Datenlevel Parallelismus profitieren. Ein Beispiel für solch einen Algorithmus ist der Hash-Join, dessen Ziel es ist, zwei Relationen über einen gemeinsamen Schlüssel zu verknüpfen. Durch die Einführung neuer Befehlssatzerweiterungen wie AVX-512 von Intel werden die funktionalen Fähigkeiten der der verfügbaren SIMD-Hardware kontinuierlich erweitert, wodurch bisherige Annahmen neu bewertet werden müssen. Die vorliegende Arbeit untersucht die Möglichkeiten und Herausforderungen breiterer SIMD-Register für die In-Memory Anfrageverarbeitung und inwiefern neue Befehlssatzerweiterungen genutzt werden können, um wichtige Herausforderungen in der Datenlevel paralleln Verarbeitung zu bewältigen. Der dritte Trend, die zunehmende Ausdifferenzierung verfügbarer Hardware erschwert den konsistenten Einsatz von SIMD. Unterschiedliche Funktionen, Datentypen und Konzepte verhindern eine einfache Portierung bereits optimierter Algorithmen. Neue Funktionalitäten erfordern mitunter eine architekturspezifische Anpassung des gesamten Algorithmus um vorhandene Möglichkeiten bestmöglich auszunutzen. Um dieser Herausforderung zu begegnen, wird die im Rahmen dieser Dissertation entwickelte SIMD-Hardwareabstraktionsbibliothek namens Template SIMD Library (TSL) vorgestellt, die eine einheitliche Schnittstelle bereitstellt um auf einer Vielzahl von Architekturen mit unterschiedlichen Datentypen Datenlevel parallelität auszunutzen. Darüber hinaus wird gezeigt, dass selbst moderne FPGAs vom SIMD-Paradigma profitieren und mit Hilfe von high-level synthesis Tools (HLS) wie Intels oneAPI programmiert werden können. Das Potenzial von SIMD zur Beschleunigung der Verarbeitung auf FPGAs wird durch diverse Benchmarks von Datenbank-spezifischen Algorithmen auf zwei verschiedenen FPGA-Karten aufgezeigt und die erforderliche Funktionalität in die TSL integriert. Während alle bisherigen Ansätze zum Einsatz von SIMD in der In-Memory Anfrageverarbeitung auf die Beschleunigung einzelner Anfragen abzielten, wird in der vorliegenden Arbeit ein neues Konzept zur Workload-Optimierung namens SIMQ vorgestellt. Dieser Ansatz nutzt SIMD-Register als von der Hardware bereitgestellte Ressource, um gemeinsame Datenzugriffe unterschiedlicher Anfragen zusammenzuführen.:1 Introduction 1.1 Single Instruction Multiple Data (SIMD) 1.1.1 Utilizing SIMD 1.1.2 SIMD in OLAP Query Processing 1.2 Thesis Goals and Contributions 1.2.1 Implications of SIMD Advancements on Analytical Query Processing 1.2.2 Leveraging SIMD to Optimize OLAP Query Throughput 1.2.3 Embracing the Heterogeneity of SIMD-aware Hardware 1.3 Impact of Thesis Contributions 1.3.1 Publications of Thesis Contribution 1.3.2 Open Source Contributions 1.3.3 Further Publications 1.4 Structure of the Thesis 2 Evaluating the Vector Supercomputer SX-Aurora TSUBASA 2.1 Problem Statement 2.2 Hardware System SX-Aurora TSUBASA 2.2.1 Overall Architecture 2.2.2 Vector Processing and Specific Systems 2.2.3 Execution Model and Programming Approach 2.3 MorphStore — In-Memory Database System 2.4 Comparative Evaluation 2.4.1 Selected Investigated Operations 2.4.2 Experimental Setup and Methodology 2.4.3 Single-Thread Evaluation Results 2.4.4 Multi-Thread Evaluation Results 2.4.5 Summary 2.5 Future Work 2.6 Conclusion 3 Fighting Duplicates in Hashing 3.1 Problem Statement 3.2 Background 3.2.1 Linear Probing 3.2.2 State-of-the-Art Vectorized Implementation of Linear Probing 3.2.3 Novel SIMD Instructions 3.3 CD-aware Vectorized Implementation of Linear Probing 3.3.1 CD-aware Hash Table Data Structures 3.3.2 Handling of Bucket Duplicates 3.3.3 Handling of Key Duplicates 3.4 Experimental Evaluation 3.4.1 Evaluation Result for Hashing without Value Handling 3.4.2 Evaluation Results for Hashing with Value Handling 3.5 Related Work 3.6 Conclusion and Future Work 4 Leveraging SIMD to Optimize OLAP Query Throughput 4.1 Problem Statement 4.2 Background and Related Work 4.2.1 Vectorization in General 4.2.2 Vectorization in Database Systems 4.2.3 Work Sharing in Database Systems 4.3 Sharing Vector Registers 4.3.1 SISQ: Single Instruction Single Query 4.3.2 SIMQ: Single Instruction Multiple Queries 4.4 Evaluation 4.4.1 Single-Threaded Evaluation 4.4.2 Multi-Threaded Evaluation 4.5 Discussion 4.6 Conclusion 5 Program your (custom) SIMD instruction set on FPGA in C++ 5.1 Problem Statement 5.2 FPGA Programming in C++ 5.2.1 Naïve C++ programming 5.2.2 Data Parallel C++ programming. 5.2.3 Using specialized data types 5.2.4 Analyzing FPGA resources 5.2.5 Summary 5.3 Programming SIMD instruction set 5.3.1 Register Definition 5.3.2 Instruction Definition 5.3.3 Comparing with RTL kernels 5.4 Use Case Studies 5.4.1 FilterCount 5.4.2 Binary Packing 5.5 Custom SIMD instructions 5.6 DPC++ Best practices 5.7 Related Work 5.8 Conclusion 6 Mastering the SIMD Heterogeneity 6.1 Problem Statement 6.2 Background 6.2.1 Applicability 6.2.2 Evolving API 6.3 TSLGen - Generative Framework 6.3.1 General Concepts 6.3.2 Framework Description 6.4 Advanced Features 6.4.1 Test Generation 6.4.2 Build Environment Files Generation 6.4.3 Further Extensions 6.4.4 Toolsupport 6.5 Use-Case Studies 6.5.1 Case Studies Description 6.5.2 Applicability 6.5.3 Extensibility 6.6 Discussion 6.7 Related Work 6.8 Conclusion 7 Tutorial on SIMD - Foundations, Abstraction, and Advanced Techniques 7.1 Problem Statement 7.2 Foundations 7.3 Abstraction 7.4 Advanced Techniques 7.4.1 Wider SIMD Registers 7.4.2 Flexibly-Sized SIMD Registers 7.4.3 Partition-based SIMD Processing 7.4.4 Increasing Heterogeneity 7.5 Summary

In den letzten Jahren haben sich spezielle Prinzipien zur Veröffentlichung strukturierter Daten im World Wide Web (WWW) etabliert. Diese Prinzipien erlauben es, von den jeweils angebotenen Daten auf weitere, nach den selben Prinzipien veröffentlichten Daten zu verweisen. Die daraus resultierende Form von Web-Daten wird entsprechend als Linked Data bezeichnet. Mit der Veröffentlichung von Linked Data im WWW entsteht ein sehr großer Datenraum, welcher Daten verschiedenster Anbieter miteinander verbindet und neuartige Möglichkeiten für Web-basierte Anwendungen bietet. Als Basis für die Entwicklung solcher Anwendungen haben mehrere Forschungsgruppen begonnen, Ansätze zu untersuchen, welche diesen Datenraum als eine Art verteilte Datenbank auffassen und die Ausführung deklarativer Anfragen über dieser Datenbank ermöglichen. Forschungsarbeit zu theoretischen Grundlagen der untersuchten Ansätze fehlt jedoch nahezu vollständig. Die vorliegende Dissertation schließt diese Lücke. / During recent years a set of best practices for publishing and connecting structured data on the World Wide Web (WWW) has emerged. These best practices are referred to as the Linked Data principles and the resulting form of Web data is called Linked Data. The increasing adoption of these principles has lead to the creation of a globally distributed space of Linked Data that covers various domains such as government, libraries, life sciences, and media. Approaches that conceive this data space as a huge distributed database and enable an execution of declarative queries over this database hold an enormous potential; they allow users to benefit from a virtually unbounded set of up-to-date data. As a consequence, several research groups have started to study such approaches. However, the main focus of existing work is to address practical challenges that arise in this context. Research on the foundations of such approaches is largely missing. This dissertation closes this gap.

Daten werden noch immer groesstenteils in Dateien und nicht in Datenbanken gespeichert. Dieser Trend wird durch den Internetboom der 90er Jahre nur noch verstaerkt. Daraus ist das Forschungsgebiet der semistrukturierten Daten entstanden. Semistrukturierte Daten sind Daten, die meist in Dokumenten gespeichert sind und eine implizite und irregulaere Struktur aufweisen. HTML- oder BibTeX-Dateien oder in ASCII-Dateien gespeicherte Genomdaten sind Beispiele. Traditionelles Datenbankmanagement erfordert Design und sichert Deklarativitaet zu. Dies ist im Umfeld der semistrukturierten Daten nicht gegeben, ein flexiblerer Ansatz wird gebraucht. In dieser Arbeit wird ein neuer Ansatz des Abfragens semistrukturierter Daten praesentiert. Wir schlagen vor, semistrukturierte Daten durch eine Menge von partiellen Schemata zu beschreiben, anstatt zu versuchen, ein globales Schema zu definieren. Letzteres ist zwar geeignet, einen effizienten Zugriff auf Daten zu ermoeglichen; ein globales Schema fuer semistrukturierte Daten leidet aber zwangslaeufig an der Irregularitaet der Struktur der Daten. Wegen der vielen Ausnahmen vom intendierten Schema wird ein globales Schema schnell sehr gross und wenig repraesentativ. Damit wird dem Nutzer ein verzerrtes Bild ueber die Daten gegeben. Hingegen koennen partielle Schemata eher ein repraesentatives Bild eines Teils der Daten darstellen. Mit Hilfe statistischer Methoden kann die Guete eines partiellen Schemas bewertet werden, ebenso koennen irrelevante Teile der Datenbank identifiziert werden. Ein Datenbanksystem, das auf partiellen Schemata basiert, ist flexibler und reflektiert den Grad der Strukturierung auf vielen Ebenen. Seine Benutzbarkeit und seine Performanz steigen mit einem hoeheren Grad an Struktur und mit seiner Nutzungsdauer. Partielle Schemata koennen auf zwei Arten gewonnen werden. Erstens koennen sie durch einen Datenbankdesigner bereitgestellt werden. Es ist so gut wie unmoeglich, eine semistrukturierte Datenbank komplett zu modellieren, das Modellieren gewisser Teile ist jedoch denkbar. Zweitens koennen partielle Schemata aus Benutzeranfragen gewonnen werden, wenn nur die Anfragesprache entsprechend entworfen und definiert wird. Wir schlagen vor, eine Anfrage in einen ``Was''- und einen ``Wie''-Teil aufzuspalten. Der ``Was''-Teil wird durch partielle Schemata repraesentiert. Partielle Schemata beinhalten reiche semantische Konzepte, wie Variablendefinitionen und Pfadbeschreibungen, die an Konzepte aus Anfragesprachen angelehnt sind. Mit Variablendefinitionen koennen verschiedene Teile der Datenbank miteinander verbunden werden. Pfadbeschreibungen helfen, durch das Zulassen einer gewissen Unschaerfe, die Irregularitaet der Struktur der Daten zu verdecken. Das Finden von Stellen der Datenbank, die zu einem partiellen Schema passen, bildet die Grundlage fuer alle Arten von Anfragen. Im ``Wie''-Teil der Anfrage werden die gefundenen Stellen der Datenbank fuer die Antwort modifiziert. Dabei koennen Teile der gefundenen Entsprechungen des partiellen Schemas ausgeblendet werden oder auch die Struktur der Antwort voellig veraendert werden. Wir untersuchen die Ausdrucksstaerke unserer Anfragesprache, in dem wir einerseits die Operatoren der relationalen Algebra abbilden und andererseits das Abfragen von XML-Dokumenten demonstrieren. Wir stellen fest, dass das Finden der Entsprechungen eines Schemas (wir nennen ein partielles Schema in der Arbeit nur Schema) den aufwendigsten Teil der Anfragebearbeitung ausmacht. Wir verwenden eine weitere Abstraktionsebene, die der Constraint Satisfaction Probleme, um die Entsprechungen eines Schemas in einer Datenbank zu finden. Constraint Satisfaction Probleme bilden eine allgemeine Klasse von Suchproblemen. Fuer sie existieren bereits zahlreiche Optimierungsalgorithmen und -heuristiken. Die Grundidee besteht darin, Variablen mit zugehoerigen Domaenen einzufuehren und dann die Werte, die verschiedene Variablen gleichzeitig annehmen koennen, ueber Nebenbedingungen zu steuern. In unserem Ansatz wird das Schema in Variablen ueberfuehrt, die Domaenen werden aus der Datenbank gebildet. Nebenbedingungen ergeben sich aus den im Schema vorhandenen Praedikaten, Variablendefinitionen und Pfadbeschreibungen sowie aus der Graphstruktur des Schemas. Es werden zahlreiche Optimierungstechniken fuer Constraint Satisfaction Probleme in der Arbeit vorgestellt. Wir beweisen, dass die Entsprechungen eines Schemas in einer Datenbank ohne Suche und in polynomialer Zeit gefunden werden koennen, wenn das Schema ein Baum ist, keine Variablendefinitionen enthaelt und von der Anforderung der Injektivitaet einer Einbettung abgesehen wird. Zur Optimierung wird das Enthaltensein von Schemata herangezogen. Das Enthaltensein von Schemata kann auf zwei Weisen, je nach Richtung der Enthaltenseinsbeziehung, genutzt werden: Entweder kann der Suchraum fuer ein neues Schema reduziert werden oder es koennen die ersten passenden Stellen zu einem neuen Schema sofort praesentiert werden. Der gesamte Anfrageansatz wurde prototypisch zunaechst in einem Public-Domain Prolog System, spaeter im Constraintsystem ECLiPSe implementiert und mit Anfragen an XML-Dokumente getestet. Dabei wurden die Auswirkungen verschiedener Optimierungen getestet. Ausserdem wird eine grafische Benutzerschnittstelle zur Verfuegung gestellt. / Most of today's data is still stored in files rather than in databases. This fact has become even more evident with the growth of the World Wide Web in the 1990s. Because of that observation, the research area of semistructured data has evolved. Semistructured data is typically stored in documents and has an irregular, partial, and implicit structure. The thesis presents a new framework for querying semistructured data. Traditional database management requires design and ensures declarativity. The possibilities to design are limited in the field of semistructured data, thus, a more flexible approach is needed. We argue that semistructured data should be represented by a set of partial schemata rather than by one complete schema. Because of irregularities of the data, a complete schema would be very large and not representative. Instead, partial schemata can serve as good representations of parts of the data. While finding a complete schema turns out to be difficult, a database designer may be able to provide partial schemata for the database. Also, partial schemata can be extracted from user queries if the query language is designed appropriately. We suggest to split the notion of query into a ``What''- and a ``How''-part. Partial schemata represent the ``What''-part. They cover semantically richer concepts than database schemata traditionally do. Among these concepts are predicates, variable definitions, and path descriptions. Schemata can be used for query optimization, but they also give users hints on the content of the database. Finding the occurrences (matches) of such a schema forms the most important part of query execution. All queries of our approach, such as the focus query or the transformation query, are based on this matching. Query execution can be optimized using knowledge about containment relationships between different schemata. Our approach and the optimization techniques are conceptually modeled and implemented as a prototype on the basis of Constraint Satisfaction Problems (CSPs). CSPs form a general class of search problems for which many techniques and heuristics exist. A CSP consists of variables that have a domain associated to them. Constraints restrict the values that variables can simultaneously take. We transform the problem of finding the matches of a schema in a database to a CSP. We prove that under certain conditions the matches of a schema can be found without any search and in polynomial time. For optimization purposes the containment relationship between schemata is explored. We formulate a sufficient condition for schema containment and test it again using CSP techniques. The containment relationship can be used in two ways depending on the direction of the containment: It is either possible to reduce the search space when looking for matches of a schema, or it is possible to present the first few matches immediately without any search. Our approach has been implemented into the constraint system ECLiPSe and tested using XML documents.

Die parallele Anfragebearbeitung für relationale Datenbankmanagementsysteme (RDBMS) ist wegen ihrer unterschiedlichen Arten der Ausführungsparallelität und den Eigenschaften der zugrunde liegenden parallelen Architektur ein äusserst komplexes Problem. Systemänderungen zur Laufzeit der Anfrage können zusätzlich ein dynamisches Verhalten der ausführenden Komponenten erfordern, um eine nahezu optimale Antwortzeit zu gewährleisten. Diese Arbeit stellt einen neuen, flexiblen Ansatz für die Optimierung und Abarbeitung von komplexen Anfragen vor, der besonders die dynamische Optimierung berücksichtigt. Insbesondere werden in der Arbeit folgende Teile präsentiert: 1. die Architektur eines neuen, verteilt-kooperierenden Komponentensystems beeinflusst von agenten-orientierten Konzepten; 2. der Entwurf und die Realisierung einer neuen Kommunikationsinfrastruktur für die identifizierten Systemkomponenten; 3. der Entwurf und die Implementierung eines flexiblen Anfrageoptimierers mit einem neuen, zufallsbasierten Algorithmus; und 4. der Entwurf und die Realisierung einer parallel arbeitenden Ausführungskomponente unter besonderer Berücksichtigung der dynamischen Anfrageoptimierung. Bei der Entwicklung der Konzepte standen neben den spezifischen Anforderungen für RDBMS besonders die Konfigurierbarkeit und die Erweiterbarkeit des verteilten Systems im Vordergrund. / Parallel query evaluation for relational database management systems (RDBSM) still remains a challenging problem. Modern systems must show near optimal performance in spite of running in a heterogeneous hardware environment, exploiting different ways of parallelism and dealing with unpredictable system load. This thesis paper presents a dynamic and flexible system addressing the issues of optimization and evaluation of relational queries for a distributed and dynamic environment. In particular, this work consists of: 1) the architecture of a distributed system which was inspired by the concepts of software agents, 2) the architecture and the implementation of a communication infrastructure for the system components, 3) the architecture and the implementation of a new query optimization algorithm, and 4) the concept and the implementation of a new query evaluation engine for parallel execution, which enables runtime optimization of queries. Furthermore, the design supports the extension and the configuration of the system and its components.

No description available.