TU Wien:Datenbanksysteme VU (Skritek)/Zusammenfassung Test 2

Für den Stoff vom 1. Test, siehe hier.

Transaktionsverwaltung

Transaktion

Eine Transaktion ist eine Folge von Datenbankoperationen welche die Datenbasis von einen konsistenten Zustand in einen anderen konsistenten Zustand überführen.

Eine Transaktion wird atomar (= (logisch) ununterbrechbar) ausgeführt, d.h.

• als Einheit fehlerfrei ausgeführt, und
• ohne Beeinflussung durch andere Transaktionen.

Operationen zur Datenverarbeitung:

• read(A,a)
• write(A,a)

Operationen zur Transaktionskontrolle:

• BOT (begin of transaction)
• commit
• abort

Historie

beschreibt die Reihenfolge der elementaren Operationen bei einer verzahnten Ausführung mehrerer Transaktionen

ACID

• Atomicity — Eine Transaktion ist die kleinste, nicht weiter zerlegbare Einheit.
• Consistency — Eine Transaktion hinterlässt einen konsistenten Zustand der Datenbasis.
• Isolation — Nebenläufig ausgeführte Transaktionen dürfen sich nicht beeinflussen.
• Durability — Die Auswirkungen einer erfolgreich abgeschlossenen Transaktion gehen nicht mehr verloren.

Recovery

Speicherverwaltung

• Speicher unterteilt in Seiten (Pages)
• Datensätze werden auf Seiten abgebildet
  • Vereinfachte Annahme in LVA: Datum $A$ auf Seite $P_{A}$

Kein Auslagern während eines Zugriffs (FIX).

Strategien zur Ersetzung von Pufferseiten:

• steal: Von Transaktionen geänderte Seiten können ausgelagert werden, während die Transaktionen aktiv sind. → Hintergrundspeicher kann Änderungen nicht abgeschlossener Transaktionen enthalten → Recovery nach Verlust des Puffers benötigt globales Undo
• ¬steal: Seiten die von einer noch aktiven Transaktion verändert wurden dürfen nicht ausgelagert werden.

Wenn eine Transaktion erfolgreich abschließt, kann die Auslagerung der geänderten Pufferseiten:

• erzwungen werden (force)
• nicht erzwungen werden (¬force) → dirty pages können im Puffer verbleiben → Recovery nach Verlust des Puffers benötigt globales Redo

Einbringstrategien

• Update-in-Place: Jede Seite hat genau einen Platz im Hintergrundspeicher. Beim Auslagern wird eine Seite auf diesen Platz kopiert. Alter Zustand der Seite wird überschrieben.
• Twin-Block-Verfahren: Für jede Seite zwei Kopien im Hintegrundspeicher + Bit das angibt welche Kopie aktuell ist. Beim Auslagern wird Seite auf aktuelle Kopie geschrieben.
• Schattenspeicherkonzept: Nur für veränderte Seiten existieren zwei Kopien

Fehlerkategorien

Lokaler Fehler

• Nur eine Transaktion betroffen.
• Durch diese Transaktion verursachte Änderungen müssen (schnell!) zurückgesetzt werden (Lokales Undo).

Fehler mit Verlust des DMBS-Puffers

• Durch abgeschlossene Transaktionen verursachte Änderungen müssen erhalten bleiben (Globales Redo).
• Durch nicht abgeschlossene Transaktionen verursachte Änderungen müssen zurückgesetzt werden (Globales Undo).

Fehler mit Hintegrundspeicherverlust

• Wiederherstellung der Daten mittels Archivkopie

Angenommene Systemkonfiguration

• steal
• ¬force
• Update-In-Place
• kleine Sperrgranulate auf Datensatzebene

Protokollierung (Logging)

Strutkur eines Log-Eintrags

[LSN, TransaktionsID, BOT, 0]

[LSN, TransaktionsID, PageID, Redo, Undo, PrevLSN]

• LSN (log sequence number)

eindeutige Kennung des Log-Eintrags, monoton aufsteigend

Wir unterscheiden zwischen:

• Physische Protokollierung: Redo- und Undo-Einträge enthalten Zustände.
• Logische Protokollierung: Redo- und Undo-Einträge enthalten Operationen.

In der Übung wird aus didaktischen Gründen die logische Protokollierung verwendet.

Jede Seite hat ein Feld für die LSN des jüngsten die Seite betreffenden Log-Eintrags, damit das DBMS beim Wiederanlauf erkennen kann ob die Auswirkung eines Log-Eintrags bereits auf der Seite vorhanden ist.

WAL-Prinzip (Write Ahead Log)

• Bevor eine Transaktion festgeschrieben wird, müssen alle Log-Einträge der Transaktion ausgeschrieben werden (für Redo).
• Bevor eine modifizierte Seite ausgelagert werden darf, müssen alle in zu dieser Seite gehörenden Log-Einträge ausgeschrieben werden (für Undo).
• Die chronologische Reihenfolge muss beim Ausschreiben erhalten bleiben.

Wiederanlauf nach einem Fehler (Recovery)

Wiederanlauf nach Fehler mit Verlust des Puffers

Eine Transaktion muss entweder vollständig rekonstruiert werden (Winner) oder vollständig rückgängig gemacht werden (Loser).

Drei Phasen des Wiederanlaufs:

1. Analyse: welche Transaktionen gibt es? Sind sie Winner oder Loser?
2. Redo aller Änderungen (Winner und Loser)
3. Undo aller Loser-Änderungen

Auch während des Wiederanlaufs kann ein Fehler mit Verlust des Puffers auftreten.

Realisierung:

• Redo-Phase: mittels LSN
• Undo-Phase: mittels CLRs (compensation log record)

Compensation Log Record (CLR)

<LSN, TransaktionsID, PageID, Redo, PrevLSN, UndoNxtLSN>

Mehrbenutzersynchronisation

Nebenläufigkeit und mögliche Fehler

Konflikt

• zwei Transaktionen greifen auf das selbe Objekt zu
• mindestens ein Zugriff ist schreibend
• mögliche Konflikte: W-W, W-R, R-W

Mögliche Fehler bei unkontrollierter Nebenläufigkeit

• Lost Update (W-W)
• Dirty Read (W-R)
• Unrepeatable Read (R-W)
• Phantomproblem (R-W)

Klassifikation von Historien

Historie

zeitliche Anordnung der elementaren Operationen einer Menge von Transaktionen

Konfliktoperationen

Paare von Operationen die auf das selbe Datenobjekt zugreifen, mindestens eine davon schreibend

Serialisierbarkeit

Serielle Historie

Jede Transaktion wird vollständig abgearbeitet bevor die nächste beginnt.

Serialisierbare Historie

Eine (verzahnte) Historie welche den selben Effekt hat wie irgendeine serielle Ausführung (informell)

konfliktäquivalent

Zwei HIstorien (über der selben Menge an Transaktionen), wenn sie sämtliche Konfliktoperationen der nicht abgrebrochenen Transaktionen in der selben Reihenfolge ausführen.

Konfliktserialisierbare Historie

EIne Historie, wenn sie konfliktäquivalent zu einer seriellen Historie ist.

Weitere Eigenschaften bei abort

Minimalanforderungen:

• Konfliktserialisierbar

rücksetzbare Historien

Abbruch einer aktiven Transaktion möglich ohne Einfluss auf erfolgreich abgeschlossene Transaktionen

Eine Transaktion darf erst mit commit abschließen nachdem alle Transaktionen von denen sie gelesen hat ebenfalls abgeschlossen sind.

Zusätzliche Eigenschaften:

Historien ohne kaskadierendes Rücksetzen

Änderungen einer Transaktion werden erst nach einem commit zum Lesen freigegeben.

strikte Historien

Auf ein von einer Transaktion geschriebenes Datum dürfen andere Trasaktionen erst nach deren Beendigung (commit oder abort) schreibend oder lesend zugreifen.

Concurrency Control

Sperrbasierte Synchronisation

Zwei Sperrmodi

• S ... shared, read lock
• X ... exclusive, write lock

Zwei-Phasen-Sperrprotokoll (2PL)

Nachdem eine Transaktion eine Sperre freigegeben hat darf sie keine weiteren Sperren mehr anfordern -> Wachstumsphase und Schrumpfungsphase

Strenges Zwei-Phasen-Sperrprotokoll (strict 2PL)

Alle Sperren werden bis Transaktionsende gehalten. -> nur strikte Historien werden zugelassen

Deadlock-Erkennung

• einfache Methode: Time-out Strategie
• exakte Methode: Wartegraph

Deadlock-Vermeidung

• Preclaiming (auch conservative 2PL): Transaktionen werden nur gestarted wenn alle benötigten Sperren bereits am Beginn gewährt werden können.
• Zeitstempelverfahren
  • wound-wait: ältere brechen jüngere ab, jüngere warten
  • wait-die: ältere warten, jüngere brechen ab

Hierarchische Sperrgranulate (MGL)

• Insert/Delete - Operationen
• Weitere Synchronisationsmethoden
  • Zeitstempel-basierende Synchronisation
  • Optimistische Synchronisation

PL/pgSQL

User defined functions:

CREATE [OR REPLACE] FUNCTION
  name ([ [argname] argtype [, ...] ])
   [ RETURNS rettype
    |RETURNS TABLE (colname coltype [, ...])]
AS $$
... – eigentlicher Source Code
$$ LANGUAGE plpgsql;

PL/pgSQL Programme sind in Blöcken strukturiert:

[ <<label>> ]
[ DECLARE
    declarations ]
BEGIN
    statements
[ EXCEPTION
  excpthandling ]
END [ label ];

Datenintegrität

Integritätsbedingungen

Hier geht es um semantische Integritätsbedingungen, die aus den Eigenschaften der modellierten Miniwelt abgeleitet werden.

• statische Integritätsbedingungen (Bedingungen an Zustand der Datenbasis)
• dynamische Integritätsbedingungen (Bedingungen an Zustandsänderungen in der Datenbank)

Statische Integritätsbedingungen in SQL

• unique(...)
• primary key(...)
• foreign key(...)
• not null
• default

check (...): Änderungen auf einer Tabelle werden nur zugelassen, wenn check zu true auswertet

Referentielle Integrität

• primary key(...)
• foreign key(...)

• references tabelle

Einhaltung der Referenziellen Integrität bei Updates, Löschen:

• on update {no action | cascade | set null | set default}
• on delete {no action | cascade | set null | set default}

Zyklische Abhängigkeiten

• ALTER TABLE zum foreign key anlegen
• DEFERRED um neue Tupel einzufügen.
• Löschen von Tabellen mit DROP CONSTRAINT oder CASCADE.

Trigger

CREATE TRIGGER name { BEFORE | AFTER}
  {INSERT | UPDATE | DELETE}
  ON table name
  [ REFERENCING { { OLD | NEW } TABLE
                [ AS ] trans name } ]
  [ FOR [ EACH ] { ROW | STATEMENT } ]
  [ WHEN ( condition ) ]
  EXECUTE PROCEDURE function_n ( arguments )

Die Funktion darf keine Argumente haben und muss den Rückgabe ert trigger haben:

CREATE FUNCTION name() RETURNS trigger
 AS $$ ... $$ LANGUAGE plpgsql;

Bei Per-ROW Before Triggern stehen spezielle Variablen zur Verfügung:

• INSERT: NEW enthält neue Zeile
• UPDATE: OLD und NEW sind definiert
• DELETE: OLD enthält die zu löschende Zeile

Bei einer Rückgabe von NULL wird die Verarbeitung der Zeile abgebrochen. Sonst Verarbeitung wird mit zurückgegebenen Wert fortgesetzt.

SQL-Vertiefung

Rekursive Abfragen

WITH RECURSIVE tabName(AttrListe) AS (
    Nicht rekursiver Abschnitt
  UNION [ ALL ]
    Rekursiver Abschnitt
)
SELECT ... FROM tabName;

Sichten (Views)

Gespeicherte Anfragen, die als virtuelle Tabelle zur Verfügung stehen.

CREATE VIEW name AS
SELECT ...

Window Functions

Sequences

CREATE SEQUENCE name
[INCREMENT [ BY ] increment]
[MINVALUE minvalue | NO MINVALUE]
[MAXVALUE maxvalue | NO MAXVALUE]
[START [WITH] start] [CACHE cache]
[[NO] CYCLE]

Zugriff mit:

• nextval(sname)
• currval(sname)
• setval(sname, val)

Weitere Datentypen und built-in Funktionen

CREATE TYPE Rang AS ENUM ('C2', 'C3', 'C4');