Alle Vl db Flashcards
Externe Ebene (ANSI-SPARK)
benutzerdefinierte Sichten
ANSI-SPARK Architektur
Externe Ebene, Logische Ebene, Physische Ebene
Logische Ebene (ANSI-SPARK)
definiert logische Datenbankenstruktur und deren Beziehungen unabhängig von physischer Repräsentation
Physische Ebene (ANSI-SPARK)
Festlegung physischer Schemata (Art und Weise der Datenspeicherung)
Zweck der Schichtenarchitektur
Datenunabhängigkeit(logische und physische Abhängigkeit) -> Änderung auf einer Schicht ohne Einfluss auf andere Schichten
Robust gegenüber Änderungen
Schlüsselattribute
kann Entity eindeutig identifizieren
disjoint-constraint
disjunkt: Untertypen sind verschieden
overlapping: Untertypen schneiden sich
completness-constraint
total: jede Entitiy des Obertyps auch Entity eines Untertyps
partiell
Datenbankschema
Menge der Relationsschemata
Datenbank
Menge der aktuellen Relationen
Kanidatenschlüssel
Auswahl für Primärschlüssel
Primärschlüssel
-minimal
-eindeutige Identifizierung
-zeitlich stabil
Fremdschlüssel
Attribut (bzw. Kombination) welches auf den Primärschlüssel verweist
minimal
Horizontale Partitionierung
jede Entity in seperaten Relation mit allen Attributen
Vertikale Partitionierung
jede Entity in eigener Relation mit Verknüpfung zu der Beziehungsrelation
Universalrelation
eine Relation
Relationale Algebra
interne Repräsentation von DB-Anfragen
ausschließlich lesende Operationen
Projektion 𝜋
Auswahl von Spalten
Selektion σ
Auswahl von Tupel unter einer Bedingung
Kartesisches Produkt
Kombination aller Tupel
keine Duplikate
Differenz R-S
alle Tupel die in R sind und nicht in S
keine Duplikate
Vereinigung
alle Tupel
bei gleichem Relationsschema
keine Duplikate
Durchschnitt
alle Tupel die sowohl in R als auch in S sind
keine Duplikate
Division
alle Tupel von R die alle Tupel aus S als Partner haben
keine Duplikate
Natural Join
verbinden von Tupel über gleiche Attribute
Theta Join
Natrual Join über andere Vergleichsoperatoren als =
Equi Join
Verbinden über Gleichheit von Attributen
Left outer Join
Verbund über gleiche Attribute, Ausgabe von R mit verbundspartner in S und Attribute aus R die in S keinen Join Partner haben -> NULL
Right Outer Join
Verbund über gleiche Attribute und Ausgabe von allen Attributen von S, die keinen Join Partner in R haben -> NULL
Full Outer Join
Left Outer Join + Right Outer Join
Semi Join
enthält nur die Tupel von R, die die Join Bedingung mit S erfüllen
Referentielle Integrität
-eindeutige Identifikation der Tupel durch Schlüsselattribute
-Datensätze dürfen über Fremdschlüssel nur auf exestierende Daten verweisen
Vorteil von datenbanksichten
- erhöht Sicherheit
-steuern Berechtigungen
-vereinfachen SQL-Anfragen - Unabhängigkeit zwischen Tabellen und Sichten
Trigger-Konzepte
Event
Condition
Action
Insert Anomalie
-fehlen von Primärschlüsselattributen
-Ursache: Vermischung von Entitätstypen
Update Anomalie
-nicht alle Vorkommen eines Attributwert werden geändert
-Ursache: Redundanz
Delete Anomalie
-durch löschen eines Datensatzes gehen mehr Informationen als gewünscht verloren
-Ursachen: vermischen von Entitätstypen
Funktionale Abhängigkeit
ein Attributwert oder Kombination von Attributwerten bestimmt den Wert eines anderen Attributs bzw. einer anderen Attributmenge
Volle funktionale Abhängigkeit
Abhängigkeit ist minimal -> es existiert keine Teilmenge
partielle funktionale Abhängigkeit
Abhängigkeit ist NICHT minimal -> es existiert eine Teilmenge
Hülle F+
Menge aller funktionalen Abhängigkeit, die aus funktionalen Abhängigkeiten in F ableitbar sind
Armstrong Axiome
-Bestimmung der Abhängigkeiten
-reflexiv
-Verstärkung
-transitiv
Erweiterte Armstrong Axiome
Vereinigung
Dekomposition
Pseudotransitivität
Kriterien für die Zerlegung eines Relationsschemas
-Verlustlosigkeit: Ursprungrelation muss durch einen Natrual Join der Teilrelation rekonstruierbar sein
-Abhängigikeitserhaltung: funktionale Abhängigkeiten müssen übertragbar sein auf Teilrelationen -> hüllengetreue Zerlegung
- Normalform
alle Attribute sind atomar
- Normalform
- 1.NF
-jedes Attribut ist Teil eines Kanditatenschlüssels oder von JEDEM Kanditatenschlüssel voll funktional abhängig
- Normalform
- 2.NF
-keine funktionalen Abhängigkeiten von Nichtschlüsselattributen innerhalb von Relationen -> KEINE transitiven Abhängigkeiten
5 Schichten Architektur
Datensystem
Zugriffssystem
Speichersystem
Pufferverwaltung
Betriebssystem
Speichersystem Organisation
double linked list
Speichersystem Header
information previos and follwing page
number of page (optional)
Type of recors
Information about free space
Satzadressierung
Speichersystem
Adressen werden beim Einfügen von Sätzen vergeben und später zum Zugreifen verwendet
Satzadressierung Probleme
Speichersystem
Eindeutigkeit -> lebenslange Adressierung
langfristige Speicherung von Datensätzen
Vermeidung von Technologieabhängigkeit
Unterstützung Migration
Satzadressierung Ziele
Speichersystem
schneller, direkter Zugriff
Stabilität gegenüber geringfügigen Verschiebungen
Selten/keine Reorganisation
TID-Konzept
Speichersystem
Adressierung über Indirektion innerhalb einer Seite
Array mit Byte-Postion der Sätze in der Sätze
TID:Tupel-Identifier (Seitennummer + Index)
binäre Suchbäume
Zugriffssystem
maximale Größe der Knoten = Speicherkapazität der Seite
direkter Schlüsselzugriff
sortierter Sequentieller Zugriff
binäre Suchbäume
Eigenschaften
Zugriffssystem
Typ(k,h)
h = maximale Länge jeden Pfades
k = minimale # Einträge
2k = maximale # Einträge
-> außer Wurzel
k+1 = min # von Nachfolgern
2k+1 = maximale # von Nachfolgern
mindestens 50% Speicherauslastung
hohe Höhe
keine Redundanz
B*-Baum
Eigenschaften
Zugriffssystem
alle Sätze in Blattknoten
innere Knoten nur Verzweigungsinformation
teilweise redundant (Schlüsselwerte)
geringe Höhe
Bitmap-Index
Zugriffssystem
Bitliste für jeden Attributwert
jedem Tupel wird ein Bit in Liste zugeordnet
Suche über Submaske (AND)
Datensystem
wie werden Daten gefunden
-> Auswertungsstrategie
physische Optimierung
Datensystem
diverse Zuordnung der algebraischen Ausdrücke
Kostenbasierte Auswahl
Datensystem
-Kostenfunktion -> berechnet Gesamtkosten der Anfrage aus Kostenabschätzung der Einzeloperationen
-Größe der Zwischenergebnisse hat Einfluss
-gesucht werden Kanidaten die schnell Lösungsraum einschränken
Prinzip der transaktionalen Verarbeitung
-zusammenfassen aufeinanderfolgender Operationen
-überführen konsistente DB in konsistente DB (möglicherweise zwischendurch inkonsistent)
Savepoint
noch aktive Aktionen lässt sich zurücksetzen -> für lange Transaktionen
Backup transaction
zurücksetzten auf letzten Sicherungspunkt (oder andere )
ACID-Eigenschaften
Atomicity
Consistency
Isolation
Durability
Atomicity
-Unteilbarkeit durch Transaktionsdefinition -> gesamte Transaktion wirkungslos, wenn ein Teil wirkungslos
Consistency
-erfolgreiche Transaktion garantiert, dass alle Konsistenzbedingungen eingehalten wurden
Isolation
mehrere Transaktionen laufen isoliert ab und benutzen keine inkonsistenten Ergebnisse
Durability
alle Ergebnisse erfolgreicher Transaktionen müssen, persistent gemacht werden 8
(dauerhaft gespeichert)
Transaktionsverwaltung
Synchronisation
Recovery
Synchronisation
Ziel: erhalten Transaktionskonsistenz, vermeiden gegenseitiges beeinflussen von Lese- und Schreiboperationen, verhindern Anomalien
Arten von Konsistenz
Datenkonsistenz
Transaktionskonsistenz
Datenkonsistenz
alle definierte Konsistenzbedingungen sind erfüllt
Transaktionskonsistenz
nebenläufiger Ablauf der Transaktionen ist korrekt
-> Gefahr Anomalien
Arten von Anomalien
lost update
dirty read
dirty overrride
non-repeatable read
Phantom Problem
Serialisierbarkeit
-verhindern Anomalien
-Historie welche zum gleichen Ergebnis wie eine serielle Historie führt
-keine Zyklen im Serialisierbarkeitsgraphen
lost update
geschriebene Daten gehen verloren
Dirty read
lesen von inkonsistenten Daten
Non-repetable read
lesen von unterschiedlichen Daten in einer Transaktion
Phantom Problem
Variable wird einmal gelesen und danach gelöschte -> erneutes lesen führt zum Problem
Ausführungsplan
Transaktionen können nebeneinander ablaufen -> regelt relative Ausführung zueinander
Konfliktoperationen
eine der Operationen ist eine Schreiboperation
sequentielle Ausführung
Vorteile, Nachteile
Vorteile: sicher
Nachteile: schlechte Systemauslastung, langsam
Datenbank Scheduler
ordnet eingehende Operationen
sorgt für Serialisierbarkeit & Rücksetzbarkeit
Strategien Scheduler
pessimistisch
optimistisch
Pessimistisch
-verzögern entgegengenommene Operationen
-festlegen geschickte Reihenfolge
-z.B. sperrbasierter Scheduler
Optimistisch
-möglichst schnelles Ausführen Operationen
-später eventuelles reparieren von Schaden
-z.B. optimistische Synchronisation, zeitstempelbasierter Scheduler
Synchronisation durch Sperren
Pessimistischer Scheduler
logischer Einbenutzerbetrieb -> sperren für exclusiven Zugriff
jedes Datenobjekt zentral eine Sperrtabelle
Arten von Sperren
X -> Exclusiv -> Schreibsperre
S/R -> Shared/Read- Sperre -> Lesesperre
Statische Sperren
zu Beginn alle Sperren anfordern -> Nachteil: alles sperren was man brauchen KÖNNTE
Dynamische Sperren
während Transaktion anfordern nach Bedarf -> Nachteil: Verklemmmung
ZweiPhasen-Sperrprotokoll
-Wachstums- und Schrumpfungsphase -> Problem: kaskadierendes Abbrechen
Striktes ZweiPhasen-Sperrprotokoll
-Freigabe Lesesperren nach 2PL
-Freigabe Schreibsperren erst am Ende
Deadlocks
-Verklemmung
-unvermeidbar bei persimistischen Ansätzen
-Vorraussetzung: paralleler Zugriff, x-Lock, keine vorzeitige Freigabe
Behandlungsmöglichkeiten Deadlocks
Deadlockererkennung
Deadlockvermeidung
Deadlockererkennung
Wartegraph
prüfen auf periodischen Zyklus
-> zurücksetzen einer Transaktion
Deadlockvermeidung
direktes zurücksetzten einer Transaktion
Optimistische Synchronisation (OCC)
Lese-Phase
Validierungsphase
Schreibphase
Lesephase OCC
eigentliche Transaktionsverarbeitung, Änderungen nur im lokalen Transaktionspuffer
Validierungsphase OCC
atomar
Konfliktprüfung
Konflikt -> zurücksetzen
Schreibphase
atomar
dauerhafte Speicherung der Änderungen
Validierungsstrategien
Backward Oriented
Forward Oriented
Backward Oriented BOCC
Validierung gegenüber bereits beendeten Transaktionen
Forward Oriented FOCC
Validierung gegenüber laufenden Transaktionen
Recovery
wiederherstellen jüngsten transaktionskonsistenten Datenbankenzustand
Undo
Recovery
Änderung aller offenen Transaktionen rückgängig machen
Redo
Recovery
Änderung aller abgeschlossen Transaktionen gegebenenfalls wiederholen
Log-Datei
Recovery
-protokolliert Änderungen
-getrennte Speicherung Sicherungspunkt und Log-Datei
Fehlerarten
Recovery
Systemfehler
Gerätefehler
Transaktionsfehler
Katastrophe
Recovery-Klassen
Recovery
-R1
-R2
-R3
-R4
force
Ausschreibungsstrategien
Recovery
am Ende einer Transaktion werden alle Seiten die verändert wurden auf die Festplatte geschrieben -> langsame Schreiboperationen nötig, garantierte Dauerhaftigkeit
no force
Ausschreibungsstrategien
Recovery
Seiten werden nicht auf Festplatte geschrieben, wenn mehrere Transaktion eine Seite verändern, muss sie nicht mehrmals gespeichert werden -> redolock wird benötigt
no steal
Ersetzungsstrategien
Recovery
-Solange Transaktion noch aktiv keine Übertragung auf Festplatte
-Veränderungen geschehen im Pufferpool -> Atomarität Transaktionen, Bei Ausfall geht Pufferpool verloren, schnell Kapazität erreicht
steal
Ersetzungsstrategien
Recovery
-schreiben von nicht veränderten Transaktionen
-Seiten laufender Transaktionen können auf Festplatte geschrieben werden -> effizientes nutzen Pufferpool, Atomarität gewährleistet
Einbringungsstrategie
Recovery
Update-in-Place
-Twin-Block-Verfahren
-Schattenspeicherkonzept
Einbringungsstrategie
Update-in-Place
Recovery
-direkte Strategie
-jede Seite hat einen Platz im Hintergrundspeicher -> alter Zustand wird überschrieben
Einbringungsstrategie
Twin-Block-Verfahren
Recovery
-indirekte Strategie
-jede Seite werden zwei Seiten zugeordnet
-für letzten und vorletzten Zustand
Einbringungsstrategie
Schattenspeicherkonzept
Recovery
-indirekte Strategie
-nur geänderte Seiten werden dupliziert, weniger Redundanz als bei Twin-Block
Protokollierungsarten
Recovery
logische Protokollierung
physische Protokollierung
Protokollierungsarten
logische Protokollierung
Recovery
-notieren Undo-Operation, um vorherigen Zustand zu erzeugen
-notieren redo-Operation, um Nachfolgezustand zu erzeugen
Protokollierungsarten
physische Protokollierung
Recovery
-notiere Before-Image des Objektes
-notiere After-Image des Objektes
Protokollierung benötigte Informationen
Recovery
Redo-Informationen
Undo-Informationen
LSN (Log Sequenz Number)
Transaktionskennung
Page ID
PrevLSN
Log-Daten
Recovery
Log-Datei: schneller Zugriff, R1,R2,R3-Recovery
Log-Archiv: R4-Recovery
Log-Puffer
Recovery
Ringpuffer
kleiner als DB-Puffer
wenn voll-> schreiben Hintergrundspeicher
Phasen des Wiederanlaufs
Recovery
-Analyse( Bestimmen Winner und Loser)
-Redo/Wiederholung der Historie
-Undo der Loser
Phasen des Wiederanlaufs
Analysephase
Recovery
-Ermittlung gestartet Transaktion durch BOT-Einträge
-Winner -> hat schon commited
Loser -> fehlende commit Einträge
Phasen des Wiederanlaufs
Redo-Phase
Recovery
-Logdatei vorwärts durchlaufen
-referenzierte Seite aus Datenbankpuffer holen
-LSN mit LSN Logdatei überprüfen
-LSN (Log) größer (jünger) -> Redo
Phasen des Wiederanlaufs
Undo-Phase
Recovery
-Logdatei rückwärts durchlaufen
-alle Log-Einträge der Loser -> holen Seite aus Puffer -> undo
