Algebraic Query Optimization in Database Systems (Algebraische Anfrageoptimierung in Datenbanksystemen)


Scheufele, Wolfgang


[img]
Preview
PDF
18_1.pdf - Published

Download (1MB)

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
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 > Praktische Informatik III (Moerkotte)
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.




+ Citation Example and Export

Scheufele, Wolfgang (1998) Algebraic Query Optimization in Database Systems (Algebraische Anfrageoptimierung in Datenbanksystemen). Open Access [Doctoral dissertation]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item