Datenbanktechnik
Vorlesung Datenbanktechnik, 4. Semester Studiengang Wirtschaftsinformatik
Vorlesung Datenbanktechnik, 4. Semester Studiengang Wirtschaftsinformatik
-
- 1 / 65
-
Cartes-fiches
Was sind die Bestandteile eines Datenbanksystems?
- Datenbank: Sammlung zusammenhängender Daten
- einfach strukturiert, logisch zusammenhängend
- Ausschnitt der realen Welt
- Datenbankmanagementsystem: Menge von Programmen, um DB zu verwalten
- definieren, manipulieren, abfragen
- Strukturen und Daten
- Wartung und Administration
Die Vorteile eines Datenbanksystems im Vergleich zur Dateiverwaltung
- definierte API, damit unabhängige Datenverwaltung von Programmlogik
- hohe Verfügbarkeit
- verschiedene Benutzersichten
- standardisierte Datenbanksprache
- strukturierte Datenablage
- Redundanzfrei
- schnelle Zugriffe
- Konsistente Daten
- Transaktionskontrolle
Komponenten eines DBMS - der Stored Data Manager
- regelt Datentransfer zwischen Platte und Hauptspeicher
- mit Hilfe von Betriebssystem-Routinen
Komponenten eines DBMS - der DDL-Compiler
- übersetzt Schema-Definitionen
- speichert diese in den Katalog
- arbeitet mit Hilfe des SDM
Komponenten eines DBMS - der Run-Time Database Processor
- führt den Datenbankzugriff zur Laufzeit aus
- mit Hilfe SDM
Komponenten eines DBMS - der Query Compiler
- übersetzt interaktive Datenbankanfragen
- lässt Anfragen durch RTDP ausführen
Komponenten eines DBMS - die Concurrency control / das Recovery System
- regelt den konkurrierenden Zugriff mehrerer Benutzer
- stellt konsistenten Zustand nach Systemfehler wieder her
Ablageformen von Datensätzen - die unsortierte Datei
- sog. Heap Datei
- keine bestimmte Ordnung
- neue Sätze ungeordnet an das Ende angefügt
- Adresse des letzten Datei-Block wird im Header geführt
- geeignet für
- feste und variable Satzlängen
- spanned oder unsapnned
Ablageformen von Datensätzen - die sortierte Datei
- sog. sequentielle Datei
- Datensätze nach einem Sortierschlüssel geordnet
- geordnetes Einfügen der Sätze nach Sortierschlüsselfeld
- immer in Verbindung mit Index (=> index-sequenteille Datei)
Ablageformen von Datensätzen - die Hash-Datei
- Datensätze nach Hash-Funktion über einen sog. Hash-Schlüssel geordnet
Wie erfolgt der Datentransfer zwischen Hauptspeicher und Platte?
- blockweise
- die Positionierung der Scheib-/Leseklöpfe ist dabei am zeitaufwändigsten
Berechnungsformel: Anzahl Sätze pro Block
bfr = B / R
bfr: Blockungsfaktor
B: Blockgröße
R: (durchschnittliche) Satzlänge
Berechnungsformel: Anzahl Blöcke
b = r / bfr
b: Anzahl Datenblöcke
r: Anzahl Datensätze
bfr: Blockungsfaktor
Welche Inhalte stehen in den Dateikopf-Infos?
- Adressen der Dateiblöcke
- Formatbeschreibung, Feldängen etc. eines Datensatzes
Die lineare Suche
- kann bei jeder Datei angewendet werden
- bei genau 1 Treffer: AnzBZ = b/2
- sonst: AnzBZ = b
AnzBZ: Anzahl Blockzugriffe
b: Anzahl Blöcke
Die binäre Suche
- nur bei Sortierfeld
AnzBZ = LOG 2 (b)
AnzBZ: Anzahl Blockzugriffe
b: Anzahl Blöcke
Das statische Hashing
- Index in Form eines Array (=Hash-Tabelle) mit Bucket-Adressen
- Hash-Tabelle sehr klein, im Datei-Header geführt
- Reserviert festen Speicherbereich
Die Kollisionsauflösung beim statischen Hashing
- mittels verketteter Liste
- jeder Bucket hat Satz-Zeiger (= Bucket-Adresse + relative Satz-Position) auf Overflow-Bucket
- Sätze im Overflow-Bucket haben jeder Satz-Zeiger
Nachteile des Statischen Hashing
- Speicherverschwendung bei viel weniger Datensätzen als verfügbare Bucket-Kapa
- System langsam durch lange Overflow-Listen bei mehr Datensätzen als Bucket-Kapa
Das dynamische Hashing
- erweiterbares Hashing mittels dynamischem Hash-Verzeichnis
- je nach Bedarf wird Anzahl Buckets erhöht bzw. verringert
- daher keine globale Reorgs erforderlich, max. lokale Bucket-Reorg
- Hash-Funktionswerte werden binär betrachtet (bspw.: nur letzten drei Bits von h(k))
Vor- und Nachteile von Hash-Datenbanken
Vorteile
- schnellstes Verfahren für Zugriff auf einen beliebigen Datensatz
- gut bei unique-Attribut
Nachteile
- schlecht bei Hash-Attribut mit gleichen Ausprägungen => Kollisionen
- für Range-Suche nicht braucbar
- Suche über Nicht-Hash-Feld => lineare Suche
Die Primärorganisation einer Datei
- Heap (unsortiert)
- sequentiell (sortiert)
- Hash (statisch, dynamisch)
Der Primärindex
- zusätzliche, schnelle Zugriffsmöglichkeit unabhängig von Primärorganisation einer Datei
- Index über eindeutiges Attribut, nach der Datei physisch (primär) geordnet ist
- pro Datenblock ein Eintrag in Index-Datei
- erster Satz im Block: Ankersatz
- nicht-dichter Index, weil nicht für jeden DS ein Indexeintrag
- Indexeintrag: Wert des PS für ersten Datensatz
Der Clusterindex
- zusätzliche, schnelle Zugriffsmöglichkeit unabhängig von Primärorganisation einer Datei
- Primärindex, aber Ordnungsfeld nicht eindeutig
- DS nach Nichtschlüsselfeld geordnet
- pro unterschiedlichen Wert ein Eintrag in Index-Datei
- Adresse des Datenblocks der den 1. mit Wert enthägt
- nicht-dichter Index
Der Sekundärindex
- zusätzliche, schnelle Zugriffsmöglichkeit unabhängig von Primärorganisation einer Datei
- Index über jedes nicht ordnende Attribute einer Datei
- zusätzlich zu Primärindex können mehrere Sekundärindexe existieren
- unabhängig von Primärordnung der Datei
- zwei Arten
- Index über eindeutiges Attribut (Sekundärschlüssel)
- Index über nicht eindeutiges Attribut
Der Sekundärschlüssel über ein eindeutiges Attribut
- pro Datensatz ein Eintrag in Index-Datei
- dichter Index
- Datenzeiger auf Blockadresse!
- über Schlüsselkandidat
Mehrstufiger Index
- Index über Index über Index...
- bis auf n-ter Ebene nur noch 1 Indexblock notwendig
- zur Optimierung der Anzahl der Blockzugriffe
Die Höhe eines mehrstufigen Index
LOG fan-out (b)
fan-out: Blockfaktor der Index-Datei
b: Anzahl Indexeinträge (= Anzahl Datenblöcke) auf 1. Ebene
Der dynamische mehrstufige Index als B-Baum
- Indexblöcke haben Freiraum
- Ordnung p (= fan-out = bfr)
- gibt an, wieviele Teilbäume verpointert werden können.
- p-1: Anzahl Werte in einem Knoten
- variable Anzahl von Schlüsseln (aufsteigend sortiert)
- Wurzel hat o, 2 oder mehr Knoten-zeiger
- alle Blätter auf derselben Höhe
Überlauf der Wurzel bei einem B-Baum
- Wurzel splitten und neue Wurzel schaffen
- Mittlerer Indexwert in neue Wurzel
- linker Rest in linkes Child
- rechter Rest in rechtes Child
Überlauf eines Blattes bei einem B-Baum
- Knoten auf gleicher Ebene splitten
- mittlerer Indexwert in Parent-Knoten mit zwei Zeigern zu gesplitteten Knoten
- Achtung: ggf. Split Parent-Knoten notwendig!
Unterlauf eines Knoten in einem B-Baum
- Knoten weniger Werte als p/2
- Knoten mit Nachbarknoten zusammenlegen
- kann ggf. zur Unterlauf Parent-Knoten führen
Der dynamische mehrstufige Index als B+ -Baum
- Indexblöcke haben Freiraum
- Ordnung p (= fan-out = bfr)
- gibt an, wieviele Teilbäume verpointert werden können.
- p-1: Anzahl Werte in einem Knoten
- Datenzeiger nur in Blätter => mehr Platz für Suchwerte => weniger Ebenen => schneller
- Suchwert eines mittleren Knotens gibt es noch einmal in einem Blatt
- Alle Blätter sind miteinander verlinkt
Überlauf eines Blattes in einem B+ - Baum
- teile Blatt
- behalte die ersten j Einträge im Originalblatt
- setze Rest in das neue Blatt
- j-te Wert in Elternknoten replizieren
- Zeiger auf neues Blatt
j = (Pblatt + 1) / 2
Überlauf eines Elternknoten in einem B+ - Baum
- teile Knoten und behalten die ersten i - 1 Einträge im Originalknoten
- der i-te Wert wandert in Elternknoten (kein Replizieren!)
- setze Rest in neu geschaffenen Knoten
i = (p + 1) / 2)
Unterlauf eines Blattes in einem B+ - Baum
- vereinige Blattinhalt mit linkem oder rechtem Geschiwster und teile gleichmäßig auf (Erhaltungstrieb!)
- falls zu wenig Werte: verschmelze Blatt mit Geschwister
- Elternknoten anpassen
- neue Indexwerte und Zeiger anpassen
Unterlauf eines Elternknotens in einem B+ - Baum
- vereinige inneren Knoten mit seinem Geschwister
- Teile Inhalt gleichmäßig auf
- oder bei zu wenig Werten lassen
Wie heißen B+ - Bäume, deren Knoten zu mindesten 2/3 gefüllt sein müssen?
B* - Bäume
Die zwei Stufen zur Optimierung einer SELECT-Anfrage
- Optimierung jeder einzelnen Operation über systematische Kostenschätzungen
- Optimierung der Reihenfolger der einzelnen Operationen über heuristische Regeln
Berechnungsformel: Selektionskardinalität
s = sl * r = r / d
s: Selektionskardinalität
sl: Selektivität
r: Anzahl Datensätze
d: Anzahl Werte
