Grundlagen von Datenbanken - NoSQLMarknosqlmark.informatik.uni-hamburg.de/gdb2013/aufgaben/GDB_Uebung… · Grundlagen von Datenbanken RelationaleAlgebraundalgebraischeOptimierung

Grundlagen von DatenbankenRelationale Algebra und algebraische Optimierung

Relationale Algebra Algebraische Optimierung

Relationale Algebra

ÜberblickSelektion: σProjektion: πMengenoperationen: ∪, ∩, −, ., ÷Kartesisches Produkt: ×Verbund (Join): ./Umbenennung: ρ

Übungen zu GDB

2


Relationenoperationen: Selektion

DefinitionAuswahl von Zeilen einer Relation über ein Prädikat:σP(R) := {t ∈ R | P(t)}

BeispielσWohnort=“Hamburg“∧Vorname=“Dieter“(Studenten)= ?

{(51896, Dieter, Müller, Hamburg)}

StudentenMatrikel Vorname Nachname Wohnort28749 Achmed Barakat Hamburg81674 Sarah Feldbusch Lübeck51896 Dieter Müller Hamburg

Übungen zu GDB

3


Relationenoperationen: Selektion

DefinitionAuswahl von Zeilen einer Relation über ein Prädikat:σP(R) := {t ∈ R | P(t)}

BeispielσWohnort=“Hamburg“∧Vorname=“Dieter“(Studenten)= {(51896, Dieter, Müller, Hamburg)}


Übungen zu GDB

3


Relationenoperationen: Projektion

DefinitionAuswahl von Spalten einer Relation:πA1,...,Ak (R) := {p | ∃t ∈ R : p = (t[A1], . . . , t[Ak ])}

BeispielπWohnort(Studenten)= ?

{(Hamburg), (Lübeck)}


Übungen zu GDB

4


Relationenoperationen: Projektion

DefinitionAuswahl von Spalten einer Relation:πA1,...,Ak (R) := {p | ∃t ∈ R : p = (t[A1], . . . , t[Ak ])}

BeispielπWohnort(Studenten)= {(Hamburg), (Lübeck)}

StudentenMatrikel Vorname Nachname Wohnort28749 Achmed Barakat Hamburg81674 Sarah Feldbusch Lübeck51896 Dieter Müller ///////////Hamburg

Übungen zu GDB

4


Relationenoperationen: Mengenoperationen

DefinitionenR ∪ S := {t | t ∈ R ∨ t ∈ S} (Vereinigung)R − S := {t | t ∈ R ∧ t 6∈ S} (Differenz)R ∩ S := {t | t ∈ R ∧ t ∈ S} (Durchschnitt)R . S := (R ∪ S)− (R ∩ S) (Symmetrische Differenz)

Voraussetzung: Vereinigungsverträglichkeit der Relationen!

BeispielStud1 ∪ Stud2

= {(2849, Achmed), (8174, Sarah), (5196, Dieter)}

Matrikel Vorname2849 Achmed8174 Sarah

Stud1 Stud2Matrikel Vorname

8174 Sarah5196 Dieter

Übungen zu GDB

5


Relationenoperationen: Mengenoperationen

DefinitionenR ∪ S := {t | t ∈ R ∨ t ∈ S} (Vereinigung)R − S := {t | t ∈ R ∧ t 6∈ S} (Differenz)R ∩ S := {t | t ∈ R ∧ t ∈ S} (Durchschnitt)R . S := (R ∪ S)− (R ∩ S) (Symmetrische Differenz)

Voraussetzung: Vereinigungsverträglichkeit der Relationen!

BeispielStud1 ∪ Stud2 = {(2849, Achmed), (8174, Sarah), (5196, Dieter)}

Matrikel Vorname2849 Achmed8174 Sarah

Stud1 Stud2Matrikel Vorname

8174 Sarah5196 Dieter

Übungen zu GDB

5


Relationenoperationen: Erweitertes Kartesisches Produkt

DefinitionR × S := {k | ∃r ∈ R, s ∈ S : k = r |s}wobei r |s := (r1, . . . , rn, s1, . . . , sm)

StudentenMatrikel Vorname Fach

2849 Achmed 188174 Sarah 2

FächerFID Name18 Informatik5 Physik

Studenten × FächerMatrikel Vorname Fach FID Name

2849 Achmed 18 18 Informatik2849 Achmed 18 5 Physik8174 Sarah 2 18 Informatik8174 Sarah 2 5 Physik

Übungen zu GDB

6


Relationenoperationen: Verbund (Join)

DefinitionR ./

AΘBS = σAΘB(R × S)

wobei Θ ∈ {=, 6=, <,>,≥,≤}

StudentenMatrikel Vorname Fach

2849 Achmed 188174 Sarah 2

FächerFID Name18 Informatik5 Physik

Studenten ./Fach=FID

FächerMatrikel Vorname Fach FID Name

2849 Achmed 18 18 Informatik2849 Achmed 18 5 Physik8174 Sarah 2 18 Informatik8174 Sarah 2 5 Physik

Übungen zu GDB

7


Relationenoperationen: Umbenennung

DefinitionUmbenennung der Spalte einer Relation:ρB←Ai (R(A1, . . . ,Ak)) := R(A1, . . . ,Ai−1,B,Ai+1, . . . ,Ak)

BeispielρName←Vorname(Studenten)


Übungen zu GDB

8





StudentenMatrikel //////////Vorname Nachname Wohnort28749 Achmed Barakat Hamburg81674 Sarah Feldbusch Lübeck51896 Dieter Müller Hamburg

Übungen zu GDB

8





StudentenMatrikel Name Nachname Wohnort28749 Achmed Barakat Hamburg81674 Sarah Feldbusch Lübeck51896 Dieter Müller Hamburg

Übungen zu GDB

9


Algebraische Optimierung

ZielEffiziente Ausführung eines algebraischen Ausdrucks(Minimierung der Zwischenergebnisse bei gleichem Endergebnis)

Heuristiken zur OptimierungI. Führe Selektion so früh wie möglich ausII. Führe Projektion (ohne Duplikateliminierung) so früh wie möglich ausIII. (Verknüpfe Folgen von unären Operatoren wie Selektion und Projektion)IV. Fasse einfache Selektionen auf einer Relation zusammenV. Verknüpfe bestimmte Selektionen mit einem vorausgehenden Kartesischen

Produkt zu einem VerbundVI. (Berechne gemeinsame Teilbäume nur einmal)VII. Bestimme die Verbundreihenfolge so, dass die Anzahl und Größe der

Zwischenobjekte minimiert wirdVIII. Verknüpfe bei Mengenoperationen immer zuerst die kleinsten Relationen

Übungen zu GDB

10


Algebraische Optimierung

ZielEffiziente Ausführung eines algebraischen Ausdrucks(Minimierung der Zwischenergebnisse bei gleichem Endergebnis)

Heuristiken zur OptimierungI. Führe Selektion so früh wie möglich ausII. Führe Projektion (ohne Duplikateliminierung) so früh wie möglich ausIII. (Verknüpfe Folgen von unären Operatoren wie Selektion und Projektion)IV. Fasse einfache Selektionen auf einer Relation zusammenV. Verknüpfe bestimmte Selektionen mit einem vorausgehenden Kartesischen

Produkt zu einem VerbundVI. (Berechne gemeinsame Teilbäume nur einmal)VII. Bestimme die Verbundreihenfolge so, dass die Anzahl und Größe der

Zwischenobjekte minimiert wirdVIII. Verknüpfe bei Mengenoperationen immer zuerst die kleinsten RelationenÜbungen zu GDB

10


Optimierungsbeispiel (Heuristik I.)

σNachname=“Müller“(Studenten ./Fach=FID

Fächer)

Studenten Fächer

./Fach=FID

σNachname=“Müller“

Studenten

σNachname=“Müller“

Fächer

./Fach=FID

Übungen zu GDB

11

Documents

Grundlagen von Datenbanken - NoSQLMarknosqlmark.informatik.uni-hamburg.de/gdb2013/aufgaben/GDB_Uebung… · Grundlagen von Datenbanken RelationaleAlgebraundalgebraischeOptimierung