TUM Informatik III: Inhaltsverzeichnis

TU München - Fakultät für Informatik
Lehrstuhl III: Datenbanksysteme

Inhaltsverzeichnis - Datenbanksysteme (6. Auflage, 2006)


Vorwort				15

1	Einleitung und Übersicht			17
	1.1	Motivation für den Einsatz eines DBMS		17
	1.2	Datenabstraktion		19
	1.3	Datenunabhängigkeit		20
	1.4	Datenmodelle		21
	1.5	Datenbankschema und Ausprägung		22
	1.6	Einordnung der Datenmodelle		22
		1.6.1	Modelle des konzeptuellen Entwurfs	22
		1.6.2	Logische (Implementations-)Datenmodelle	23
	1.7	Architekturübersicht eines DBMS		26
	1.8	Übungen		28
	1.9	Literatur		28

2	Datenbankentwurf			29
	2.1	Abstraktionsebenen des Datenbankentwurfs		29
	2.2	Allgemeine Entwurfsmethodik		30
	2.3	Die Datenbankentwurfsschritte		31
	2.4	Die Anforderungsanalyse		31
		2.4.1	Informationsstrukturanforderungen	33
		2.4.2	Datenverarbeitungsanforderungen	35
	2.5	Grundlagen des Entity-Relationship-Modells		35
	2.6	Schlüssel		37
	2.7	Charakterisierung von Beziehungstypen		37
		2.7.1	Funktionalitäten der Beziehungen	37
		2.7.2	Funktionalitätsangaben bei n-stelligen Beziehungen	39
		2.7.3	Die $(min, max)$-Notation	42
	2.8	Existenzabhängige Entitytypen		46
	2.9	Generalisierung		47
	2.10	Aggregation		48
	2.11	Kombination von Generalisierung und Aggregation		50
	2.12	Konsolidierung, Sichtenintegration		51
	2.13	Konzeptuelle Modellierung mit UML		57
		2.13.1	UML-Klassen	57
		2.13.2	Assoziationen zwischen Klassen	58
		2.13.3	Aggregation in UML	59
		2.13.4	Anwendungsbeispiel: Begrenzungsflächendarstellung von Polyedern in UML	60
		2.13.5	Generalisierung in UML-Notation	61
		2.13.6	Die Modellierung der Universität in UML	61
		2.13.7	Verhaltensmodellierung in UML	62
		2.13.8	Anwendungsfall-Modellierung (use cases)	62
		2.13.9	Interaktionsdiagramme	64
		2.13.10	Interaktionsdiagramm zur Prüfungsdurchführung	64
	2.14	Übungen		65
	2.15	Literatur		67

3	Das relationale Modell			69
	3.1	Definition des relationalen Modells		69
		3.1.1	Mathematischer Formalismus	69
		3.1.2	Schema-Definition	70
	3.2	Umsetzung eines konzeptuellen Schemas in ein relationales Schema		71
		3.2.1	Relationale Darstellung von Entitytypen	71
		3.2.2	Relationale Darstellung von Beziehungen	71
	3.3	Verfeinerung des relationalen Schemas		76
		3.3.1	$1$:$N$-Beziehungen	76
		3.3.2	1:1-Beziehungen	78
		3.3.3	Vermeidung von Null-Werten	79
		3.3.4	Relationale Modellierung der Generalisierung	80
		3.3.5	Beispielausprägung der Universitäts-Datenbank	81
		3.3.6	Relationale Modellierung schwacher Entitytypen	83
	3.4	Die relationale Algebra		83
		3.4.1	Selektion	84
		3.4.2	Projektion	85
		3.4.3	Vereinigung	85
		3.4.4	Mengendifferenz	86
		3.4.5	Kartesisches Produkt (Kreuzprodukt)	86
		3.4.6	Umbenennung von Relationen und Attributen	87
		3.4.7	Definition der relationalen Algebra	88
		3.4.8	Der relationale Verbund (Join)	88
		3.4.9	Mengendurchschnitt	93
		3.4.10	Die relationale Division	94
		3.4.11	Operatorbaum-Darstellung	95
	3.5	Der Relationenkalkül		95
		3.5.1	Beispielanfrage im relationalen Tupelkalkül	96
		3.5.2	Quantifizierung von Tupelvariablen	97
		3.5.3	Formale Definition des Tupelkalküls	98
		3.5.4	Sichere Ausdrücke des Tupelkalküls	99
		3.5.5	Der relationale Domänenkalkül	99
		3.5.6	Beispielanfragen im Domänenkalkül	100
		3.5.7	Sichere Ausdrücke des Domänenkalküls	101
	3.6	Ausdruckskraft der Anfragesprachen		102
	3.7	Übungen		102
	3.8	Literatur		105

4	Relationale Anfragesprachen			107
	4.1	Geschichte		107
	4.2	Datentypen		108
	4.3	Schemadefinition		108
	4.4	Schemaveränderung		109
	4.5	Elementare Datenmanipulation: Einfügen von Tupeln		110
	4.6	Einfache SQL-Anfragen		110
	4.7	Anfragen über mehrere Relationen		111
	4.8	Aggregatfunktionen und Gruppierung		114
	4.9	Geschachtelte Anfragen		115
	4.10	Quantifizierte Anfragen in SQL		120
	4.11	Nullwerte		122
	4.12	Spezielle Sprachkonstrukte		123
	4.13	Joins in SQL-92		125
	4.14	Rekursion		125
	4.15	Veränderungen am Datenbestand		130
	4.16	Sichten		132
	4.17	Sichten zur Modellierung von Generalisierungen		133
	4.18	Charakterisierung update-fähiger Sichten		135
	4.19	Einbettung von SQL in Wirtssprachen		136
	4.20	Anfragen in Anwendungsprogrammen		137
	4.21	JDBC: Java Database Connectivity		140
		4.21.1	Verbindungsaufbau zu einer Datenbank	141
		4.21.2	Resultset-Programmbeispiel	143
		4.21.3	Vorübersetzung von SQL-Ausdrücken	145
	4.22	SQLJ: Eine Einbettung von SQL in Java		145
	4.23	Query by Example		148
	4.24	Übungen		150
	4.25	Literatur		153

5	Datenintegrität			155
	5.1	Referentielle Integrität		156
	5.2	Gewährleistung referentieller Integrität		156
	5.3	Referentielle Integrität in SQL		157
	5.4	Überprüfung statischer Integritätsbedingungen		158
	5.5	Das Universitätsschema mit Integritätsbedingungen		160
	5.6	Komplexere Integritätsbedingungen		162
	5.7	Trigger		163
	5.8	Übungen		165
	5.9	Literatur		166

6	Relationale Entwurfstheorie			167
	6.1	Funktionale Abhängigkeiten		167
		6.1.1	Konventionen zur Notation	168
		6.1.2	Einhaltung einer funktionalen Abhängigkeit	168
	6.2	Schlüssel		169
	6.3	Bestimmung funktionaler Abhängigkeiten		170
		6.3.1	Kanonische Überdeckung	173
	6.4	`Schlechte' Relationenschemata		174
		6.4.1	Die Updateanomalien	174
		6.4.2	Einfügeanomalien	175
		6.4.3	Löschanomalien	175
	6.5	Zerlegung (Dekomposition) von Relationen		175
		6.5.1	Verlustlosigkeit	176
		6.5.2	Kriterien für die Verlustlosigkeit einer Zerlegung	178
		6.5.3	Abhängigkeitsbewahrung	179
	6.6	Erste Normalform		181
	6.7	Zweite Normalform		182
	6.8	Dritte Normalform		184
	6.9	Boyce-Codd Normalform		186
	6.10	Mehrwertige Abhängigkeiten		189
	6.11	Vierte Normalform		191
	6.12	Zusammenfassung		193
	6.13	Übungen		194
	6.14	Literatur		197

7	Physische Datenorganisation			199
	7.1	Speichermedien		199
	7.2	Speicherarrays: RAID		200
	7.3	Der Datenbankpuffer		204
	7.4	Abbildung von Relationen auf den Sekundärspeicher		206
	7.5	Indexstrukturen		207
	7.6	ISAM		209
	7.7	B-Bäume		211
	7.8	$\unhbox \voidb@x \hbox {B}^+\mskip -\thinmuskip $-Bäume		215
	7.9	Präfix-$\unhbox \voidb@x \hbox {B}^+\mskip -\thinmuskip $-Bäume		216
	7.10	Hashing		217
	7.11	Erweiterbares Hashing		219
	7.12	Mehrdimensionale Indexstrukturen		221
	7.13	Ballung logisch verwandter Datensätze		225
	7.14	Unterstützung eines Anwendungsverhaltens		227
	7.15	Physische Datenorganisation in SQL		229
	7.16	Übungen		229
	7.17	Literatur		231

8	Anfragebearbeitung			233
	8.1	Logische Optimierung		234
		8.1.1	Äquivalenzen in der relationalen Algebra	236
		8.1.2	Anwendung der Transformationsregeln	238
	8.2	Physische Optimierung		242
		8.2.1	Implementierung der Selektion	244
		8.2.2	Implementierung von binären Zuordnungsoperatoren	244
		8.2.3	Gruppierung und Duplikateliminierung	251
		8.2.4	Projektion und Vereinigung	252
		8.2.5	Zwischenspeicherung	252
		8.2.6	Übersetzung der logischen Algebra	254
	8.3	Kostenmodelle		257
		8.3.1	Selektivitäten	258
		8.3.2	Kostenabschätzung für die Selektion	260
		8.3.3	Kostenabschätzung für den Join	261
		8.3.4	Kostenabschätzung für die Sortierung	261
	8.4	`Tuning' von Datenbankanfragen		262
	8.5	Übungen		263
	8.6	Literatur		266

9	Transaktionsverwaltung			269
	9.1	Begriffsbildung		269
	9.2	Anforderungen an die Transaktionsverwaltung		270
	9.3	Operationen auf Transaktions-Ebene		270
	9.4	Abschluss einer Transaktion		271
	9.5	Eigenschaften von Transaktionen		273
	9.6	Transaktionsverwaltung in SQL		274
	9.7	Zustandsübergänge einer Transaktion		275
	9.8	Literatur		276

10	Fehlerbehandlung			277
	10.1	Fehlerklassifikation		277
		10.1.1	Lokaler Fehler einer Transaktion	277
		10.1.2	Fehler mit Hauptspeicherverlust	278
		10.1.3	Fehler mit Hintergrundspeicherverlust	279
	10.2	Die Speicherhierarchie		279
		10.2.1	Ersetzung von Puffer-Seiten	279
		10.2.2	Einbringen von Änderungen einer Transaktion	280
		10.2.3	Einbringstrategie	281
		10.2.4	Hier zugrunde gelegte Systemkonfiguration	282
	10.3	Protokollierung von Änderungsoperationen		282
		10.3.1	Struktur der Log-Einträge	283
		10.3.2	Beispiel einer Log-Datei	283
		10.3.3	Logische oder physische Protokollierung	283
		10.3.4	Schreiben der Log-Information	284
		10.3.5	Das WAL-Prinzip	286
	10.4	Wiederanlauf nach einem Fehler		286
		10.4.1	Analyse des Logs	287
		10.4.2	Redo-Phase	288
		10.4.3	Undo-Phase	288
	10.5	Fehlertoleranz des Wiederanlaufs		288
	10.6	Lokales Zurücksetzen einer Transaktion		290
	10.7	Partielles Zurücksetzen einer Transaktion		291
	10.8	Sicherungspunkte		292
		10.8.1	Transaktionskonsistente Sicherungspunkte	292
		10.8.2	Aktionskonsistente Sicherungspunkte	293
		10.8.3	Unscharfe (fuzzy) Sicherungspunkte	295
	10.9	Recovery nach einem Verlust der materialisierten Datenbasis		296
	10.10	Übungen		297
	10.11	Literatur		298

11	Mehrbenutzersynchronisation			299
	11.1	Fehler bei unkontrolliertem Mehrbenutzerbetrieb		300
		11.1.1	Verlorengegangene Änderungen (lost update)	300
		11.1.2	Abhängigkeit von nicht freigegebenen Änderungen	300
		11.1.3	Phantomproblem	301
	11.2	Serialisierbarkeit		301
		11.2.1	Beispiele serialisierbarer Ausführungen (Historien)	302
		11.2.2	Nicht serialisierbare Historie	302
	11.3	Theorie der Serialisierbarkeit		305
		11.3.1	Definition einer Transaktion	305
		11.3.2	Historie (Schedule)	306
		11.3.3	Äquivalenz zweier Historien	307
		11.3.4	Serialisierbare Historien	308
		11.3.5	Kriterien für Serialisierbarkeit	308
	11.4	Eigenschaften von Historien bezüglich der Recovery		310
		11.4.1	Rücksetzbare Historien	310
		11.4.2	Historien ohne kaskadierendes Rücksetzen	310
		11.4.3	Strikte Historien	311
		11.4.4	Beziehungen zwischen den Klassen von Historien	311
	11.5	Der Datenbank-Scheduler		312
	11.6	Sperrbasierte Synchronisation		313
		11.6.1	Zwei Sperrmodi	313
		11.6.2	Zwei-Phasen-Sperrprotokoll	314
		11.6.3	Kaskadierendes Rücksetzen (Schneeballeffekt)	316
	11.7	Verklemmungen (Deadlocks)		316
		11.7.1	Erkennung von Verklemmungen	317
		11.7.2	Preclaiming zur Vermeidung von Verklemmungen	318
		11.7.3	Verklemmungsvermeidung durch Zeitstempel	319
	11.8	Hierarchische Sperrgranulate		320
	11.9	Einfüge- und Löschoperationen, Phantome		324
	11.10	Zeitstempel-basierende Synchronisation		325
	11.11	Optimistische Synchronisation		327
	11.12	Synchronisation von Indexstrukturen		328
	11.13	Mehrbenutzersynchronisation in SQL-92		331
	11.14	Übungen		333
	11.15	Literatur		336

12	Sicherheitsaspekte			337
	12.1	Discretionary Access Control		339
	12.2	Zugriffskontrolle in SQL		339
		12.2.1	Identifikation und Authentisierung	340
		12.2.2	Autorisierung und Zugriffskontrolle	340
		12.2.3	Sichten	341
		12.2.4	Individuelle Sicht für eine Benutzergruppe	342
		12.2.5	Auditing	343
	12.3	Verfeinerung des Autorisierungsmodells		343
		12.3.1	Rollenbasierte Autorisierung: Implizite Autorisierung von Subjekten	344
		12.3.2	Implizite Autorisierung von Operationen	346
		12.3.3	Implizite Autorisierung von Objekten	346
		12.3.4	Implizite Autorisierung entlang einer Typhierarchie	347
	12.4	Mandatory Access Control		348
	12.5	Multilevel-Datenbanken		349
	12.6	Kryptographie		352
		12.6.1	Der Data Encryption Standard	353
		12.6.2	Public-Key Kryptographie	354
		12.6.3	Public Key Infrastruktur (PKI)	356
	12.7	Zusammenfassung		356
	12.8	Übungen		357
	12.9	Literatur		358

13	Objektorientierte Datenbanken			359
	13.1	Bestandsaufnahme relationaler Datenbanksysteme		359
	13.2	Vorteile der objektorientierten Datenmodellierung		363
	13.3	Der ODMG-Standard		364
	13.4	Eigenschaften von Objekten		365
		13.4.1	Objektidentität	366
		13.4.2	Typ eines Objekts	367
		13.4.3	Wert eines Objekts	367
	13.5	Definition von Objekttypen		368
		13.5.1	Attribute	368
		13.5.2	Beziehungen	368
		13.5.3	Typeigenschaften: Extensionen und Schlüssel	375
	13.6	Modellierung des Verhaltens: Operationen		375
	13.7	Vererbung und Subtypisierung		378
		13.7.1	Terminologie	378
		13.7.2	Einfache und Mehrfachvererbung	379
	13.8	Beispiel einer Typhierarchie		380
	13.9	Verfeinerung (Spezialisierung) und spätes Binden von Operationen		383
	13.10	Mehrfachvererbung		386
	13.11	Die Anfragesprache OQL		387
		13.11.1	Einfache Anfragen	387
		13.11.2	Geschachtelte Anfragen und Partitionierung	388
		13.11.3	Pfadausdrücke	389
		13.11.4	Erzeugung von Objekten	390
		13.11.5	Operationsaufruf	390
	13.12	C++-Einbettung		390
		13.12.1	Objektidentität	392
		13.12.2	Objekterzeugung und Ballung	393
		13.12.3	Einbettung von Anfragen	393
	13.13	Übungen		394
	13.14	Literatur		395

14	Erweiterbare und objekt-relationale Datenbanken			397
	14.1	Übersicht über die objekt-relationalen Konzepte		397
	14.2	Large Objects (LOBs)		398
	14.3	Distinct Types: Einfache benutzerdefinierte Datentypen		400
	14.4	Table Functions		404
		14.4.1	Nutzung einer \textit {Table Function} in Anfragen	405
		14.4.2	Implementierung einer \textit {Table Function}	405
	14.5	Benutzerdefinierte strukturierte Objekttypen		407
	14.6	Geschachtelte Objekt-Relationen		411
	14.7	Vererbung von SQL-Objekttypen		415
	14.8	Komplexe Attribut-Typen		418
	14.9	Übungen		419
	14.10	Literatur		420

15	Deduktive Datenbanken			421
	15.1	Terminologie		421
	15.2	Datalog		421
	15.3	Eigenschaften von Datalog-Programmen		425
		15.3.1	Rekursivität	425
		15.3.2	Sicherheit von Datalog-Regeln	425
	15.4	Auswertung von nicht-rekursiven Datalog-Programmen		426
		15.4.1	Auswertung eines Beispielprogramms	426
		15.4.2	Auswertungs-Algorithmus	429
	15.5	Auswertung rekursiver Regeln		431
	15.6	Inkrementelle (semi-naive) Auswertung rekursiver Regeln		433
	15.7	Bottom-Up oder Top-Down Auswertung		437
	15.8	Negation im Regelrumpf		439
		15.8.1	Stratifizierte Datalog-Programme	439
		15.8.2	Auswertung von Regeln mit Negation	440
		15.8.3	Ein etwas komplexeres Beispiel	441
	15.9	Ausdruckskraft von Datalog		441
	15.10	Übungen		443
	15.11	Literatur		447

16	Verteilte Datenbanken			449
	16.1	Terminologie und Abgrenzung		449
	16.2	Entwurf verteilter Datenbanken		451
	16.3	Horizontale und vertikale Fragmentierung		453
		16.3.1	Horizontale Fragmentierung	454
		16.3.2	Abgeleitete horizontale Fragmentierung	456
		16.3.3	Vertikale Fragmentierung	457
		16.3.4	Kombinierte Fragmentierung	459
		16.3.5	Allokation für unser Beispiel	460
	16.4	Transparenz in verteilten Datenbanken		461
		16.4.1	Fragmentierungstransparenz	461
		16.4.2	Allokationstransparenz	462
		16.4.3	Lokale Schema-Transparenz	462
	16.5	Anfrageübersetzung und -optimierung in VDBMS		463
		16.5.1	Anfragebearbeitung bei horizontaler Fragmentierung	463
		16.5.2	Anfragebearbeitung bei vertikaler Fragmentierung	465
	16.6	Join-Auswertung in VDBMS		467
		16.6.1	Join-Auswertung ohne Filterung	467
		16.6.2	Join-Auswertung mit Filterung	468
	16.7	Transaktionskontrolle in VDBMS		471
	16.8	Mehrbenutzersynchronisation in VDBMS		476
		16.8.1	Serialisierbarkeit	476
		16.8.2	Das Zwei-Phasen-Sperrprotokoll in VDBMS	476
	16.9	Deadlocks in VDBMS		477
		16.9.1	Erkennung von Deadlocks	477
		16.9.2	Deadlock-Vermeidung	480
	16.10	Synchronisation bei replizierten Daten		481
	16.11	Übungen		484
	16.12	Literatur		487

17	Betriebliche Anwendungen: OLTP, Data Warehouse, Data Mining			489
	17.1	SAP R/3: Ein betriebswirtschaftliches Datenbankanwendungssystem		489
		17.1.1	Architektur von SAP R/3	489
		17.1.2	Datenmodell und Schema von SAP R/3	490
		17.1.3	ABAP/4	491
		17.1.4	Transaktionen in SAP R/3	494
	17.2	Data Warehouse, Decision-Support, OLAP		495
		17.2.1	Datenbankentwurf für das Data Warehouse	496
		17.2.2	Anfragen im Sternschema: Star Join	499
		17.2.3	Roll-Up/Drill-Down-Anfragen	500
		17.2.4	Flexible Auswertungsmethoden	502
		17.2.5	Materialisierung von Aggregaten	502
		17.2.6	Der cube-Operator	504
		17.2.7	Wiederverwendung materialisierter Aggregate	504
		17.2.8	Bitmap-Indices für OLAP-Anfragen	507
		17.2.9	Auswertungsalgorithmen für komplexe OLAP-Anfragen	508
		17.2.10	Data Warehouse-Architekturen	510
	17.3	Data Mining		511
		17.3.1	Klassifikation von Objekten	512
		17.3.2	Assoziationsregeln	513
		17.3.3	Der Á Priori-Algorithmus	514
		17.3.4	Bestimmung der Assoziationsregeln	516
		17.3.5	Cluster-Bestimmung	517
	17.4	Übungen		518
	17.5	Literatur		519

18	Internet-Datenbankanbindungen			521
	18.1	HTML- und HTTP-Grundlagen		521
		18.1.1	HTML: Die Hypertext-Sprache des World Wide Web	521
		18.1.2	Adressierung von Web-Dokumenten	522
		18.1.3	Client/Server-Architektur des World Wide Web	524
		18.1.4	HTTP: Das HyperText Transfer Protokoll	524
		18.1.5	HTTPS	525
	18.2	Web-Datenbank-Anbindung via Servlets		526
		18.2.1	Beispiel-Servlet	526
	18.3	Java Server Pages / Active Server Pages		532
		18.3.1	JSP/HTML-Seite mit Java-Code	533
		18.3.2	HTML-Seite mit Java-Bean-Aufruf	535
		18.3.3	Die Java-Bean Komponente VorlesungenBean	536
		18.3.4	Sokrates' Homepage	538
	18.4	Datenbankanbindung via Java-Applets		538
	18.5	Übungen		539
	18.6	Literatur		540

19	XML-Datenmodellierung und Web-Services			541
	19.1	XML-Datenmodellierung		541
		19.1.1	Schema oder kein Schema	542
		19.1.2	Rekursive Schemata	544
		19.1.3	Universitätsinformation in XML-Format	544
		19.1.4	XML-Namensräume	546
		19.1.5	XML Schema: Eine Schemadefinitionssprache	548
		19.1.6	Verweise (Referenzen) in XML-Daten	550
	19.2	XQuery: Eine XML-Anfragesprache		551
		19.2.1	Pfadausdrücke	551
		19.2.2	Verkürzte XPath-Syntax	556
		19.2.3	Beispiel-Pfadausdrücke in verkürzter Syntax	557
		19.2.4	Anfragesyntax von XQuery	558
		19.2.5	Geschachtelte Anfragen	560
		19.2.6	Joins in XQuery	560
		19.2.7	Join-Prädikat im Pfadausdruck	561
		19.2.8	Das let-Konstrukt	562
		19.2.9	Dereferenzierung in FLWOR-Ausdrücken	563
		19.2.10	Rekursive Anfragen	565
	19.3	Zusammenspiel von relationalen Datenbanken und XML		567
		19.3.1	XML-Repräsentation gemäß Pre- und Postorder-Rängen	573
		19.3.2	Der neue Datentyp xml	577
		19.3.3	Änderungen der XML-Dokumente	581
		19.3.4	Publikation relationaler Daten als XML-Dokumente	582
	19.4	Web-Services		586
		19.4.1	Erstellen und Nutzen eines Web-Services im Überblick	588
		19.4.2	Das Auffinden von Diensten	591
		19.4.3	Ein Beispiel-Web-Service	593
		19.4.4	Definition der Web-Service-Schnittstellen	593
		19.4.5	Nachrichtenformat für die Interaktion mit Web-Services	596
		19.4.6	Implementierung des Web-Services	598
		19.4.7	Aufruf des Web-Services	599
	19.5	Übungen		601
	19.6	Literatur		604

20	Leistungsbewertung			607
	20.1	Überblick über Datenbanksystem-Benchmarks		607
	20.2	Der TPC-C Benchmark		607
	20.3	Die TPC-H und TPC-R (früher TPC-D) Benchmarks		610
	20.4	Der OO7 Benchmark für oo-Datenbanken		616
	20.5	Der TPC-W Benchmark		617
	20.6	Übungen		620
	20.7	Literatur		620

Literaturverzeichnis				621

Index				657

Lehrstuhl für Datenbanksysteme
Letzte Änderung: 05.04.2006 um 17:16:46