Efficient evaluation of conjunctive queries

Abstract

Konjunktive Abfragen (``Conjunctive Queries'' -- in SQL auch als SELECT-PROJECT-JOIN Abfragen bekannt) sind eine der wichtigsten Klassen von Abfragen im Datenmanagement. Üblicherweise wird angenommen, dass die Abfrage um mehrere Größenordnungen kleiner ist als die Datenbank, weshalb Anfrage-Optimierungstechniken meistens auf die Bewältigung großer Datenmengen ausgerichtet sind. Es gibt jedoch Anwendungen, bei denen die Größe der Abfrage nicht vernachlässigt werden kann.<br />Insbesondere Algorithmen zur Anfragebeantwortung in Datenintegrationssystemen basieren häufig auf dem automatischen Umschreiben von Abfragen, wodurch sehr umfangreiche Abfragen erzeugt werden können. Andere wichtige Einsatzgebiete des Abfrage - Umschreibens sind unter anderem die Abfrageoptimierung unter auf einem Schema definierten Bedingungen sowie die Abfrageoptimierung von Abbildungen zwischen Datenbankschemata.<br />In solchen Szenarien stimmt die übliche Annahme, dass die Datenbankgröße die Abfragegröße bei weitem übersteigt, meist nicht mehr.<br />Diese Arbeit behandelt Fragestellungen im Bezug auf die Beantwortung großer konjunktiver Abfragen (KAs) --- das heißt von Abfragen, deren Größe mit jener der Datenbank vergleichbar ist. Dabei liegt der Schwerpunkt auf der Azyklizitätseigenschaft von KAs: Während im allgemeinen Fall die Abfrageauswertung KAs NP-vollständig ist, ist bekannt dass azyklische AKs nur polynomielle Datenkomplexity (``data complexity'') besitzen.<br />Zur Auswertung azyklischer KAs implementierten wir den Semi-Join Algorithmus von Yannakakis und den DB-Shunt Algorithmus von Gottlob et.\ al. Zur Auswertung von zyklischen Abfragen verwenden wir Techniken wie die Hypertree-Zerlegung (``Hypertree-Decomposition'') und Abfrage-Zerlegung (``Query-decomposition'').<br />Als ein Ergebnis dieser Arbeit wurde ein Modul zur Abfragebeantwortung großer KAs implementiert, welches verfügbare Open-Source Datenbanken wie z.B. die ebenfalls auf Java basierte H2 Datenbank (im ``im-Hauptspeicher'' Modus) leistungsmäßig übertrifft. An Hand der Versuchsergebnisse mit dieser Implementierung wurden darüber hinaus Empfehlungen zur Auswahl der besten Strategie zur Abfrageausführung für verschiedene Arten von KAs formuliert.<br />

Conjunctive queries (or, in SQL terminology, SELECT-PROJECT-JOIN queries) have extremely wide application in data management. It is usually assumed that the typical query is several orders of magnitude smaller in size than the database, and thus the typical query optimizations are concerned with tackling huge datasets. There are applications, however, where the query size can become especially important: in particular, the data integration algorithms often rely on automatic query rewritings, and can potentially generate quite large queries.<br />Other important applications of query rewriting include optimization of queries under schema constraints, and optimization of schema mappings. In contrast to the data querying, in such scenarios the usual assumption of the database size by far exceeding the query size does not hold.<br />The goal of this thesis is to address the issues of evaluating large conjunctive queries (CQ), that is, the queries comparable in size with the database.<br />Our focus is placed on the acyclicity property of CQs: Acyclic CQs are known to have polynomial query complexity, while in the general case the problem of boolean query evaluation is NP-complete. To this end, we implemented the traditional Semi-join algorithm by Yannakakis and the DB-Shunt algorithm by Gottlob et al. For the case of cyclic queries, we made use of such techniques as Hypertree decomposition and Query decomposition.<br />As a result of this thesis, a conjunctive query engine has been implemented, which by far outperforms the available open-source databases (in particular, the Java-based H2 database in the in-memory mode). Based on the experiments with this implementation we formulated recommendations concerning the choice of query evaluation strategy for different classes of CQs.