Overview

Immer komplexere Anwendungen stellen steigende Leistungsanforderungen an relationale Datenbanksysteme. Um diese zu erf}llen, ist eine Parallelisierung der Anfragebearbeitung erforderlich. Als Beitrag hierzu wird ein Verfahren zur ]bersetzung von Anwenderanfragen, die in der Standard-Sprache SQL formuliert sind, in effiziente parallele Bearbeitungspl{ne vorgestellt. Dabei wird die Technik der regelbasierten Optimierung zugrundegelegt. Von generellem Nutzen f}r die korrekte und effiziente Bearbeitung von SQL-Anfragen ist die Integration bekannter Optimierungstechniken auf der Basis einer erweiterten relationalen Algebra. Mit einer systematischen und kompaktenBeschreibung paralleler Bearbeitungspl{ne wird dar}ber hinaus ein Beitrag zum Verst{ndnis der Parallelisierbarkeit komplexer relationaler Anfragen geleistet.

Full Product Details

Author:   Günter v. Bültzingsloewen ,  G Von B'Ultzingsloewen
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Dimensions:   Width: 15.50cm , Height: 1.40cm , Length: 23.50cm
Weight:   0.410kg
ISBN:  

9783540542520

ISBN 10:   3540542523
Pages:   245
Publication Date:   16 January 1992
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Out of stock  
The supplier is temporarily out of stock of this item. It will be ordered for you on backorder and shipped when it becomes available.
Language:   German

Table of Contents

1 Einleitung.- 1.1 Einfuhrung des Optimierungsproblems.- 1.1.1 Anfragen.- 1.1.2 Parallele Anfragebearbeitung.- 1.1.3 Optimierungsziel.- 1.2 Techniken der Anfrageoptimierung.- 1.2.1 Komplexitatsaspekte.- 1.2.2 Regelbasierte Optimierung.- 1.2.3 Anfragedarstellung.- 1.2.4 Transformationsregeln.- 1.2.5 Suchraum und Suchstrategie.- 1.2.6 Kostenbewertung.- 1.3 Kernprobleme der Arbeit.- 1.4 Vorgehensweise.- 1.5 Abgrenzung gegenuber anderen Problemstellungen.- 2 Grundlagen und Literaturuberblick.- 2.1 Relationale Anfragesprachen.- 2.1.1 Relationales Datenmodell.- 2.1.2 Relationale Algebra.- 2.1.3 Relationaler Kalkul.- 2.1.4 Erweiterung um Aggregatfunktionen.- 2.1.5 SQL.- 2.2 Parallele Anfragebearbeitung.- 2.2.1 Klassifikation von Systemumgebungen.- 2.2.2 Datenverteilung.- 2.2.3 Bearbeitungsmethoden.- 2.2.3.1 Zugriff auf eine Basisrelation.- 2.2.3.2 Verbund zweier Relationen (Join).- 2.2.3.3 Zusammenfassung.- 2.2.4 Bearbeitungsplan.- 2.2.4.1 Datenflussprogramm.- 2.2.4.2 Parallelisierung.- 2.2.4.3 Zuordnungsentscheidungen.- 2.3 Anfragetransformation.- 2.3.1 Transformation in der Algebra.- 2.3.2 Transformation im Kalkul.- 2.3.3 Transformation vom Kalkul in die Algebra.- 2.3.4 Transformation und UEbersetzung von SQL-Anfragen.- 2.4 Parallelisierung.- 2.4.1 Ansatze zur Parallelisierung wahrend der Optimierung.- 2.4.2 Theorie der Ablaufplanung.- 2.4.2.1 Problemstellung.- 2.4.2.2 Konstruktion von Ablaufplanen minimaler Lange.- 3 Grundkonzept des Optimierers.- 3.1 Loesungsansatz.- 3.1.1 Regelbasierte Optimierung.- 3.1.2 Anforderungen an Anfragereprasentation und Transformationsregeln.- 3.1.3 Konkretisierung der Vorgehensweise.- 3.1.4 Prazisierung der Optimierungsphasen.- 3.2 Anfragereprasentation.- 3.2.1 Funktionale Darstellungsform.- 3.2.2 Erweiterte relationale Algebra.- 3.2.3 Bearbeitungsplane.- 3.3 Anfragetransformation und Generierung algebraischer Ausdrucke.- 3.4 Generierung paralleler Bearbeitungsplane.- 3.4.1 Transformationsregeln.- 3.4.2 Parallefisierungsstrategien.- 4 Erweiterte relationale Algebra und SQL.- 4.1 Spezifikation der erweiterten relationalen Algebra.- 4.1.1 Definition der Werte und Typen.- 4.1.2 Definition der Grundfunktionen.- 4.1.2.1 Komposition von Funktionen.- 4.1.2.2 Funktionen auf atomaren Datentypen.- 4.1.2.3 Tupelfunktionen.- 4.1.2.4 Mengenfunktionen.- 4.1.3 Relationale Operatoren.- 4.1.4 Ausdrucke.- 4.1.5 Weitere Schreibweisen.- 4.1.5.1 Kompakte Darstellung von Tupelkonstruktoren.- 4.1.5.2 Kompakte Darstellung von Pradikaten.- 4.1.5.3 Ableitbare relationale Operatoren.- 4.1.6 Einordnung der bisherigen Darstellungsformen.- 4.2 Die Anfragesprache SQL.- 4.2.1 Datenmodell.- 4.2.2 Syntax.- 4.2.3 Semantik: UEbersetzung in die erweiterte relationale Algebra.- 4.2.3.1 Terme.- 4.2.3.2 Pradikate.- 4.2.3.3 Anfragen.- 4.2.3.4 Unteranfragen.- 4.3 Beispiele fur die UEbersetzung von SQL-Anfragen.- 5 Grundlagen der Anfragetransformation.- 5.1 UEberblick.- 5.2 Pradikat-Transformation.- 5.3 Gruppierende Abbildungen.- 5.3.1 Definition.- 5.3.2 Konstruktion.- 5.4 Ersetzung nicht geschlossener Ausdrucke.- 5.4.1 Korrekte Ersetzung.- 5.4.2 Verlustfreie Ersetzung.- 5.4.3 Aufloesung von Unteranfrage-Pradikaten.- 5.4.3.1 Korrekte Aufloesung einer Selektion.- 5.4.3.2 Verbesserungsmoeglichkeiten.- 5.4.3.3 Korrekte Aufloesung einer Outer-Selektion.- 5.5 Algebraische Transformationsregeln.- 5.5.1 Distributiv- und Kommutativgesetze.- 5.5.2 Einsparung von Joins.- 5.6 Zusammenfassung.- 6 Anfragetransformation und Generierung algebraischer Ausdrucke.- 6.1 UEberblick.- 6.2 Standardisierung.- 6.2.1 Pradikat-Transformation.- 6.2.2 Aufloesung von Existenzquantoren.- 6.2.3 Aufloesung von Allquantoren.- 6.2.4 Aufloesung von Aggregatfunktionen.- 6.2.5 Ergebnis der Standardisierung.- 6.3 Verbesserung algebraischer Ausdrucke.- 6.3.1 Durchschieben der Projektion.- 6.3.2 Einsparung von Joins.- 6.4 Beispiele fur Standardisierung und Verbesserung.- 6.5 Aufzahlung algebraischer Ausdrucke.- 6.5.1 Zielsetzung.- 6.5.2 Plazierung und Integration von Aufloesungen.- 6.5.3 Join-Reihenfolge.- 6.5.4 Ergebnis der Aufzahlung.- 7 Implementierung relationaler Operatoren.- 7.1 Grundlagen.- 7.1.1 Tupellisten.- 7.1.2 Korrekte Implementierung relationaler Operatoren.- 7.1.3 Eigenschaften von Tupellisten.- 7.2 Zugriffspfade.- 7.2.1 Zugriff auf Basisrelationen.- 7.2.1.1 Physisches Datenbankschema.- 7.2.1.2 Sequentieller Zugriff.- 7.2.1.3 Selektiver Zugriff.- 7.2.2 Zugriff auf Tupellisten.- 7.2.3 Zugriff auf atomare Werte und Tupel.- 7.3 Sequentielle Bearbeitung relationaler Operatoren.- 7.3.1 Konkatenation.- 7.3.2 Filterung.- 7.3.3 Join.- 7.3.4 Aggregierung.- 7.3.5 Division.- 7.3.6 Ergebnisbildung.- 7.3.7 Beispiel fur eine sequentielle Implementierung.- 7.4 Einsatz von Indizes.- 7.5 Ausnutzung einer Sortierung.- 7.5.1 Merge-Join.- 7.5.2 Aggregierung.- 7.5.3 Beispiel fur die Ausnutzung einer Sortierung.- 7.6 Verwendung von Hashing.- 7.6.1 Hashing-Join.- 7.6.2 Aggregierung.- 7.6.3 Beispiel fur den Einsatz von Hashing.- 7.7 Zerlegung von Operationen in Phasen.- 7.8 Zusammenfassung.- 8 Grundlagen der Parallelisierung.- 8.1 UEberblick.- 8.2 Datenflussprogramm.- 8.2.1 Struktur.- 8.2.2 Konstruktion.- 8.3 Meta-Datenflussprogramm.- 8.3.1 Struktur.- 8.3.2 Konstruktion des Meta-Datenflussprogramms: Node Splitting.- 8.3.2.1 Zugriff auf eine Basisrelation.- 8.3.2.2 Filterung.- 8.3.2.3 Existenzquantor.- 8.3.2.4 Join und Semijoin.- 8.3.2.5 Merge-Join.- 8.3.2.6 Aggregierung.- 8.3.3 Konstruktion des Meta-Datenflussprogramms: Pipelining.- 8.3.4 Beispiel fur die Konstruktion eines Meta-Datenflussprogramms.- 8.4 Transformationen auf dem Meta-Datenflussprogramm.- 8.4.1 Node Splitting.- 8.4.2 Pipelining.- 8.4.3 Beispiel fur den Einsatz von Node Splitting und Pipelining.- 8.5 Abbildung des Meta-Datenflussprogramms auf ein Datenflussprogramm.- 8.5.1 Generierung der Teilknoten.- 8.5.2 Vorliegende Zerlegung der Operanden.- 8.5.3 Partitionierung und Anpassung des Operandenzugriffs.- 8.5.4 Beispiel fur die Abbildung auf ein Datenflussprogramm.- 8.5.5 Einsparung uberflussiger Knoten.- 8.6 Generierung eines parallelen Bearbeitungsplans.- 8.7 Zusammenfassung.- 9 Kostenmodell.- 9.1 Zielsetzung und Vorgehensweise.- 9.2 Kostenarten.- 9.3 Kostenanteile.- 9.4 Kostenfaktoren.- 9.5 Kostenfunktionen.- 9.5.1 Kosten der Zugriffsoperationen.- 9.5.2 Kosten der Bearbeitungsoperationen.- 9.5.3 Kosten der Ergebnisubermittlung.- 9.6 Bewertung eines parallelen Bearbeitungsplans.- 9.6.1 Definition und Kennzahlen eines Parallelitatsprofils.- 9.6.2 Konstruktion eines Parallelitatsprofils.- 9.6.3 Bestimmung der Bearbeitungskosten und der Bearbeitungszeit.- 9.7 Bewertung eines Meta-Datenflussprogramms.- 9.7.1 Ausgangspunkt.- 9.7.2 Kosten der Teilknoten eines Metaknotens.- 9.7.3 Initiale Verteilung von Teilknoten auf Prozessoren.- 9.7.4 Konstruktion von Pipeboxen.- 9.7.5 Zusammensetzen der Pipeboxen zu einem Parallelitatsprofil.- 9.7.6 Bestimmung der Bearbeitungskosten und der Bearbeitungszeit.- 9.7.7 Neubewertung nach einem Parallelisierungsschritt.- 9.7.8 Beispiel fur die Bewertung anhand des Parallelitatsprofils.- 10 Parallelisierungsstrategien.- 10.1 Aufgaben einer Parallelisierungsstrategie.- 10.2 Heuristiken zur Erzeugung eines Meta-Datenflussprogramms.- 10.2.1 Konstruktion des Meta-Datenflussprogramms.- 10.2.1.1 Auswahl des Parallelisierungsschemas beim Join.- 10.2.1.2 Auswahl des Parallelisierungsschemas bei der Aggregierung.- 10.2.1.3 Beispiel.- 10.2.2 Phasenzerlegung: Vermeidung von Hauptspeicheruberlauf.- 10.2.3 Node Splitting und Pipelining zur Vermeidung von Auslagerungen.- 10.2.4 Kopplung der Parallelisierung aufeinanderfolgender Knoten.- 10.3 Heuristiken auf der Basis des Parallelitatsprofils.- 10.3.1 Betrachtung zeitkritischer Meta-Pipes.- 10.3.2 Auswahl von Meta-Pipes fur den Einsatz von Node Splitting.- 10.3.3 Parallelisierung einer Meta-Pipe durch Node Splitting.- 10.3.4 Auswahl von Meta-Pipes fur den Einsatz von Pipelining.- 10.4 Heuristiken fur die Zuordnung.- 10.5 Zusammenfassung.- 11 Zusammenfassung und Ausblick.- 11.1 Hauptergebnisse der Arbeit.- 11.2 Weiterfuhrende Arbeiten.

Reviews

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions