|
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
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
1998
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Moerkotte, Guido
|
|
Datum der mündl. Prüfung:
|
22 Dezember 1999
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science III (Moerkotte 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
Fachklassifikation:
|
CCS:
H.2.4 ,
|
|
Normierte Schlagwörter (SWD):
|
Relationales Datenbanksystem , Objektorientiertes Datenbanksystem , Optimierung , Komplexität
|
|
Freie Schlagwörter (Deutsch):
|
Anfrageoptimierung , Konjunktive Anfrage , Dynamisches Programmieren
|
|
Freie Schlagwörter (Englisch):
|
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.
|
|
Übersetzter Titel:
|
null
(Deutsch)
|
|
Übersetzung des Abstracts:
|
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.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)