Datenbanksysteme


Relationale Algebra

Operatoren

Sonst Wichtig

SQL - DQL

Demo

SELECT a, b AS c, avg(d), 1000
    FROM f NATURAL JOIN g JOIN h ON g.a = g.h
    WHERE Name LIKE '%u%' AND NOT (Name LIKE 't%' OR Name LIKE '%t')
    GROUP BY a, c
    HAVING sum(e) > 1234
UNION (
    SELECT DISTINCT i
        FROM j JOIN k USING l LEFT JOIN m
    )
LIMIT 5678;
SELECT (SELECT COUNT(∗)∗1.0 FROM Training) / (SELECT COUNT (∗) FROM Benutzer) AS FOO;

Bemerkenswert

SQL DDL und DML

DEMO

CREATE TABLE T (
    TID INTEGER PRIMARY KEY AUTOINCREMENT,
    W   TEXT DEFAULT 'blabla',
    R   REAL,
    B   BLOB,
    UID INTEGER UNIQUE,
    D   INTEGER CHECK ( D >= 19000101),
    DIM INTEGER CHECK ( DIM >= 0),
    K   INTEGER CHECK ( K >= 0 AND K <= 100 ∗ DIM ),
    FOREIGN KEY ( W ) REFERENCES B ( BID ) ON DELETE CASCADE ,
    FOREIGN KEY ( UID ) REFERENCES U ( UID ) ON DELETE RESTRICT
);
ALTER TABLE T
    ADD TR INTEGER DEFAULT NULL REFERENCES B ( BID ) ON DELETE SET NULL;
ALTER TABLE Tabelle
    DROP/ALTER COLUMN Spaltenname
INSERT INTO Training (Wer, UebungsID, Datum, VALUES
    ("3", "103" ,"20240326", "60", "100"),
    ("1", "102" ,"20240326", "60", "350");

ON DELETE

Funktionale Abhängigkeiten

Minimale Menge funktionaler Abhängigkeiten finden

Schlüsselmengen

Normalisierung

Normalformen

Syntheseverfahren

Dekompositionsverfahren

Transaktionen

Anforderungen

Konzepte

Fehlerklassen

2-Phasen-Sperrprotokoll

Legalität:

Vor dem Lesen oder Schreiben eines Objektes muss immer eine Lese- oder Schreibsperre geholt werden. Eine Schreibsperre impliziert immer auch eine Lesesperre. Alle Sperren werden nach den Operationen wieder freigegeben.

Sperr-Regel:

Es darf nur entweder eine Schreibsperre oder beliebig viele Lesesperren auf ein Objekt gleichzeitig geben.

Zweiphasigkeit:

Die Anzahl der Sperren muss in der ersten Phase monoton zunehmen und in der zweiten Phase monoton abnehmen. Keine Sperre darf freigegeben werden, bevor die letzte angefordert wurde.

Um das Phantomproblem zu umgehen, sind Sperren logisch und beziehen sich nicht auf konkrete Tupel.

Parallele Validierung

Eine Transaktion hat drei Phasen:

  1. Lesephase
  2. Validierungsphase
  3. Schreibphase

Transaktionen werden anhand des Endes ihrer Lesephase sortiert und müssen gegen alle älteren Transaktionen validieren, damit die zunächst auf einer lokalen Kopie vorgenommenen Änderungen in die Datenbank geschrieben werden. Schlägt die Validierung fehl, werden sie neu gestartet.

Validierungsphase von Tneu

Tneu unterteilt alle älteren Transaktionen in 3 Gruppen:

  1. Talt1: Transaktionen, die beendet werden, bevor Tneu in der Lesephase ist
  2. Talt2: Transaktionen, die beendet werden, während Tneu in der Lesephase ist
  3. Talt3: Transaktionen, die beendet werden, nachdem Tneu in der Lesephase war

Validierung liefert genau dann true, wenn es keine Transaktion aus Talt2 gibt, deren writeSet eine Schnittmenge mit dem readSet(Tneu) hat und wenn es außerdem keine Transaktion aus Talt3 gibt, deren writeSet eine Schnittmenge mit der Vereinigung vom readSet(Tneu) und dem writeSet(Tneu) hat.

Recovery

Um Durability zu gewährleisten, müssen Datenbanken so arbeiten, dass committete Änderungen auch nach einem Crash noch zuverlässig Bestand haben, andere jedoch nicht. Dies ließe sich mit der Policy

erreichen. Dies würde allerdings die Parallelisierbarkeit viel zu stark einschränken, so dass reale Datenbanken fast ausschließlich steal und non force verwenden. Stattdessen verwenden sie ein sogenanntes Write-Ahead-Log (WAL).

Write Ahead Log

Beispiel:

Bildschirmfoto_20240724_181411.png

Recovery-Vorgang

Sollte es währenddessen zu einem erneuten Absturz kommen, sind diese CLR schon Teil der Redo-Phase und die Undo-Phase kann für jede Transaktion beim Undo-Next-LSN des letzten CLR fortgesetzt werden.

Checkpoints

brauchen wir, damit Redo und Undo nicht beliebig weit in die Vergangenheit zurück gemacht werden müssen

Arten:

Lineare Anfrageoptimierung

Datenbankanfragen haben das Potenzial, sehr ineffizient und langsam zu sein. Die Datenbank selbst optimiert zwar zu einem gewissen Grad, aber es macht definitiv Sinn, seine Queries auch von Hand auf Performance zu optimieren. Hierbei wird versucht, die Zahl der zu berechnenden Zwischenergebnise möglichst gering zu haltenn.

LAO in vier Schritten

  1. Teile die Selektionsbedingungen so auf, dass sich jede bedingung auf genau eine Tabelle bezieht
  2. Führe alle Selektionen, die sich nur auf eine Tabelle beziehen direkt auf dieser aus
  3. Ersetze Kombinationen aus Selektion und kartesischem Produkt durch einen Join
  4. Bestimme die Ausführungsreihenfolge aller Joins, die zu den kleinsten Zwischenergebnissen führt

Regeln

Außerdem

NoSQL

Relationale Datenbanken sind unflexibel und skalieren schlecht horizontal. Um hier Abhilfe zu schaffen, gibt es NoSQL-Datenbanken mit weniger starrer Struktur und optimierung für horizontale Skalierung.

Arten von NoSQL-Datenbanken

Map-Reduce

Beispiel zur Berechnung eines Durchschnittswertes:

def map(self, data):
      yield ('count', (len(data[1]), 1))

  def reduce(self, key, values, rereduce):
      return (sum(value[0] * value[1] for value in values) /
          sum(value[1] for value in values),
          sum(value[1] for value in values))

Graph-Datenbanken

Knoten

Kanten

Attribut

Beispiele

MATCH (tom:Person {name:"Tom Hanks"})-[r:ACTED_IN]->(m)
WHERE m.released >= 1900 AND m.released < 2000
RETURN tom,m;
CREATE (TheMatrix:Movie {title:'The Matrix', released:1999, Tagline:'Welcome to the Real World’})
CREATE (Keanu)-[:ACTED_IN {roles:['Neo']}]->(TheMatrix)

Allgemeine Syntax