[WIP] DBS summaries

.gitignore

Ü?_T?.md

Algorithmen.md

Synthesealgorithmus

1. Einführung neuer FD (Alles) -> δ

2. Rechtsreduktion (Nur ein Attribut rechts, also aufspalten)

3. Linksreduktion (Keine überflüssugen Attribute links, die sich durch andere Abhängigkeiten ergeben)

   z.B. A -> B und AB -> C zu A -> B, A -> C

4. Reduktion von redundanten FD (Membership test)

   1. Eine löschen
   2. Hülle bilden
   3. Go to i.

5. Äquivalenzklasen bilden (Zusammenfassen von FD mit gleicher oder äquivalenter (Es gibt A -> B und B -> A, sie sind also gleich mächtig) linker Seite)

Anfrageausführung.md

Naive Übersetzung

Die Anfrage wird der Reihe nach wie sie im SQL steht abgearbeitet.

z.B.:

SELECT
  CUSTOMER.CName,
  Account
FROM
  CUSTOMER,
  ORDER
WHERE
  CUSTOMER.CName = ORDER.CName
  AND Item = 'Coffee'

Zuerst der Join von Customer und Order
Dann das Select (SQL WHERE)
Dann die Projektion (SQL SELECT)

Das ist ineffizient, weil Selektion und Projektion die Ergebnisse deutlich kleiner machen
==> Großer Speicheraufwand
==> Viele page accesses (read, write)
==> Laaaaaangsam (Die Festplatten sind archaisch)

Besser: Indizes, Algebraische Optimierung

Auswertungsphasen

1. Übersetzung, View expansion

• Algebraische Ausdrücke vereinfachen
• sub-queries auflösen (und ggf. durch andere Operationen ersetzen)

2. Logische Query-Optimierung

• Algebraischen Ausdruck optimieren (Projektionen zusammenfassen, Select vorschieben, etc.)
• Unabhängig von physischer Repräsentation

3. Interne Optimierung

• Physische Repräsentation berücksichtigt (Indizes, Cluster, etc.)
• Algorithmen auswählen (Nested Loop Join, Hash Join, etc.)
  ==> Verschiedene mögliche Ausführungspläne

4. Kostenabschätzung ; Auswahl eines Planes

• Basierend auf Statistiken und Heuristiken den billigsten Plan auswählen

5. Codegenerierung

• Umwandeln in ausführbaren code (SQLite hat eine eigene VM zur Ausführung)

6. EXECUTE

Phase	Ausgabe
Query schreiben	SQL
Translation	Algebraischer Ausdruck
View Expansion	Algebraischer Ausdruck
Optimierung (2., 3., 4.)	Ausführungsplan
Codegenerierung	Ausführbarer Code irgendeiner Form
Ausführung	Ergebnis!

Translation

Einfach mal ganz dumm in Algebra übersetzen. Joins zu joins, SELECT ... als Projektion, WHERE als Selektion, …

Baumdarstellung

Ausdrücke der relationalen Algebra lassen sich als Bäume darstellen.

Knoten sind Operationen Kanten sind Eingaben

        π[Name]
          |
          ⋈
         /  \
  Student    Personeninformation

Das hilft bei Visualisierung und Optimierung

Algebraische Optimierung

Verbessern der algebraischen Ausdrücke durch Eigenschaften der Operatoren (Äquivalenz von Ausdrücken). Verbesserung durch Transformationsregeln, die Äquivalenz erhalten.

Ggf. auch Verbesserung durch Heuristiken:

• kleine Zwischenergebnisse
• Redundanzen eliminieren

Redundante Operationen entfernen:

• Join ist idempotent (r = r ⋈ r)
• Views auflösen

Push Selection:

• Selektion möglichst weit nach unten in dem Baum schieben ==> Früher durchgeführt ==> Potentiell kleinere Zwischenergebnisse

Join Ordering:
Joins sind assoziativ und kommutativ ==> Schiebe sie rum, um das Zwischenergebnis klein zu machen

ProjProj:
Geschachtelte Projektionen zusammenziehen, die äußerste gewinnt.

SelSel:
Geschachtelte Selektionen lassen sich durch eine Selektion mit ∧ ersetzen (oder andersrum!).

SelProj:
Selektion und Projektionen kommutieren, wenn die Selektionsattribute in der Projektionsliste sind.

SelJoin:
Selektion und Join kommutieren, wenn die ganzen Selektionsattribute aus einer der beiden Relationen sind:

z.B.: σ[name = 'A']( Buch ⋈ Autoren ) = (σ[name = 'A'](Autoren)) ⋈ Buch

Spezialfall: Prädikat zerfällt in 2 UND Verknüpfte Teile, die jeweils nur in einer Relation sind
σ[name = 'A' ∧ ISBN = '20']( Buch ⋈ Autoren )
= σ[name = 'A'](Buch) ⋈ σ[ISBN = '20'](Autoren)

Viele weitere, die keinen interessieren:
z.B.:
SelDiff: Selektion und Differenz kommutieren
SelUnion: Selektion und Union kommutieren
ProjJoin: Projektion und Join kommutieren
ProjUnion: Projektion und Union kommutieren

Algebraischer Optimierungsalgorithmus

1. Komplexe Selektionen aufspalten (an ∧ und vlt. ¬)
2. Selektionen in die Blätter runterschieben (SelJoin, SelProj, SelUnion, SelDiff) SelSel vlt. auch cool dafür, zum Umordnen von Selektionen
3. Projektionen in die Blätter runterschieben (ProjProj, ProjJoin, ProjUnion)

Bsp:

                π[title]
                    |
                 __ ⋈  __
                /        \
              ⋈           σ[autor = 'Heuer']
             /  \                 |
σ[Date < 2010]  r(Borrower)    r(Books)
      |
r(Borrowing)

Zusätzliche Projektionen um sie weiter runterschieben zu können (braucht Wissen über benötigte Attribute):

                π[title]
                    |
                 __ ⋈  __
                /        \
            π[ISBN]      π[ISBN, title]
              |                   |
              ⋈           σ[autor = 'Heuer']
             /  \                 |
σ[Date < 2010]  r(Borrower)    r(Books)
      |
r(Borrowing)

Interne Optimierung

Umwandlung von abstrakter Algebra in interne Operationen.

Dabei:

• Weg von Mengen zu Listen von (vlt. sortierten) Tupeln
• Multimengen (erlauben Duplikate)
• Indizes und Cluster
• Tuple-ID Listen könne ebenfalls analysiert und behandelt werden

Nested-Loop Join

Für jeden Eintrag in Relation X gehe über alle Einträge in Relation Y:

for tupleX in X:
  for tupleY in Y:
    # do join, output (tupleX || tupleY)

Aufwand:
O(|X| * |Y|)

Block-Nested-Loop join

Teile X und Y in Blöcke auf und mache den Nested-Loop Join blockweise. Das ist Cache effizienter: Blöcke in Y können im Cache behalten werden, bis sie ganz abgearbeitet sind. Kein dauerndes Neuladen und Leeren des Caches.

for blockX in X:
  for blockY in Y:
    for tupleX in blockX:
      for tupleY in blockY:
        # do join, output (tupleX || tupleY)

Aufwand:
O(<Anzahl Blöcke in X> * <Anzahl Blöcke in Y>) (Da der Rest im Memory anscheinend einfach unterschlagen wird. Ohne Disk access ist es wohl kostenlos)

Noch cooler:
Cache mit Tupeln von Y Relation volllaufen lassen
==> Weniger Disk-accesses für jeden X Tupel

Merge Join

Normaler Mergesort merge. Geht nur, wenn beide nach dem gleichen Schlüssel sortiert sind.

Aufwand:
Bei Join on S = X ∩ Y

Bedingung	Aufwand	Kommentar
Alle Tupel haben gleichen S Wert (oder einfach S ist nicht Schlüssel, da worst case)	O(n_X * n_Y)	Normaler loop join
S ist Schlüssel von X oder Y	O(n_x log n_x + n_y log n_y )	beides sortieren
S ist Schlüssel X oder Y und beide sortiert	O(n_x + n_y)	Cooler merge-sort merge

Hash Join

Für Joins der Form X ⋈ Y mit X.A = Y.B.

Idee:
Gehe über eine der Relationen, finde alle passenden Tupel in der anderen durch Hash lookup.

# Annahme: X ist kleiner. Die kleinere hashen ist effizienter
# Vielleicht muss man mehrere hash table bauen, wenn X nicht ganz in den RAM
# passt
hash_table = load_and_hash(X)

for tupleY in Y:
  key = hash(tuple.B)
  for tupleX in hash_table.get(key):
    # do join, output (tupleX || tupleY)

Aufwand:
O(b_X + p * b_Y) (p ist Anzahl an Scans über Y, falls Y nicht in den RAM passt. Sonst ist p 1)
Und Blöcke schätze ich mal, weil man ja direkt die Optimierte Form des nested loop joins nehmen kann.

Wann nutzt man welchen Join

Szenario	Join
Index existiert, andere kann in-memory sortiert werden	Merge sort
Große Relationen, im Allgemeinen	Hash join
Auch fancy: Partitionierung durch Hash Wert erlaubt parallele Verarbeitung von
Teilen

Blockierende Operatoren

Ein Operator, der erst vollständig ausgewertet werden muss, bevor er eine Ausgabe produziert, heißt "blockierend". z.B.: sort. Der letzte gelesene Tupel könnte der erste in der Ausgabe sein, also muss alles davor gelesen werden.

Formale Definition, weil man die total braucht:
G ist der Operator mit Tupel-Sequenz als Input und Output
G liest Tupel tⱼ im j.ten Schritt
G^j(S) ist Ausgabe bis zu Schritt j (inklusive)

Wenn ein Operator blockiert, so gilt für alle S (n = |S|) :

1. G^j(S) = [] ∀j < n
2. G^n(S) = G(S) ist Ausgabe

Nicht-Blockierende Operatoren

Der Operator kann bereits eine Ausgabe produzieren, bevor er seine Eingabe komplett verarbeitet hat.

z.B.: select. Sobald ein Tupel gefunden wurde, kann er ausgegeben werden

Gut für "first few" Anfragen (z.B. nach LIMIT X oder so).

Wenn ein Operator nicht blockiert, so gilt für alle S (n = |S|):

1. G^j(S) = G(S^j) ∀j < n

Erweiterbar auf 2 Eingaben.

Progressiver Merge Join

Wichtige Eigenschaften:

• Stellt sehr schnell erste Ergebnisse bereit
• Am Ende erhält man ebenfalls 2 sortierte Relationen
• Erste Ausgabe ist relativ gute Approximation der Ausgabedaten, da zufällige Teile von R₁ und R₂ genommen werden (wenn sie in zufälliger Reihenfolge ankommen)

Grundidee:

• Auftrennen der Relationen in kleinere Chunks
• Mergen der einzelnen Chunks und direktes Ausgeben der Ergebnisse davon

|--------------|  |--------------|
| Relation 1   |  | Relation 2   |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (1)    |  | Daten (2)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (3)    |  | Daten (4)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (5)    |  | Daten (6)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (7)    |  | Daten (8)    |
| ------------ |  | ------------ |

1. Sortiere 1 und 2 in-memory
2. Joine 1 und 2 mit merge join und gebe Ergebnisse direkt aus
3. Lade 3 und 4, sortiere in-memory
4. Joine 3 und 4 mit merge join und gebe Ergebnisse direkt aus
5. Gleiches für 5, 6 und 7, 8

|--------------|  |--------------|
| Relation 1   |  | Relation 2   |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (1)    |  | Daten (2)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (3)    |  | Daten (4)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (5)    |  | Daten (6)    |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (7)    |  | Daten (8)    |
| ------------ |  | ------------ |

6. Streame 1, 2, 3 und 4 in den Speicher und merge 1-3 und 2-4 (iteriere drüber, lade tupelweise)
   1. Joine währenddessen 1 mit 4 und 2 mit 3 über Kreuz. Das ist sinnvoll, weil 1-2 und 3-4 bereits gejoint wurden — aber 1-4 und 2-3 nicht.
7. Gleiches für 5, 6, 7 und 8

|--------------|  |--------------|
| Relation 1   |  | Relation 2   |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (1)    |  | Daten (2)    |
|              |  |              |
| Daten        |  | Daten        |
| ------------ |  | ------------ |

| ------------ |  | ------------ |
| Daten (3)    |  | Daten (4)    |
|              |  |              |
| Daten        |  | Daten        |
| ------------ |  | ------------ |

8. Jetzt wiederholt sich der Algorithmus für die größeren Blöcke.
   1. Streame 1, 2, 3 und 4 in den Speicher und merge 1-3 und 2-4
   2. Mache das gleiche mit den größeren Blöcken, die darunter vlt. sind
9. Irgendwann ist links die sortierte R₁ und rechts die sortierte R₂ und wir sind fertig

Anfrageausführung_Physisch.md

Physische Operatoren

• Verschiedene Ausprägungen eines algebraischen Operators (z.B. nested loop join, merge join, etc.) ==> Datenbank wählt passendsten physischen Operator aus (geringste Kosten)

Zusammenfassung logischer Operatoren:

• Eine natural join kann direkt auch noch nach dem Join Attribut selektieren
• Projektion und Selektion gleichzeitig in einem Operator

Phyische Operatoren können physisches Datenlayout nutzen:

• z.B. kann eine Selektion σ[name='A'] entweder:
  • Einen kompletten Tablescan machen
  • Einen Index-Scan durchführen

Index

Ein Index ist eine spezialisierte Datenstruktur, die für einen Primärschlüssel oder andere Attribute einer Relation aufgebaut wird.

Ein Index lässt sich von der Funktionsweise wie ein Binärbaum vorstellen:

• Er nutzt Werte der Attributmenge, für die er erstellt wurde, als Schlüssel
• Er speichert für jeden Eintrag den Schlüssel (logisch) und den Ort an dem man den Tupel findet (z.B. TupelId)

Sucht man nun nach einem bestimmten Wert, z.B. mit SELECT * FROM X WHERE A = 10, so kann in dem Binärbaum nach allen Tupeln gesucht werden, die den Wert 10 haben. Dies ist deutlich schneller (hier wäre es logarithmisch) und muss nur Seiten in den Speicher laden, auf denen wirklich relevante Daten sind (oder der Index, der ist aber klein). Das ist deutlich effizienter als ein ganzer Tablescan.

Weitere nützliche Operationen:

• Join, wenn das Attribut bei mindestens einer Relation einen Index besitzt (z.B. Schlüssel ist).
  Dann kann ein merge join angewandt werden, der über den Index schnell alle passenden Tupel findet (ähnlich dem Hash join)
• Bereichsanfragen: A BETWEEN 10 AND 20
• Sortierung

Je nach Datenbank kann es gut sein, dass der Index ein B-Tree ist.

Physische Projektion

Allgemeine Form: π^REL/MOD_AttList.

Form oben	Erklärung
REL/with	Full table scan (REL), with duplicate elimination
REL/w_out	Full table scan (REL), with out duplicate elimination
SORT/with	Full table scan auf SORTierter Relation with duplicate elimination
SORT/w_out	Full table scan auf SORTierter Relation with out duplicate elimination

Physische Selektion

• Full table scan
• Index scan

Physischer Join

• ⋈ ^DIRECT: Nested-Loop Join
• ⋈ ^MERGE: Merge Join. Relationen müssen sortiert sein
• ⋈ ^HASH: Hash join

Mengenvereinigung, Differenz und Schnitt sind gleich.

Indexbasierter Zugriff

Komische Selektion:
σ_Aθa ^IND ( I( R(A) ) ) liefert TupleIDs von allen Tupeln der Relation R sortiert nach A, für die der Tupel das Prädikat erfüllt

Ich denke mal das heißt:

1. R(A) sortiert das nach A? Geht nur mit σ zusammen anscheinend?
2. I(Relation) gibt die TupleIDs aus dem Indexzugriff
3. σ^IND[Aθa](Relation) ist Selektion auf TupleIDs (IND)

Fancy Projektion:
Nutze Ausgabe von der Komischen Selektion als Input für σ^SORT

1. π^IND/width _AttrList - Mit Duplikat-Eliminierung, Zugriff über INDex
2. π^IND/w_out _AttrList - Ohne Duplikat-Eliminierung, Zugriff über INDex

Projektion auf den Index benötigt keinen Zugriff auf Relation, da die TupleIDs des Indizes direkt genutzt werden können

TupleID Realisierung: Umwandlung in Tupel

ρ( (Liste von TupleIDs für R), r(R) )

Physischer Sortierungsoperator

ω_AttrList(liste von tupeln) - Sortiert die Tupel nach AttrList

Sortierung über einen Index

ρ( σ_true^IND ( I(R(AttrList)) ), r(R) ) ≡ ω_AttrList(r(R))
O(|R|) vs O(|R| * |R| log |R|)

Pipelining

Aufgeben von "Set at a time", Ergebnisse werden direkt weitergereicht oder sogar zu einem Operator zusammengezogen. Damit entfallen kostenspielige Zwischenergebnisse.

Häufige pipelines:

• Selektion und Projektion (prüfen und direkt Zeug wegwerfen)
• Selektion und Join zusammenfassen (direkt beim Join einfach prüfen)
• Selektion im äußeren Loop eines Nested-Loop joins durchführen
• Selektion in den Merge Join einbauen
• Selektion und Realisierung (TupleID -> Tuple) zusammenfassen

Optimizer Hints

Hinweise (eher Befehle!) an den Optimierer und Query-Planer:

Anweisung	Auswirkung
/* +use_nl(inner_tbl) */	Erzwingt einen Nested-Loop Join
/* +use_merge(tbl1 tbl2) */	Erzwingt einen Merge Join
/* +use_hash(tbl1 tbl2) */	Erzwingt einen Hash Join
/* +ordered */	Erzwingt gleiche Join Reihenfolge wie in FROM clause
/*+ index(emp ename_idx) */	Erzwingt Nutzung eines bestimmten Indexes
/*+ all rows */	Maximiere Throughput
/*+ first rows(10) */	Minimiere Zeit bis zur Rückgabe der ersten 10 Ergebnisse

Beispiel:

SELECT
  /* +ordered */ *
FROM
  tab1,
  tab2,
  tab3
WHERE
  tab1.col = tab2.col AND tab1.col = tab3.col;

Relationenalgebra.md

Anforderungen an Relationenalgebra

1. Optimierbarkeit
   Wenige Regeln, dafür mit Optimierungsregeln
2. Effizienz
   i.e. <= O(n^2)
3. Mengenorientiert
   Jede Operation operiert auf Mengen und nicht nur einzelnen Tupeln

Ein Tupel

Ist eine Abbildung t: R -> ∪ D, i.e. eine Abbildung von der Attributmenge einer Relation auf einen Menge von Elementen in den Zieldimensionen: <Element aus Dimension von Attribut 1>, <Element aus Dimension von Attribut 2>, ...

Projektion

π[Attributmenge](Relation) oder π_Attributmenge(Relation)
z.B. π[Name](Ausleihe) π[Inventarnummer, ISBN](Buch)

Weitere Eigenschaften:

• Eliminiert Duplikate (Mengenorientiert)

Optimierungsregeln:

• Bei geschachtelten Projektionen reicht die äußerste π[Inventarnummer]( π[Inventarnummer, ISBN](Buch) ) ≡ π[Inventarnummer](Buch)

Selektion

σ[Bedingung](Relatioon) oder σ_Bedingung(Relatioon)
z.B.σ[name ≤ 'N'](Ausleihe)

Formen:

• Konstantenselektion (Attribut Konstante)
• Attributselektion (Attribut Attribut)

Optimierungsregeln:

• Selektionen lassen sich beliebig vertauschen
• Wenn Selektionsattribut Teil der Projektionsliste, lassen sich Selektion und Projektion tauschen
• Komplexere konjugierte Selektionsbedingungen lassen sich mit geschachtelten Selektionen ersetzen

Verbund (natural join)

Relation1 ⋈ Relation2
z.B. Buch ⋈ Inventur

Semantik:
r₁ ⋈ r₂ := {t | t(R₁ ∪ R₂) ∧ [∀ i ∈ {1,2} ∃t_i ∈ r_i : t_i = t(R_i)]}
Es gibt einen Tupel in R₁, sodass die Attribute aus R₁ übereinstimmen und das gleiche für R₂. D.h. es gibt ein Paar von Tupeln t₁ und t₂ in R₁ und R₂ respektive, sodass sie zusammen t ergeben. Das eliminiert einem "dangling tuples".
Z.B.: R₁ = (Name, Alter), R₂ = (Name, Wohnort) Wenn (Peter, 20, Karlsruhe) im Join Ergebnis ist, muss es geben:

1. Der Tupel darf nur die Attribute R₁ ∪ R₂ = {Name, Alter, Wohnort} enthalten
2. Eine Tupel (Peter, 20) in R₁
3. Eine Tupel (Peter, Karlsruhe) in R₂
4. korrespondiert zu t(R₁ ∪ R₂), 2. und 3. zu dem Allquantor Z.B. Gäbe es nur die Tupel (Peter, 20) und (Petra, Karlsruhe), ist (Peter, 20, Karlsruhe) oder (Petra, 20, Karlsruhe) nicht im Join.
5. Ist okay, hat die richtigen Attribute
6. ist okay, (Peter, 20) ∈ R₁
7. Ist nicht okay, (Peter, Karlsruhe) ∉ R₂

Eigenschaften:

• Ergebnisrelation ist Union der Attribute der Relationen
• Tupel ohne Partner (dangling tuples) werden eliminiert In SQL: OUTER JOIN, der das mit ausgibt
• Verbund ist kommutativ und assoziativ
• Verbundreihenfolge kann Geschwindigkeit stark beeinflussen
  • Hängt von der Größe der einzelnen Relationen ab

Verhalten bei keinem gleichem Attribut:
Entartet zu kartesischem Produkt:
r₁ ⋈ r₂ := {t | t(R₁ ∪ R₂) ∧ [∀ i ∈ {1,2} ∃t_i ∈ r_i : t_i = t(R_i)]}
Sei t₁ ein beliebiger Tupel aus R₁ und R₁ ∩ R₂ = ∅. Dann gilt für jeden Tupel t₂ aus R₂:

1. t₁ konkateniert t₂ hat nur Attribute aus R₁ ∪ R₂
2. Ist auch okay, da t₁ in R₁
3. Ist auch okay, da t₂ in R₂ Damit ergibt sich das kartesische Produkt, da alle Tupel der Form (t₁, t₂) gültig sind.

Mengenoperation (Schnitt, Vereinigung, Differenz) sind auch gültig!

Aber nur, wenn die Attributmengen übereinstimmen

Umbenennung

β[neu ← alt](Relation) oder β_neu ← alt(Relation)
z.B. β[ISBN <- Buchnummer](Bücher)

Eigenschaften:

• Erlaubt Verbunde bei verschieden benannten Attributen Man denke an JOIN ON A = B in SQL
• Erlaubt kartesisches Produkte bei gleich benannten Attributen β[ISBN1 ← ISBN](Buch) ⋈ Buch liefert kartesisches Produkt von Bücher mit sich selbst

Minimale / unabhängige Relationenalgebra

Eine Relationenalgebra, aus der man keine Operation weglassen kann. Sobald man eine Operation weglässt, ist sie nicht mehr vollständig.
Auch: Alle Operationen / Die Relationenalgebra ist unabhängig.

Unsere coole minimale Relationenalgebra, die einfach alles per Definition kann:
Ω = π, σ, ⋈ , β, ∪, — Projektion, Selektion, Natürlicher Verbund, Umbenennung, Mengenvereinigung, Mengendifferenz

Relationale Vollständigkeit

Eine Relationenalgebra ist vollständig, falls sie genauso mächtig ist wie unsere coole Ω.
D.h. man kann alle Operationen von Ω mit ihr emulieren.

Strenge relationale Vollständigkeit

Zu jeder Operation in Ω gibt es genau eine Operation in der anderen Menge, die diese emulieren kann. (Nicht so Zeug wie while, for, loops, Statements (;), if, etc.)

Relationenmodell.md

Attribut

Element von U, dem Universum.

z.B.
U = {Name, Alter, Haarfarbe, Größe}
Attribut ist z.B. Alter oder Name

Domäne

Wertebereich eines Attributes.

dom: U -> D bildet Attribut auf seine Domäne ab

Deklarierung in SQL:

CREATE DOMAIN <name> AS <type> CHECK (...)
-- z.B.
CREATE DOMAIN UserID AS INTEGER CHECK (VALUE BETWEEN 1 AND 999999)

Tupel

Abbildung von R (Relationenschema) zu "Vereinigung aller Domänen", i.e.
t₁(R) = { name → "Peter", age → 20 }

Es gilt:

• t(A) ⊆ dom(A), i.e. das Ergebnis ist Teilmenge des Wertebereichs

Relationenschema

Ist eine Menge von Attributen.

Menge aller Relationen über Relationenschema R: REL(R) := { r | r(R) }

Relation

Eine Relation ist eine endliche Menge von Tupeln über einem Relationenschema.

Schreibweise:
r(R) ist Relation r über Relationenschema R

Beispiel:
Relation r ist:

Name	Alter	Haarfarbe
Peter	20	Blond
Daisy	22	Schwarz

Dann gilt:

• r ∈ REL({Name, Alter, Haarfarbe})
• r ∉ REL({Name, Haarfarbe})

Datenbankschema

Eine Menge S = {R₁, R₂, ...} von Relationenschema heißt Datenbankschema

Datenbank

Analog zu Relation.
Eine Menge d = {r₁, r₂, ...} von Relationen heißt Datenbank zu Datenbankschema S, wenn für alle r_i gilt: r_i(R_i).

Dann schreibt man auch d(S) ist Datenbank zu Datenbankschema S.

Lokale Integritätsbedingung

Abbildung aller Relationen zu einem Schema auf true oder false nach der Frage
"Erfüllt die gegebene Relation die Integritätsbedingung?"

Damit bastelt man dann die Menge Comic-Sans B, die alle möglichen lokalen Integritätsbedingung enthält und definiert

• Comic-Sans R = (R, Comic-Sans B) (Erweitertes Relationenschema)
• r(Comic-Sans R) ist Relation von R, die alle Integritätsbedingung erfüllt.

Weiter gilt:

• SAT_R(Comic-Sans B) ist die Menge aller erweiterten Relationen (Relationen über R SATisfies Bedingungen Comic-Sans B)

z.B. r1:

Name	Alter
Peter	20
Petra	22

r2:

Name	Alter
Peter	-1
Petra	22

Sei R = {Name, Alter} und r₁, r₂ ∈ REL(R) und b = Alter > 0.
Dann gilt:

• b(r₁) = true
• b(r₂) = false

Und somit:

• r₁ ∈ SAT_({b})
• r₁ ∉ SAT_({b})

Integritätsbedingungen im Relationalen Modell

Schlüssel:

Konzept	Erklärung
Schlüsselkandidat (manchmal auch Schlüssel)	Minimale identifizierende Attributmenge (für jeden Tupel)
Primattribut	Attribut, das Teil eines Schlüsselkandidaten ist
Primärschlüssel	Als Hauptschlüssel markierter Schlüsselkandidat
Fremdschlüssel	Attribut in Relation X, das einen Schlüssel in Relation Y referenziert

Schlüssel und Fremdschlüssel sind die einzigen Integritätsbedingungen im relationalen Modell

Relationentheorie.md

Abhängigkeitstreue

Menge der FDs ist äquivalent zur Menge der Schlüsselabhängigkeiten. (i.e. wir verlieren keine FD)

Verbundtreue

Alle Anwendungsdaten können aus den Basisrelationen durch natural joins hergeleitet werden.

Ein Kriterium: X zerlegt in X_1 / X_2 ist verbundtreu, falls
X_1 ∩ X_2 Schlüssel für X_1 oder
X_1 ∩ X_2 Schlüssel für X_2

z.B. R = (A B C), A -> B, B -> C
X_1 = (AB), X_2 = (BC) ist verbundtreu, da X_1 ∩ X_2 = B
und B -> (BC) = X_2 gilt (B ist Schlüssel für X_2).

Anderes Kriterium: Eine Relation muss einen Universalschlüssel enthalten, d.h. eine Zerlegung X_i -> X.

Primattribut

Attribut, das Teil eines Schlüsselkandidaten ist

Nicht-Primattribut

Attribut, das nicht Teil eines Schlüsselkandidaten ist

Determinate

Attributmenge von der andere Attribute funktional abhängen.

1 NF

Alle Attribute sind atomar (also keine Listen oder so).

Nicht in 1 NF:

Name	Tiere
Peter	Goldi, Rotlöckchen

2 NF

Kein Nicht-Primattribut hängt funktional von einer echten Teilmenge eines Schlüsselkandidaten ab.
I.e. eliminiert partielle Abhängigkeiten von einem Nicht-Prim zu Primattribut.

Triviale Erfüllung:

1. Keine Nicht-Primattribute
2. Schlüsselkandidaten sind nur ein Attribut

3 NF

Kein Nicht-Primattribut hängt transitiv von einem Schlüsselkandidaten ab. Ein Nicht-Primattribut darf also nur direkt von einem Schlüsselkandidaten abhängen.

Warum? Transitive Abhängigkeiten offenlegen, thematische Durchmischung vermeiden.

Triviale Erfüllung:

1. Keine Nicht-Primattribute

BCNF

Jede Determinate (Menge, von der andere Attribute funktional abhängen) ist Schlüsselkandidat. I.e. wenn X -> Y gilt, ist X ein Schlüsselkandidat

Überführung nicht immer abhängigkeitstreu möglich

4 NF

Nur triviale mehrwertige Abhängigkeiten (Alle mehrwertigen Abhängigkeiten sind nicht unabhängig):

Personnummer	Haustier	Fahrzeug

ist nicht in 4 NF, da Personnummer -> Haustier, Personnummer -> Fahrzeug MWA, aber Haustier -> Fahrzeug nicht existiert ==> Unabhängig

Person	Partner	Kind

ist in 4NF. Person -> Partner, Person -> Kind, aber auch Partner -> Kind.

Multi valued dependency

Triviale (X ->> Y): Y folgt bereits aus X (durch FD)

Erkennen A:

1. Aufspalten der Relation an FD
2. Natural joinen
3. Schauen, ob alle Tupel drinnen sind

Erkennen B (A ->> B):

1. Für jeden Wert von A:
   1. Halte A fest
   2. Sammle alle Tupel mit A=der Wert
   3. Sammle alle B Werte, die in diesen Tupeln vorkommen
   4. Tausche die B Werte in den Tupel aus 2 rum, bilde alle Kombinationen
   5. Wenn einer nicht drinnen ist, ist das kaputt

Transaktionen.md

Lost update

T1	T2	Probleme?
x = read()	x = read()
	write(x + 1)	Lost!
write(x)

Dirty read (abort und commit wichtig!)

T1	T2	Probleme?
write(x, 5)
	read(x) := 5
	commit
abort		Falscher read in T2, das sollte nicht 5 gewesen sein

Non-Repeatable read

T1	T2	Probleme?
read(x) := 5
	write(x, 6)
read(x) := 6		Sad, sollte immer noch 5 sein

Transaktion

Ausführung eines Programmes, das auf die DB zugreift.
Partielle Ordnung (Σ, <).

Eigenschaften:

• Ausführungsreihenfolge
• Gelesene / Geschriebene Datenobjekte
• Ende (commit, abort, nichts)

Bedingungen:

• T_i besteht aus abort (a_i), commit (c_i) oder r_i[X] / w_i[X] wobei X ein gültiges Datenobjekt ist
• a_i \in T_i <=> c_i nicht \in T_i (und es enthält mindestens ein davon!)
• Jede Operation kommt vor abort/commit
• Wenn konfligierende Operationen in der Transaktion sind, ist für sie eine Ordnung bestimmt.

Konfligieren

2 Operationen greifen auf das gleiche Datenobjekt zu, mindestens eine ist Schreiboperation

Vollständige Historie

Vollständige History H über Transaktionenmenge T:

• H = Vereinigung aller Transaktionen
• Ordnungsrelation auf H ist Teilmenge der Vereinigung der Ordnungsrelation auf allen Transaktionen (i.e. sie macht nichts anders wie die Transaktionen)
• Wenn p und q konfligieren, ist für sie in H eine Ordnung bestimmt

Historie

Präfix einer vollständigen Historie:
Von hinten kommen können Sachen weggelassen werden.

T: r[x] -> w[x] -> c
H_1: r[x] -> w[x]
H_2: r[x]
Vollständige Historie ist hier T

Committed Projection einer Historie

Löschen aller Operationen von nicht-committeten Transaktionen (z.B. beim Neustart nach einem Absturz, um Atomarität zu wahren)

Prefix-Commit-Closedness

Eigenschaft α einer Historie gilt auch für die Committed Projection aller Präfixe.
Mit anderen Worten: H erfüllt Eigenschaft ==> C(H') erfüllt die Eigenschaft, mit H' ist Präfix von H und C(H') ist die Committed Projection

z.B.
+ H enthält weniger al 10 Operationen
+ Alle Operationen in H sind Leseoperationen
- H enthält mehr als 10 Operationen

Konflikt-Äquivalenz (Historie)

H und H' sind konflikt-äquivalent, wenn

1. Sie die gleichen Transaktionen haben
2. Sie die gleiche Ordnung für konfligierende Operationen haben

Serialisierbarkeit

H ist serialisierbar, wenn C(H) zu serieller Historie H_s (konflikt) äquivalent ist.

Serielle History:
Committete Transaktionen jeweils komplett und nacheinander (abortete Transaktionen fliegen raus!).

Test: Serialisierbarkeitsgraph / Abhängigkeitsgraph
Knoten: Transaktionen
Kante: Abhängigkeit (T_1 vor T_2)

• Greifen auf das gleiche Datenobjekt zu und konfligieren
• Richtung: Später zu früher (eigentlich egal, solange konsistent)
• Transitivität ist implied, muss also nicht aufgeschrieben werden

Serialisierbar, falls Graph zyklenfrei (partielle zu totaler Ordnung erweiterbar)

Locking

Notation: ol[x], ou[x]
Können auch konfligieren.

RX locking (einfachster Fall, nur read und write):

• rl[x]
• ru[x]
• wl[x]
• wu[x]

Zwei-Phasen Sperrprotokoll

1. Phase: Locks anfordern
2. Phase: Locks freigeben

Wenn in 2. Phase übergegangen, darf man nichts mehr freigeben. Erzwingt Serialisierbarkeit.

Strenges Zwei-Phasen Sperrprotokoll

Freigeben von locks erst am ENDE der Transaktion (behebt Dirty Reads)

Reads-From Beziehung

Lesen von der letzte Transaktion, die eine wirksame Änderung gemacht hat:

T_i liest von T_j, falls:

• w_j(x) < r_i(x) [T_j schrieb davor]
• a_j nicht vor r_i(x) [T_j wurde (bis dahin) nicht zurückgesetzt]
• falls es noch irgendein w_k mit w_j(x) < w_k(x) < r_i(x), dann gilt a_k < r_i(x) [alle anderen Transaktionen, die dazwischen was gemacht haben, wurden bereits abgebrochen. J ist also die letzte!]

Rücksetzbarkeitsklassen

Korrekte Historie: Serialisierbar und mindestens RC
Ziel: Alle Effekte von committeten Transaktionen, keine von nicht committeten

Recoverability (RC):
Ein abort darf die Semantik einer committeten Transaktion nicht verändern.
==> Wenn T_i von T_j liest und c_i in H, dann c_j < c_i (Abhängigkeiten sind bereits fertig, daher kann ihr Abbruch die Werte von T_i nicht verändern, wenn sie bereits committet wurde.)

Avoids Cascading Aborts (ACA):
Verhindert kaskadierende aborts durch Zurücksetzen einer Transaktion, von der gelesen wurde.
Nur lesen von bereits committeten Transaktionen.
==> Wenn T_i x von T_j liest, gilt: c_j < r_i(x)

Strictness (ST):
"Rückgängig machen" soll einfach zu implementieren sein
==> Speichere immer letzten Wert bei schreiben (before image)

Problem:

       x=1 w_1(x, 2)  w_2(x, 3) a_1 a_2
BI           x = 1      x = 2

Jetzt wäre aber der Wert 2 da. Falsch! Beruht auf Wert der abgebrochenen Transaktion.

Lösung:
Die Transaktion, die den Wert davor geschrieben hat, muss beim nächsten Schreiben einer anderen Transaktion bereits abortet oder committet sein.

Formal:
Wenn w_j(x) < o_i(x), dann:
a_j < o_i(x) oder
c_j < o_i(x)

i.e. Ausweitung von reads-from auf "overwrites" Paare

ST strenger ACA strenger RC