Title: IN0008_GDB / GDB: Kapitel 8: Anfragebearbeitung
On every note of this deck, unless a note says otherwise:
Title: IN0008_GDB::GDB: Kapitel 8: Anfragebearbeitung
Logo: tum_logo.png

Front: Nenne vier grundlegende relationale Operatoren die kommutativ sind.
Back: - Join
- Vereinigung
- Schnitt
- Kreuzprodukt

Front: Ja oder Nein? [$]R_1 \Join R_2 = R_2 \Join R_1[/$]
Back: Ja. Die Join Operation ist kommutativ.

Front: Ja oder Nein? [$]R_1 \times R_2 = R_2 \times R_1[/$]
Back: Ja. Das Kreuzprodukt ist kommutativ.

Front: Nenne vier grundlegende relationale Operatioren die assoziativ sind.
Back: - Kreuzprodukt
- Vereinigung
- Schnitt
- Join
Assoziativität
[$$]R_1 \times (R_2 \times R_3) = (R_1 \times R_2) \times R_3[/$$]
[$$]R_1 \cap (R_2 \cap R_3) = (R_1 \cap R_2) \cap R_3[/$$]
[$$]R_1 \cup (R_2 \cup R_3) = (R_1 \cup R_2) \cup R_3[/$$]
[$$]R_1 \Join (R_2 \Join R_3) = (R_1 \Join R_2) \Join R_3[/$$]

Front: Welche Äquivalenz gilt bei einer Selektion mit Konjunktionen in der Bedingung?
Back: Sie können in mehrere Selektionen aufgebrochen (und auch wieder zusammengefügt) werden.
[$$]\sigma_{p_1 \land p_2 \land \dots \land p_n}(R) = \sigma_{p_1}(\sigma_{p_2}(\dots \sigma_{p_n}(R) \dots))[/$$]

Front: Wann kann eine Selektion an einer Projektion "vorbeigeschoben" werden?
Back: Falls die Projektion keine Attribute aus der Selektionsbedingung entfernt. Es gilt also:
[$$]\Pi_l(\sigma_p(R)) = \sigma_p(\Pi_l(R)), attr(p) \subseteq l[/$$]
Wobei [$]attr(p)[/$] die Menge aller in [$]p[/$] enthaltenden Attribute ist.

Front: Wie können geschachtelte Projektionen optimiert werden?
Back: Durch Eliminierung:
[$$]\Pi_{l_1}(\Pi_{l_2}(\dots (\Pi_{l_n}) \dots)) = \Pi_{l_1}(R)[/$$]

Front: Sind Selektionen untereinander vertauschbar?
Back: Ja. Es gilt:
[$$]\sigma_p(\sigma_q(R)) = \sigma_q(\sigma_p(R))[/$$]

Front: Wann kann eine Selektion an einer Joinoperation (oder einem Kreuzprodukt) vorbeigeschoben werden?
Back: Falls sie nur Attribute eines der beiden Join-Argumente verwendet. Enthält die Bedingung [$]p[/$] beispielsweise nur Attribute aus [$]\mathcal{R}_1[/$], dann gilt:
[$$]\sigma_p(R_1 \Join R_2) = \sigma_p(R_1) \Join R_2[/$$]
[$$]\sigma_p(R_1 \times R_2) = \sigma_p(R_1) \times R_2[/$$]

Front: Was muss beachtet werden, wenn Projektionen verschoben werden?
Back: Joinattribute (Attribute in Joinpredikat) müssen bis zum Join erhalten bleiben.
[$$]\Pi_l(R_1 \Join_p R_2) = \Pi_l(\Pi_{l_1}(R_1) \Join_p \Pi_{l_2}(R_2))[/$$]
Wobei (Bei Attributmenge [$]l_2[/$] Analog):
[$$]l_1 = {A \vert A \in \mathcal{R}_1 \cap l} \cup {A \vert A \in \mathcal{R}_1 \cap attr(p)}[/$$]

Front: Können Selektionen mit Mengenoperationen wie Vereinigung, Schnitt und Differenz vertauscht werden?
Back: Ja. Es gilt (für Schnitt und Differenz analog):
[$$]\sigma_p(R \cup S) = \sigma_p(R) \cup \sigma_p(S)[/$$]

Front: Kann die Projektion mit Durchschnitt und Differenz getauscht werden?
Back: Nein.

Front: Kann der Projektionsoperator mit der Vereinigung vertauscht werden?
Back: Sei [$]sch(R_1) == sch(R_2)[/$], dann gilt:
[$$]\Pi_l(R_1 \cup R_2) = \Pi_l(R_1) \cup \Pi_l(R_2)[/$$]

Front: Bedingung können mit Hilfe von DeMorgans Gesetz umgeformt werden
Back: Ein Beispiel:
[$$]\neg(p_1 \lor p_2) = \neg p_1 \land \neg p_2[/$$]

Front: Wann können eine Selektion und ein Kreuzprodukt zu einem Join zusammengefasst werden?
Back: Wenn die Selektionsbedingung eine Joinbedingung ist, sie also Attribute einer Argumentrelation mit Attributen der anderen vergleicht.
Beispiel Equijoin:
[$$]\sigma_{R_1.A_1 = R_2.A_2}(R_1 \times R_2) = R_1 \Join_{R_1.A_1 = R_2.A_2} R_2[/$$]

Front: Wie funktioniert der Nested Loop join?
Back: - Trivialer brute force anstatz
- Zwei schleifen vergleichen alle Paare aus Elementen
- O(n²)

Front: Wie funktioniert der Index Join?
Back: - Unter umständen kann die Indexstruktur ausgenutzt werden
- z.B. bei Equijoins
- Index kann in O(log(n)) nachgeschlagen werden

Front: Wie funktioniert der Merge Join? (Bei einem Equijoin)
Back: - Ausnutzen von Sortierung: Beide Relationen müssen sortiert sein
- Zwei Zeiger R, L auf rechte und Linke relation
- Wenn L > R, bewege R nach unten
- Wenn L = R -> Tupel gefunden, bewege R nach unten
- Wenn L < R -> Bewege L nach unten, setzte R auf den größten wert kleiner gleich L

Front: Wie funktioniert der Hash Join? (Bei einem Equijoin)
Back: - Der Build input wird mit hashfunktionen Partitioniert und auf Hashtabellen verteilt
- Der Probe input wird mit hashfunktionen partitioniert, und jeweils eine einzelne Seite mit der korrespondierenden Hashtabelle des build inputs gejoint

Front: Wenn m Hauptspeicherseiten zur Verfügung stehen, wie werden diese Bei einem Hashjoin aufgeteilt?
Back: - m - 1 Seiten für das Partitionieren des build inputs
- eine Seite zum Vergleichen mit elementen aus dem Probe inputs

Front: Was ist der "Build input" und "Probe input" bei einem Hashjoin?
Back: - Build input: Die kleinere Tabelle, welche den großteil des verfügbaren Hauptspeichers bekommt, Partitioniert und in hashtabellen verteilt wird.
- Probe input: Die größere Tabelle, welche ebenfalls partitioniert wird, und mit den Hashtabellen des build inputs verglichen wird

Front: Was ist das Problem bei der Sortierung / Bearbeitung von großen Datenmengen?
Back: Die Daten passen oft nicht mehr in den Hauptspeicher

Front: Was ist ein "Run"/"Lauf" bei Mergesort?
Back: Ein Teil der Daten, welcher sortiert wird und dann mit anderen Teilen "gemerged" wird

Front: was heißt "jedwelcher"
Back: Alle, welche ...