Efficient join processing is a central task of database management systems. Traditionally, joins between more than two relations are processed by breaking them down into consecutive, pair-wise joins. It can be shown that there are worst-case scenarios in which this method of computing joins causes significant runtime overhead by producing large intermediate results. Recent years have seen the development of new join algorithms that aim to improve performance in scenarios where the traditional method is suboptimal. In this thesis, we examine possible worst-case scenarios and assess their practical relevance. Furthermore, we give an overview of the theory of worstcase optimal join algorithms. As a modern representative of this class of algorithms, we analyze Leapfrog Triejoin, highlighting both theoretical and practical aspects. Lastly, we present and analyze the results of several experiments using Leapfrog Triejoin, by means of which we evaluate the relevance of worst-case optimal join algorithms for modern databases.     «

Efficient join processing is a central task of database management systems. Traditionally, joins between more than two relations are processed by breaking them down into consecutive, pair-wise joins. It can be shown that there are worst-case scenarios in which this method of computing joins causes significant runtime overhead by producing large intermediate results. Recent years have seen the development of new join algorithms that aim to improve performance in scenarios where the traditional me...     »

Die effiziente Verarbeitung von Joins ist eine zentrale Aufgabe eines Datenbankmanagementsystems. Traditionell werden Joins zwischen mehr als zwei Relationen verarbeitet, indem sie in aufeinanderfolgende, paarweise Joins aufgeteilt werden. Es kann gezeigt werden, dass es worst-case Szenarien gibt, in denen diese Methode der Joinverarbeitung signifikanten Mehraufwand versursacht, da große Zwischenergebnisse produziert werden. In den vergangenen Jahren wurden neue Joinalgorithmen entwickelt, welche die Zielsetzung haben, die Leistung in eben solchen Situationen zu verbessern, für die traditionelle Methoden suboptimal sind. In dieser Arbeit werden mögliche worst-case Szenarien untersucht und deren praktische Relevanz eingeschätzt. Des Weiteren geben wir einen Überblick über die Theorie der worst-case optimalen Joinalgorithmen. Wir analysieren Leapfrog Triejoin als moderner Repräsentant dieser Klasse von Algorithmen, wobei sowohl theoretische als auch praktische Aspekte betrachtet werden. Letztendlich präsentieren und analysieren wir die Ergebnisse mehrerer Experimente mit Leapfrog Triejoin, welche dazu dienen, die Relevanz von worst-case optimalen Joinalgorithmen für moderne Datenbanken zu evaluieren.     «

Die effiziente Verarbeitung von Joins ist eine zentrale Aufgabe eines Datenbankmanagementsystems. Traditionell werden Joins zwischen mehr als zwei Relationen verarbeitet, indem sie in aufeinanderfolgende, paarweise Joins aufgeteilt werden. Es kann gezeigt werden, dass es worst-case Szenarien gibt, in denen diese Methode der Joinverarbeitung signifikanten Mehraufwand versursacht, da große Zwischenergebnisse produziert werden. In den vergangenen Jahren wurden neue Joinalgorithmen entwickelt, welch...     »