K4 Grundlagen des Relationenmodells Flashcards

Question 1

Q

GDB K4 Grundlagen des Relationenmodells

Welche Datenstruktur hat das Relationenmodell?

Answer

A

Relation (Tabelle)

einzige Datenstruktur
alle Informationen ausschließlich durch (atomare) Werte dargestellt
zeitinvariante Typinformation: Relationenschema

Question 2

Q

GDB K4 Grundlagen des Relationenmodells

Welches sind die Operatoren auf Relationen beim Relationenmodell?

Answer

A

Vereinigung, Differenz (Schemata müssen kompatibel sein)
Kartesisches Produkt
Projektion
Selektion
zusätzlich: Grundoperationen (Einfügen, Löschen, Ändern)

Question 3

Q

GDB K4 Grundlagen des Relationenmodells

Was gilt für Beziehungen beim Relationenmodell?

Answer

A

werden durch Werte dargestellt
◼ Primär-/Fremdschlüssel
◼ Gewährleistung von referentieller Integrität
◼ können in SQL automatisch gewartet werden (referentielle Aktionen)
Fremdschlüssel verbindet zwei Relationen ⇒ Beziehung binär
Komplexere Beziehungen durch Kombination mehrerer Fremdschlüssel

Question 4

Q

GDB K4 Grundlagen des Relationenmodells

Was ist die Entwurfstheorie beim Relationenmodell?

Answer

A

Normalformenlehre (wünschenswerte und zweckmäßige Relationen)
Synthese von Relationen

Question 5

Q

GDB K4 Grundlagen des Relationenmodells

Vergleich ERM und RM

Question 6

Q

GDB K4 Grundlagen des Relationenmodells

mathematische Notation und Notation für Datenbank-Relationen

Answer

A

Relation kann als Tabelle dargestellt werden

Relation ist eine Menge

Garantie der Eindeutigkeit der Zeilen/Tupel durch Primärschlüssel (und ggf. mehrere Schlüsselkandidaten)

Question 7

Q

GDB K4 Grundlagen des Relationenmodells

Gundregeln des Relationenmodells

Answer

A

Jede Zeile (Tupel) ist eindeutig und beschreibt ein Objekt der Miniwelt
Die Ordnung der Zeilen ist ohne Bedeutung; durch ihre Reihenfolge wird keine für den Benutzer relevante Information ausgedrückt
Die Ordnung der Spalten ist ohne Bedeutung, da sie einen eindeutigen Namen (Attributnamen) tragen
Jeder Datenwert innerhalb einer Relation ist ein atomares Datenelement
Alle für den Benutzer bedeutungsvollen Informationen sind ausschließlich durch Datenwerte ausgedrückt
Es existieren ein Primärschlüssel und ggf. weitere Schlüsselkandidaten

Question 8

Q

GDB K4 Grundlagen des Relationenmodells

Wie wird im Relationenmodell „relationenübergreifende“ Information dargestellt?

Answer

A

Fremdschlüssel, Definition:

Ein Fremdschlüssel bzgl. einer Relation R1 ist ein Attribut oder eine Attributkombination FS einer Relation R2, für das/die zu jedem Zeitpunkt gilt: zu jedem Wert (ungleich Null) von FS muss ein gleicher Wert des Primärschlüssels PS oder eines Schlüsselkandidaten SK in irgendeinem Tupel von Relation R1 vorhanden sein.

Bemerkungen zu Fremdschlüssel:

Fremdschlüssel und zugehöriger Primärschlüssel (Schlüsselkandidat) tragen wichtige inter-relationale (manchmal auch intra-relationale) Informationen. Sie sind auf dem gleichen Wertebereich definiert (vergleichbar und vereinigungsverträglich). Sie gestatten die Verknüpfung von Relationen mit Hilfe von Relationenoperationen.
Fremdschlüssel können Nullwerte aufweisen, wenn sie nicht Teil eines Primärschlüssels sind und wenn nicht explizit NOT NULL spezifiziert ist.
Schlüsselkandidaten können Nullwerte aufweisen, wenn nicht explizit NOT NULL spezifiziert ist.
Ein Fremdschlüssel ist zusammengesetzt, wenn der zugehörige Primärschlüssel (Schlüsselkandidat) zusammengesetzt ist.
Eine Relation kann mehrere Fremdschlüssel besitzen, welche die gleiche oder verschiedene Relationen referenzieren.
Referenzierte und referenzierende Relation sind nicht notwendigerweise verschieden.
Zyklen sind möglich.

Question 9

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Kriterien

Answer

A

Informationserhaltung, d.h. möglichst genaue Übereinstimmung der Semantik (Übernahme aller spezifizierten Eigenschaften)
Minimierung der Redundanz
Minimierung des Verknüpfungsaufwandes
Natürlichkeit der Abbildung
Keine Vermischung von Objekten
Verständlichkeit

Question 10

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: 2 Entity-Typen mit (1:n)-Verknüpfung

Answer

A

Regel: (1:n)-Beziehungen lassen sich ohne eigene Relation darstellen. Hierzu wird in der abhängigen Relation (mit Beziehungskardinalität 1) der Primärschlüssel der referenzierten Relation als Fremdschlüssel verwendet.

Question 11

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: 1 Entity-Typ mit (1:1)-Verknüpfung

Answer

A

Regel: Der Primärschlüssel des zugehörigen Entity-Typs wird in zwei Rollen verwendet. Deshalb ist eine Umbenennung erforderlich.

Question 12

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: 1 Entity-Typ mit (n:m)-Verknüpfung

Answer

A

Regel: Ein (n:m)-Relationship-Typ muss durch eine eigene Relation dargestellt werden. Der Primärschlüssel des zugehörigen Entity-Typs wird in zwei Rollen verwendet. Deshalb ist eine Umbenennung erforderlich.

Question 13

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: mehrere (>2) Entity-Typen mit (n:m)-Verknüpfung

Question 14

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Mehrwertige (zusammengesetzte) Attribute

Question 15

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung

Answer

A

RM sieht keine Unterstützung der Abstraktionskonzepte vor
keine Maßnahmen zur Vererbung (von Struktur, Integritätsbedingungen, Operationen)
„Simulation“ der Generalisierung eingeschränkt möglich

Question 16

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung: Hausklassenmodell

Answer

A

Jede Instanz ist genau einmal und vollständig in ihrer Hausklasse gespeichert
Es wird eine horizontale Partitionierung der DB-Instanzen erreicht

Eigenschaften:

niedrige Speicherungskosten und keine Änderungsanomalien
Eindeutigkeit von IDs muss über Relationen hinweg gewährleistet werden
Retrieval kann rekursives Suchen in Unterklassen erfordern
explizite Rekonstruktion durch Relationenoperationen (π, ∪)

Projektion: unärer Operator der Relationenalgebra zur Auswahl von Spalten/Attributen.

Question 17

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung: Partitionierungs-Modell

Answer

A

Jede Instanz wird entsprechend der Klassenattribute in der Is-a-Hierarchie zerlegt und in Teilen in den zugehörigen Klassen gespeichert
Es wird nur das ID-Attribut dupliziert (evtl. Verwendung als Fremdschlüssel)
Es wird eine vertikale Partitionierung in der DB erzielt

Eigenschaften

geringfügig erhöhte Speicherungskosten, aber hohe Aufsuch- und Aktualisierungskosten
Integritätsbedingungen: TECHNIKER.ID ⊆ ANGESTELLTE.ID, usw. (Gewährleistung durch Verwendung von Fremdschlüsseln)
Instanzenzugriff erfordert implizite oder explizite Verbundoperationen (⋈)

Join/Verbund: binärer Operator der Relationenalgebra zur Verbindung der Tupeln der Argumentrelationen über gleiche Attributwerte.

Question 18

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung: Volle Redundanz

Answer

A

Eine Instanz wird wiederholt in jeder Klasse, zu der sie gehört, gespeichert
Sie besitzt dabei die Werte der Attribute, die sie geerbt hat, zusammen mit den Werten der Attribute der Klasse

Eigenschaften

sehr hoher Speicherplatzbedarf
Auftreten von Änderungsanomalien
Zur Vermeidung: Aufwendige (evtl. synchrone) Änderungen von redundant gespeicherten Daten notwendig
sehr einfaches Retrieval, da nur die Zielklasse (z. B. ANGESTELLTE) aufgesucht werden muss

Question 19

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung: Modellierung in einer einzigen Relation

Answer

A

Die Attribute aller Entity-Typen werden in einer Relation zusammengefasst
Spezielle Attribute um Typ-Zugehörigkeit zu modellieren

Eigenschaften

Sehr viele Nullwerte (⇒ großer Speicherbedarf)
Keine Redundanz
Keine intuitive Modellierung da verschiedene Entity-Typen in einer Relation
Retrieval kann Scan großer Tupelmengen erfordern inkl. Selektion (σ) auf Zugehörigkeitsattribut

Selektion: unärer Operator der Relationenalgebra zur Auswahl von Zeilen/Tupeln.

Question 20

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung mit nicht-disjunkten Untertypen

Answer

A

Hausklassenmodell nicht mehr eindeutig definiert
Variante 1: Eine Relation pro Entity-Typ.
Eine Instanz muss in mehreren Relationen gespeichert werden
Variante 2: Eindeutige Relationen-Zugehörigkeit für jede Instanz.
Eine Relation pro Kombination von nicht-disjunkten Untertypen

Question 21

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Generalisierung Überblick

Answer

A

Generalisierung mit vererbten n:m Relationship-Typen:
Modellierung durch Fremdschlüssel
Ein Fremdschlüssel zeigt auf eine konkrete Relation

Hausklassenmodell:

Eine Relation für den Relationship-Typ pro Unterklasse (der Fremdschlüssel zeigt jeweils auf die zugehörige Unterklasse)

Partitionierungs-Modell oder volle Redundanz:

Insgesamt eine Relation für den Relationship-Typen (der Fremdschlüsse zeigt auf die „oberste“ Unterklasse)

Modellierung in einer einzigen Relation:

Insgesamt eine Relation für den Relationship-Typen
Integritätsbedingungen, die gewährleisten, dass nur Tupel mit passenden Werten in den Zugehörigkeitsattributen im Fremdschlüssel referenziert werden können

Question 22

Q

GDB K4 Grundlagen des Relationenmodells

Abbildung ERM-RM: Zusammenfassung der Abbildungskonzepte

Answer

A

Datenstruktur: Relation (Tabelle)

einzige Datenstruktur (neben atomaren Werten)
alle Informationen ausschließlich durch Werte dargestellt
Integritätsbedingungen auf/zwischen Relationen

Abbildung von Beziehungen durch PS/SK – FS

Eine (n:1)-Verknüpfung wird in der Regel auf eine eigene Relation abgebildet
(n:m)-Verknüpfungen sind durch eine eigene Relation darzustellen
Verknüpfungen mit mehr als zwei Rollen müssen im Prinzip durch mehrere (n:1)Verknüpfungen dargestellt werden

Abstraktionskonzepte

keine direkte Bereitstellung der Abstraktionskonzepte, z.B. Generalisierung
Verschiedene Modelle zur Simulation einer Generalisierung

Question 23

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Algebra und Operationen

Answer

A

Algebra: nicht leere Menge von Objekten + Familie von Operationen

Operationen (unär, binär)

Klassische Mengenoperationen:
◼ Vereinigung, Differenz, kartesisches Produkt
◼ ableitbar: Durchschnitt
Relationenoperationen:
◼ Projektion, Restriktion (Selektion), Umbenennung
◼ ableitbar: Verbund (Join), Division

Auswahlvermögen entspricht Relationenkalkül („relational vollständig“)

Question 24

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Selektion

Answer

A

auch Restriktion σ_P

Question 25

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Projektion

Question 26

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Umbenennung

Question 27

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Klassische Mengenoperationen

Question 28

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Erweitertes Kartesisches Produkt

Question 29

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Verbund

Question 30

Q

GDB K4 Grundlagen des Relationenmodells

Θ

Answer

A

Gleichverbund ( = „=“) in Gleichverbund zwischen R und S heißt verlustfrei , wenn alle Tupel von R und S am Verbund teilnehmen (sonst verlustbehaftet ). Die inverse Operation Projektion erzeugt dann wieder R und S (lossless join).

Question 31

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: Definition Natürlicher Verbund

Answer

A

gegeben: R(A₁, A₂, . . . , A_r_-_j+1, . . . , A_r), S(B₁, B₂, . . ., B_j, . . . , B_s)
o.B.d.A. (sonst. Umsortierung): B₁ = A_r_-_j+1, B₂ = A_r_-_j+2, …, B_j = A_r
Natürlicher Verbund zwischen R und S:

Question 32

Q

Question 33

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra - Operatoren: ACHTUNG: Connection Trap!

Question 34

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra: Beispiel - ER-Diagramm

Aufgabe: relationales DB-Schema

Question 35

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra – Beispiel

Aufgabe:

Finde alle Schauspieler (NAME), die die Figur „Faust“ gespielt haben.
Finde alle Schauspieler (NAME), die im Drama „Faust“ mitgespielt haben.
Finde alle Schauspieler (NAME), die in Dramen von Schiller mitgespielt haben.

Question 36

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra – Beispiel

Aufgabe:

Finde alle Schauspieler (NAME, W-ORT), die bei in Weimar uraufgeführten Dramen an ihrem Wohnort als ’Held’ mitgespielt haben.

Question 37

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra – Beispiel

Aufgabe:

Liste alle Dramen mit ihren Autoren (TITEL, AUTOR, G-JAHR) auf, die nach 1800 uraufgeführt wurden.
Finde alle Schauspieler (NAME, W-ORT), die in Dramen von Schiller, die von in Weimar geborenen Dichtern kritisiert wurden, mitgespielt haben.

Question 38

Q

GDB K4 Grundlagen des Relationenmodells

Relationenalgebra – Beispiel

Aufgabe:

Finde die Schauspieler, die nie gespielt haben.
Finde die Schauspieler, die nur Faust oder Wallenstein gespielt haben.

Question 39

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung

Answer

A

Relationenalgebraische Formulierungen spezifizieren Ausführungsreihenfolge (prozedurale Elemente), äquivalente Umformungen möglich

Optimierungsproblem

gegeben: Ausdruck der Relationenalgebra (RA)
gesucht: äquivalenter, möglichst effizient auszuführender RA-Ausdruck
Bestimmung einer möglichst guten Ausführungsreihenfolge (Einsatz von Heuristiken)

Statistische Kenngrößen werden dem DB-Katalog entnommen

N_i = Card(R_i)
j_i = Anzahl der verschiedenen Werte eines Attributs A_i

Question 40

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Rewrite-Regeln

Question 41

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Selektivitätsfaktor (SF)

Answer

A

Annahmen

Gleichverteilung der Attributwerte eines Attributes
Stochastische Unabhängigkeit der Werte verschiedener Attribute

Selektivitätsfaktor (SF)

basiert auf statistischen Werten
beschreibt hinsichtlich eines Qualifikationsprädikats den erwarteten Anteil an Tupeln, die das Prädikat erfüllen
0 ≤ SF ≤ 1
Card (σ_p(R)) = SF(p) * Card (R)

Question 42

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: SF-Berechnung

Question 43

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: SF-Berechnung bei Ausdrücken

Answer

A

SF (p(A) ∧ p(B)) = SF (p(A)) • SF (p(B))
SF (p(A) ∨ p(B)) = SF (p(A)) + SF (p(B)) - SF (p(A)) • SF (p(B))
SF (¬p(A)) = 1 - SF (p(A))

Question 44

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Join-Selektivitätsfaktor (JSF)

Answer

A

Card (RS) = JSF * Card(R) * Card(S)
bei (N:1)-Joins (verlustfrei): Card (RS) = Max(Card(R), Card(S))
bei verlustbehafteten (N:1)-Joins die Relationen über FK-PK Beziehungen verknüpfen: Card (RS) = Card(S), wenn S den Fremdschlüssel und R den zugehörigen Primärschlüssel besitzt (Annahme: keine Nullwerte im FK)

Beispiel: Relation ABT besitzt ein Attribut LEITER welches auf den PK der Relation PERS referenziert

Anmerkung: Wenn der FK-PK Join verlustfrei ist, gilt Card(S)>Card(R) und beide Regeln liefern das selbe Ergebnis

Question 45

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Beispiel

Question 46

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Beispiel

Aufgabe: I. Führe Selektion so früh wie möglich aus!

Question 47

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Beispiel

Aufgabe: II. Führe Projektion (ohne Duplikateliminierung) so früh wie möglich aus!

Answer

A

Bem.: Der Nutzen einer frühzeitigen Projektionsausführung hängt von mehreren Faktoren ab.

Question 48

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Beispiel

Aufgabe: III. Verknüpfe Folgen von unären Operatoren wie Selektion und Projektion (wenn diese tupelweise abgewickelt werden können)!

Question 49

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Beispiel

Aufgabe: IV. Fasse einfache Selektionen auf einer Relation zusammen!

Question 50

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Heuristische Regeln

Answer

A

Führe Selektion so früh wie möglich aus!
Führe Projektion (ohne Duplikateliminierung) so früh wie möglich aus!
Verknüpfe Folgen von unären Operatoren wie Selektion und Projektion (wenn diese tupelweise abgewickelt werden können)!
Fasse einfache Selektionen auf einer Relation zusammen!
Verknüpfe bestimmte Selektionen mit einem vorausgehenden Kartesischen Produkt zu einem Verbund!
Berechne gemeinsame Teilbäume nur einmal (wenn die Zwischen speicherung der Ergebnisse nicht zu teuer ist)!
Bestimme die Verbundreihenfolge so, dass die Anzahl und Größe der Zwischenobjekte minimiert wird!
Verknüpfe bei Mengenoperationen immer zuerst die kleinsten Relationen!

Kombination von Verbundoperationen

Assoziativität und Kommutativität von Verbundoperationen (gilt auch für Vereinigung und Durchschnitt)

Allgemeines Problem bei binären Relationenoperationen

Was ist die beste Verknüpfungsreihenfolge?
Im allgemeinen Fall sind n! Reihenfolgen möglich
Die genaue Größe einer Zwischenrelation ergibt sich erst nach Ende der erzeugenden Operation
◼ Dynamische Entscheidung aufwendiger, aber genauer als Abschätzung
◼ Bei jedem Auswertungsschritt werden die momentan kleinsten (Zwischen-)Relationen ausgewählt

Question 51

Q

GDB K4 Grundlagen des Relationenmodells

Algebraische Optimierung: Zu VIII. Verknüpfe bei Mengenoperationen immer zuerst die kleinsten Relationen!

Question 52

Q

GDB K4 Grundlagen des Relationenmodells

Division

Answer

A

Ziel

Beantwortung von Fragen, bei denen eine „ganze Relation“ zur Qualifikation herangezogen wird
Simulation des Allquantors ⇒ ein Tupel aus R steht mit allen Tupeln aus S in einer bestimmten Beziehung

Definition

Sei R vom Grad r und S vom Grad s, r > s und s ≠ 0; t sei (r-s)-Tupel, u sei s-Tupel; S-Attribute ⊂ R-Attribute;
Dann gilt: R ÷ S = {t | ∀ u ∈ S: (t | u ∈ R)}

Question 53

Q

Question 54

Q

GDB K4 Grundlagen des Relationenmodells

Finde alle Schauspieler (NAME), die alle Rollen in Dramen von Goethe gespielt haben.
Finde alle Schauspieler (NAME), die alle Narrenrollen am Pfalztheater gespielt haben.