Datenbanken -- Implementierungstechniken, 4. Auflage

Datenbanken -- Implementierungstechniken, 4. Auflage

by Andreas Heuer, Kai-Uwe Sattler, Gunter Saake
Released June 2019
Publisher(s): mitp Verlag
ISBN: 9783958457812

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

  • Architekturprinzipien und Datenstrukturen moderner Datenbanksysteme
  • Algorithmen und optimierte Anfragen für Datenbankoperationen
  • Transaktionsmodelle sowie Transaktionsverwaltung im Mehrbenutzerbetrieb

Datenbankmanagementsysteme (DBMS) bilden häufig die Kernkomponente von Informationssystemen und ermöglichen die integrierte Speicherung von großen Datenbeständen, auf die mehrere Anwendungen gleichzeitig zugreifen können. Bei der Implementierung dieser Systeme müssen einige Anforderungen berücksichtigt werden:

  • Effiziente Speicherung und schnelles Wiederauffinden der Daten
  • Datenunabhängigkeit
  • Zuverlässiger Mehrbenutzerbetrieb
  • Wiederherstellung der Daten nach Systemausfällen
  • Kompatibilität zu verschiedenen Rechnerarchitekturen

Die Autoren behandeln die wichtigsten Konzepte und Techniken der Implementierung von DBMS, wobei der Schwerpunkt auf den Konzepten und Basistechnologien kommerzieller, meist relationaler Datenbanksysteme liegt: Architektur, Datenorganisation, Anfragebearbeitung, Synchronisation im Mehrbenutzerbetrieb und Recovery.

Darüber hinaus gehen die Autoren auch auf aktuelle Entwicklungen bei Speichermedien, alternativen Speichermodellen, der Bearbeitung von Data-Warehouse-Anfragen, Anfrageoptimierern und Transaktionsmodellen ein. Angaben zu vertiefender Literatur sowie Übungen am Ende der Kapitel helfen beim Vertiefen des Gelernten sowie bei Selbststudium und Prüfungsvorbereitung.

Zum Verständnis des Buches sind Grundkenntnisse der theoretischen Grundlagen von DBMS wie Relationenalgebra sowie Basiskenntnisse in SQL notwendig.

Aus dem Inhalt:

Externspeicher- und Pufferverwaltung

  • Speicherhierarchie und -medien
  • Seiten, Datensätze und ihre Adressierung
  • Row Stores und Column Stores
  • Seitenersetzungsstrategien
Dateiorganisation und Indexstrukturen
  • B-Bäume
  • Partitionierung
  • Dynamisches Hashing
  • Mehrdimensionale und geometrische Indexstrukturen
  • Bitmap-Indexe
Anfrageverarbeitung und -optimierung
  • Anfrageoperatoren
  • Logische und physische Optimierung
  • Kostenmodelle und Statistiken in DBMS
Transaktionsverwaltung und Recovery
  • Serialisierbarkeit
  • Sperrprotokolle und nichtsperrende Verfahren
  • Commit-Protokolle
  • Logging und Recovery-Strategien

Table of contents

  1. Umschlag
  2. Titel
  3. Impressum
  4. Vorwort zur vierten Auflage Inhaltsverzeichnis
  5. 1 Aufgaben und Prinzipien von Datenbanksystemen
    1. 1.1 Wiederholung der Datenbank-Grundbegriffe
      1. 1.1.1 Architektur eines Datenbanksystems
      2. 1.1.2 Neun Funktionen nach Codd
      3. 1.1.3 Datenbankmodelle und Datendefinition
      4. 1.1.4 Anfrage- und Änderungsoperationen
      5. 1.1.5 Sprachen und Sichten
    2. 1.2 Wann kommt was?
      1. 1.2.1 Optimierer
      2. 1.2.2 Dateiorganisation und Zugriffspfade
      3. 1.2.3 Transaktionen
      4. 1.2.4 Recovery und Datensicherheit
    3. 1.3 Vertiefende Literatur
    4. 1.4 Übungen
  6. 2 Architektur von Datenbanksystemen
    1. 2.1 Betrachtete Fragestellungen
    2. 2.2 Schichtenmodell eines relationalen DBMS
    3. 2.3 Hardware und Betriebssystem
    4. 2.4 Pufferverwaltung
    5. 2.5 Speichersystem
    6. 2.6 Zugriffssystem
    7. 2.7 Datensystem
    8. 2.8 Katalog und Data Dictionary
    9. 2.9 Vertiefende Literatur
    10. 2.10 Übungen
  7. I Speichermodelle und Zugriffspfade
    1. 3 Speichermodelle und Zugriffspfade
      1. 3.1 Speichermedien
        1. 3.1.1 Speicherhierarchie
        2. 3.1.2 Cache, Hauptspeicher und Sekundärspeicher
        3. 3.1.3 Die Magnetplatte
        4. 3.1.4 Flash-Laufwerke
        5. 3.1.5 Speicherkapazität, Geschwindigkeit und Kosten
      2. 3.2 Speicher-Arrays: RAID
        1. 3.2.1 Ziele von RAID-Systemen
        2. 3.2.2 RAID-Levels
      3. 3.3 Sicherungsmedien: Tertiärspeicher
        1. 3.3.1 Optische Platten
        2. 3.3.2 Bänder
        3. 3.3.3 Jukeboxes und Roboter
        4. 3.3.4 Langzeitarchivierung
      4. 3.4 Modell des Hintergrundspeichers
        1. 3.4.1 Betriebssystemdateien
        2. 3.4.2 Abbildung der konzeptuellen Ebene auf interne Strukturen
        3. 3.4.3 Einpassen von Datensätzen auf Blöcke
        4. 3.4.4 Modell des Sekundärspeichers
      5. 3.5 Seiten, Sätze und Adressierung
        1. 3.5.1 Struktur der Seiten
        2. 3.5.2 Satztypen
        3. 3.5.3 Adressierung von Datensätzen
        4. 3.5.4 Alternative Speichermodelle und Kompression
      6. 3.6 Speicherorganisation und physische Datendefinition in SQLSystemen
      7. 3.7 Vertiefende Literatur
      8. 3.8 Übungen
    2. 4 Pufferverwaltung
      1. 4.1 Einordnung und Motivation
      2. 4.2 Suche von Seiten und Speicherzuteilung
        1. 4.2.1 Suchen einer Seite
        2. 4.2.2 Speicherzuteilung im Puffer
      3. 4.3 Seitenersetzungsstrategien
        1. 4.3.1 Merkmale gängiger Strategien
        2. 4.3.2 Konkrete Seitenersetzungsstrategien
        3. 4.3.3 Fazit
      4. 4.4 Vertiefende Literatur
      5. 4.5 Übungen
    3. 5 Dateiorganisation und Zugriffsstrukturen
      1. 5.1 Klassifikation der Speichertechniken
        1. 5.1.1 Primärschlüssel vs. Sekundärschlüssel
        2. 5.1.2 Primärindex vs. Sekundärindex
        3. 5.1.3 Dateiorganisationsform vs. Zugriffspfad
        4. 5.1.4 Dünn besetzter vs. dicht besetzter Index
        5. 5.1.5 Geclusterter vs. nicht-geclusterter Index
        6. 5.1.6 Schlüsselzugriff vs. Schlüsseltransformation
        7. 5.1.7 Ein-Attribut- vs. Mehr-Attribut-Index
        8. 5.1.8 Eindimensionale vs. mehrdimensionale Zugriffsstruktur
        9. 5.1.9 Nachbarschaftserhaltende vs. streuende Zugriffsstruktur
        10. 5.1.10 Statische vs. dynamische Zugriffsstruktur
        11. 5.1.11 Beispiele für Klassifikationen
        12. 5.1.12 Alternative Klassifikationen von Zugriffsverfahren
        13. 5.1.13 Anforderungen an Speichertechniken
      2. 5.2 Sequenzielle und indexierte Dateien
        1. 5.2.1 Heap-Organisation
        2. 5.2.2 Sequenzielle Speicherung
        3. 5.2.3 Indexsequenzielle Dateiorganisation
        4. 5.2.4 Indexiert-nichtsequenzieller Zugriffspfad
      3. 5.3 Suchbäume
        1. 5.3.1 B-Bäume
        2. 5.3.2 B-Bäume und Varianten in Datenbanken
        3. 5.3.3 B-Bäume in der Praxis
      4. 5.4 Hashverfahren
        1. 5.4.1 Grundprinzipien von Hashverfahren
        2. 5.4.2 Hashverfahren für Datenbanken
      5. 5.5 Cluster-Bildung
        1. 5.5.1 Index-organisierte Tabellen
        2. 5.5.2 Cluster für Verbundanfragen
      6. 5.6 Partitionierung
        1. 5.6.1 Fragmentierung und Allokation in verteilten Datenbanken
        2. 5.6.2 Formen der horizontalen Partitionierung
        3. 5.6.3 Bereichspartitionierung
        4. 5.6.4 Hash-Partitionierung
      7. 5.7 Vertiefende Literatur
      8. 5.8 Übungen
    4. 6 Spezielle Indexstrukturen
      1. 6.1 Dynamisches Hashing
        1. 6.1.1 Hashfunktionen mit erweiterbarem Bildbereich
        2. 6.1.2 Lineares Hashen
        3. 6.1.3 Erweiterbares Hashen
        4. 6.1.4 Spiralhashen
        5. 6.1.5 Kombinierte Methoden
      2. 6.2 Mehrdimensionale Speichertechniken
        1. 6.2.1 Mehrdimensionale Baumverfahren
        2. 6.2.2 Mehrdimensionales Hashen
        3. 6.2.3 Grid-File
        4. 6.2.4 UB-Baum
      3. 6.3 Geometrische Zugriffsstrukturen
        1. 6.3.1 Probleme und Aufgaben
        2. 6.3.2 Eignung klassischer Suchbäume und Indexstrukturen
        3. 6.3.3 Prinzipien nachbarschaftserhaltender Suchbäume
        4. 6.3.4 R-Bäume und Varianten
        5. 6.3.5 Rechteckspeicherung durch Punktdatenstrukturen
        6. 6.3.6 Klassifizierung und Vergleich
      4. 6.4 Hochdimensionale Daten
        1. 6.4.1 Hochdimensionale Feature-Vektoren
        2. 6.4.2 Operationen auf Feature-Vektoren
        3. 6.4.3 Metriken für Abstände
        4. 6.4.4 Nächster-Nachbar-Suche in R-Bäumen
        5. 6.4.5 Der X-Baum
        6. 6.4.6 Alternativen zu Baumverfahren
      5. 6.5 Bitmap-Indexe
        1. 6.5.1 Vor- und Nachteile von Bitmap-Indexen
        2. 6.5.2 Varianten von Bitmap-Indexen
        3. 6.5.3 Implementierung von Bitmap-Indexen
      6. 6.6 Indexierung von Texten
        1. 6.6.1 Eignung von B-Bäumen: Probleme und Präfix-B-Baum
        2. 6.6.2 Digitale Bäume
        3. 6.6.3 Invertierte Listen
      7. 6.7 Relationenübergreifende Indexe
        1. 6.7.1 Verbundindexe
        2. 6.7.2 Multi-Join-Indexe
        3. 6.7.3 Pfadindexe
        4. 6.7.4 Zugriffsunterstützungsrelationen
        5. 6.7.5 Zugriffspfade für berechnete Werte
      8. 6.8 Vertiefende Literatur
      9. 6.9 Übungen
  8. II Anfragebearbeitung
    1. 7 Basisalgorithmen für Datenbankoperationen
      1. 7.1 Benötigte Grundalgorithmen
        1. 7.1.1 Parameter für Kostenbestimmung
        2. 7.1.2 Grundannahmen
        3. 7.1.3 Hauptspeicheralgorithmen
        4. 7.1.4 Zugriffe auf Datensätze
        5. 7.1.5 Externe und interne Sortieralgorithmen
      2. 7.2 Navigationsoperationen: Scans
        1. 7.2.1 Arten von Scans
        2. 7.2.2 Operationen auf Scans
        3. 7.2.3 Scan-Semantik
      3. 7.3 Unäre Operationen: Selektion, Projektion und Gruppierung
        1. 7.3.1 Selektion
        2. 7.3.2 Projektion
        3. 7.3.3 Aggregatfunktionen und Gruppierung
      4. 7.4 Binäre Operationen: Mengenoperationen
        1. 7.4.1 Techniken für binäre Operatoren
        2. 7.4.2 Klassen binärer Operatoren
        3. 7.4.3 Vereinigung mit Duplikateliminierung
      5. 7.5 Berechnung von Verbunden
        1. 7.5.1 Nested-Loops-Verbund
        2. 7.5.2 Merge-Techniken
        3. 7.5.3 Hashverbund
        4. 7.5.4 Vergleich der Techniken
      6. 7.6 Operationen für spezielle Anwendungen
        1. 7.6.1 Cube-Berechnung
        2. 7.6.2 Skyline-Operator
      7. 7.7 Vertiefende Literatur
      8. 7.8 Übungen
    2. 8 Optimierung von Anfragen
      1. 8.1 Grundprinzipien der Optimierung
      2. 8.2 Motivierende Beispiele
      3. 8.3 Phasen der Anfragebearbeitung
      4. 8.4 Anfrageübersetzung und -vereinfachung
        1. 8.4.1 Parsen und Analysieren der Anfrage
        2. 8.4.2 Übersetzung in Relationenalgebra
        3. 8.4.3 Auflösung von Sichten
        4. 8.4.4 Standardisierung und Vereinfachung von Ausdrücken
        5. 8.4.5 Entschachteln von Anfragen
      5. 8.5 Weitere Phasen der Optimierung
      6. 8.6 Vertiefende Literatur
      7. 8.7 Übungen
    3. 9 Logische Optimierung
      1. 9.1 Algebraische Optimierung
        1. 9.1.1 Entfernen redundanter Operationen
        2. 9.1.2 Änderung der Reihenfolge von Operationen
        3. 9.1.3 Optimierungsregeln
        4. 9.1.4 Ein einfacher Optimierungsalgorithmus
        5. 9.1.5 Vorgruppierungen
        6. 9.1.6 Erkennung gemeinsamer Teilanfragen
        7. 9.1.7 Ergebnis der algebraischen Optimierung
      2. 9.2 Verbundoptimierung mit Tableaus
        1. 9.2.1 Tableaus – Eine informale Einführung
        2. 9.2.2 Formale Definition einer Tableau-Anfrage
        3. 9.2.3 Konstruktion einer Tableau-Anfrage
        4. 9.2.4 Äquivalenz von Tableau-Anfragen
        5. 9.2.5 Minimalität
        6. 9.2.6 Optimierung von Tableau-Anfragen
        7. 9.2.7 Erweiterung der Tableau-Optimierung
      3. 9.3 Semantische Optimierung
        1. 9.3.1 Darstellungsvarianten für Anfragen
        2. 9.3.2 Berücksichtigung von Integritätsbedingungen
        3. 9.3.3 Äquivalenz von Anfragen unter Integritätsbedingungen
        4. 9.3.4 Tableau-Optimierung mit CHASE
      4. 9.4 Vertiefende Literatur
      5. 9.5 Übungen
    4. 10 Interne Optimierung und kostenbasierte Planauswahl
      1. 10.1 Physische oder interne Optimierung
        1. 10.1.1 Planoperatoren und Planrepräsentation
        2. 10.1.2 Plangenerierung und Suchstrategien
      2. 10.2 Kostenmodelle und Kostenabschätzung
        1. 10.2.1 Komponenten von Kostenmodellen
        2. 10.2.2 Histogramme
        3. 10.2.3 Kostenabschätzungen am Beispiel
        4. 10.2.4 Statistiken in DBMS
      3. 10.3 Strategien zur kostenbasierten Planauswahl
        1. 10.3.1 Greedy-Suche
        2. 10.3.2 Dynamische Programmierung
        3. 10.3.3 Anfragedekomposition
        4. 10.3.4 Iterative Improvement und Simulated Annealing
        5. 10.3.5 Optimierung mit genetischen Algorithmen
      4. 10.4 Beeinflussung von Anfrageoptimierern
        1. 10.4.1 Ausgabe von Plänen
        2. 10.4.2 Optimizer Hints
      5. 10.5 Vertiefende Literatur
      6. 10.6 Übungen
  9. III Transaktionsverarbeitung und Recovery
    1. 11 Transaktionsmodelle
      1. 11.1 Transaktionen im Mehrbenutzerbetrieb
      2. 11.2 Transaktionseigenschaften
      3. 11.3 Probleme im Mehrbenutzerbetrieb
        1. 11.3.1 Inkonsistentes Lesen: Nonrepeatable Read
        2. 11.3.2 Lesen inkonsistenter Zustände
        3. 11.3.3 Abhängigkeiten von nicht freigegebenen Daten: Dirty Read
        4. 11.3.4 Das Phantom-Problem
        5. 11.3.5 Verloren gegangene Änderungen: Lost Update
        6. 11.3.6 Integritätsverletzung durch Mehrbenutzer-Anomalie
        7. 11.3.7 Cursor-Referenzen
        8. 11.3.8 Problemklassifikation
        9. 11.3.9 Isolation: Serialisierbarkeit oder Snapshot Isolation
      4. 11.4 Serialisierbarkeit
        1. 11.4.1 Einführung in die Serialisierbarkeitsthematik
        2. 11.4.2 Der Begriff des Schedules
        3. 11.4.3 Grundlegende Definitionen
        4. 11.4.4 Das Konzept der Serialisierbarkeit
        5. 11.4.5 Sichtserialisierbarkeit
        6. 11.4.6 Konfliktserialisierbarkeit
        7. 11.4.7 Graphbasierter Test auf Konfliktserialisierbarkeit
        8. 11.4.8 Abgeschlossenheitseigenschaften
      5. 11.5 Transaktionsabbruch und Fehlersicherheit
        1. 11.5.1 Rücksetzbarkeit
        2. 11.5.2 Vermeidung kaskadierender Abbrüche
        3. 11.5.3 Striktheit
        4. 11.5.4 Rigorose Striktheit oder Strenge
        5. 11.5.5 Operationen für den Transaktionsabbruch
      6. 11.6 Mehrversionen-Serialisierbarkeit
        1. 11.6.1 Idee des MVCC
        2. 11.6.2 Ein- und Mehrversionen-Schedules
        3. 11.6.3 Serialisierbarkeitsgraph für MV-Schedules
        4. 11.6.4 Serielle und serialisierbare MV-Schedules
        5. 11.6.5 Mehrversionen-Serialisierbarkeitsgraph
        6. 11.6.6 MVCC in DBMS
      7. 11.7 Snapshot Isolation
        1. 11.7.1 Definition der Snapshot Isolation
        2. 11.7.2 Vergleich zur Serialisierbarkeit
        3. 11.7.3 Serialisierbare Snapshot Isolation
      8. 11.8 Ausnutzung semantischer Informationen
        1. 11.8.1 Vertauschbarkeit von Operationen
        2. 11.8.2 Kompensierende Aktionen
      9. 11.9 Vertiefende Literatur
      10. 11.10 Übungen
    2. 12 Transaktionsverwaltung
      1. 12.1 Der Scheduler
      2. 12.2 Sperrmodelle
        1. 12.2.1 Sperrdisziplin
        2. 12.2.2 Verklemmungen
        3. 12.2.3 Livelock-Problem
      3. 12.3 Sperrprotokolle
        1. 12.3.1 Notwendigkeit von Sperrprotokollen
        2. 12.3.2 Zwei-Phasen-Sperrprotokoll
        3. 12.3.3 Striktes und strenges Zwei-Phasen-Sperrprotokoll
        4. 12.3.4 Aggressive und konservative Protokolle
      4. 12.4 Sperrgranulate
        1. 12.4.1 Hierarchisches Sperren
        2. 12.4.2 Prädikatsperren
        3. 12.4.3 Baumprotokolle für Sperren in Indexstrukturen
      5. 12.5 Nichtsperrende Verfahren zur Synchronisation
        1. 12.5.1 Zeitmarkenverfahren
        2. 12.5.2 Serialisierbarkeitsgraphentester
        3. 12.5.3 Optimistische Verfahren
      6. 12.6 Mehrversionen-Synchronisation
        1. 12.6.1 Begrenzung der Anzahl der Versionen
        2. 12.6.2 Synchronisation von MV-Schedules
      7. 12.7 Commit-Protokolle
        1. 12.7.1 Verteiltes Commit
        2. 12.7.2 Das Zwei-Phasen-Commit-Protokoll
        3. 12.7.3 Lineares 2PC
        4. 12.7.4 Verteiltes 2PC
        5. 12.7.5 Hierarchisches 2PC
        6. 12.7.6 Das Drei-Phasen-Commit-Protokoll
      8. 12.8 Transaktionen in SQL-DBMS
        1. 12.8.1 Aufweichung von ACID in SQL-92: Isolationsebenen
        2. 12.8.2 Explizite Sperren in SQL
      9. 12.9 Vertiefende Literatur
      10. 12.10 Übungen
    3. 13 Wiederherstellung und Datensicherung
      1. 13.1 Beteiligte Systemkomponenten
      2. 13.2 Fehlerklassifikation und Recovery-Klassen
        1. 13.2.1 Fehlerklassifikation
        2. 13.2.2 Fehlerkategorien und zugehörige Recovery-Maßnahmen
      3. 13.3 Protokollierungsarten
        1. 13.3.1 Aufbau des Logbuchs
        2. 13.3.2 Physisches vs. logisches Logbuch
        3. 13.3.3 Sicherungspunkte
      4. 13.4 Recovery-Strategien
        1. 13.4.1 Seitenersetzungsstrategien
        2. 13.4.2 Propagierungsstrategien
        3. 13.4.3 Einbringstrategien
        4. 13.4.4 Konkrete Recovery-Strategien
        5. 13.4.5 Wiederanlauf nach einem Fehlerfall
        6. 13.4.6 Das REDO-Protokoll als konkrete Realisierung
        7. 13.4.7 Abbrüche im Recovery-Prozess
      5. 13.5 Das ARIES-Verfahren
        1. 13.5.1 Vorgehensweise in ARIES
        2. 13.5.2 Grundprinzipien und Datenstrukturen
        3. 13.5.3 Phasen des Wiederanlaufs
      6. 13.6 Schattenspeicherverfahren
      7. 13.7 Backup-Strategien und Archivierung
        1. 13.7.1 Backups und Archivierung
        2. 13.7.2 Spiegelung von Datenbanken
      8. 13.8 Vertiefende Literatur
      9. 13.9 Übungen
  10. IV Aktuelle Entwicklungen
    1. 14 Moderne Datenbanksystem-Architekturen
      1. 14.1 Alternative Speichermodelle: DSM und PAX
      2. 14.2 Kompression von Daten
      3. 14.3 Multicore- und Spezialprozessoren
        1. 14.3.1 Hashverbunde für Multicore-Systeme
        2. 14.3.2 GPGPU-Beschleunigung von Datenbankoperationen
      4. 14.4 Alternative transaktionale Garantien
        1. 14.4.1 Von ACID zu BASE
        2. 14.4.2 Das CAP-Theorem
        3. 14.4.3 Abgeschwächte Konsistenzmodelle
      5. 14.5 Vertiefende Literatur
  11. Laufendes Beispiel
  12. Abbildungsverzeichnis
  13. Tabellenverzeichnis
  14. Liste der Codefragmente
  15. Literaturverzeichnis
  16. Anmerkungen

Product information

  • Title: Datenbanken -- Implementierungstechniken, 4. Auflage
  • Author(s): Andreas Heuer, Kai-Uwe Sattler, Gunter Saake
  • Release date: June 2019
  • Publisher(s): mitp Verlag
  • ISBN: 9783958457812