Klausur

Schema darf keine Mengenartigen Attribute enthalten.

Jede FD (a->b) muss mindesten eine der folgenden Bedingungen erfüllen:

1. b ist Teil eines Kandidatenschlüssels

2. b ist nicht von einer echten Teilmenge eines Schlüsselkandidaten abhängig

Alle nicht prim Attribute sind voll funktional abhängig von jedem Schlüsselkandidaten

(Voll funktional abhängig bedeutet, dass sie nicht schon von Teilen des eines Schlüsselkandidaten abhängig sind)

∀ a ∈ R: prim(a) v ( k -> r ^ -k’ -> r)

Jede FD (a->b) muss mindestens eine der folgenden 3 Bedingungen erfüllen:

1. a->b ist trivial (b ist teil von a, z.B: AB->B)

2. a ist ein Superschlüssel (a bestimmt die gesamte Relation)

3. Jedes Attribut in b ist prim

Keine Abhängigkeiten zwischen Nicht-Schlüssel-Attributen (NSAs).

∀ a ∈ R: prim(a) v -determinante(a)

Jede FD muss mindestens eine folgenden 2 Bedingung erfüllen:

1. a->b ist trivial (b ist Teil von a, z.B ABC->AB)

2. a ist ein Superschlüssel (a bestimmt die gesamte Relation)

Jede Determinante ist ein Schlüsselkandidat

Jede MVD muss mindestens eine folgenden 2 Bedingung erfüllen:

1. a->>b ist trivial (b ist Teil von a, z.B ABC->AB)

2. a ist ein Superschlüssel (a bestimmt die gesamte Relation)

Keine doppelten mehrweertigen Abhängigkeiten

Eine minimale Menge von Attributen, welche die gesamte Relation bestimmt.

Dh. Ganz R ist funktional abhängig von S.

Man darf dabei kein Attribut von S entfernen können sodass S' immernoch ganz R bestimmt

Eine Menge von Attributen welche die Relation ganz bestimmt.

Trivial ist R ein Superschlüssel von R

Zu jeder Determinante a in den FDs, bilde die Attributhülle a+:

Sie muss zwei Eigenschaften Erfüllen damit a ein Schlüsselkandidat ist:

1. Sie muss ganz R bestimmen: a -> R

2. Sie muss minimal sein: Dh. Nimmt man was aus a weg gilt nicht a’ -> R

z.B:

A+ = { A,B,D,E,F } => nicht a -> R

B+ = { B,F } nicht a -> R

CF+ = { C,F,A,B,D,E } ok a -> R

=> Also CF+ bestimmt R. Aber:

C+ = { C } und F+ = { F } bestimmt nicht R

=> Also ist CF der einzige Schlüsselkandidat

Mit dem Synthesealgorithmus:

1. Bestimmung von Funktionalen Abhängkeiten

   1. Linksreduktion

   2. Rechtsreduktion

   3. Zusammenfassen

2. Aus jeder FD eine Tabelle machen

Mit dem Dokompositionsalgorithmus:

Die kleinste Menge von FDs für ein Schema

Eine Zeitliche Abfolge von Operationen von N Transaktionen.

z.B: w1(X) w2(y) c1 c2

Wenn ihr Serialisierungsgraph keine Zyklen hat.

Man beginnt die Operationen durchzulaufen. Wenn für eine Operation auf X eine spätere Operation einer anderen TX folgt die einen “Konflikt“ hat zichnet man eine Kante von der jetzigen TX auf die folgende TX

Wenn jede Transaktion A, die von einer anderen Transaktion B gelesen hat nach dieser TX B commited.

w1(x) r2(x) c2 c1

-> Nicht rücksetzbar

Eine Historie vermeidet kaskadierendes Rücksetzten, wenn jede TX commited, bevor von ihr gelesen wird.

Das ist nicht der Fall, wenn von einer nicht-commiteten TX gelesen wird:

w1(x) r2(y)

Wenn eine TX auf A schreibt w(A), muss sie commiten oder aborten BEVOR eine andere Transaktion A benutzt.

-> Jede TX erhält einen WRITE-LOCK, der erst nach Ende der TX freigegeben wird.

• Lost Update: Das Ergebnis einer TX wird überschrieben

• Dirty Read: TX liest einen Wert der dann zurückgesetzt wird

• Non Repeatable Read: TX liest zweimal den selben Wert. Beim zweiten mal ist er aber anders

• Phantom Problem: TX fände beim zweiten Lesen einer Tabelle A ein Tupel mehr

ACID:

• Atomicity: Alles oder nix. Entweder ganz commited oder aborted

• Consistency: Vor und nach jeder TX ist der DB Zustand Konsistent

• Isolation: Jede TX ist scheinbar die einzige

• Durability: Nach einem commit bleiben die Änderungen immer erhalten

• Regular join: Kreuzprodukt + Selektionsprädikat

• Equi Join: Regular join mit = als Selektionsprädikat

• Natural Join: Equi Join über gleichnamige Attribute

• Left/Right/Full outer join: Behält Tupel aus A, B oder A und B die keinen Partner haben

• Left/Right Semi Join: Behält nur Tupel die Partner haben und übernimmt nur Attribute dieser Tupel.

• Left/Right Anti join: Kickt alle Tupel die keinen Partner haben

1. Analyse: Finden aller Winner und Loser Transaktionen (->)

2. Redo: Ausühren aller Eintrage gemäß LSN (->):

   1. Holen der Seite aus dem Hintergrundspeicher

   2. if( log.lsn < seite.lastLsn ) { perform(); seite.lastLsn = log.lsn }

3. Undo: Undo aller Einträge von Loser transaktionen (<-)

   1. Holen der Seite aus dem Hintergrundspeicher

   2. Undo ausführen & Kompensationseintrag einfügen

Ein Compensation Log Record besteht aus:

• LSN: Neue Log Sequenze Number (Oft #i’)

• Transaktions ID (z.B: T2)

• Seitennummer z.B: PA

• Undo Infos. z.B: A -= 10

• PrevLSN: Pointer zum Vorherigen Log Eintrag der Transaktion

• UndoNxtLSN: Verweis auf die LSN des zurückgesetzten Eintrags

Die schwachen Entitäten sind doppelt umschlossen.

Die Menge an Tupeln in einer Relation. z.B: |A| = 10

der Anteil an Tupeln die bei einer Operation herauskommen.

select *, rank() over (order by name)

from Students