Zusammenfassung Einführung in Datenbanksysteme

Aus VISki
Wechseln zu: Navigation, Suche

Ziel dieser Zusammenfassung: All denjenigen welche die Vorlesung besucht (oder Slides studiert) haben, helfen, sich an alle Details und Zusammenhänge zu erinnern

  • Die behandelten Konzepte kurz und präzise erläutern und übersichtlich darstellen
  • Die wichtigsten Eigenschaften von Konzepten auflisten
  • Die Begriffe (Buzz-Words) wichtiger Konzepte auflisten und kurz beschreiben, damit man sich an die Begriffe erinnern kann
  • Überblick vermitteln (Wo gehört was hin? Wie hängt was zusammen? Worin unterscheiden sich die Konzepte?)


Nicht Ziel dieser Zusammenfassung: Jemandem der keine Ahnung vom Stoff der Vorlesung hat diesen verständlich machen

  • Die Konzepte ins Detail erklären (Dies ist Aufgabe der Vorlesung/Slides)
  • Viele Beispiele auflisten
  • Prüfungsfragen als Beispiele (Besser das getestete Wissen in die Zusammenfassung integrieren)
  • Nicht vorlesungsbezogenes Wissen vermitteln (Dies ist eine Zusammenfassung der Vorlesung. Eine Auswahl von all dem was es zu wissen gibt. Wer mehr will darf jeder Zeit Wikipedia verlinken)
  • Wikipedia kopieren
  • Alle Möglichkeiten und Ausnahmefälle auflisten
  • Einzelne SQL-Dialekte behandeln


Inhaltsverzeichnis

Grundlagen

Datenunabhängigkeit

Idee: Änderungen auf einer Ebene betreffen die anderen Ebenen nicht


  -------------------------
 | Sichten                 |
  -------------------------   Logische Datenunabhängigkeit
 | Logische Ebene          |
  -------------------------   Physische Datenunabhängigkeit
 | Physische Ebene         |
  -------------------------

Logische Datenmodelle

Es gibt verschiedene Datenmodelle:

  • Netzwerkmodell
  • Hierarchisches Datenmodell
  • Relationales Datenmodell (SQL)
  • Objektorientiertes Datenmodell
  • Semistrukturiertes Datenmodell (XML)
  • Deduktives Datenmodell

Entity Relationship (ER)

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Funktionalitäten

Eine n-stellige Funktionalität

                E_1
                 | N
                 |
           P     |    M
      E_n------- R-------E_2
                /|\...
            .../ | 
                 | 1
                E_k

ToDo:
Komische Schreibweise, besser als funktionale Abhängigkeit schreiben? So wie hier unten dran?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Für gilt

Min-Max

                E_1
                 | (min1, max1)
                 |
  (minn, maxn)   |     (min2, max2)
      E_n------- R-------E_2
                /|\...
            .../ | 
                 | (mink, maxk)
                E_k

Für gilt

  • Mindestens Tupel der Art (..., ek, ...) in der Relation R
  • Maximal Tupel der Art (..., ek, ...) in der Relation R

Vergleich Funktionalitäten und Min-Max

  • Mächtigkeit: Min-Max Notation und Funktionalitäten sind gleichmächtig
ToDo:
Was kann in Min-Max ausgesagt werden aber nicht in Funktionalitäten, was umgekehrt? Warum sind sie gleichmächtig?
Alle momentan zu editierenden Einträge werden hier gesammelt.


  • Eine 1:N Beziehung zwischen A und B ist äquivalent zu einer Min-Max-Notatin mit (1,1) für A und (0,*) für B
             1           N
       A --------- R --------- B
           (1,1)       (0,*)
ToDo:
Stimmt die Aussage für 1:1??? Bin mir nicht sicher! Könnte auch min-max Notation von (1,1) / (1,1) sein!?!?
Alle momentan zu editierenden Einträge werden hier gesammelt.
  • Eine 1:1 Beziehung zwischen A und B ist äquivalent zu einer Min-Max-Notatin mit (0,1) für A und (0,1) für B
             1           1
       A --------- R --------- B
           (0,1)       (0,1)

Entities

Schwache, existenztabhängige Entities

Satz: Funktionalität von existenzabhängigen Entities

Die Funktionalität zwischen starken Entities und schwachen Entities ist immer 1:N oder in seltenen fällen 1:1


Satz: Schlüssel von schwachen Entitäten

Der Schlüssel einer schwachen Entität setzt sich zusammen aus dem eigenen Schlüssel und dem Schlüssel von welcher die Entität abhängig ist. (Die schwache Entität erbt den Schüssel der Entität, von welcher sie abhängig ist)


Attribute

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Beziehung

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Aggregation

(teil-von Beziehung)

ToDo:
Beispiel
Alle momentan zu editierenden Einträge werden hier gesammelt.

Generalisierung

(is-a Beziehung)

ToDo:
Beispiel
Alle momentan zu editierenden Einträge werden hier gesammelt.

Relationales Modell

Grundlage

Domäne

Definition: Domäne

Eine Domäne D ist ein Wertebereich, also eine Menge von Werten


Beispiel

 Strings , Integers, Chars, Alle Postleitzahlen, Alle Ortsnamen der Schweiz


Schema

Definition: Schema

Ein Schema legt die Struktur der gespeicherten Daten fest. Das Schema beschreibt also die Relation
Für Domänen A, B, C ist ein Schema


Beispiel

Telefonbuch = {Attributname: Domäne, Attributname: Domäne, ...}
Telefonbuch = {Name: string, Adresse: string, Telefonnr: integer}


Relation

ToDo:
Unterschied Relation und Ausprägung?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Definition: Relation

Eine Relation R ist eine Teilmenge des kartesischen Produktes von mehreren Domänen
Seien Domänen, dann ist eine Relation


Beispiel

Telefonbuch  string  string  integer               //Name x Adresse x Telefonnumer
Telefonbuch = {("Peter", "Musterstrasse", 3223), ("Hans", "Buntestrasse", 4711), ("Martha", "Irgendwo", 34023)}

Ausprägung

Definition: Ausprägung

Die Menge aller Tupel


Beispiel

Telefonbuch = {("Peter", "Musterstrasse", 3223), ("Hans", "Buntestrasse", 4711), ("Martha", "Irgendwo", 34023)}


Tupel

Definition: Tupel

Ein Tupel ist ein Element einer Relation
Tupel


Beispiel

t  Telefonbuch
t = ("Peter", "Musterstrasse", 3223)


Schlüssel

Definition: Schlüssel / Kandidaten-Schlüssel / Schlüsselkandidat

Als Schlüssel bezeichnet man die minimale Menge von Attributen, deren Werte ein Tupel eindeutig identifizieren


Bemerkung

  • Es kann pro Relation mehrere mögliche Schlüssel geben
  • Es gibt immer einen Schlüssel. Dieser setzt sich im Extremfall aus allen Attributen zusammen


Primärschlüssel

Definition: Primärschlüssel

Als Primärschlüssel einer Relation wird ein beliebiger Schlüssel der Relation ausgewählt. Der Primärschlüssel wird zur eindeutigen Identifikation von Tupeln verwendet


Fremdschlüssel

Definition: Fremdschlüssel

Menge von Attributen einer Relation, welche auf einen Primärschlüssel einer anderen oder der gleichen Relation verweist

Probleme mit schlechten relationalen Modellen

ToDo:
Besser beschreiben!
Alle momentan zu editierenden Einträge werden hier gesammelt.

Update-Anomalie

Wegen Redundanz müssen viele Tupel geändert werden anstatt nur eines

Lösch-Anomalie

Wegen schlechtem Schema kann durch löschen Inkonsistenz entstehen, welche nicht einfach zu beheben ist. (Fremdschlüssel von einer anderen Relation verweist auf inexistentes Tupel. Löschen jedoch nicht

Einfüge-Anomalie

Ähnlich wie Lösch-Anomalie: z.B. einfü̈gen eines Professors schwierig, wenn er gar keine Vorlesung liest


Relationales Modell aus einem ER-Diagramm erstellen

ToDo:
Bitte sehr skeptisch überprüfen ob das stimmt hier unten dran?
Alle momentan zu editierenden Einträge werden hier gesammelt.
ToDo:
Punkt 2.2 konnte bis jetzt nich verifiziert werden
Alle momentan zu editierenden Einträge werden hier gesammelt.


Algorithmus

  • Namenskonflikte müssen selbst behandelt werden
  1. Entitäten umwandeln: Für jede Entität E:
    1. Definiere für E ein gleichnamiges Schema, wobei die Attribute der Entität E den Attributen des Schemas entsprechen
    2. Falls E eine schwache Entität ist, übernehme im Schema zusätzlich den Primärschlüssel der Entität von welcher E abhängig ist. Der neue Primärschlüssel von E ist der zusammengesetzte Schlüssel.
    3. Falls E als Teil einer Generalisierung von einer anderen Entität abhängig ist, füge den Primärschlüssel der Entität zum Schema hinzu, von welcher E abhängig ist
  2. Beziehungen umwandeln: Für jede Beziehung B (keine Generalisierungen oder Aggregationen):
    • Bemerkung: Schwache Entitäten erben den Schlüssel der Entität von welcher sie abhängig sind!
    1. Definiere für B ein gleichnamiges Schema. Die Attribute des Schemas setzen sich zusammen aus:
      • Den Attributen der Beziehung B
      • Allen Primärschlüsseln der Entitäten, welche Teil der Beziehung B sind (inkl geerbten Schlüsseln). Diese werden als Fremdschlüssel in das Schema übernommen.
    2. Bestimme den Primärschlüssel für die eben definierte Relation. Der Primärschlüssel setzt sich zusammen aus
      • allen Fremdschlüssel in B von Entities mit Funktionalität N
      • n-1 Fremdschlüssel von den n Fremdschlüsseln der n Entities mit Funktionalität 1 in B
  3. Schemas mit gleichem Schlüssel kann man zusammenfassen (ausschliesslich diese!)
    • Achtung: Gleichnamige Schlüssel müssen nicht zwingend auch semantisch gleich sein! Dies gilt insbesondere für Schlüssel die durch die Übersetzung von Generalisierung entstehen! Diese sind nie gleich obwohl sie gleich heissen!

Relationale Algebra

Grundoperationen

Mit den Grundoperatoren lassen sich alle anderen Operationen darstellen. Die Grundoperatoren sind:

  • Selektion (Auswahl von Tupeln / Zeilen)
  • Projektion (Auswahl von Domänen / Spalten / Attribute)
  • Kreuzprodukt
  • Umbennen (Von Relationen oder Attributen)
  • Mengendifferenz
  • Vereinigung


Projektion

Projektion der Tabelle E auf die Attribute :


Umbenennung

  • Umbenennung von Tabelle E nach V:
  • Umbenennung von Attribut B der Tabelle E nach A:


Vereinigung

Vereinigung der Relationen R und S:


Bemerkung

  • R und S müssen gleiches Schema haben

Weitere Operationen

Mit den Grundoperationen lassen sich folgende Operationen darstellen:

  • Division
  • Durchschnitt
  • Natürliche Join
  • Linker-äusserer-Join
  • Rechter-äusserer-Join
  • Äusserer-Join


Division

Division in den Grundoperatoren


Besipiel

  • R hören, S Vorlesung
  • Dann ist die Menge der Studenten die alle Vorlesungen hören

Durchschnit

Durchschnitt in den Grundoperatoren


Bemerkung

  • R und S müssen gleiches Schema haben

Natürliche Join

Natürliche Join in den Grundoperationen

ToDo:
Ausdruck in Grundoperationen
Alle momentan zu editierenden Einträge werden hier gesammelt.

Joint auf die gleich benannten Attribute zweier Relationen


Allgemeiner Join

Allgemeiner Join in den Grundoperationen

ToDo:
Ausdruck in Grundoperationen
Alle momentan zu editierenden Einträge werden hier gesammelt.

Joint auf die spezifizierten Attribute


linker-äusserer-Join

Linker-äusserer-Join R S in den Grundoperatoren

R S =


rechter-äusserer-Join

Rechter-äusserer-Join R S in den Grundoperatoren

R S =


äusserer-Join

Äusserer-Join R S in den Grundoperatoren

R S =


Relationenkalkül

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Tupelkalkül

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Domänenkalkül

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Ausdruckskraft

Satz: Ausdruckskraft

Die relationale Algebra, das relationale Tupelkalkül eingeschränkt auf sichere Ausdrücke und das relationale Domänenkalkül eingeschränkt auf sichere Ausdrücke sind gleich mächtig

SQL

SQL ist:

  • Datendefinitionssprache (DDL)
  • Datenmanipulationssprache (DML)
  • Anfragesprache (Query)

Datendefinitionssprache (DDL)

SQL-Statements wie

  • CREATE TABLE
  • ALTER TABLE
  • DROP TABLE
  • CREATE INDEX
  • CREATE VIEW
ToDo:
Diesen Abschnitt vervollständigen
Alle momentan zu editierenden Einträge werden hier gesammelt.

Datenmanipulationssprache (DML)

SQL-Statements wie

  • INSERT
  • UPDATE
  • DELETE
ToDo:
Diesen Abschnitt vervollständigen
Alle momentan zu editierenden Einträge werden hier gesammelt.


Änderbarkeit von Sichten

In SQL sind nur Sichten änderbar, welche folgende Kriterien erfüllen:

  • nur eine (1) Basisrelation (keine Mengenoperationen)
  • keine Aggregatfunktionen, Gruppierungen und Duplikateliminierung
  • Schhlüssel muss vorhanden sein

Anfragesprache (Query)

SQL-Statements wie

  • SELECT
  • inkl Mengenoperationen, Aggregatfunktionen, Gruppierungen, etc

Mengenoperationen

  • UNION : Vereinigung ohne Berücksichtigung von Duplikaten
  • INTERSECT : Schnittmenge ohne Berücksichtigung von Duplikaten
  • MINUS : Differenz ohne Berücksichtigung von Duplikaten
  • UNION ALL : Vereinigung mit Berücksichtigung von Duplikaten
  • INTERSECT ALL : Schnittmenge mit Berücksichtigung von Duplikaten
  • MINUS ALL : Differenz mit Berücksichtigung von Duplikaten
  • EXIST : Existenzquantor
  • ALL : Allquantor
  • IN : Ist ein Tupel in einer Tabelle?
ToDo:
Ist es gemäss sql standard MINUS oder EXCEPT?
Alle momentan zu editierenden Einträge werden hier gesammelt.

SQL hat keinen vollwertigen Allquantor. Es gilt jedoch folgende Äquivalenz bekannt aus der Logik:


Aggregatfunktionen und Gruppierung

Aggregatifunktionen sind:

  • AVB
  • MIN
  • MAX
  • COUNT
  • SUM


Regel
In der SELECT-Klausel aufgeführte Attribute - ausgenommen die aggregierten - müssen auch in der GROUP BY-Klausel aufgeführt werden

Umbenennung

ToDo:
Aufzeigen wie Tabellen, Attribute in SQL umbenannt werden können
Alle momentan zu editierenden Einträge werden hier gesammelt.

Geschachtelte Anfragen

ToDo:
Alle Möglichkeiten von Verschachtelungen aufzeigen!!
Alle momentan zu editierenden Einträge werden hier gesammelt.

Null-Werte

Der Wert null hat gemäss SQL die Bedeutung unbekannt, wird jedoch oft für 'nicht vorhanden' missbraucht


Eigenschaften

  • null-Werte werden propagiert
    • z.B 0 * null wird zu null
    • z.B 1 + null wird zu null
  • Vergleichsoperationen liefern null, wenn mindestens eines der Argumente null ist
    • z.B das Prädikat P(x):= Persnr = x wertet mit P(null) zu null aus
  • Logische Ausdrücke werden gemäss dreiwertiger Logik ausgewertet
    • True and null = null
    • False and null = False


Integrität

Datenintegrität

Unterteilung in:

  • Statische Integritätsbedingungen: Bedingungen an den Zustand der Datenbasis
    • z.B Eindeutige Schlüssel, Datentyp von Domänen (z.B Domäne alter hat Typ int), eine Domäne hat nur gewisse Werte
  • Dynamische Integritätsbedingungen: Bedingungen an Zustandsübergänge
    • z.B ???


Gewährleistung in SQL durch:

  • Datentypen
    • INTEGER, CHAR, etc
  • CHECK
  • CONSTRAINT
  • UNIQUE
  • PRIMARY KEY

Referentielle Integrität

  • Fremdschlüssel einer Relation müssen auf existierende Tupel verweisen oder einen Nullwert enthalten
    • Vergleichbar mit der Forderung nach keinen Dangling-Pointer in C


Beispiel

  • Relation gelesenVon := {VorlesungsNummer, ProfessorenNummer}: Jeder Wert in dieser Relation steht für eine Vorlesung resp Professor. Die referentielle Integrität ist genau dann gegeben, wenn für jeden Wert in dieser Relation der genau gleiche Wert auch in der entsprechenden Relation Vorlesungen resp Professoren existiert


Gewährleistung in SQL

Die referentielle Integrität wird in SQL durch die folgenden keywords gewährleistet:

  • REFERENCES
    • ON UPDATE CASCADE: Passt den Fremdschlüssel an
    • ON UPDATE SET NULL: Setzt den Fremdschlüssel auf NULL
    • ON UPDATE NO ACTION: Führt zu einem Error falls versucht wird den Schlüssel des referenzierten Tupels zu updaten
    • ON DELETE CASCADE: Passt den Fremdschlüssel an
    • ON DELETE SET NULL: Setzt den Fremdschlüssel auf NULL
    • ON DELETE NO ACTION: Führt zu einem Error falls versucht wird das referenzierten Tupel zu löschen

Einsatz

Satz: Ref. Integrität betreffend starken und schwachen Relationen

If a tuple of the strong relation is deleted, the dependent tuples must be deleted as well


Satz: Ref. Integrität betreffend N:M Beziehungen

If a referenced tuple in a N:M relationship is deleted, all references should be deleted

Relationale Entwurfstheorie

Für das Kapitel Relationale Entwurfstheorie gelte die folgende Variablenkonvention:

  • Ausprägung
  • Schema
  • ,


Definitionen

Funktionale Abhängigkeiten

Definition: Funktionale Abhängigkeit / Functional dependency (FD)

ist funktional abhängig von (Notation: ) genau dann wenn mit

Eigenschaften

  • Anzahl funktionale Abhängigkeiten: Ein Schema mit hat funktionale Abhängigkeiten (inkl trivialen funktionalen Abhängigkeiten)


Definition: Triviale funktionale Abhängigkeit

Eine funktionale Abhängigkeit der Form heisst trivial genau dann wenn

Beispiele


Definition: Voll funktional abhängig

ist voll funktional abhängig von (Notation: ) genau dann wenn

  • kann nicht mehr verkleinert werden


Definition: Mehrwertige funktionale Abhängigkeit (MVD)

gilt genau dann wenn für Tupel t1, t2, t3, t4


Definition: Mehrwertige funktionale Abhängigkeit (MVD)

gilt genau dann wenn )


Eigenschaften


Definition: Triviale mehrwertige funktionale Abhängigkeit

Eine mehrwertige funktionale Abhängigkeit der Form heisst trivial genau dann wenn oder

Schlüssel

Definition: Super-Schlüssel

ist ein Super-Schlüssel, falls funktional abhängig von , also

Beispiel

  • Ein trivialer Super-Schlüssel einer Relation R ist die Menge aller Attribute von R


Eigenschaften

  • Ein Super-Schlüssel hat als Teilmenge mindestens einen Kandidaten-Schlüssel


Definition: Kandidaten-Schlüssel / Schlüsselkandidat

ist ein Kandidaten-Schlüssel, falls voll funktional abhängig von , also

Attribute

Definition: Schlüsselattribut, Nicht-Schlüsselattribut

Ein Schlüsselattribut ist ein Attribut, das Teil mindestens eines Schlüsselkandidaten ist. Alle anderen Attribute sind Nicht-Schlüsselattribute

Armstrong-Axiome

Die Axiome Reflexifität, Verstärkung und Transitivität sind zusammen vollständig. Alle weiteren sind lediglich zur Erleichterung von Herleitungen aufgeführt

Reflexifität

Falls dann


Verstärkung

Falls dann auch


Transitivität

Falls und dann auch


Vereinigungsregel

Falls und dann auch


Dekompositionsregel

Falls dann auch und


Pseudotransitivitätsregel

Falls und dann auch

Normalformen

1. Normalform (1 NF)

Definition: 1. Normalform

Eine Relation ist genau dann in der ersten Normalform, wenn sie nur atomare Domänen hat


Eigenschaften

  • Aufgrund der Definition von SQL ist jede Tabelle automatisch in der ersten Normalform


2. Normalform (2 NF)

Definition: 2. Normalform

Eine Relation ist in zweiter Normalform, falls jedes Nichtschlüssel-Attribut voll funktional abhängig ist von jedem Schlüsselkandidaten der Relation


Eigenschaften

  •  ?


3. Normalform (3 NF)

Definition: 3. Normalform

Ein Relationsschema ist in dritter Normalform, wenn für jede für geltende funktionale Abhängigkeit der Form mit mindestens eine von drei Bedingungen gilt:

  • (triviale funktionale Abhängigkeit)
  • B ist prim (B ist in einem Kandidatenschlüssel von enthalten)
  • ist Superschlüssel von


Bemerkung

  • Funktionale Abhängigkeiten der Form sind gemäss Armstrong-Axiome äquivalent zur Menge der funktionalen Abhängigkeiten und sind deshalb auch zu betrachten!


Eigenschaften

  • Eine Relation in der 3. Normalform ist auch in der 2. Normalform
  • Eine Relation die nicht in 3. Normalform ist kann mit dem Synthesealgorithmus in eine Zerlegung in 3. Normalform gebracht werden

Boyce-Codd Normalform (BCNF)

Definition: Boyce-Codd Normalform

Ein Relationsschema ist in Boyce-Codd Normalform, wenn für jede für geltende funktionale Abhängigkeit der Form mit mindestens eine der zwei Bedingungen gilt:

  • (triviale funktionale Abhängigkeit)
  • ist Superschlüssel von


Eigenschaften

  • Eine Relation in BCNF ist auch in der 3. Normalform
  • Es kann jede Relation verlustlos in BCNF-Normalform gebracht werden
  • Es kann nicht jede Relation abhängigkeitserhaltend in BCNF-Normalform zu bringen
  • Eine Relation die nicht in BCNF ist kann mit dem Dekompositionsalgorithmus in eine Zerlegung in BCNF gebracht werden

4. Normalform (4 NF)

Definition: 4. Normalform

Ein Relationsschema ist in vierter Normalform, wenn für jede für geltende mehrwertige funktionale Abhängigkeit der Form mindestens eine der zwei Bedingungen gilt:

  • Triviale mehrwertige funktionale Abhängigkeit
    • oder
  • ist Superschlüssel von


Eigenschaften

  • Eine Relation in 4 NF ist auch in BCNF
  • Eine Relation die nicht in 4. Normalform ist kann mit dem Dekompositionsalgorithmus (wobei anstatt FD die MVD der Relation betrachtet werden) in eine Zerlegung in 4. Normalform gebracht werden

Attributhülle

Definition: Attributhülle

Die Attributhülle ist die Menge von Attributen für die gilt, unter Verwendung von gegebenen funktionalen Abhängigkeiten F


Algorithmus zur Bestimmung der Attributhülle

Bestimmung der Attributhülle wobei F eine Menge von funktionalen Abhängigkeiten ist


Algorithmus

  • Result :=
  • WHILE (Änderung an Result) DO
    • FOREACH FD IN F DO
      • IF Result THEN Result := Result

Kanonische Überdeckung

Definition: Kanonische Überdeckung

Eine Menge FC von funktionalen Abhängigkeiten ist eine kanonische Überdeckung von F (ebenfalls eine Menge von funktionalen Abhängigkeiten), wenn

  • FC+ = F+ : Beide die selben Attribut-Hüllen haben
  • In FC existieren keine funktionalen Abhängigkeiten welche überflüssige Attribute enthalten
    • : linke Seite hat keine überflüssigen Attribute
    • : rechte Seite hat keine überflüssigen Attribute
  • Jede linke Seite einer funktionalen Abhängigkeit in FC ist einzigartig.


Algorithmus zur Berechnung der kanonischen Überdeckung

Algorithmus zur Berechnung der kanonischen Überdeckung Fc von F

  • Linksreduktion: Überprüfe in jeder funktionalen Abhängigkeit ob überflüssig ist
    • Wenn , dann ist A überflüssig. Ersetzte durch
  • Rechtsreduktion: Überprüfe in jeder funktionalen Abhängigkeit ob überflüssig ist
    • Wenn , dann ist B überflüssig. Ersetzte durch
  • Entferne alle für beliebige
  • Vereinige alle zu


Intuitv

  • Linksreduktion: ?
  • Rechtsreduktion: Entfernt funktionale Abhängigkeiten, welche über die Transitivitätsregel hergeleitet werden können


Eigenschaften

  • Die Menge FC ist nicht eindeutig

Dekomposition von Relationen

(= Zerlegung von Relationen)

Korrektheitskriterien für eine Zerlegung:

  • Verlustlosigkeit: Die ursprüngliche Relationsausprägung muss aus den durch die Zerlegung entstandenen Schemas rekonstruierbar sein (z.B durch Join)
    • Notwendige Bedingungen:
      • R = R1 R2
    • Hinreichende Bedingung:
      • Es gilt die funktionale Abhängigkeit oder
  • Abhängigkeitserhaltung: Jede funktionalen Abhängigkeiten im alten Schema muss in einem Schema der Zerlegung gelten


Beispiel Abhängigkeitserhaltung

  • Für das Schema gelte die funktionale Abhängigkeit
  • Abhängigkeitserhaltende Zerlegung: , : gilt in und gilt in
  • Nicht abhängigkeitserhaltend: , : gilt in . gilt jedoch weder in noch in . Folglich wurde die funktionale Abhängigkeit nicht erhalten.


Synthesealgorithmus

Für ein gegebenes Relationsschema mit funktionalen Abhängigkeiten F erzeugt der Synthesealgorithmus eine Zerlegung wobei alle in 3. Normalform sind


Algorithmus

  1. Berechne die kanonische Überdeckung FC zu F
  2. Für jede funktionale Abhängigkeit der Form
    • Kreiere ein Relationsschema
    • Ordne die funktionalen Abhängigkeiten zu
  3. Falls kein erzeugtes Schemata einen Kandidatenschlüssel von enthält
    • Wähle einen Kandidatenschlüssel aus und definiere das Schema
  4. Eliminiere alle Schemata , welche in einem anderen Schemata enthalten sind


ToDo:
Frage betreffend Eindeutigkeit verifizieren
Alle momentan zu editierenden Einträge werden hier gesammelt.

Eigenschaften

  • Zerlegung ist nicht eindeutig (Da kanonische Überdeckung nicht eindeutig) (? Stimmt das?)
  • Zerlegung ist
    • verlustlos
    • abhängigkeitserhaltend
    • sind in dritter Normalform

Dekompositionsalgorithmus

Für ein gegebenes Relationsschema mit funktionalen Abhängigkeiten F erzeugt der Dekompositionsalgorithmus eine Zerlegung wobei alle in BCNF sind


Algorithmus

  1. Initialisierung: Z = {}
  2. WHILE welches nicht in BCNF
    1. Finde eine funktionale Abhängigkeit der Form in für welche gilt:
      • Nicht trivial:
      • kein Superschlüssel:
    2. Falls es mehrere gibt, wähle diejenige für welche alle von abhängigen Attribute B enthält (So terminiert der Algorithmus schneller)
    3. Zerlege in
    4. Ersezte in Z durch und

Transaktionsverwaltung

Definitionen

Definition: Transaktion

Eine Transaktion ist eine Partialordnung von Lese- und Schreiboperationen die mit einem "begin of transaction" beginnen und entweder mit einem abort oder commit enden. Lese- und Schreiboperationen sowie mehrfache Schreiboperationen auf dem selben Objekt sind geordnet


Definition: Historie

Eine Historie ist eine Folge von Lese- und Schreiboperationen auf Objekten, commit's und abort's von verschiedenen Transaktionen


Definition: Äquivalente Historien

Zwei Historien sind äquivalent, wenn

  • Leseoperationen von nicht abgebrochenen Transaktionen denselben Wert sehen
  • Am Ende der Ausführung beider Historien der Zustand der Datenbasis identisch ist


Definition: Serielle Historie

Eine serielle Historie ist eine Historie welche sich dadurch auszeichnet, dass jeweils für zwei Transaktionen Ti und Tj alle Operationen von Ti vor allen Operationen von Tj in der Historie auftreten oder umgekehrt


Definition: Serialisierbar

Eine Historie ist serialisierbar, wenn sie äquivalent zu einer seriellen Historie ist

Eigenschaften von Transaktionen

ToDo:
Konzepte genauer/besser beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.
  • Atomarität (engl atomicity)
    • Führe ganze Transaktion durch oder nichts
  • Konsistenz (engl consistency)
    • Überprüfe Integritätsbedingungen erst am Ende einer Transaktion
  • Isolation
    • Jede Transaktion glaubt die DB für sich alleine zu haben
  • Dauerhaftigkeit (engl durability)
    • Änderungen dürfen nie verloren gehen


Operationen einer Transaktion

  • ri(A) Lesen des Datenobjekts A durch Transaktion i
  • wi(A) Schreiben des Datenobjekts A durch Transaktion i
  • ai Abort von Transaktion i
    • Ein Abort beinhaltet implizit das Schreiben aller vorher geschriebenen Datenobjekten
  • ci Commit von Transaktion i


Konfliktoperationen

Die Reihenfolge zweier Konfliktoperationen darf in einer Historie NICHT geändert werden.

Konfliktoperationen sind

  • ri(A), wj(A)
  • wi(A), rj(A)
  • wi(A), wj(A)
  • ri(A), aj(A) NUR Konfliktoperation falls Tj zuvor auf Objekt A geschrieben hat (Abort beinhaltet implizit das Schreiben aller vorher geschriebenen Datenobjekten)
  • wi(A), aj(A) NUR Konfliktoperation falls Tj zuvor auf Objekt A geschrieben hat (Abort beinhaltet implizit das Schreiben aller vorher geschriebenen Datenobjekten)

Serialisierung

  • Der Serialisierbarkeitsgraph ist ein Graph dessen Knoten Transaktionen sind und dessen gerichtete Kanten die Reihenfolge der Ausführung der Transaktion definierern.
  • Die Reihenfolg der Transaktionen wird durch die Reihenfolge der Konfliktoperationen in der Historie bestimmt


Satz: Serialisierbarkeitstheorem

Eine Historie H ist genau dann serialisierbar, wenn der zugehörige Serialisierbarkeitsgraph SG(H) azyklisch ist

Links