|
Algebraic Query Optimization in Database Systems (Algebraische Anfrageoptimierung in Datenbanksystemen)
Scheufele, Wolfgang
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/18
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-188
|
|
Document Type:
|
Doctoral dissertation
|
|
Year of publication:
|
1998
|
|
The title of a journal, publication series:
|
None
|
|
Publishing house:
|
Universität Mannheim
|
|
Evaluator:
|
Moerkotte, Guido
|
|
Date of oral examination:
|
22 December 1999
|
|
Publication language:
|
English
|
|
Institution:
|
School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
|
|
Subject:
|
004 Computer science, internet
|
|
Classification:
|
CCS:
H.2.4 ,
|
|
Subject headings (SWD):
|
Relationales Datenbanksystem , Objektorientiertes Datenbanksystem , Optimierung , Komplexität
|
|
Individual keywords (German):
|
Anfrageoptimierung , Konjunktive Anfrage , Dynamisches Programmieren
|
|
Keywords (English):
|
Query Optimization , Conjunctive Query , Dynamic Programming
|
|
Abstract:
|
The thesis investigates different problem classes in algebraic query optimization. For the problem of computing optimal left-deep processing trees with cross products for chain queries and ASI cost functions we present two efficient algorithms. Although, in practice both algorithms yield identical results we have not been able to prove this. For the case of acyclic query graphs, left-deep processing trees, expensive selection and join predicates and ASI cost functions we describe a polynomial time algorithm which is based on a job sequencing algorithm. The algorithm assumes that the set of expensive selections that can be applied directly to the base relations can be guessed. The cheapest plans can be found within the search space of bushy processing trees with cross products. We prove that the problem is NP-hard in this case. The rest of the thesis deals with the general problem of computing optimal bushy processing trees for arbitrary query graphs and expensive selection and join predicates. For this problem we present three efficient dynamic programming algorithms. Our algorithms can handle different join algorithms, split conjunctive predicates, and exploit structural information from the join graph to speed up computation. The time and space complexities of the algorithms are analyzed carefully and efficient implementations based on bitvector arithmetic are presented.
|
|
Translation of the title:
|
null
(German)
|
|
Translation of the abstract:
|
In der Dissertation werden verschiedene Problemklassen der algebraischen Anfrageoptimierung untersucht. Zunächst werden für die Berechnung optimaler linkstiefer Auswertungsbäume mit Kreuzprodukten im Fall kettenförmiger Anfragegraphen und ASI-Kostenfunktionen zwei effiziente Algorithmen vorgestellt. Obwohl beide Algorithmen in der Praxis identische Ergebnisse liefern, konnte dies nicht bewiesen werden. Für den Fall azyklischer Anfragegraphen, linkstiefer Auswertungsbäume, teurer Selektions- und Joinprädikate und ASI-Kostenfunktionen wird ein polynomialer Algorithmus beschrieben, der auf einem Job-Sequencing-Algorithmus basiert. Der Algorithmus setzt voraus, dass die Menge der direkt auf die Basisrelationen anzuwendenden, teuren Selektionen erraten werden kann. Die kostengünstigsten Auswertungsbäume findet man im Suchraum der verzweigten Bäume mit Kreuzprodukten. Es wird gezeigt, dass das Problem für diesen Fall NP-hart ist. Für das allgemeine Problem der Berechnung optimaler verzweigter Auswertungsbäume für beliebige Anfragegraphen und teure Selektions- und Joinprädikate werden drei effiziente Algorithmen vorgestellt. Die Algorithmen basieren auf Dynamischem Programmieren und sind in der Lage verschiedene Joinalgorithmen zu berücksichtigen, konjunktive Prädikate zu trennen und die Struktur des Anfragegraphen auszunutzen um die Berechnung zu beschleunigen. Die Zeit- und Platzkomplexitäten der Algorithmen werden sorgfältig analysiert und effiziente, auf Bitvektor-Arithmetik basierende Implementierungen beschrieben.
(German)
|
|
Additional information:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Search Authors in
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)