Datenbanken (eBook)

Implementierungstechniken

Gunter Saake, Kai-Uwe Sattler (Autoren)

eBook Download: PDF

2019 | 4. Auflage
736 Seiten
MITP Verlags GmbH & Co. KG
978-3-95845-780-5 (ISBN)

Infos

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

Die Autoren sind Professoren für Datenbank- und Informationssysteme - Gunter Saake an der Universität Magdeburg, Kai-Uwe Sattler an der TU Ilmenau und Andreas Heuer an der Universität Rostock.

Inhalt

Vorwort zur vierten Auflage 5
Inhaltsverzeichnis 11
Aufgaben und Prinzipien von Datenbanksystemen 21
Wiederholung der Datenbank-Grundbegriffe 22
Architektur eines Datenbanksystems 22
Neun Funktionen nach Codd 25
Datenbankmodelle und Datendefinition 26
Anfrage- und Änderungsoperationen 32
Sprachen und Sichten 33
Wann kommt was? 35
Optimierer 35
Dateiorganisation und Zugriffspfade 37
Transaktionen 40
Recovery und Datensicherheit 40
Vertiefende Literatur 41
Übungen 42
Architektur von Datenbanksystemen 43
Betrachtete Fragestellungen 44
Schichtenmodell eines relationalen DBMS 46
Hardware und Betriebssystem 49
Pufferverwaltung 51
Speichersystem 54
Zugriffssystem 55
Datensystem 59
Katalog und Data Dictionary 60
Vertiefende Literatur 62
Übungen 63
I Speichermodelle und Zugriffspfade 65
Verwaltung des Hintergrundspeichers 67
Speichermedien 68
Speicherhierarchie 68
Cache, Hauptspeicher und Sekundärspeicher 71
Die Magnetplatte 72
Flash-Laufwerke 75
Speicherkapazität, Geschwindigkeit und Kosten 79
Speicher-Arrays: RAID 81
Ziele von RAID-Systemen 81
RAID-Levels 82
Sicherungsmedien: Tertiärspeicher 88
Optische Platten 89
Bänder 90
Jukeboxes und Roboter 90
Langzeitarchivierung 91
Modell des Hintergrundspeichers 92
Betriebssystemdateien 92
Abbildung der konzeptuellen Ebene auf interne Strukturen 94
Einpassen von Datensätzen auf Blöcke 95
Modell des Sekundärspeichers 97
Seiten, Sätze und Adressierung 98
Struktur der Seiten 98
Satztypen 99
Adressierung von Datensätzen 105
Alternative Speichermodelle und Kompression 107
Speicherorganisation und physische Datendefinition in SQL-Systemen 109
Vertiefende Literatur 113
Übungen 114
Pufferverwaltung 117
Einordnung und Motivation 118
Suche von Seiten und Speicherzuteilung 121
Suchen einer Seite 121
Speicherzuteilung im Puffer 122
Seitenersetzungsstrategien 122
Merkmale gängiger Strategien 125
Konkrete Seitenersetzungsstrategien 126
Fazit 138
Vertiefende Literatur 140
Übungen 140
Dateiorganisation und Zugriffsstrukturen 143
Klassifikation der Speichertechniken 144
Primärschlüssel vs. Sekundärschlüssel 145
Primärindex vs. Sekundärindex 146
Dateiorganisationsform vs. Zugriffspfad 147
Dünn besetzter vs. dicht besetzter Index 149
Geclusterter vs. nicht-geclusterter Index 151
Schlüsselzugriff vs. Schlüsseltransformation 152
Ein-Attribut- vs. Mehr-Attribut-Index 153
Eindimensionale vs. mehrdimensionale Zugriffsstruktur 153
Nachbarschaftserhaltende vs. streuende Zugriffsstruktur 154
Statische vs. dynamische Zugriffsstruktur 155
Beispiele für Klassifikationen 156
Alternative Klassifikationen von Zugriffsverfahren 157
Anforderungen an Speichertechniken 159
Sequenzielle und indexierte Dateien 160
Heap-Organisation 160
Sequenzielle Speicherung 164
Indexsequenzielle Dateiorganisation 165
Indexiert-nichtsequenzieller Zugriffspfad 170
Suchbäume 174
B-Bäume 175
B-Bäume und Varianten in Datenbanken 183
B-Bäume in der Praxis 190
Hashverfahren 193
Grundprinzipien von Hashverfahren 193
Hashverfahren für Datenbanken 195
Cluster-Bildung 199
Index-organisierte Tabellen 200
Cluster für Verbundanfragen 201
Partitionierung 204
Fragmentierung und Allokation in verteilten Datenbanken 205
Formen der horizontalen Partitionierung 207
Bereichspartitionierung 208
Hash-Partitionierung 209
Vertiefende Literatur 210
Übungen 211
Spezielle Indexstrukturen 213
Dynamisches Hashing 214
Hashfunktionen mit erweiterbarem Bildbereich 214
Lineares Hashen 215
Erweiterbares Hashen 218
Spiralhashen 221
Kombinierte Methoden 224
Mehrdimensionale Speichertechniken 225
Mehrdimensionale Baumverfahren 226
Mehrdimensionales Hashen 232
Grid-File 236
UB-Baum 242
Geometrische Zugriffsstrukturen 245
Probleme und Aufgaben 245
Eignung klassischer Suchbäume und Indexstrukturen 248
Prinzipien nachbarschaftserhaltender Suchbäume 249
R-Bäume und Varianten 253
Rechteckspeicherung durch Punktdatenstrukturen 259
Klassifizierung und Vergleich 266
Hochdimensionale Daten 267
Hochdimensionale Feature-Vektoren 267
Operationen auf Feature-Vektoren 268
Metriken für Abstände 270
Nächster-Nachbar-Suche in R-Bäumen 272
Der X-Baum 275
Alternativen zu Baumverfahren 277
Bitmap-Indexe 279
Vor- und Nachteile von Bitmap-Indexen 280
Varianten von Bitmap-Indexen 281
Implementierung von Bitmap-Indexen 282
Indexierung von Texten 283
Eignung von B-Bäumen: Probleme und Präfix-B-Baum 283
Digitale Bäume 284
Invertierte Listen 289
Relationenübergreifende Indexe 290
Verbundindexe 290
Multi-Join-Indexe 292
Pfadindexe 293
Zugriffsunterstützungsrelationen 295
Zugriffspfade für berechnete Werte 296
Vertiefende Literatur 297
Übungen 298
II Anfragebearbeitung 301
Basisalgorithmen für Datenbankoperationen 303
Benötigte Grundalgorithmen 305
Parameter für Kostenbestimmung 305
Grundannahmen 306
Hauptspeicheralgorithmen 307
Zugriffe auf Datensätze 307
Externe und interne Sortieralgorithmen 308
Navigationsoperationen: Scans 312
Arten von Scans 312
Operationen auf Scans 313
Scan-Semantik 316
Unäre Operationen: Selektion, Projektion und Gruppierung 317
Selektion 317
Projektion 319
Aggregatfunktionen und Gruppierung 320
Binäre Operationen: Mengenoperationen 323
Techniken für binäre Operatoren 324
Klassen binärer Operatoren 325
Vereinigung mit Duplikateliminierung 326
Berechnung von Verbunden 328
Nested-Loops-Verbund 328
Merge-Techniken 330
Hashverbund 332
Vergleich der Techniken 336
Operationen für spezielle Anwendungen 338
Cube-Berechnung 339
Skyline-Operator 345
Vertiefende Literatur 351
Übungen 352
Optimierung von Anfragen 353
Grundprinzipien der Optimierung 355
Motivierende Beispiele 356
Phasen der Anfragebearbeitung 361
Anfrageübersetzung und -vereinfachung 363
Parsen und Analysieren der Anfrage 363
Übersetzung in Relationenalgebra 365
Auflösung von Sichten 366
Standardisierung und Vereinfachung von Ausdrücken 367
Entschachteln von Anfragen 369
Weitere Phasen der Optimierung 373
Vertiefende Literatur 374
Übungen 375
Logische Optimierung 377
Algebraische Optimierung 378
Entfernen redundanter Operationen 379
Änderung der Reihenfolge von Operationen 380
Optimierungsregeln 381
Ein einfacher Optimierungsalgorithmus 384
Vorgruppierungen 387
Erkennung gemeinsamer Teilanfragen 389
Ergebnis der algebraischen Optimierung 390
Verbundoptimierung mit Tableaus 390
Tableaus – Eine informale Einführung 391
Formale Definition einer Tableau-Anfrage 393
Konstruktion einer Tableau-Anfrage 396
Äquivalenz von Tableau-Anfragen 399
Minimalität 400
Optimierung von Tableau-Anfragen 401
Erweiterung der Tableau-Optimierung 404
Semantische Optimierung 405
Darstellungsvarianten für Anfragen 406
Berücksichtigung von Integritätsbedingungen 407
Äquivalenz von Anfragen unter Integritätsbedingungen 410
Tableau-Optimierung mit CHASE 411
Vertiefende Literatur 415
Übungen 416
Interne Optimierung und kostenbasierte Planauswahl 419
Physische oder interne Optimierung 420
Planoperatoren und Planrepräsentation 421
Plangenerierung und Suchstrategien 432
Kostenmodelle und Kostenabschätzung 436
Komponenten von Kostenmodellen 436
Histogramme 442
Kostenabschätzungen am Beispiel 449
Statistiken in DBMS 453
Strategien zur kostenbasierten Planauswahl 455
Greedy-Suche 456
Dynamische Programmierung 458
Anfragedekomposition 462
Iterative Improvement und Simulated Annealing 465
Optimierung mit genetischen Algorithmen 468
Beeinflussung von Anfrageoptimierern 470
Ausgabe von Plänen 471
Optimizer Hints 474
Vertiefende Literatur 477
Übungen 478
III Transaktionsverarbeitung und Recovery 481
Transaktionsmodelle 483
Transaktionen im Mehrbenutzerbetrieb 483
Transaktionseigenschaften 485
Probleme im Mehrbenutzerbetrieb 487
Inkonsistentes Lesen: Nonrepeatable Read 488
Lesen inkonsistenter Zustände 489
Abhängigkeiten von nicht freigegebenen Daten: Dirty Read 489
Das Phantom-Problem 491
Verloren gegangene Änderungen: Lost Update 491
Integritätsverletzung durch Mehrbenutzer-Anomalie 492
Cursor-Referenzen 493
Problemklassifikation 494
Isolation: Serialisierbarkeit oder Snapshot Isolation 495
Serialisierbarkeit 496
Einführung in die Serialisierbarkeitsthematik 496
Der Begriff des Schedules 501
Grundlegende Definitionen 504
Das Konzept der Serialisierbarkeit 505
Sichtserialisierbarkeit 506
Konfliktserialisierbarkeit 509
Graphbasierter Test auf Konfliktserialisierbarkeit 511
Abgeschlossenheitseigenschaften 513
Transaktionsabbruch und Fehlersicherheit 516
Rücksetzbarkeit 517
Vermeidung kaskadierender Abbrüche 518
Striktheit 518
Rigorose Striktheit oder Strenge 520
Operationen für den Transaktionsabbruch 522
Mehrversionen-Serialisierbarkeit 524
Idee des MVCC 524
Ein- und Mehrversionen-Schedules 525
Serialisierbarkeitsgraph für MV-Schedules 528
Serielle und serialisierbare MV-Schedules 528
Mehrversionen-Serialisierbarkeitsgraph 530
MVCC in DBMS 533
Snapshot Isolation 534
Definition der Snapshot Isolation 535
Vergleich zur Serialisierbarkeit 536
Serialisierbare Snapshot Isolation 539
Ausnutzung semantischer Informationen 540
Vertauschbarkeit von Operationen 540
Kompensierende Aktionen 543
Vertiefende Literatur 545
Übungen 546
Transaktionsverwaltung 549
Der Scheduler 549
Sperrmodelle 552
Sperrdisziplin 552
Verklemmungen 553
Livelock-Problem 554
Sperrprotokolle 555
Notwendigkeit von Sperrprotokollen 555
Zwei-Phasen-Sperrprotokoll 556
Striktes und strenges Zwei-Phasen-Sperrprotokoll 558
Aggressive und konservative Protokolle 558
Sperrgranulate 559
Hierarchisches Sperren 560
Prädikatsperren 564
Baumprotokolle für Sperren in Indexstrukturen 565
Nichtsperrende Verfahren zur Synchronisation 569
Zeitmarkenverfahren 570
Serialisierbarkeitsgraphentester 573
Optimistische Verfahren 574
Mehrversionen-Synchronisation 577
Begrenzung der Anzahl der Versionen 577
Synchronisation von MV-Schedules 579
Commit-Protokolle 584
Verteiltes Commit 584
Das Zwei-Phasen-Commit-Protokoll 585
Lineares 2PC 588
Verteiltes 2PC 590
Hierarchisches 2PC 591
Das Drei-Phasen-Commit-Protokoll 592
Transaktionen in SQL-DBMS 595
Aufweichung von ACID in SQL-92: Isolationsebenen 595
Explizite Sperren in SQL 597
Vertiefende Literatur 599
Übungen 599
Wiederherstellung und Datensicherung 601
Beteiligte Systemkomponenten 602
Fehlerklassifikation und Recovery-Klassen 604
Fehlerklassifikation 604
Fehlerkategorien und zugehörige Recovery-Maßnahmen 607
Protokollierungsarten 608
Aufbau des Logbuchs 608
Physisches vs. logisches Logbuch 611
Sicherungspunkte 615
Recovery-Strategien 619
Seitenersetzungsstrategien 619
Propagierungsstrategien 620
Einbringstrategien 621
Konkrete Recovery-Strategien 622
Wiederanlauf nach einem Fehlerfall 624
Das Redo-Protokoll als konkrete Realisierung 625
Abbrüche im Recovery-Prozess 626
Das ARIES-Verfahren 627
Vorgehensweise in ARIES 627
Grundprinzipien und Datenstrukturen 628
Phasen des Wiederanlaufs 629
Schattenspeicherverfahren 631
Backup-Strategien und Archivierung 633
Backups und Archivierung 634
Spiegelung von Datenbanken 636
Vertiefende Literatur 636
Übungen 637
IV Aktuelle Entwicklungen 639
Moderne Datenbanksystem-Architekturen 641
Alternative Speichermodelle: DSM und PAX 642
Kompression von Daten 645
Multicore- und Spezialprozessoren 652
Hashverbunde für Multicore-Systeme 653
GPGPU-Beschleunigung von Datenbankoperationen 655
Alternative transaktionale Garantien 658
Von ACID zu BASE 659
Das CAP-Theorem 660
Abgeschwächte Konsistenzmodelle 662
Vertiefende Literatur 664
Laufendes Beispiel 667
Abbildungsverzeichnis 671
Tabellenverzeichnis 680
Liste der Codefragmente 683
Sachindex 685
Literaturverzeichnis 699

Produkt-Details

• Erscheint lt. Verlag: 21.6.2019
• Reihe/Serie: mitp Professional
• Verlagsort: Frechen
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Schlagworte: Codd • Data Warehouse • Datenbanksysteme • Datensicherung • DB • DBMS • Externspeicher • Pufferverwaltung • RAID • Recovery
• ISBN-10: 3-95845-780-0 / 3958457800
• ISBN-13: 978-3-95845-780-5 / 9783958457805