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

From VoWi
Jump to navigation Jump to search

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

Einführung[edit]

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[edit]

  • 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[edit]

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[edit]

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

Relationale Algebra[edit]

Siehe auch de.wikipedia:Relationale Algebra.

  • Basisoperatoren
Selektion
Projektion — Duplikate werden eliminiert
Vereinigung
Mengendifferenz
kartesisches Produkt (Kreuzprodukt)
Umbenennung von Attributen
Umbenennung von Relationen
  • natürlicher Join
  • ⟕, ⟖, ⟗ linker, rechter bzw. voller äußerer Join
  • , linker bzw. rechter Semi-Join
  • Durchschnitt
  • Division

Relationenkalkül[edit]

Relationale Tupelkalkül[edit]

Atome:

  • — Tupelvariable in Relation
  • — Vergleich zweier Tupelvariablen ()
  • — Vergleich einer Tupelvariablen mit einer Konstanten
Relationale Domänenkalkül[edit]

Atome:

  • — Domänenvariablen in Relation
  • — Vergleich zweier Domänenvariablen
  • — Vergleich einer Domänenvariable mit einer Konstante

SQL[edit]

  • 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[edit]

Notation
  • Ein Relationenschema bezeichnet eine Menge von Attributen .
  • Eine Relation enthält Tupel (Zeilen), die dem Relationenschema entsprechen.
  • Die Attributmengen enthalten alle Ausprägungen eines Attributs.

Sei ein Relationenschema und . Eine Funktionale Abhängigkeit (FD) ist eine Beziehung ("α bestimmt β").

Eine funktionale Abhängigkeit ist genau dann erfüllt, wenn .

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[edit]

Hülle einer Attributmenge
Enthält alle Attribute welche von der Attributmenge funktional abhängen.
Ableitung von FD-Mengen
Jede Relation welche alle FDs in erfüllt, erfüllt auch alle FDs in .
Hülle von FD-Menge
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
  • Verstärkung
  • Transitivität
Dararus folgen:
  • Vereinigung
  • Dekomposition
  • Pseudotransitivität

Aufgrund der Reflexivität gilt . Definitionsgemäß gilt dies auch wenn man die linke Seite erweitert:

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

Kanonische Überdeckung[edit]

Kanonische Überdeckung

  1. In existieren keine FDs, die überflüssige Attribute enthalten.
  2. Jede linke Seite einer FD in 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 die Linksreduktion durch.
    Entferne falls .
  3. Führe für jede (verbliebene) FD die Rechtsreduktion durch.
    Entferne die Abhängigkeit falls .
  4. Fasse mittels der Vereinigungsregel FDs zusammen.

Schlüssel[edit]

Schlüssel
und ist minimal.
Superschlüssel
.

Entwurfstheorie und Zerlegung[edit]

Korrektheitskriterien für die Zerlegung von Relationenschemata:

Verlustlosigkeit
Die in der Ausprägung des Schemas enthaltenen Informationen müssen aus den Ausprägungen der neuen Schemata rekonstruierbar sein.
Abhängigkeitstreue
Die auf geltenden funktionalen Abhängigkeiten müssen auf die Schemata übertragbar sein.

Normalformen[edit]

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[edit]

Für jede auf geltende FD der Form gilt mindestens eine der folgenden Bedingungen:

  1. (trivial)
  2. ist Superschlüssel von
  3. das Attribut B ist in einem der Schlüssel von enthalten
Synthesealgorithmus
  1. Bestimme kanonische Überdeckung zu .
  2. Für jede FD :
    • Erstelle ein Relationenschema
    • Orde die FDs zu.
  3. Enthält keines der in Schritt 2. erzeugten Teilschemata einen Schlüssel von bzgl. , wähle einen Schlüssel aus und definiere folgendes zusätzliche Schema: mit .
  4. Eliminiere die in einem anderen Schema enthaltenen Schemata .

Boyce-Codd Normalform (BCNF)[edit]

Für jede auf geltende FD der Form gilt mindestens eine der folgenden Bedingungen:

  1. (trivial)
  2. ist Superschlüssel von
Dekompositionsalgorithmus
  1. Starte mit
  2. Solange es Relationenschema gibt, das die BCNF verletzt
Wähle eine solche FD aus und zerlege wie folgt:
Entferne aus Z und füge und ein.