Saake / Heuer / Sattler Datenbanken
3. überarbeitete Auflage 2012
ISBN: 978-3-8266-9157-7
Verlag: MITP
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Implementierungstechniken
E-Book, Deutsch, 656 Seiten
Reihe: mitp Professional
ISBN: 978-3-8266-9157-7
Verlag: MITP
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Dieses Buch behandelt Konzepte und Techniken der Implementierung von Datenbanksystemen, die heutzutage die Kernkomponente von Informationssystemen darstellen. Im Mittelpunkt stehen Architekturprinzipien, Datenstrukturen und Algorithmen für die Verwaltung von Externspeichern, die Realisierung von Speicher- und Zugriffsstrukturen, die Anfrageverarbeitung und -optimierung sowie die Transaktionsverwaltung und die Wiederherstellung der Datenbank im Fehlerfall.
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.
Autoren/Hrsg.
Weitere Infos & Material
1;Vorwort;4
2;Inhaltsverzeichnis;8
3;Aufgaben und Prinzipien von Datenbanksystemen;16
3.1;Wiederholung der Datenbank-Grundbegriffe;17
3.1.1;Architektur eines Datenbanksystems;17
3.1.2;Neun Funktionen nach Codd;20
3.1.3;Datenbankmodelle und Datendefinition;21
3.1.4;Anfrage- und Änderungsoperationen;24
3.1.5;Sprachen und Sichten;26
3.2;Wann kommt was?;27
3.2.1;Optimierer;28
3.2.2;Dateiorganisation und Zugriffspfade;29
3.2.3;Transaktionen;32
3.2.4;Recovery und Datensicherheit;33
3.3;Vertiefende Literatur;33
3.4;Übungen;34
4;Architektur von Datenbanksystemen;36
4.1;Betrachtete Fragestellungen;37
4.2;Schichtenmodell eines relationalen DBMS;39
4.3;Hardware und Betriebssystem;42
4.4;Pufferverwaltung;44
4.5;Speichersystem;46
4.6;Zugriffssystem;48
4.7;Datensystem;52
4.8;Katalog und Data Dictionary;52
4.9;Vertiefende Literatur;55
4.10;Übungen;56
5;Verwaltung des Hintergrundspeichers;58
5.1;Speichermedien;59
5.1.1;Speicherhierarchie;59
5.1.2;Cache, Hauptspeicher und Sekundärspeicher;62
5.1.3;Die Magnetplatte;63
5.1.4;Flash-Laufwerke;66
5.1.5;Speicherkapazität, Geschwindigkeit und Kosten;70
5.2;Speicher-Arrays: RAID;72
5.2.1;Ziele von RAID-Systemen;72
5.2.2;RAID-Levels;73
5.3;Sicherungsmedien: Tertiärspeicher;79
5.3.1;Optische Platten;80
5.3.2;Bänder;80
5.3.3;Jukeboxes und Roboter;81
5.3.4;Langzeitarchivierung;82
5.4;Verwaltung des Hintergrundspeichers;83
5.4.1;Betriebssystemdateien;84
5.4.2;Abbildung der konzeptuellen Ebene auf interne Strukturen;85
5.4.3;Einpassen von Datensätzen auf Blöcke;86
5.4.4;Modell des Sekundärspeichers;88
5.5;Seiten, Sätze und Adressierung;88
5.5.1;Struktur der Seiten;89
5.5.2;Satztypen;90
5.5.3;Adressierung von Datensätzen;96
5.5.4;Alternative Speichermodelle: DSM und PAX;98
5.6;Kompression von Daten;101
5.7;Speicherorganisation und physische Datendefinition in SQL-Systemen;108
5.8;Vertiefende Literatur;111
5.9;Übungen;114
6;Pufferverwaltung;116
6.1;Einordnung und Motivation;117
6.2;Suche von Seiten und Speicherzuteilung;120
6.2.1;Suchen einer Seite;120
6.2.2;Speicherzuteilung im Puffer;121
6.3;Seitenersetzungsstrategien;121
6.3.1;Merkmale gängiger Strategien;124
6.3.2;Konkrete Seitenersetzungsstrategien;125
6.3.3;Fazit;137
6.4;Vertiefende Literatur;139
6.5;Übungen;139
7;Dateiorganisation und Zugriffsstrukturen;142
7.1;Klassifikation der Speichertechniken;143
7.1.1;Primärschlüssel vs. Sekundärschlüssel;144
7.1.2;Primärindex vs. Sekundärindex;145
7.1.3;Dateiorganisationsform vs. Zugriffspfad;146
7.1.4;Dünn besetzter vs. dicht besetzter Index;148
7.1.5;Geclusterter vs. nicht-geclusterter Index;150
7.1.6;Schlüsselzugriff vs. Schlüsseltransformation;151
7.1.7;Ein-Attribut- vs. Mehr-Attribut-Index;152
7.1.8;Eindimensionale vs. mehrdimensionale Zugriffsstruktur;152
7.1.9;Nachbarschaftserhaltende vs. streuende Zugriffsstruktur;154
7.1.10;Statische vs. dynamische Zugriffsstruktur;154
7.1.11;Beispiele für Klassifikationen;155
7.1.12;Alternative Klassifikationen von Zugriffsverfahren;155
7.1.13;Anforderungen an Speichertechniken;156
7.2;Sequenzielle und indexierte Dateien;158
7.2.1;Heap-Organisation;158
7.2.2;Sequenzielle Speicherung;162
7.2.3;Indexsequenzielle Dateiorganisation;163
7.2.4;Indexiert-nichtsequenzieller Zugriffspfad;168
7.3;Suchbäume;172
7.3.1;B-Bäume;173
7.3.2;B-Bäume und Varianten in Datenbanken;181
7.3.3;B-Bäume in der Praxis;188
7.4;Hashverfahren;191
7.4.1;Grundprinzipien von Hashverfahren;191
7.4.2;Hashverfahren für Datenbanken;193
7.5;Cluster-Bildung;197
7.5.1;Index-organisierte Tabellen;198
7.5.2;Cluster für Verbundanfragen;199
7.6;Partitionierung;202
7.6.1;Fragmentierung und Allokation in verteilten Datenbanken;203
7.6.2;Formen der horizontalen Partitionierung;205
7.6.3;Bereichspartitionierung;206
7.6.4;Hash-Partitionierung;207
7.7;Vertiefende Literatur;208
7.8;Übungen;209
8;Spezielle Indexstrukturen ;212
8.1;Dynamisches Hashing;213
8.1.1;Hashfunktionen mit erweiterbarem Bildbereich;213
8.1.2;Lineares Hashen;214
8.1.3;Erweiterbares Hashen;217
8.1.4;Spiralhashen;220
8.1.5;Kombinierte Methoden;223
8.2;Mehrdimensionale Speichertechniken;224
8.2.1;Mehrdimensionale Baumverfahren;225
8.2.2;Mehrdimensionales Hashen;230
8.2.3;Grid-File;235
8.2.4;UB-Baum;241
8.3;Geometrische Zugriffsstrukturen ;243
8.3.1;Probleme und Aufgaben;244
8.3.2;Eignung klassischer Suchbäume und Indexstrukturen;247
8.3.3;Prinzipien nachbarschaftserhaltender Suchbäume;248
8.3.4;R-Bäume und Varianten;251
8.3.5;Rechteckspeicherung durch Punktdatenstrukturen;258
8.3.6;Klassifizierung und Vergleich;265
8.4;Hochdimensionale Daten;266
8.4.1;Hochdimensionale Feature-Vektoren;266
8.4.2;Operationen auf Feature-Vektoren;267
8.4.3;Metriken für Abstände;269
8.4.4;Nächster-Nachbar-Suche in R-Bäumen;271
8.4.5;Der X-Baum;274
8.4.6;Alternativen zu Baumverfahren;276
8.5;Bitmap-Indexe;278
8.5.1;Vor- und Nachteile von Bitmap-Indexen;279
8.5.2;Varianten von Bitmap-Indexen;280
8.5.3;Implementierung von Bitmap-Indexen;281
8.6;Indexierung von Texten;282
8.6.1;Eignung von B-Bäumen: Probleme und Präfix-B-Baum;282
8.6.2;Digitale Bäume;283
8.6.3;Invertierte Listen;288
8.7;Relationenübergreifende Indexe;289
8.7.1;Verbundindexe;289
8.7.2;Multi-Join-Indexe;291
8.7.3;Pfadindexe;293
8.7.4;Zugriffsunterstützungsrelationen;294
8.7.5;Zugriffspfade für berechnete Werte;295
8.8;Vertiefende Literatur;296
8.9;Übungen;297
9;Basisalgorithmen für Datenbankoperationen ;300
9.1;Benötigte Grundalgorithmen;301
9.1.1;Parameter für Kostenbestimmung;301
9.1.2;Grundannahmen;303
9.1.3;Hauptspeicheralgorithmen;303
9.1.4;Zugriffe auf Datensätze;304
9.1.5;Externe und interne Sortieralgorithmen;305
9.2;Navigationsoperationen: Scans;308
9.2.1;Arten von Scans;309
9.2.2;Operationen auf Scans;310
9.2.3;Scan-Semantik;313
9.3;Unäre Operationen: Selektion, Projektion und Gruppierung;314
9.3.1;Selektion;314
9.3.2;Projektion;316
9.3.3;Aggregatfunktionen und Gruppierung;317
9.4;Binäre Operationen: Mengenoperationen;320
9.4.1;Techniken für binäre Operatoren;321
9.4.2;Klassen binärer Operatoren;322
9.4.3;Vereinigung mit Duplikateliminierung;323
9.5;Berechnung von Verbunden;325
9.5.1;Nested-Loops-Verbund;325
9.5.2;Merge-Techniken;327
9.5.3;Hashverbund;330
9.5.4;Vergleich der Techniken;334
9.6;Operationen für spezielle Anwendungen;335
9.6.1;Cube-Berechnung;335
9.6.2;Skyline-Operator;342
9.7;Vertiefende Literatur;347
9.8;Übungen;349
10;Optimierung von Anfragen;350
10.1;Grundprinzipien der Optimierung;351
10.2;Motivierende Beispiele;352
10.3;Phasen der Anfragebearbeitung;357
10.4;Anfrageübersetzung und -vereinfachung;360
10.4.1;Parsen und Analysieren der Anfrage;360
10.4.2;Übersetzung in Relationenalgebra;361
10.4.3;Auflösung von Sichten;363
10.4.4;Standardisierung und Vereinfachung von Ausdrücken;363
10.4.5;Entschachteln von Anfragen;365
10.5;Logische Optimierung;369
10.5.1;Algebraische Optimierung;370
10.5.2;Verbundoptimierung mit Tableaus ;381
10.6;Physische Optimierung;395
10.6.1;Planoperatoren und Planrepräsentation;395
10.6.2;Plangenerierung und Suchstrategien;405
10.7;Kostenmodelle und Kostenabschätzung;409
10.7.1;Komponenten von Kostenmodellen;409
10.7.2;Histogramme;415
10.7.3;Kostenabschätzungen am Beispiel;422
10.7.4;Statistiken in DBMS;426
10.8;Strategien zur kostenbasierten Planauswahl;428
10.8.1;Greedy-Suche;429
10.8.2;Dynamische Programmierung;430
10.8.3;Anfragedekomposition;435
10.8.4;Iterative Improvement und Simulated Annealing;437
10.8.5;Optimierung mit genetischen Algorithmen;440
10.9;Beeinflussung von Anfrageoptimierern;444
10.9.1;Ausgabe von Plänen;444
10.9.2;Optimizer Hints;447
10.10;Vertiefende Literatur;450
10.11;Übungen;451
11;Transaktionsmodelle ;454
11.1;Transaktionen im Mehrbenutzerbetrieb;454
11.2;Transaktionseigenschaften;456
11.3;Probleme im Mehrbenutzerbetrieb;458
11.3.1;Inkonsistentes Lesen: Nonrepeatable Read;458
11.3.2;Lesen inkonsistenter Zustände;459
11.3.3;Abhängigkeiten von nicht freigegebenen Daten: Dirty Read;459
11.3.4;Das Phantom-Problem;461
11.3.5;Verloren gegangene Änderungen: Lost Update;462
11.3.6;Integritätsverletzung durch Mehrbenutzer-Anomalie;462
11.3.7;Cursor-Referenzen;463
11.3.8;Problemklassifikation;464
11.4;Serialisierbarkeit;465
11.4.1;Einführung in die Serialisierbarkeitsthematik;465
11.4.2;Der Begriff des Schedules;470
11.4.3;Grundlegende Definitionen;473
11.4.4;Das Konzept der Serialisierbarkeit;475
11.4.5;Sichtserialisierbarkeit;475
11.4.6;Konfliktserialisierbarkeit;478
11.4.7;Graphbasierter Test auf Konfliktserialisierbarkeit;481
11.4.8;Abgeschlossenheitseigenschaften;483
11.5;Transaktionsabbruch und Fehlersicherheit;486
11.5.1;Rücksetzbarkeit;486
11.5.2;Vermeidung kaskadierender Abbrüche;487
11.5.3;Striktheit;488
11.5.4;Operationen für den Transaktionsabbruch;489
11.6;Mehrversionen-Serialisierbarkeit;490
11.7;Ausnutzung semantischer Informationen;500
11.7.1;Vertauschbarkeit von Operationen;500
11.7.2;Kompensierende Aktionen;504
11.8;Vertiefende Literatur;505
11.9;Übungen;506
12;Transaktionsverwaltung ;510
12.1;Der Scheduler;510
12.2;Sperrmodelle;513
12.2.1;Sperrdisziplin;513
12.2.2;Verklemmungen;514
12.2.3;Livelock-Problem;515
12.3;Sperrprotokolle;516
12.3.1;Notwendigkeit von Sperrprotokollen;516
12.3.2;Zwei-Phasen-Sperrprotokoll;517
12.3.3;Striktes Zwei-Phasen-Sperrprotokoll;519
12.3.4;Aggressive und konservative Protokolle ;519
12.4;Sperrgranulate;520
12.4.1;Hierarchisches Sperren;521
12.4.2;Baumprotokolle für Sperren in Indexstrukturen;525
12.5;Nichtsperrende Verfahren zur Synchronisation;527
12.5.1;Zeitmarkenverfahren;528
12.5.2;Serialisierbarkeitsgraphentester;531
12.5.3;Optimistische Verfahren;532
12.6;Mehrversionen-Synchronisation;534
12.6.1;Begrenzung der Anzahl der Versionen;535
12.6.2;Synchronisation von MV-Schedules;536
12.7;Commit-Protokolle;541
12.7.1;Verteiltes Commit;542
12.7.2;Das Zwei-Phasen-Commit-Protokoll;542
12.7.3;Lineares 2PC;546
12.7.4;Verteiltes 2PC;546
12.7.5;Hierarchisches 2PC;547
12.7.6;Das Drei-Phasen-Commit-Protokoll;548
12.8;Transaktionen in SQL-DBMS;551
12.8.1;Aufweichung von ACID in SQL-92: Isolationsebenen;551
12.8.2;Explizite Sperren in SQL;554
12.9;Vertiefende Literatur;555
12.10;Übungen;556
13;Wiederherstellung und Datensicherung ;558
13.1;Beteiligte Systemkomponenten;559
13.2;Fehlerklassifikation und Recovery-Klassen;561
13.2.1;Fehlerklassifikation;561
13.2.2;Fehlerkategorien und zugehörige Recovery-Maßnahmen;564
13.3;Protokollierungsarten;565
13.3.1;Aufbau des Logbuchs;565
13.3.2;Physisches vs. logisches Logbuch;567
13.3.3;Sicherungspunkte;572
13.4;Recovery-Strategien;576
13.4.1;Seitenersetzungsstrategien;576
13.4.2;Propagierungsstrategien;577
13.4.3;Einbringstrategien;578
13.4.4;Konkrete Recovery-Strategien;578
13.4.5;Wiederanlauf nach einem Fehlerfall;581
13.4.6;Das Redo-Protokoll als konkrete Realisierung;582
13.4.7;Abbrüche im Recovery-Prozess;583
13.5;Das ARIES-Verfahren;584
13.5.1;Vorgehensweise in ARIES;584
13.5.2;Grundprinzipien und Datenstrukturen;585
13.5.3;Phasen des Wiederanlaufs;586
13.6;Schattenspeicherverfahren;588
13.7;Backup-Strategien und Archivierung;590
13.7.1;Backups und Archivierung;591
13.7.2;Spiegelung von Datenbanken;592
13.8;Vertiefende Literatur;593
13.9;Übungen;593
14;Abbildungsverzeichnis;596
15;Tabellenverzeichnis;604
16;Liste der Codefragmente;606
17;Sachindex;608
18;Schlüsselwortindex;620
19;Literaturverzeichnis;624
