kapitel 3

ERD $\to$ Relationenschema §

ERD	Relationenschema
Entität	Tabelle
Attribut	Spalte
Subattribut	Einzelne Spalten
Mehrwertiges Attribut	1:N Beziehung
Beziehungen	Fremdschlüssel
Schwache Entität	Zusammengesetzter PK
Ternäre Beziehung	wie N:M Beziehungen
Generalisierung	siehe unten

Generalisierung §

Methode	Erklärung
Volle Redundanz	Jede Entität wird zu einer Tabelle mit allen Spalten, führt zu Redundanz
Hausklassenmodell	Wie volle Redundanz, aber es wird nur in eine Tabelle eingefügt
Vertikale Partitionierung	Bei Subentitäten nur spezielle Spalten übernehmen
Hierarchierelation	Nur eine Tabelle mit allen Spalten, + type tag

Mengenoperationen §

• $\cap$ Schnittmenge
• $\text{textbackslash}-$ Subtraktion
• $\cup$ Vereinigung

Projektion $\pi$ §

${\pi }_{\text{Spalte 1, Spalte 2, ...}}(R)$ begrenzt die Ausgabe auf die angegebenen Spalten.

Selektion $\sigma$ §

${\sigma }_{\text{Kriterium}}(R)$ begrenzt die Ausgabe auf die Zeilen, die das Kriterium erfüllen.

Kartesisches Produkt $\times$ §

$R\times S$ hat alle Spalten aus R und S, und weist jeder Zeile aus R jede Zeile aus S zu.

Umbenennung $\rho$ §

${\rho }_{\text{Alias}}(R)$ gibt der Tabelle R den Namen ‘Alias’.

Join $\bowtie$ §

$R{\bowtie }_{P}S$ ist äquivalent zu ${\sigma }_P(R\times S)$. P ist das join-Kriterium.

Typ	Erklärung
Inner join	(= Join) $\bowtie$
Outer Join	⟕ ⟖ ⟗
Equi-Join	Nur $=$
Theta-Join	$<\le =\ne \ge >$
Natural Join	Equi-Join mit gleich heißenden Attributen
Self-Join	$R\bowtie R$
Semi-Join	R⋉S bzw. R⋊S: ${\pi }_{R.\ast }$ bzw. ${\pi }_{S.\ast }$

Division $÷$ §

$R÷S$ gibt eine Tabelle mit allen Spalten aus R, welche nicht auch in S sind. Die resultierenden Zeilen sind jene aus R, für die gilt: Die Zeile hat alle möglichen Kombinationen mit S.

Man kann $R÷S$ folgendermaßen umschreiben (nicht klausurrelevant):

$$R÷S={\pi }_{R.\ast -S.\ast }(R)-{\pi }_{R.\ast -S.\ast }\left(\right({\pi }_{R.\ast -S.\ast }(R)\times S)-R)$$

Es gilt:

$$(R\times S)÷S=R$$

Sind die Spalten in S keine Teilmenge von jenen in R, so ist das Ergebnis der Division immer leer.

https://en.wikipedia.org/wiki/Relational_algebra#Division_(%C3%B7)

Anfrageoptimierung §

Heuristiken

• Frühstmögliche Selektion
• Join statt Kreuzprodukt
• Frühstmögliche Projektion (ohne Duplikateliminierung)
• Join-Reihenfolge so wählen, dass Zwischenergebnisse klein sind
• Folgen von Selektionen und Projektionen zusammenfassen
• Selektionen statt Mengenoperationen
• Nichts doppelt berechnen

Kardinalitätsschätzung

• Selektion
  • $|{\sigma }_{R.a=x}(R)|=\frac{|R|}{|R.a|}$
  • $s{f}_P=\frac{|{\sigma }_{P}R|}{|R|}$
• Kartesisches Produkt
  • $|R\times S|=|R|\cdot |S|$
• Join
  • $0\le |R\bowtie S|\le |R|\cdot |S|$
  • $|R{\bowtie }_{R.a=S.a}S|=|R|$ bzw. $|S|$

Normalformenlehre §

Abhängigkeiten §

Funktionale Abhängigkeit

• $A\to B$ (A bestimmt B)
• A und B sind Attributmengen aus R

**Volle Funktionale Abhängigkeit

• $A\Rightarrow B$ (A bestimmt B voll-funktional)
• Voraussetzung: $A\to B$ und es gibt keine Teilmenge aus A, für die gilt $A^{\prime }\to B$.

Schlüssel §

Superschlüssel

• $A\to R$ (A bestimmt alle Attribute, A ist also Superschlüssel)

Schlüsselkandidat

• Voraussetzung: A ist superschlüssel und bestimmt R voll-funktional
• minimaler Superschlüssel

Normalformen §

NFNF

• Non-First Normal Form
• Nicht in Normalform

1NF

• Attribute sind nicht zusammengesetzt oder Tabellen

2NF

• in 1NF
• jedes nicht-Schlüsselattribut hängt voll vom ganzen Schlüssel ab

3NF

• in 2NF
• keine transitiven Abhängigkeiten $A\to B\to C$