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

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

Einführung

Datenbankmanagementsystem (DBMS)

Gesamtheit der Programme zum Zugriff auf die (im DBMS) gespeicherten Daten.

Datenbasis

Als Datenbasis bezeichnet man die in einem DBMS gespeicherten Daten.

Datenbankschema

Das Datenbankschema legt die Struktur der Daten fest.

Entity-Relationship (ER) Modell

• Entitytypen: Rechtecke
• Beziehungstypen: Rauten
  • Es gibt zwei Notationen für Kardinalitäten, die verschiedenes ausdrücken:
    • Funktionalitäten — wie viele Entitäten sind in einer Relation?
    • (min,max) Notation — wie viele Relationen kann eine Entität insgesamt haben?
• Attribute: Ellipsen
  • Im Schlüssel enthaltenen Attribute werden unterstrichen.
• Generalisierung notiert mit Pfeilen

Schwache Entities

Entities, deren Existenz von einer anderen, ̈ubergeordneten Entity abhängen und die durch eine Kombination mit dem Schlüssel der übergeordneten Entity identifizierbar sind.

Relationales Modell

Schlüssel

Ein Schlüssel ist eine minimale Menge von Attributen, deren Werte ein Tupel eindeutig identifizieren.

Fremdschlüssel

Eine Menge von Attributenwelche auf den Schlüssel einer (anderen) Relation verweist.

Datenabfragesprachen

Relationale Algebra und Relationenkalkül bilden die theoretische Grundlage für SQL, sind gleich ausdrucksstark und relational abgeschlossen.

Relationale Algebra

Siehe auch de.wikipedia:Relationale Algebra.

• Basisoperatoren

$\sigma _{F}(R)$	Selektion
$\pi _{A}(R)$	Projektion — Duplikate werden eliminiert
$R\cup S$	Vereinigung	$\mathrm {att} (R)=\mathrm {att} (S)$
$R-S$	Mengendifferenz	$\mathrm {att} (R)=\mathrm {att} (S)$
$R\times S$	kartesisches Produkt (Kreuzprodukt)
$\rho _{A\leftarrow B}(R)$	Umbenennung von Attributen
$\rho _{V}(R)$	Umbenennung von Relationen

• $\bowtie$ natürlicher Join
• ⟕, ⟖, ⟗ linker, rechter bzw. voller äußerer Join
• $\rtimes$, $\ltimes$ linker bzw. rechter Semi-Join
• $\cap$ Durchschnitt
• $\div$ Division

Relationenkalkül

$\{t\mid P(t)\}$

Relationale Tupelkalkül

Atome:

• $t\in R$ — Tupelvariable in Relation
• $s.A\ \phi \ t.B$ — Vergleich zweier Tupelvariablen ($\phi \in \{=,\neq ,<,\leq ,>,\geq \}$)
• $s.A\ \phi \ c$ — Vergleich einer Tupelvariablen mit einer Konstanten

Relationale Domänenkalkül

Atome:

• $[v_{1},\dots ,v_{n}]\in R$ — Domänenvariablen in Relation
• $x\ \phi \ y$ — Vergleich zweier Domänenvariablen
• $x\ \phi \ c$ — Vergleich einer Domänenvariable mit einer Konstante

SQL

• SQL stellt keinen Allquantor zur Verfügung. Realisierung durch
  • Logische Äquivalenz (mittels 2x NOT EXISTS)
  • Teilmengen (mittels EXISTS und EXCEPT)
  • Abzählen (mittels COUNT)
  • Division (mittels EXCEPT)
• GROUP BY ... [HAVING ...]
• COALESCE

Funktionale Abhängigkeiten

Notation

• Ein Relationenschema bezeichnet eine Menge von Attributen ${\mathcal {R}}=\{A,B,C,\dots \}$.
• Eine Relation $R$ enthält Tupel (Zeilen), die dem Relationenschema entsprechen.
• Die Attributmengen $\alpha ,\beta ,\gamma ,\dots$ enthalten alle Ausprägungen eines Attributs.

Sei ${\mathcal {R}}$ ein Relationenschema und $\alpha \in {\mathcal {R}},\beta \in {\mathcal {R}}$. Eine Funktionale Abhängigkeit (FD) ist eine Beziehung $\alpha \to \beta$ ("α bestimmt β").

Eine funktionale Abhängigkeit ist genau dann erfüllt, wenn $\forall x,y\in R:x.\alpha =y.\alpha \implies x.\beta =y.\beta$.

In SQL kann man funktionale Abhängigkeiten wie folgt überprüfen. Die Query darf keine Ergebnisse liefern.

select * from R r1 , R r2 where r1.α = r2.α and r1.β != r2.β;

Hülle

Hülle $\gamma ^{+}$ einer Attributmenge $\gamma$

Enthält alle Attribute welche von der Attributmenge $\gamma$ funktional abhängen.

Ableitung von FD-Mengen $F_{1}\vDash F_{2}$

Jede Relation welche alle FDs in $F_{1}$ erfüllt, erfüllt auch alle FDs in $F_{2}$.

Hülle $F^{+}$ von FD-Menge $F$

Die Menge aller aus F ableitbaren FDs.

Armstrong Axiome

Sind vollständig (erzeugen alle implizierten FDs) und korrekt (erzeugen nur gültige FDs).

• Reflexivität $\alpha \to \beta ,\quad \beta \subseteq \alpha$
• Verstärkung $\alpha \to \beta \implies \alpha \gamma \to \beta \gamma$
• Transitivität $\alpha \to \beta \land \beta \to \gamma \implies \alpha \to \gamma$

Dararus folgen:

• Vereinigung $\alpha \to \beta \land \alpha \to \gamma \implies \alpha \to \beta \gamma$
• Dekomposition $\alpha \to \beta \gamma \implies \alpha \to \beta \land \alpha \to \gamma$
• Pseudotransitivität $\alpha \to \beta \land \gamma \beta \to \delta \implies \alpha \gamma \to \delta$

Aufgrund der Reflexivität gilt $\alpha \to \alpha$. Definitionsgemäß gilt dies auch wenn man die linke Seite erweitert: $\alpha \beta \to \alpha$

Äquivalenz von FDs $F\equiv G$

Zwei Mengen von FDs sind äquivalent, wenn sie dieselbe Hülle besitzen.

Kanonische Überdeckung

Kanonische Überdeckung $F_{C}$

1. $F_{C}^{+}=F^{+}$
2. In $F_{C}$ existieren keine FDs, die überflüssige Attribute enthalten.
3. Jede linke Seite einer FD in $F_{C}$ ist einzigartig.

Sie kann wie folgt berechnet werden:

1. Zerlege alle FDs mittels Dekomposition auf der rechten Seite.
2. Führe für jede FD $\alpha \to B\in F$ die Linksreduktion durch.

   Entferne $A\in \alpha$ falls $B\in {\text{AttrHülle}}(F,\alpha -A)$.

3. Führe für jede (verbliebene) FD $\alpha \to B\in F$ die Rechtsreduktion durch.

   Entferne die Abhängigkeit falls $B\in \alpha :B\in {\text{AttrHülle}}(F-(\alpha \to B),\alpha )$.

4. Fasse mittels der Vereinigungsregel FDs zusammen.

Schlüssel

Schlüssel $\gamma \subseteq {\mathcal {R}}$

$\gamma \to {\mathcal {R}}$ und $\gamma$ ist minimal.

Superschlüssel

$\gamma \to {\mathcal {R}}$.

Entwurfstheorie und Zerlegung

Korrektheitskriterien für die Zerlegung von Relationenschemata:

Verlustlosigkeit

Die in der Ausprägung $R$ des Schemas ${\mathcal {R}}$ enthaltenen Informationen müssen aus den Ausprägungen $R_{1},\dots ,R_{n}$ der neuen Schemata ${\mathcal {R}}_{1},\dots ,{\mathcal {R}}_{n}$ rekonstruierbar sein.

Abhängigkeitstreue

Die auf ${\mathcal {R}}$ geltenden funktionalen Abhängigkeiten müssen auf die Schemata ${\mathcal {R}}_{1},\dots ,{\mathcal {R}}_{n}$ übertragbar sein.

Normalformen

1. Normalform

Ein Relationenschema, wenn die Domänen atomar sind.

2. Normalform

Eine Relation modelliert nur Informationen von einem Konzept. Nur von historischem Interesse, da es immer noch zu Anomalien kommen kann.

3. Normalform

Für jede auf ${\mathcal {R}}$ geltende FD der Form $\alpha \to B,\quad \alpha \subseteq {\mathcal {R}},B\in {\mathcal {R}}$ gilt mindestens eine der folgenden Bedingungen:

1. $B\in \alpha$ (trivial)
2. $\alpha$ ist Superschlüssel von ${\mathcal {R}}$
3. das Attribut B ist in einem der Schlüssel von ${\mathcal {R}}$ enthalten

Synthesealgorithmus

1. Bestimme kanonische Überdeckung $F_{c}$ zu $F$.
2. Für jede FD $\alpha \to \beta \in F_{c}$:
   • Erstelle ein Relationenschema ${\mathcal {R}}_{i}:=\alpha \cup \beta$
   • Orde ${\mathcal {R}}_{\alpha }$ die FDs $F_{i}:=F_{c}[{\mathcal {R}}_{i}]$ zu.
3. Enthält keines der in Schritt 2. erzeugten Teilschemata einen Schlüssel von ${\mathcal {R}}$ bzgl. $F_{c}\implies$, wähle einen Schlüssel $k\in {\mathcal {R}}$ aus und definiere folgendes zusätzliche Schema: ${\mathcal {R}}_{k}:=k$ mit $F_{k}:=\emptyset$.
4. Eliminiere die in einem anderen Schema ${\mathcal {R}}_{j}$ enthaltenen Schemata ${\mathcal {R}}_{i}$.

Boyce-Codd Normalform (BCNF)

Für jede auf ${\mathcal {R}}$ geltende FD der Form $\alpha \to B,\quad \alpha \subseteq {\mathcal {R}},B\in {\mathcal {R}}$ gilt mindestens eine der folgenden Bedingungen:

1. $B\in \alpha$ (trivial)
2. $\alpha$ ist Superschlüssel von ${\mathcal {R}}$

Dekompositionsalgorithmus

1. Starte mit $Z=\{({\mathcal {R}},F)\}$
2. Solange es Relationenschema $({\mathcal {R}}_{i},F_{i})\in Z$ gibt, das die BCNF verletzt

Wähle eine solche FD $\alpha \to \beta$ aus und zerlege wie folgt:

• ${\mathcal {R}}_{i_{1}}:=(\alpha \cup \beta ),F_{i_{1}}:=F_{i}^{+}[{\mathcal {R}}_{i_{1}}]$
• ${\mathcal {R}}_{i_{2}}:={\mathcal {R}}_{i}-(\beta -\alpha ),F_{i_{2}}:=F_{i}^{+}[{\mathcal {R}}_{i_{2}}]$

Entferne $({\mathcal {R}}_{i},F_{i})$ aus Z und füge $({\mathcal {R}}_{i_{1}},F_{i_{1}})$ und $({\mathcal {R}}_{i_{2}},F_{i_{2}})$ ein.