Datenbanksysteme

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.