Datenbanksysteme: Konzepte Und Techniken Der Implementierung

ISBN-13: 9783642980176 / Niemiecki / Miękka / 2012 / 600 str.

Theo H. Rder; Erhard Rahm

Opis

Das Buch bietet eine umfassende und aktuelle Darstellung der Konzepte und Techniken zur Implementierung von Datenbanksystemen. Ausgangspunkt ist ein hierarchisches Architekturmodell: Die Schichten dieses Modells ermoglichen es, den Systemaufbau, die Einordnung der bereitzustellenden Funktionen und ihr Zusammenspiel detailliert zu beschreiben.
Es werden alle Aspekte der Datenabbildung mit den erforderlichen Algorithmen und Datenstrukturen behandelt, also vor allem Externspeicherabbildung, Realisierung von Speicherungsstrukturen und Zugriffspfaden sowie die Ableitung logischer Sichten. Neben der Datenabbildung, in deren Aufgaben sich Speicher-, Zugriffs- und Datensystem teilen, steht als zweiter Schwerpunkt des Buches das Transaktionskonzept und seine Erweiterungen. Dabei werden insbesondere alle Funktionen zur Synchronisation des Mehrbenutzerbetriebs und zur Wiederherstellung der Datenbank im Fehlerfall (Logging und Recovery) dargestellt."

Spis treści

I: Architektur von Datenbanksystemen.- 1 Architektur von Datenbanksystemen.- 1.1 Anforderungen an Datenbanksysteme.- 1.1.1 Entwicklung von Anwendungssystemen.- 1.1.2 Entwurfsziele.- 1.2 DB-Schemaarchitektur nach ANSI/SPARC.- 1.2.1 Beschreibungsrahmen für DBS-Schnittstellen.- 1.2.2 Die wichtigsten DBS-Schnittstellen.- 1.3 Schichtenmodell-Architektur.- 1.3.1 Anforderungen an den Systementwurf.- 1.3.2 Architekturprinzipien.- 1.3.3 Ein einfaches Schichtenmodell.- 1.3.4 Integration von Metadaten- und Transaktionsverwaltung.- 1.3.5 Schichtenmodell eines datenunabhängigen DBS.- 1.3.6 Optimierungsüberlegungen.- 1.4 Erweiterungen der DBS-Architektur.- 1.4.1 DBS-Kern-Architeküir.- 1.4.2 Client/Server-Architekturen.- 1.4.3 Verteilte und parallele DBS-Architekturen.- 1.4.4 Architekturen von Transaktionssystemen.- 1.4.5 Komponentenbasierte Systemarchitekturen.- 1.5 Themenüberblick.- II: Speichersystem.- 2 Konzepte und Komponenten der E/A-Architektur.- 2.1 Die großen Einflußfäktoren.- 2.2 Nutzung von Speicherhierarchien.- 2.2.1 Aufbau einer Speicherhierarchie.- 2.2.2 Arbeitsweise einer Speicherhierarchie.- 2.3 Halbleiterspeicher.- 2.3.1 Hauptspeicher.- 2.3.2 Cache-Speicher.- 2.3.3 Erweiterter Hauptspeicher.- 2.3.4 Solid State Disks.- 2.4 Aufbau und Arbeitsweise von Magnetplatten.- 2.4.1 Aufzeichnungskomponente.- 2.4.2 Positioniemngskomponente.- 2.4.3 Sequentieller vs. wahlfreier Zugriff.- 2.4.4 Platten-Controller.- 2.5 Organisationsformen für Magnetplatten.- 2.5.1 Disk-Farm.- 2.5.2 Disk-Array.- 2.6 Maßnahmen zur E/A-Optimierung.- 2.7 Überblick über die weiteren Speichermedien.- 2.7.1 Magnetbänder.- 2.7.2 Optische und magneto-optische Speicher.- 3 Dateien und Blöcke.- 3.1 Aufgaben der Extemspeicherverwaltung.- 3.2 Realisierung eines Dateisystems.- 3.2.1 Dateikonzept.- 3.2.2 Dateisystem.- 3.3 Blockzuordnung bei Magnetplatten.- 3.3.1 Statische Dateizuordnung.- 3.3.2 Dynamische Extent-Zuordnung.- 3.3.3 Dynamische Blockzuordnung.- 3.3.4 Versetzungsverfahren.- 3.3.5 Log-strukturierte Dateien.- 3.4 Kontrolle der E/A-Operationen.- 3.4.1 Fehlerbehandlung bei Magnetplatten.- 3.4.2 Erhöhung der Fehlertoleranz.- 3.4.3 Erkennung von fehlerhaften Blöcken.- 3.4.4 Schutz des Datentransfers.- 3.5 DBS-Unterstützung für Dateisysteme.- 4 Segmente und Seiten.- 4.1 Aufgaben der Abbildungsschicht.- 4.2 Segmente mit sichtbaren Seitengrenzen.- 4.3 Verfahren der Seitenabbildung.- 4.3.1 Direkte Seitenadressierung.- 4.3.2 Indirekte Seitenadressierung.- 4.4 Einbringstrategien für Änderungen.- 4.4.1 Schattenspeicherkonzept.- 4.4.2 Zusatzdatei-Konzept.- 5 DB-Pufferverwaltung.- 5.1 Aufgaben und Charakteristika.- 5.1.1 Unterschiede zur BS-Speicherverwaltung.- 5.1.2 Allgemeine Arbeitsweise.- 5.1.3 Eigenschaften von Seitenreferenzfolgen.- 5.2 Auffinden einer Seite.- 5.3 Speicherzuteilung im DB-Puffer.- 5.3.1 Klassifikation von Speicherzuteilungsstrategien.- 5.3.2 Bestimmung von dynamischen Partitionen.- 5.4 Ersetzungsverfahren für Seiten.- 5.4.1 Prefetching und Demand-Fetching.- 5.4.2 Klassifikation und Bewertung.- 5.4.3 Behandlung geänderter Seiten.- 5.5 Nutzung von Kontextwissen.- 5.5.1 Offene Ersetzungsprobleme.- 5.5.2 Modellierung des Pufferbedarfs.- 5.5.3 Prioritätsgesteuerte Seitenersetzung.- 5.6 Seiten variabler Größe.- 5.7 Betriebsprobleme.- 5.7.1 Virtuelle Betriebssystemumgebung.- 5.7.2 Maßnahmen zur Lastkontrolle.- III: Zugriffssystem.- 6 Speicherungsstrukturen.- 6.1 Freispeicherverwaltung.- 6.2 Adressierung von Sätzen.- 6.2.1 Externspeicherbasierte Adressierung.- 6.2.2 Hauptspeicherbasierte Adressierung — Swizzling.- 6.3 Abbildung von Sätzen.- 6.3.1 Speicherung von linearen Sätzen.- 6.3.2 Techniken der Satzdarstellunng.- 6.3.3 Darstellung komplexer Objekte.- 6.3.4 Unterstützung von Cluster-Bildung.- 6.4 Realisierung langer Felder.- 6.4.1 Lange Felder als B*-Baum-Varianten.- 6.4.2 Lange Felder als sequentielle Strukturen.- 6.4.3 Lange Felder mit Segmenten variabler Größe.- 7 Eindimensionale Zugriffspfade.- 7.1 Allgemeine Entwurfsüberlegungen.- 7.2 Sequentielle Zugriffspfade.- 7.2.1 Sequentielle Listen.- 7.2.2 Gekettete Listen.- 7.3 Baumstrukturierte Zugriffspfade.- 7.3.1 Binäre Suchbäume.- 7.3.2 Mehrwegbäume.- 7.3.3 Digitalbäume.- 7.4 Statische Hash-Verfahren.- 7.4.1 Kollisionsfreie Satzzuordnung.- 7.4.2 Verfahren mit Kollisionsbehandlung.- 7.4.3 Überlaufbehandlung.- 7.4.4 Externes Hashing mit Separatoren.- 7.5 Dynamische Hash-Verfahren.- 7.5.1 Verfahren mit Indexnutzung.- 7.5.2 Verfahren ohne Indexnutzung.- 7.6 Sekundäre Zugriffspfade.- 7.6.1 Verknüpfungsstrukturen für Satzmengen.- 7.6.2 Implementierung der Invertierung.- 7.6.3 Erweiterungen der Invertiemngsverfahren.- 7.7 Zusammenfassende Bewertung.- 8 Typübergreifende Zugriffspfade.- 8.1 Hierarchische Zugriffspfade:.- 8.1.1 Spezielle Charakteristika.- 8.1.2 Verknüpfungsstrukturen für zugehörige Sätze.- 8.2 Verallgemeinerte Zugriffspfadstruktur.- 8.2.1 Realisiemngsidee.- 8.2.2 Vorteile der Verallgemeinerung.- 8.3 Verbund- und Pfadindexe.- 8.3.1 Verbundindex.- 8.3.2 Mehrverbundindex.- 8.3.3 Pfadindex.- 8.4 Zusammenfassender Vergleich.- 9 Melirdimensionale Zugriffspfade.- 9.1 Allgemeine Anforderungen und Probleme.- 9.1.1 Klassifikation der Anfragetypen.- 9.1.2 Anforderungen an die Objektabbildung.- 9.2 Mehrattributzugriff über eindimensionale Zugriffspfade.- 9.2.1 Separate Attribute als Schlüssel.- 9.2.2 Konkatenierte Attribute als Schlüssel.- 9.3 Organisation der Datensätze.- 9.3.1 Quadranten-Baum.- 9.3.2 Mehrschlüssel-Hashing.- 9.3.3 Mehrdimensionaler binärer Suchbaum (k-d-Baum).- 9.4 Organisation des umgebenden Datenraüms — Divide and Conquer.- 9.4.1 Lineare Einbettungen.- 9.4.2 Heterogener k-d-Baum.- 9.4.3 k-d-B-Baum.- 9.4.4 hB-Baum.- 9.5 Organisation des umgebenden Datenraums — Dimensionsverfeinerung.- 9.5.1 Prinzip der Dimensions Verfeinerung.- 9.5.2 Grid-File.- 9.5.3 Interpolationsbasiertes Grid-File.- 9.5.4 Mehrdimensionales dynamisches Hashing.- 9.6 Zugriffspfade für räumlich ausgedehnte Objekte.- 9.6.1 Abbildungsprinzipien.- 9.6.2 R-Baum.- 9.6.3 R+-Raum.- 9.6.4 Mehrschichtenstrukturen.- 9.7 Verallgemeinerte Suchbäume für DBS.- 9.7.1 Struktur und Eigenschaften des GiST.- 9.7.2 Die wesentlichen Parameter.- 9.7.3 Spezialisierung durch Schlüssehnethoden.- 9.7.4 Weitergehende Forschungsaspekte.- 9.8 Zusammenfassung und Vergleich.- IV: Datensystem.- 10 Satzorientierte DB-Schnittstelle.- 10.1 Objekte und Operatoren.- 10.2 Aufgaben und Funktionen dés DB-Katalogs.- 10.3 Satzorientierte DB-Verarbeitung.- 10.3.1 Abbildung von externen Sätzen.- 10.3.2 Kontextfreie Operationen.- 10.3.3 Navigationskonzepte.- 10.3.4 Implementierung von Scans.- 10.3.5 Verarbeitung großer Objekte.- 10.4 Einsatz eines Sortieroperators.- 10.4.1 Unterstützung komplexer DB-Operationen.- 10.4.2 Entwurfsüberlegungen für einen Sortieroperator.- 10.4.3 Optionen des Sortieroperators.- 10.5 Scheduling und Lastkontrolle von Transaktionen.- 11 Implementierung von relationalen Operatoren.- 11.1 Operatoren auf einer Relation.- 11.1.1 Planoperatoren zur Modifikation.- 11.1.2 Planoperatoren zur Selektion.- 11.2 Operatoren auf mehreren Relationen.- 11.3 Implementierung der Verbundoperation.- 11.3.1 Nested-Loop-Verbund.- 11.3.2 Sort-Merge-Verbund.- 11.3.3 Hash-Verbund.- 11.3.4 Semi-Verbund und Bitfilterung.- 11.3.5 Nutzung von typübergreifenden Zugriffspfaden.- 11.3.6 Vergleich der Verbundmethoden.- 11.4 Weitere binäre Operatoren.- 12 Mengenorientierte DB-Schnittstelle.- 12.1 Übersetzung von DB-Anweisungen.- 12.1.1 Allgemeine Aufgaben.- 12.1.2 Ausdrucksmächtigkeit mengenorientierter DB-Sprachen.- 12.2 Anbindung an Anwendungsprogramme.- 12.3 Anbindung mengenorientierter DB-Schnittstellen.- 12.4 Intemdarstellung einer Anfrage.- 12.5 Anfrageoptimierung.- 12.5.1 Standardisierung einer Anfrage.- 12.5.2 Vereinfachung einer Anfrage.- 12.5.3 Anfragerestrukturierung.- 12.5.4 Anfragetransformation.- 12.5.5 Kostenmodelle und Kostenberechnung.- 12.6 Code-Generierung.- 12.7 .Ausführung von DB-Anweisungen.- 12.7.1 Ausführung der vorübersetzten Zugriffsmodule.- 12.7.2 Behandlung von Ad-hoc-Anfragen.- V: Transaktionsverwaltung.- 13 Das Transaktionsparadigma.- 13.1 Die ACID-Eigenschaften.- 13.2 Benutzerschnittstelle.- 13.3 Integritätskontrolle.- 13.3.1 Arten von Integritätsbedingungen.- 13.3.2 Trigger-Konzept und ECA-Regeln.- 13.3.3 Implementierungsaspekte.- 14 Synchronisation.- 14.1 Anomalien im Mehrbenutzerbetrieb.- 14.1.1 Verlorengegangene Änderungen (Lost Update).- 14.1.2 Zugriff auf schmutzige Daten (Dirty Read, Dirty Write).- 14.1.3 Nicht-wiederholbares Lesen (Non-repeatable Read).- 14.1.4 Phantom-Problem.- 14.2 Das Korrektheitskriterium der Serialisierbarkeit.- 14.3 Überblick zu Synchronisations verfahren.- 14.4 Grundlagen von Sperrverfahren.- 14.4.1 Zwei-Phasen-Sperrverfahren.- 14.4.2 RX-Sperrverfahren.- 14.4.3 Behandlung von Sperrkonversionen.- 14.4.4 Logische vs. physische Sperren.- 14.5 Konsistenzstufen.- 14.5.1 Konsistenzstufen nach [GRAY76].- 14.5.2 Cursor Stability.- 14.5.3 Konsistenzstufen in SQL92.- 14.6 Hierarchische Sperrverfahren.- 14.6.1 Anwartschaftssperren.- 14.6.2 Hierarchische Sperren in objektorientierten DBS.- 14.7 Deadlock-Behandlung.- 14.7.1 Deadlock-Verhütung.- 14.7.2 Deadlock-Vermeidung.- 14.7.3 Timeout-Verfahren.- 14.7.4 Deadlock-Erkennung.- 14.7.5 Abschließende Bemerkungen.- 14.8 Weitere Verfahrensklassen und Optimierungen.- 14.8.1 Optimistische Synchronisation.- 14.8.2 Zeitmarkenverfahren.- 14.8.3 Mehrversionen-Synchronisation.- 14.8.4 Synchronisation auf Hot-Spot-Objekten.- 14.9 Leistungsbewertung von Synchronisationsverfahren.- 14.9.1 Einflußfaktoren.- 14.9.2 Lastkontrolle.- 15 Logging und Recovery.- 15.1 Fehler-und Recovery-Arten.- 15.1.1 Transaktionsfehler.- 15.1.2 Systemfehler.- 15.1.3 Geräte- bzw. Externspeicherfehler.- 15.1.4 Katastrophen-Recovery.- 15.1.5 Grenzen der Recovery.- 15.2 Logging-Techniken.- 15.2.1 Physisches Logging.- 15.2.2 Logisches Logging.- 15.2.3 Physiologisches Logging.- 15.3 Abhängigkeiten zu anderen Systemkomponenten.- 15.3.1 Einfluß der Einbringstrategie.- 15.3.2 Einfluß des Sperrgranulats.- 15.3.3 Ausschreiben geänderter Seiten.- 15.3.4 WAL-Prinzip und Commit-Regel.- 15.3.5 Commit-Verarbeitung.- 15.4 Sicherungspunkte.- 15.4.1 Direkte Sicherungspunkte.- 15.4.2 Fuzzy Checkpoints.- 15.4.3 Klassifikation von DB-Recovery-Verfahren.- 15.5 Aufbau der Log-Datei.- 15.5.1 Log-Satzarten.- 15.5.2 Begrenzung des Log-Umfangs.- 15.6 Crash-Recovery.- 15.6.1 Überblick zur Restart-Prozedur.- 15.6.2 Redo-Recovery.- 15.6.3 Compensation Log Records (CLR).- 15.6.4 Crash-Recovery beim Schattenspeicherkonzept.- 15.7 Geräte-Recovery.- 15.7.1 Erstellung vollständiger Archivkopien.- 15.7.2 Inkrementelles Dumping.- 15.7.3 Alternativen zur Geräte-Recovery.- 15.8 Verteilte Commit-Behandlung.- 16 Erweiterungen des Transaktionskonzepts.- 16.1 Beschränkungen des ACID-Konzepts.- 16.2 Transaktionen mit Rücksetzpunkten.- 16.3 Geschachtelte Transaktionen.- 16.3.1 Freiheitsgrade im Modell geschachtelter Transaktionen.- 16.3.2 Regeln der Zusammenarbeit in geschachtelten Transaktionen.- 16.3.3 Synchronisation geschachtelter Transaktionen.- 16.4 Offen geschachtelte Transaktionen.- 16.4.1 Synchronisationsprobleme.- 16.4.2 Kompensationsbasierte Recovery.- 16.5 Mehrebenen-Transaktionen.- 16.6 Langlebige Aktivitäten.- 16.6.1 Das Konzept der Sagas.- 16.6.2 ConTracts.- 16.7 Datenbankverarbeitung in Entwurfsumgebungen.- VI: Ausblick.- 17 Ausblick.- 17.1 Universal Storage.- 17.1.1 SQL3-Standard.- 17.1.2 Java und SQLJ.- 17.1.3 Dynamische Erweiterbarkeit.- 17.1.4 Erweiterungsinfrastruktur.- 17.1.5 Universal Storage — alleiniges DBS-Entwicklungsziel?.- 17.2 Universal Access.- 17.2.1 Zugriff auf heterogene relationale Daten.- 17.2.2 Zugriffsvereinfachung bei heterogenen Datenquellen.- 17.2.3 DB-Techniken für das WWW.- 17.2.4 Nutzung von persistenten Warteschlangen.- 17.3 Neue Architektur- und Verarbeitungskonzepte.- 17.3.1 Restrukturierung des DBS-Kerns.- 17.3.2 Client-seitige DBS-Unterstützung.- 17.4 Transaktionsverwaltung.- Literatur.