Prüfungsfragen aus Protkollen [Ausstehend] Flashcards
1
Q
Erzählen sie was für Probleme bei der Speicherung von E-Commerce Daten auftauchen können! Welche Möglichkeiten gibt es das Problem zu lösen?
A
2
Q
Wie funktioniert die Transformation von horizontal nach vertikal? Was passiert, wenn man eine Zeile hat, die nur NULL-Werte enthält?
A
da
3
Q
Hier sehen sie eine SELECT Query, die bestimmte Attribute aus der horizontalen Tabelle auswählt. Formen sie diese Query für die vertikale Datenspeicherung um!
Select A2=c und A3=a
A
Siehe Bild
Übrigens Projektion ist das Gleiche wie v2h mit entsprechenden Attributen
4
Q
Was für Probleme gibt es bei der Erzeugung von der horizontalen Sicht aus einer vertikalen Sicht?
A
**Man muss viele Leftjoins durchführen, wenn man die ganze horizontale Tabelle haben will
5
Q
(1)Beschreiben Sie bitte was ein R Baum ist! (2)Wie führt man eine NN Abfrage in dem R Baum durch? (3)Was für ein Problem gibt es in den hochdimensionalen Räumen? (4)Wie kann man das Problem lösen? (5)Wie funktioniert dann die NN Abfrage?
Es ist sind besserer Karten im Set enthalten!!
A
(1) **Ein Baum aus Minimum Bounding Rectangles eines Raumes
(2) **Priority Queue erzeugen, die die Bounding Rectangles nach dem Abstand sortieren und diese nach und nach aufmachen und Punkte dort betrachten. Die Punkte werden auch nach dem Abstand sortiert
(3) **Bei vielen Dimensionen überlappen sich über 50% der Rectangles und man muss somit viele oder sogar alle Rectangles betrachten.
Frage vom Prüfer: Warum überlappen die sich?
⇒**Bei vielen Dimensionen können die Abstände in den jeweiligen Dimensionen nie unterschiedlich sein. anscheinend statistisch unmöglich
(4) **Man partitioniert den Raum uns fasst alle Dimensionen zu einem Durchscnittsabstand zusammen un ordnet jeder Partition einen Punkt zu. Zusätzlich erstellt man eine Tabelle, wo man jeden Punkt einem Durchschnittsabstan zuordnet
(5) **I-Distance: Man legt einen Query Punkt in den Raum und erweitert iterativ seinen Radius.
⇒ Wenn der enstehende Kreis eine Partition schneidet, dann betrachtet man alle Punkte die in der Schaale des Schnitts zwischen der Partition und dem Kreis liegen. Dafür benutzt man die Tabelle, in der alle Durchschnittsabstände gespeichert sind und man somit schnell naschschauen kann, ob der Punkt in der Schaale liegt. Für alle Punkte die in der Schaale liegen, macht man dann die tatsächliche Abstandsberechnung in allen Dimensionen zu dem Querypunkt // Kommt glaub ich in der Datenbanksysteme VL dran oder so
6
Q
- Wir hatten in der Vorlesung verschiedene Möglichkeiten Daten abzufragen, Relationale Algebra, Datalog. Was ist Datalog? Abgrenzung du RA?
- Warum kann es keine Schnittmenge (Mengendifferenz) in Datalog geben?
- Was ist das Problem mit Negation?
- Ist Negation in Datalog grundsätzlich nicht erlaubt? (5) Kann man das Prüfen?
A
- **Datalog erklärt und gegen Relationale Algebra abgegrenzt (keine Schnittmenge, dafür Rekursion)
- –> 1.0 –> Logik-basierte Anfragesprache, Syntax basiert auf Prolog.
- –> 1.0 –> Datalog kann andere Informationsbedürfnisse befriedigen. Z.B. Rekursion ist möglich, was mit RA nicht geht (umständlich). Dafür unterstützt Datalog keine Mengedifferenz (Schnittmengenberechnung) .
- **Auf Grund der Monotonie-Eigenschaft bzw im Fall von
- Negation ist nicht-monoton: Eine Vergrößerung der Eingabemenge verkleinert die Ausgabemenge und das nicht in Datalog erlaubt ist, da Datalog monoton ist!
- Aus anderm Protokol mit 1.0 ⇒ Dafür würde Negation benötigt. Negation ist im allgemeinen nicht monoton, deshalb in Datalog nicht ohne weiteres erlaubt.
- ** Es kann zu Oszillation kommen –> Beispiel aus VL malen Prüfer: ist das immer so? siehe
- ** Nein, wenn negierte Prädikate vollständig berechnet sind, bevor sie negiert vorkommen geht das (5)**Ja, mit Stratifikation bzw. dem Abhängikeitsgraph.
7
Q
Was ist Oszillation, Warum taucht sie auf? Was ist ein Abhänigkeitgraph Wie kann man Ozillation beseitigen?
A
da
8
Q
Was ist Relationale Algebra? Was ist Relationale Vollständigkeit?
A
- RA= Menge von Operationen, die neue Relation berechnen, ausgehend von einer oder mehreren Relationen.
- Jede andere Menge von Operationen, die mindestens genauso mächtig ist wie Omega
9
Q
Wie unterscheidet sich Datalog von relationalen Kalkülen, relationaler Algebra, Prolog, SQL?
A
- Unterschied zu Kalkülen:
- Striktere Vorgaben bezüglich des Aufbaus von Anfragen,
- zieht diverse vorteilhafte Eigenschaften nach sich, formal nachweisbar.
- Andererseits: Erweiterungen problembehaftet.
- Datalog vs. SQL
in Datalog:Aggregation kann zu Nicht-Monotonizität führen – Illustration (1) Aggregation – nicht Teil von Datalog, deswegen Darstellung mit SQL.
- Datalog vs. Prolog
Datalog: Anordnung von Prädikaten und Fakten spielt keine Rolle.
Datalog erlaubt im Gegensatz zu Prolog keine komplexen Terme als Argumente in Prädikaten. Beispiel: P(1, 2) ist erlaubt, nicht aber P(f(1), 2).
- Datalog vs. relatinaler Algebra
Datalog hat wichtige Beschränktheit in der Ausdruckskraft der relationalen Algebra nicht (Berechnung transitive Hülle), trotzdem effizient.
Datalog ist monoton. (Keine Negation in Rümpfen von Regeln erlaubt.)
monoton := Vergrößerung des Inputs (einer Anfrage/eines Operators) verkleinert nicht den Output.
Rekursive Anfragen nicht in relationaler Algebra. Relationale Algebra hat dafür diff-Operator, der nicht in Datalog ausdrückbar ist.
10
Q
Warum beschäftigen wir uns mit Datalog, gegeben dass wir relationale Anfragesprachen schon kennen?
A
Rekursion ist möglich!
11
Q
[mP] Was bedeutet modelltheoretische/ beweistheoretische Semantik von Datalog Programmen? Unter welchen Umständen können diese Betrachtungsweisen sich im Ergebnis unterscheiden?
A
Zwei alternative Herangehensweisen:
- Modelltheoretisch: Berechnung der Menge aller Grundfakten, die logische Konsequenzen des Programms sind.
- Beweistheoretisch: Berechnung der Menge aller Grundfakten, die aus dem Programm (in endlich vielen Schritten) ableitbar sind.
Ansätze liefern – für Horn-Klauseln – das gleiche Ergebnis.
12
Q
Was ist Stratifikation? Warum ist dieses Konzept im Kontext von Datalog bedeutsam?
A
Stratifikation bedeutet das auszuführende Programm in eine ausfühbare Reihenfolge zu bringen über Einteilung sog. Strata! Intressant für Datalogprogramme, die Negation enthalten.
Denn ein Programm das Negation auf noch nicht vollständig berechnete Realtionen enthält ist nicht ausführbar!
Man kann es aber mit Hilfe von Stratifikation (Abhängigkeitsgraph + Algorithmus) in eine ausführbare Reihenfolge bringen, sofern die Negation nicht teil eineses Zykels ist!!
13
Q
Ist Negation grundsätzlich erlaubt in Datalog? Wie kann es zugelassen werden?
A
[Negation in rekursiven Regeln]
Es ist grundsätzlich nicht erlaubt, auf Grund der nicht-Monotonizität!
Datalog ist monoton. Negation kann aber mit Stratifikation zugelassenwerden.
Verwendung von Negation in Rümpfen muss kontrolliert erfolgen. Wird negatives Literal der Form negationP in Regel benutzt, muss P bis dahin vollständig berechnet sein.
14
Q
Wozu kann Negation führen? Zeigen sie ein Beispiel!
A
Es kann zur Oszillation führen!
Anwendung des Algorithmus auf folgendes Beispiel führt zu „Oszillieren.“
Bei beweißtheoretischem Vorgehen!
- P(X) :- R(X), -Q(X) .
- Q(X) :- R(X), -P(X) .
Anmerkung beim Ausführen des Algo –> Ich beziehe mich im Schritt 1 auf den Ausganszustand: Also nur die 0 in R und Rest leer oder was anderes
Führt modelltheoretische Betrachtung zu gleichem Ergebnis wie beweistheoretische Betrachtung?
Für Illustration, Formeln hierfür umformen. (nur für modelltheoretisches Vorgehen)
Es reicht mit beweistheoretischem Vorgehen stumpf die Regeln aus dem Beispiel anzuwenden um Oszillieren zu zeigen. Also oszilieren zwischen dem Anfangszustand und den 1. Zustrand –> es gibt kein terminierten Zustand –> Regeln würden unentlich fortgesetzt!
15
Q
Wie können wir denn nach Mustern in Graphen suchen? Also zum Beispiel diese Dreieck?
A
Funktioniert über sogenannte Motifs
Motif = (flexible) Spezifikation von Mustern in Graphen
Es gibt simple (elementare) Motifs und zusammengesetzte Motifs
einfache Motifs sind im Prinzip Graphen ohne jegliche Flexibilität
Motifs können graphisch oder textuell dargestellt werden (Textuell hat den Charm, dass es quasi schon Teil unserer Anfrage ist)
Wir haben die Möglichkeit den Mustern Namen zu geben
Zusammensetzungen bringen Übersichtlichkeit!
Bild bsp !
Es gibt nun unterschiedliche Möglichkeiten wie wir die Zusammensetzung machen können
16
Q
Stellen sie mal einen Join mit Datalog dar! Mit Student(MatrNr, Name) und Prüfung(MatrNr, Note) –> Name und Note ausgeben
A
Einfach mit Komma getrennt !
Ergebnis(Name, Note) :- Student(MatrNr, Name), Prüfung(MatrNr, Note)
17
Q
Stellen sie mal Selektion mit Datalog dar! –> x>100 in R(x,y) (Mit 2 Bedingung AND/OR y=’some string’ )
A
- x>100 in R(x,y)
S(x,y) :- R(x,y), x > 100,
- Selection x>100 AND y=’some string’
S(x,y) :- R(x,y), x > 100, y=’some string’
- Selection x>100 OR y=’some string’ Need two rules (Also Union mit oder!)
S(x,y) :- R(x,y), x > 100
S(x,y) :- R(x,y), y=’some string’
18
Q
Stellen sie mal Union mit Datalog dar!
A
Für Union brauchen wir 2 Regeln // gegeben R1(X,Y,Z) und R2(X,Y,Z)
U(X,Y,Z) :- R1(X,Y,Z)
U(X,Y,Z) :- R2(X,Y,Z)
19
Q
Stellen sie mal Projektion mit Datalog dar! R(A,B.C) und ich möchte das B wegprojezieren!
A
S(A,C) :- R(A,B,C) .
20
Q
Warum ist ein external Interface bei Motifs nötig?
A
Es ist im allgemeinen erforderlich, dass ein Motif ein externes Interface hat, weil wir ansonsten nichts haben von diesem Motif was wir dann in ein größeres Motif einbauen können
21
Q
Schreiben Sie mal das Muster für einen Pfad beliebiger Länge auf und mal einen Cycle! Und was beinhaltet diese Muster?
A
Das Muster beinhaltet Rekursion
Warum muss die Export Klausel dazu?
siehe tonspur
22
Q
Nennen und schreiben Sie mal die Muster für alle Arten von Komplexen Motifs auf?
Benutze das Motif aus dem Bild und führe Vereinigung durch!
A
- Komplexe Motifs
- Concatenation (keine Flexibilität)
- by edges
- by unification
- Disjunction. (Flexibilität - common part’ – here shown in blue.)
- Repetition
Beispiele im Bild
23
Q
Motifs ist keine vollständige Anfragesprache was fehlt noch? Schreibe Beispiele zu den fehlenden Bestandteilen auf!
A
- Ich möchte zum einen noch bestimmte Bedingungen an einzelne Elemente des Graphen stellen (z.b Knoten1.name=”A” oder Knoten2.year > 2000)
- Möglich mit Graph Patterns
- Zum anderen möchte ich die Struktur des ausgegebenen Graphen bestimmen. Es für eine Anfragesprache von Nöten, dass da Ergebnis wiederverwendbar ausgegeben wird.
- Möglich mit Templates
- Graph Patterns (kurz = eigenes Motif mit Where Klausel)
= Im Prinzip ein Motif, das durch Where Klausel erweitert wird, wo dann auf Knoten bezug genommen wird, die Teil unseres externen Interfaces sind. Über die Where Klausel können wir dann Bedingungen formulieren!
- Template
Bestandteile
- Body = Vorgabe wie der auszugebende Graph strukturell beschaffen ist
- Pattern = Pattern wird in neuer Ausgabe verarbeitet
Aus dem Template entsteht einer neuer Graph!
24
Q
Was ist denn der Abhänigkeitsgraph und was sind die Knoten und die Kanten?
Male den Abhänigkeitsgraph für dieses Beispiel!
A
Zwei rekursive Definitionen, die voneinander abhängen (d. h. Definition von A hat B im Rumpf u. u.)
Erkennen mit Hilfe des Abhängigkeitsgraphen:
- Knoten – Relationen,
- Kante – direkte Abhängigkeit, [A->B, Prädikat A hängt von B ab]
- Zykel.
25
Wie können wir das Beispiel abändern damit es kein Problem mit der Negation gibt?
-Q(X) aus P(X) entfernen!
Ausführung siehe Bild
26
Erkläre die Schritte und Führe Stratifikation an folgendem Beispiel aus!
Voraussetzung: Ein Abhänigkeitsgraph ohne Zykel, die Negation enthalten!
Bei Zykeln mit Negation kommt der Algorithmus nicht zur Ausführung! ⇒ D.h. Programm nicht stratifizierbar und so nicht ausführbar
ALSO:
1. Abhängigkeitsgraph aufstellen und auf Zykel prüfen/ ggf. Abbruch siehe oben!
2. Alle Knoten die eine ausgehende Kante mit Negation haben weglassen
3. Alle Knoten, die von den eben gelöschten Knoten abhängen ebenfalls entfernen
4. Der Rest, der übrig bleibt ist unser Stratum 0, welches zuerst berechnet werden muss
5. Stratum 1 sind dann die gelöschen
Lösung im Bild
27
Es gibt ja außer den Attributwerten von Knoten im Graph noch komplett andere Informationsbedürfnisse! Was meine ich damit? Was sind diese Maße?
Sogenannte Zentralitätsmaße können folgendes Messen:
* **Shortest Path**: „What is my closest connection to Barack Obama on Facebook?“
* „Welcher DBE Student hat die **meisten** Facebook-**Freunde**?“
* „Wie viele Freunde haben DBE Studenten auf Facebook im Durchschnitt?“
* „Welche Teilnehmer sind wichtig oder **einflussreich**?“
* „Welche Teilnehmer sind (in irgendeiner Weise) **auffällig**?“
* „Gibt es Gruppen ähnlicher Teilnehmer?“
28
Welche Zentralitätsmaße kenne Sie? Klassifizieren sie diese!
Lösung --\> Bild
29
Was ist Betweennes Centrality? Formel angeben und erklären wann ein großer/kleiner Wert angenommen wird!
Informell: Wie oft ich (als Knoten) zwischen anderen Knoten bin
A und B besprechen was, aber C (ich) liegt zwischen beiden. Also bekommt C mit was besprochen wird "haha". Aus sich von C ist das gut
Angenommen aber es gibt viele Pfade von A nach B und nur ein Pfad geht dabei über C. Naja dann ist die Betweenes Centrality von C "nicht so toll"
Gibt es nur einen Pfad, des dann auch über C führt ist das "das beste"
ALSO: Beschreibt nicht Erreichbarkeit, sondern eher Informiertheit!
30
Wann ist Betweenness Centrality maximal/minimal?
(\*mP) Sternförmiger Graph --\> Hub bzw Triad?!
Bei Proximity Prestige war es der Stern (Hub) und hier auch?! Was ist der Unterschied?
Naja wenn nur ein Pfad von vielen zwischen j und k über mich (i) führt ist BC minimal
31
Was ist Proximity Prestige? Beschreibe auch wann es minimal/maximal wird (anhand der Formel)
Maß aus der Kategorie Distanz-basiert:
Idee: Wie gut ein Knoten von den anderen Knoten im Graph erreichbar ist
Erreichbarkeit (zweierlei)
(1) Es gibt von vielen anderen Knoten des Graphen einen Pfad zu mir, besser als von wenigen Knoten ein Pfad zu mir
ALSO: Von wie vielen Knoten kann ich über einen Pfad zu mir kommen
(2) Wie lang sind diese Pfade? Kurze Pfade sind besser
* *Zähler:** Anzahl der anderen Knoten die mich erreichen durch alle Knoten im Graph (Relative Größe der Influence Domain)
* *Nenner:** Durchschnittliche **kürzeste-**Pfadlänge zu mir!
(\*mP) maximal wenn --\> hub-artiger Graph = ich in der Mitte und von allen anderen Knoten gibt es eine Kante zu mir
minimal wenn --\> Ii (Influence Domain) = leer also 0, durch 0 teilen gibt 0 BZW. Ii klein und Pfade lang
32
Wann sind die Ergebnisse von Betweenness und Proximity Prestige unterschiedlich?
Es gibt beim Hub mit außenverbindungen weitere kürzeste wege, die nicht durch i führen (mittlerer Knoten)
Jedoch hat dieser Graph kein negativen Einfluss auf Proximity Prestige
33
Welche Vorteile hat es Zentralitätsmaße direkt in die Anfragesprache zu integrieren?
Also: erst Zentralitätsberechnung und dann darauf aufbauen weitere Berechungen
Oder aber anders herum!
Bsp --\> LinkedIn (FrauenGraph)
ALSO: Welche Frauen nutzen hauptsächlich Männer um sich zu vernetzen vs. welche Frauen sind hauptsächlich auf ihr Frauennetzwerk gestützt?
Unterschied zu vorhin --\> erst Graph A´ konstruiert (onlyFrauenGraph) und dann Zentralität berechnet
Unten --\> (1) Berechnung (2) Zentralität
Oben umgekert --\> (1) Zentralität (2) weitere Berechnung
--\> Worauf will Böhm hinaus: Zentalitätsmaß sollte elementares Konstrukt bei der Anfrage sein und lässt sich an beliebiger Stelle einsetzen
--\> Also aus 2 schritten einen machen!
Beobachtung: Standard-Operatoren der RA nicht ausreichend zum formulieren der behavior-based trust policies. Zusätzliche Operatoren erforderlich.
Berechnung direkt mit Zentralitäts Operator möglich --\> Beispeil entwickelter CENTRALITY Operator
34
Warum ist in Datalog Negation grunsätzlich nicht erlaubt?
Es ist grundsätzlich nicht erlaubt, auf Grund der nicht-Monotonizität!
s kann zu Oszillation kommen!
35
Kommt es bei Negation in Datalog immer zu Oszillation?
Meine Antwort:
Es kommt darauf an
(1) Negatrion an min. 1 Stelle im Zykel: Programm nicht stratifizierbar! --\> nicht ausführbares Programm, sofern Negation, oder Zykel nicht entfent wird
(2) Negation nicht im Zykel: Das Programm kann durch Stratifikation in eine ausfühbare Reihenfolge gebracht werden. Negation erst zum Schluss berechnen, wenn alle dafür notwendigen Relationen berechnet sind (Stratum0 (erst vollständig berechnen)/ Stratum 1 (Negation berechnen))
Also: Ein Stratum muss vor dem nächsten Stratum vollständig berechnet sein!
36
Haben wir in relationaler Algebra Negation
Nicht direkt, aber wir haben den Mengendifferenz Operator, der der Negation entpricht:
Datalog: P(X) :- R(X), -Q(X)
rel Algebra: R(X) - Q(X) bzw. R(X)\Q(X)
37
Vergleichen sie mal Datalog mit relationaler Algebra!
Relationale Algebra und Datalog sind unvergleichbar, d. h. Datalog hat Rekursion und relationale Algebra die Mengendifferenz. Man kann hier keine Aussage treffen was nun besser ist!
Was man sagen kann ist, dass die Schnittmenge von RA und Datalog:
ALSO: Datalog ohne Rekursion == relationale Algebra ohne diff-Operator.
gleich wäre!
Siehe Tonspur!
38
[mP] Was ist Zusammenhang zwischen Aggregation und Nicht-Monotonizität?
Aggregation kann zu Nicht-Monotonizität führen!
Das **Überschreiben** durch die Aggregation (Summe) ist das Problem, es verletzt die monotonizität Eigeschaft (Es wird was rausgenommen und ersetzt).
39
Geht so etwas auch in Datalog -\> S(X) :- -R(X) ?
am besten anhand eines Zahlenbeispiels erklären
⇒ Hier würde man durch Negation alle Zahlen/Werte, die nicht in R sind definieren würde (Hinweis: Darum Negation grundsätzlich nicht in Datalog erlaubt)
⇒ X wäre ein Tupel mit einer NUll (0)
⇒ Dann würden unendlich viele Zahlen in S(X) erzeugt, die eben nicht 0 sind!
40
1. Was ist die Monotonie-Eigenschaft?
2. [grüne Frage] Welcher Operator der relationalen Algebra ist nicht monoton?
3. Ist Datalog monoton?
1. monoton := Vergrößerung des Inputs (einer Anfrage/eines Operators) verkleinert nicht den Output.
2. Mengendifferenz
3. Ja, Datalog ist monoton. (Keine Negation in Rümpfen von Regeln erlaubt.)
Beispiele siehe Tonspur
41
Wir haben in der Vorlesung 2 verschiedene Graph Frameworks kennen gelernt. Wie unterscheiden die sich?
1. Vertex-centric (Giraph Framework)⇒ (machen im moment alle (2016))
2. Graph-centric (Giraph++ Framework)
1. Vorteil ⇒ bessere Performance (da auf verteilten Rechnern)
2. Nachteil ⇒ Partitionierung muss vom Programmierer berücksichtigt werden. D.h ⇒ Mehr intelektueller Aufwand nötig für eigenen Code
Giraph = Einfache Verarbeitungsmodell == Knotenorientierte VerMod (von Google)
(1)**Partitionierung der Menge der Knoten** des Graphen, zwecks Parallelisierung
* (2)Folge von **Iterationen, sogenannte supersteps, parallel**.
* Ausführung einer Funktion **compute(),** anwendungsspezifisch und **vom Anwender** zu schreiben für **jeden Knoten.**
* Es stehen graphspezifische Methoden (**Interface**) zu Verfügung, die in **compute()** verwendet werden können,
* **Synchronisation** am Ende jedes Schritts. D.h. **Nach compute()** werden an **direkte Nachbarn** des Knoten **Nachrichten** gesendet und am Anfang des nächsten Schritts stehen diese Nachrichten der Funktion compute() zur Verfügung und werden verarbeitet
* (3).Ausgabe des Ergebnisses.
Giraph++ == Partitionsbasierte Verarbeitungsmodell
Hier hingegen: **Nicht einzelne Knoten, sondern Teilgraphen (Partitionen)** ⇒ Compute für Teilgraphen.
* Knoten werden **partitioniert UND** noch es gibt noch eine **Kopie (secondary copy)** der Knoten, die mit einer **ausgehenden Kante** mit einer **anderen Partition** verknüpft sind
* Außerdem werden Zusammenhängende Knoten einer Partition sogleich im 0. Schritt mit d**em Minimum der Partition ausgestattet,** da ein Algo die zusammenhängenden Teilgraphen ausmacht und die Informationen schonmal an den Teilgraph verteilet!
* **secondary** copy gehören **zur hiesigen**(ausgehenden) Partition und **primary** copy zur "**echten**"(ziel) Partition)
* Besonderheit: Sammeln der eingehenden werte durch second copy´s an einer Partition in einer Tabelle und das anpassen der gesamten Partition auf einmal in dem das Minimum der Tabelle genommen wird!
⇒Vorteil = schneller als bisheriges durch den Graph diffundieren
* ⇒ Vorteil: Nachrichtenaustausch geringer **Kommunikation nur noch zwischen Partitionen**. Von einer **secondary copy zur primary copy** des Knotens der "echten" Partition
* ⇒Nachteil: Implementierung der Graph-Algorithmen durch Anwender muss Partitionierungen angemessen berücksichtigen.
42
Was bleibt bei der Stratifikation übrig, wenn sie nicht funktioniert?
Es können Knoten und Kanten übrig bleiben!
?? Bei Negation in Zykeln würde der Algo eh nicht ausgeführt ??
43
1. Aus was ist ein Typsystem aufgebaut?
2. Warum ist ein Schema eigentlich ein Typ?
1. Typsystem:
1. Programmiersprachen --\> nicht relevant hier
2. Hier ⇒ Menge von Typen und Festlegung ihres Zusammenspiels, also welche Operationen es gibt um Instanzen eines Typs in einen anderen zu überführen
2. Das nämlich gesagt wird, welche Zustände zulässig sind.
44
Für was kann man Graphen (ganz allgemein) kann man Graphen einsetzten?
Darstellung von z.B.:
```
#Soziale Netzwerke (SN),
#Web Graphen,
#Chemische (Struktur-) Formeln,
#(Schematische) Karten (Netzpläne),
#Prozess- und Programmausführungen.
```
45
Warum verwenden wir Graphen und nicht ein relationales Modell?
Je eine Relation für Knoten (V) und Kanten (E).
1. Personen(Person,Attr1, Attr2, ...)
2. Beziehung(Person, Person, "Freundschaft")
Knoten und Kanten können beliebige Attribute haben Falls unterschiedliche Knoten oder Kantentypen
⇒ Knackpunkte:
* SQL stößt bei relevanten Informationsbedürfnissen an seine Grenzen.
* Zentralitätsmaße (Wie beliebt/vernetzt etc. ist jmd.)
* Oft Rekursion nötig (Über viele Kanten navigieren)
* Anfrageverarbeitung wäre nicht effizient!
46
Was muss Anwendungsentwickler noch tun, wenn er Giraph Giraph++
einsetzt, und was wird ihm abgenommen?
da
47
Inwieweit ist Giraph++ gegenüber Giraph eine Verbesserung?
Graph-centric (Giraph++ Framework)
Vorteil ⇒ bessere Performance (da auf verteilten Rechnern)
Vorteil ⇒ Nachrichtenaustausch geringer Kommunikation nur noch zwischen Partitionen.
Nachteil ⇒ Mehr intelektueller Aufwand nötig für eigenen Code
48
Geben sie mal ein Giraph Beispiel und der Kommunikation der Knoten!
Bild und Ton!
49
Geben sie mal ein Beispiel für einen Partitonierten mit 2 Partitionen und erklären sie das!
50
1. Schreiben Sie mal die Formel für den PageRank auf und erklären Sie!
2. Wofür ist der erste Summand der Formel und was ist der Damping-Factor?
(1)
* PageRank – Kann als **Reputation oder Wichtigkeit** interpretiert werden. Kante steht für ‚recommendation‘, ‚positive mention‘, etc….
* Intuition: Für Knoten **ohne** eingehende Kanten, **PR ist minimal**.
* Wird ein Knoten von anderem Knoten mit hoher Reputation referenziert, erhöht sich dessen Reputation.
* Wird mit hoher Reputation **exklusiv** referenziert, erhöht sich die Reputation schneller.
* Formel rekursiv: PR anderer Knoten geht in PRi ein!
Salopp: wenn viele angesehene Knoten auf mich verweisen, ist das gut!
(2)
Es gibt nun ggf. Knoten, auf die keiner verweiset. Um dem Rechnung zu tragen gibt es den 1. Summanden.
d = damping factor (orft um 0.9)
naja auch Knoten, auf die keiner verweist sollen einen minimalen PR bekommen.
Wert von 0 für Knoten auf die keiner verweist würde Berechnungen schwierig machen!
Also: alle Knoten haben einen pos. PageRank
51
Welche Schwierigkeiten gibt es bei der Speicherung von E-Commerce Daten im relationalen Modell?
Schema-Evolution in Verbindung mit Sparsity
Zum Beispiel Produktdaten bei Elektronikbauteilen
2000 Produktkategorien, insgesamt \> 5000 Attribute über alle Kategorien
* Schema-Evolution ⇒ Anpassung des Datenbank-Schemas, während Datenbank bereits operational ist (Aufwändig)
* Sprasity ⇒ Relation ist ‚dünn besetzt‘, viele NULL-Werte (Speichervergeudung)
Bsp: //ständig neue Teile - mit neuen Attributen//manche Hersteller haben Attribute als "Alleinstellungsmerkmal". Andere haben dieses A. nicht, daher haben sie dort NULL-Werte
Auch bei Anfragen muss man bei Sparsity viele Seiten Laden --\> Effizienz leidet
== diese Schema-Evolution ist aufwändig und Sparsity ist störend
52
1. Malen Sie mal eine Beispielrelation auf mit ein Paar Werten (Attribute\<4) und erklären Sparsity! Und wie könnte man das Problem lösen?
2. Was ist das Problem, wenn ich in der horizontalen Repräsentation unterschiedliche Typen habe
Physische Speicherung folgendermaßen! (Logische sicht bleibt Horizontal)
1. Logische horizontale Sicht auf vertikale Repräsentation (oder Binär = collum store)
2. Lösung: unterschiedliche vertikale Relationen pro Typ!
53
1. Was ist wenn ein Tupel nur NULL-Werte besitzt? Wie geht man damit in der vertikalen Repräsentation um?
2. Von welchem Typ ist das Val Attribut der vertikalen Relation?
Tupel mit nur NULL-Werten grundsätzlich zulässig (pathologischer Fall)
⇒Vertikal: immer nur ein Tupel vorhanden, wenn auch ein Wert für ein Attribut vorhanden ist! Sprich das Tupel würde nicht repräsentiert werden!
1. **Es würde nicht** in der vertikalen Darstellung **repräsentiert.** **Aber:In diesem Ausnahmefall** lassen wir ein Eintrag in der relation vertikal zu, indem OID vorhanden ist es für Key und Value aber NULL-Werte besitzt
2. Wir können es in einer seperaten Relation speichern (nur für diese Fälle)
1. Das generischste, das es gibt, also das, welches am meisten umfasst!
54
1. Was versteht man unter Higher Order View?
2. Was unter Enablement Layer?
1. **High Order View** ⇒ **Inhalt** der vertikalen Relation **Bestandteil des Schemas** der horizontalen Relation und umgekehrt!!
2. **Enablement Laye**r ⇒ dort findet die **Transformation von Anfragen** aus h-Sicht auf v-Sicht und die Transformation der Ergebnisse von v-Sicht auf h-Sicht statt
1. Aus Datenbanksicht ⇒ Anwendung über Datenbank
2. Aus Anwendungssicht ⇒ Bestandteil der Datenbank
Genauer:Tonspur
55
Was ist mit Erweiterung der Algebra, Rewritings gemeint
56
[A] v2h Aufschreiben und kurz Erklären!
[B] Warum Left Outer Join und nich (outer)Join
[A] v2h
**Wir gehen Spaltenweise vor**!
Anm: **Projektion** ist Mengenwertig und **entfernt Duplikate**
1. **Schritt**: Dupplikate 1 Spalte in V mit Projektion eliminieren **π**Oid(V)
2. Schritt: **Outer-Left-Join** mit **ProjektionOid,Val** des 1. Attributs. Also: σ(**Key=A1**(V))
3. Schritt: **Das gleiche** mit dem vorherigen Gesamtergebnis wie eben **nur mit** dem **2. Attribut ⇒ usw**
⇒ Alles schön und gut, geht jedoch so nicht weil
* auch wenn wir Left-Outer-Join in relationale Algebra hinzuhmenen
1. **es gibt keinen** LOJoin mit Iteration und laufindex K (**Phantasie-Operator**)
2. benötigter String-Manipulation um A[**1**], A[**2**], A[**3**]... an A[**i**] anzuhängen gibt es nicht
3. Spalten Beschriftung klappt nicht (Higher-Order View) ⇒ h(Oid,Val,Val,Val..) kommt raus, statt h(Oid,A1,A2,A3...)
Aus Skript
Wo ‘knirscht’ es?
* Es gibt keine Iteration (Schleife)
* Übergang i ⇒ 'Ai'.
* Spalten heißen alle 'Val'.
* Es gibt Operator für Umbenennung in relationaler Algebra (b).
* Jedoch nicht mit Datenbank-Inhalt als Argument.
* Woher kommt das k? gibt es nicht
[B] Naja, wir wollen ja, dass alle Zeilen, die wir im 1. Schritt erzeugt haben erhalten bleiben! **Und** Falls es entsprechungen gibt, **der Wert ergänzt** werden soll **und** falls es keine Entsprechung gibt **der NULL-Wert ergänzt** werden soll!
57
h2v Aufschreiben und kurz Erklären!
1. Schritt: **Selektieren** in Spalte A1 alles, wo was drin steht (σA1!=Null(H))
1. Zudem Projezieren wir **Oid** (wo was **drin steht**), den **String "A1"** und den **Wert von A1 ⇒** πOid,"A1",A1
* Zwischen-Ergebnis 1. Tupel mit πOid,"A1",A1(σA1!=Null(H))
2. **Analog** für weitere Attribute **A2,A3,...**
3. **Vereinigung** aller erzeugten Tupel (Zeilen) + **Pathologischer Fall** (Vereinigung zusätzlich mit Tupel, die leere Attributbez. und Attributwert enthalten)
**Wo ‘knirscht’ es?**
* Es gibt **keine Iteration** (Schleife)
* Übergang i ⇒ 'Ai'.
* Spaltenbeschriftungen **nicht umsetzbar**
* Es gibt Operator für Umbenennung in relationaler Algebra (ß).
* Jedoch **nicht mit** Datenbank-**Inhalt als Argument**.
* Woher kommt das k? **gibt es nicht!**
58
Was ist Rewriting?
Rewritings (1)
Implementierung der Operatoren der relationalen Algebra.
⇒**Input in vertikaler** Repräsentation, **Ergebnis in horizontaler** Repräsentation.
59
Was muss ich tun, wenn ich in der horizontale Relation alle **Oid** Einträge mit **A3=4** suchen möchte?
Ich müsste ein Rewriting machen
Horizontale Anfrage wäre ⇒ πOid(σA3=4(H))
in Vertikal ⇒ πOid(σKey=A3^Val=3(V))
60
Beschreiben Sie bitte was ein R-Baum ist!
Was bedeuten Überlappungen der Rectangles?
* R für Rechteck. Mehrdimensionale räaumliche Indexstruktur.
* Jeder Knoten des Baums entspricht einem Ausschnitt des Raums
* Die **Wurzel** entspricht dem **gesamten Raum**
* Die **Blattknoten** sind jeweils **Minimum Bounding** Rectangles, **der Datenobjekte, die in ihnen enthalten sind**
Überlappung: Rechtecke überlappen sich (innere Knoten des R-Baums)
¡ Überlappungen sind unerwünscht, denn ⇒ wir müssen in mehrere Teilbäume absteigen d.h. es ist weniger effizient, als nur in einen Teilbaum abzusteigen ¡
**Vorgehen**: Wir steigen in die Teilbäume ab, die mit unserem Bereich, für den wir uns interessieren, eine Überlappung haben
Anmerkung: Nearest Neighbour gleich wie bei Kd-Baum (Priority Queue usw)
61
Was für ein Problem mit R-Bäumen gibt es in hochdimensionalen Räumen?
Was wäre eine Lösung des Problems?
Die Anzahl der Überlappungen nimmt mit der Anzahl der Dimensionen zu!
Und warum ist das so? ⇒ Abstände können statistisch nicht
Also: Problem: je mehr Dimensionen D hat, desto teurer wird wird die Tiefensuche, da wir in mehr und mehr Teilbäume absteigen müssen...
**_R-Baum - Lösungsansätze_**
1. Mehrdimensionale Indexstruktur ist problematisch
1. ⇒ verwende **eindimensionale** Struktur, **z.B. iDistance**
2. Brauchen wir überhaupt immer exakte Ergebnisse?
1. ⇒ Approximate **Nearest Neighbour** via z.B. Locality Sensitive Hashing
62
Wie führt man eine kNearest Neighbour Anfrage in einem R-Baum durch?
Erinnerung:
* **Bereichsanfrage**: abstieg in Baum wo sich jeweils Überlappungen ergeben
* **kNN-Abfrage**: **Position** im **Raum** und wir Fragen uns **welche k** **Objekte** haben von dieser Position den **kleinsten Abstand**
1. Schritt: Priority **Queue erzeugen** und bei der Wurzel einsteigen. Also **erster Zustand** der Queue ist **die Wurzel** und sonst nichts
2. Schritt: Entnehme das erste Objekt aus der Queue und **betrachten** statt dessen **die Kinder**
3. Schritt: **Ordnen die Kinder** gemäß ihres geringsten **Abstandes** in die Queue ein
noch beenden!
63
1. Wie löst iDistance das beim R-Baum vorliegende Problem? (Viele Überlappungen bei vielen Dimensionen)
2. Welche Partitionierungs-Ansätze gibt es bei iDistance?
Teil1 **Vorgehen** des **Partitionieren** in 3 Steps **iDistance**
1. Im ersten Schritt wird der hochdimensionale Datenraum in einen Satz von **Partitionen** aufgeteilt.
2. Im zweiten Schritt wird **für jede Partition** ein **Referenzpunkt** festgelegt. O0, O1, . . . ,
3. Im dritten Schritt werden schließlich alle Datenpunkte in einem **eindimensional**dargestellt
Teil2 Möglichkeiten
1. **Raumbasierte** Partitionierung: zerteile Raum in **gleich große Partitionen**
1. vllt. für gleichverteilte Daten gut
2. Gleichverteilung ist in Praxis aber oft nicht gegeben
2. **Datenbasierte** Partitionierung: **Clustering**
1. jedes Clusteringverfahren möglich
2. hier: k-Means
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.5288&rep=rep1&type=pdf
64
Wie funktioniert eine kNN-Anfrage bei iDistance?
**Beobachtung:**
alle kNN von q (Query) liegen **im
Raum**sphere(q; r\*) wobei der Abstand zum am**weitesten entfernten**Nearest Neighbour**kleiner r\* ist!**
* *Problem**: r\* unbekannt
* *Idee**: finde **r\* iterativ**
1. Schritt: Man legt einen **Query Punkt** in den Raum und startet mit **kleinem** Radius **r** an.
2. Schritt: **erweitere itterativ** den Radius **r** und sobald der entstehende Kreis (sphere(q,r)) eine **Partition** (da iDistance) schneidet finde alle Objekte der Partition
Ein Array wird verwendet, um die m Datenraum-Partitionen und ihre jeweilige Referenz Punkte O1, O2, usw zu speichern. Das Array wird verwendet, um die Datenpartitionen zu ermitteln, die während der Query-Verarbeitung durchsucht werden.
* **Array zu Verwaltung der Referenzpunkte**, beinhaltet zu jeder Partition:
* Referenzpunkte Oi selbst
* weiteste (maxi ) Distanz von Objekten in Partition i zu Oi
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.5288&rep=rep1&type=pdf
65
Was ist ein Approximate Nearest Neighbour? Geben Sie ein Beispiel.
Beschreibung des Verfahrens
https: //graphics.stanford.edu/courses/cs468-06-fall/Slides/aneesh-michael.pdf
https: //www.youtube.com/watch?v=WyTx-TY0XvU
exaktes kNN ist teuer
Idee: **manchmal reicht auch eine Näherung**..
**Beispiel**: finde ähnlichsten Tweet
Finde Objekt **p** Element D, der ein **e**-approximierter Nearest Neighbour von
Query-Objekt **q** ist. D.h. es gilt für alle p' Element D
Siehe Bild
wobei p\* der wahre nächste Nachbar zu q ist. Mit anderen Worten, p ist innerhalb des relativen Fehlers des wahren nächsten Nachbarn. Allgemeiner ausgedrückt, für 1 k n ist ein k-ter (1)-approximierter nächster Nachbar von q ein Datenpunkt, dessen relativer Fehler vom wahren k-ter nächsten Nachbarn von q ist. Definieren Sie für 1 k n eine Folge von k näherungsweise nächsten Nachbarn des Abfragepunkts q als Folge von k eindeutigen Datenpunkten, so dass der i-te Punkt in der Folge eine Näherung an den i-ten ist
66
Was ist LSH und wie funktioniert es?
**Locality-Sensitive Hashing**
* teile Datenobjekte aus **D in Buckets** auf
* habe **mehrere** unterschiedliche ”**Bucketings**”
* während Query: betrachte **nur** Objekte, die bei mind. einem
Bucketing **im selben Bucket wie q** liegenn
Intuition: **Objekte**, die **nah beieinander** liegen, sind im **selben Bucket**
67
[mP] Was ist ein Datenbank-Schema? Welche Definitionen sind im Umlauf?
Schema hier lediglich Attribute, keine Integritätsbedingungen.
68
[mP] Läßt sich die NF2-Datenbank auf Seite 4 als herkömmliche relationale Datenbank darstellen? Wenn ja, wie?
Bild Meine Lsg
69
[mP] Wie unterscheidet sich NF2 vom herkömmlichen relationalen Modell?
**Relationales Modell**
* **Keine strukturierten Attribut-Werte**
* erste Normalform (1NF) – **alle Attributwerte atomar.**
**NF²**
* Attribute müssen nicht atomar sein, **aber**
* Es muss **mindestens ein atomares** Attribut geben.
* Attribut kann selbst wieder **Menge von Attributen** sein. **Attributwert kann** selbst wieder **Relation sein**.
⇒ Möglicherweise natürlicher zur Darstellung komplexer Strukturen. (Lesbarer für Mensch)
⇒ Höhere Flexibilität **führt zu komplexen Definitionen der Operatoren** und Notwendigkeit neuer Operatoren.
70
[mP] Wie funktionieren Selektion, Projektion, Nest, Unnest?
Zeige an den Beispielen!
Bild!
71
1. [mP] Was ist PNF? Geben Sie ein Beispiel für eine Relation, die nicht in PNF ist, und erklären Sie dies.
2. [mP] Wie lautet die alternative Definition (von PNF)? Begründen Sie, warum beide Definitionen äquivalent sind.
**Partitioned Normal Form**
* **Def1:** PNF entschachtelt durch äquivalente **1NF-Relation** darstellbar
* **Def2:** PNF Relation durch **Folge** von **Nests** konstruierbar.
**ALSO** ⇒Eine geschachtelte Relation, die **nicht duch Nestung herleitbar** ist ist **nicht in PNF**
(2) Wenn **keine** **funktionale Abhängigkeit**,
* *dann** auch **nicht** durch Nests **konstruierbar**
72
Wir haben NF² in der Vorlesung definiert. Geben Sie ein Beispiel! welche neuen Operatoren gibt es?
**Operatoren:**
* **Nesting-Operator**
* Neuer Strukturbaum, neues Schema.
* Ähnelt in gewisser Weise Gruppierung.
* Reihenfolge der Nesting-Operatoren ist von Bedeutung.
* Lässt sich das an Beispiel von vorangegangener Folie zeigen?
⇒ Durch mehrmaliges Anwenden von Nesting enstehen so belibig tief geschachtelte NF² Relationen
* **Unnesting-Operator**
* **Pentdant zu Nesting**
73
Ändern sich die bekannten Operatoren der relationalen Algebra bei NF²?
**Definition der ‚herkömmlichen‘ Operatoren ändert sich**, ist hier **komplexer**.
Definition gemäß Vossen-Buch: **Projektion** nur für ‚**top-level Attribute**‘.
Keine wirkliche Einschränkung, wegen Nest-/Unnest-Operator im Folgenden.
74
Ist NF² ausrucksmächtiger als rel. Algebra?
Keine wirkliche Alternative zum relationalen Modell, man ist **nur dann ausdrucksmächtiger**,
* wenn **neue Operatoren dazukommen**, z. B. Potenzmengen-Operator. Potenzmengen-Operator – erzeugt alle Teilmengen einer gegebenen Relation.
ABER:
Warum gibt es keinen Potenzmengen-Operator für die herkömmliche relationale Algebra?
⇒**Tupel** im Ergebnis des Potenzmengen-Operators enthalten wieder Mengen. **Nicht im herkömmlichen relationalen Modell darstellbar.**
75
Was ist das NF²-Modell?
Geschachtelte Relationen (‚Non First Normal Form‘): Attribut kann selbst wieder Menge von Attributen sein. Attributwert kann selbst wieder Relation sein.
Es muss **mindestens ein atomares Attribut** geben.
Das NF²-Datenmodell **bemüht sich** um die **Behebung** des **Aggregierungsproblems**, indem es die Spezifikation von Hierachien erlaubt
* Enthält durch **Schachtelung**/Hierachien zusätzkliches **semantisches Wissen**
* **Anwenderfreudlich (lesbarkeit)** ⇒ keinen Joins von verscheidenen Relationen nötig
**ABER:** Es löst nicht das Problem der Reihenfolge bzw. der Ordnung der Daten, wie es in. In der Praxis spielt die Reihenfolge der Daten eine wichtige Rolle
76
1. In der VL haben wir uns in-memory-systeme angesehen. Was ist **heute** das problem und was war **füher** das Problem?
2. Geben sie mal ein paar Zahlen!
3. Was können wir machen um die Cacheausnutzung zu verbessern?
**Problem früher (1+2)**
* Hauptspeicher auf **wenige MB begrenzt**
* Nur kleiner Teil der Daten passt in den Hauptspeicher (DRAM) (**32 MB**)
* **Vergleichsweise riesige** Festplattenkapazität **(2 GB) ⇔ s.o**
* Genutzt als Primärspeicher
* Extrem **hohe Zugriffslücke** von HS DRAM **(32 MB)** auf Disk **(2 GB)**
* Parallele Anfrageverarbeiten um HD Latenz zu kompensieren
* Minimierung der HD-Zugriffe durch geschickte Pufferstrategien
* Architekturelle Altlasten des ‚System R‘ aus den 70ernSpeicher klein
**Problem heute**
* Hauptspeicherkapazitäten von 1000e GB
* Nutzung als Primärspeicher
* **Zugriffslücke zwischen HS und Disk eliminiert**
* Problem: **Traditionelle Architektur zielt auf Minimierung der Diskzugriffe**
Beobachtung: **Es gibt eine offensichtlich immer größer werdende Zugriffslücke zwischen CPU und Hauptspeicher (DRAM)**
⇒ CPU wartet Großteil der Zeit auf Daten des Hauptspeichers Auch bezeichnet als **memory wall**
**Lösung: (3)**
* Caches bzw. **cache-awareness** ähnelt dem Puffermanagement
* Prinzip der Lokalität
* Räumlich (Zugriff Adressbereich in Nachbarschaft)
* Zeitlich (Zugriff Addressbereich in naher Zukunft)
* **Provozieren** der effizienten Ausnutzung
* Tupel-at-a-Time (--+)
* Operator-at-a-Time (-++)
* vektorbasiert (Menge von Tupel) (**+++**)
* Speicherlayout
* zeilenorientiert (+)
* + schreiben mehrere Attr.
* - lesen (Cold Data = laden unnützer Daten)
* spaltenorientiert
* + lesen einzelne Attr.
* - schreiben mehrere Attr.
77
Was können wir machen um Chaches besser zu Nutzen?
Caches bzw. cache-awareness **(Übersicht) an Maßnahmen**
**Prinzip der Lokalität**
* Räumlich (Zugriff Adressbereich in Nachbarschaft)
* Zeitlich (Zugriff Addressbereich in naher Zukunft)
**Speicher/Cache Zugriff**
* Cache Hit: Daten im Cache vorhanden
* werden aus Cache gelesen
* kein Zugriff auf Hauptspeicher
* Cache Miss:
* gesamte Cache Line aus Hauptspeicher
* CPU wartet bis Daten verfügbar
**Provozieren der effizienten Ausnutzung ⇒ Alternative Modelle moderner DBs**
* **Tupel-at-a-Time** (--+)
* + kleine Zwischenergebnisse passen in DRAM (Hauptsp.)
* - Kombinierte Ausführung aller Operatoren zu groß f. Cache
* Cache Miss
* - Function-Call-Overhead
**Operator-at-a-Time** (-++) || "Zweischneidiges Schwert"
* + kein Function-Call-Overhead
* + Optimierbarer Code
* - Daten passen nicht in Cache
* oft DRAM lesen
* passt nicht in DRAM ⇒ **Strategie versagt**
**Vektorbasiert** (Vektor = Menge von Tupel) (+++)
⇒ Vektor muss **groß genug** sein für Methoden-Aufruf-Kompensation
⇒ Vektor muss **klein genug** sein um Cache nicht zu verstopfen
**Speicherlayout**
* zeilenorientiert (+)
* + schreiben mehrere Attr.
* - lesen (Cold Data = laden unnützer Daten)
* spaltenorientiert
* + lesen einzelne Attr.
* - schreiben mehrere Attr.
**Hier Verbindung zu OLAP-lesend =+Spalten und OLTP-mixed +**
* Workload lesend? schreibend? mixed? Speicherlayout!
78
Erklären Sie mal OLAP und OLTP. Was genau ist das?
**Kurzübersicht**
**2 Technologien für das Arbeiten mit Datenbanksystemen**
[https://www.youtube.com/watch?v=Zd4VK3gHYs0](https://www.youtube.com/watch?v=Zd4VK3gHYs0)
[https://www.youtube.com/watch?v=I-HVEP8xoQo](https://www.youtube.com/watch?v=I-HVEP8xoQo)
**OLAP (Methoden) Hauptspeicherdatenbanken**
* Typisches Daten-Zugriffsmuster
* Wenige **Attribute**
* Alle oder **große** zusammenhängende **Anzahl an Tupel**
* ⇒ Bsp. Reports, Analyse, Aggregierte Daten
* ****Hauptsächlich **lesend**
****⇒ Spaltenorientiertes Layout bietet sich an
* + Lesezugriff einzelne Attr.
* - schreiben mehrere Attr
⇒ Optimierungsziel - Response time Leseoperationen
1. **Kompressionsverfahren**
* ****Ordnungserhaltende Wörterbuchcodierung
* Bit Packing
* Lauflängenkodierung
* Ziel: Bessere Cacheausnutzung durch Reduktion des Datenvolumens
Frage: Wie minimiere ich die Kosten für das Hauptproblem spaltenorientierter DB-Systeme: Tupel-Rekonstruktion
1. Spezielle **Optimierungen** der Anfrageverarbeitung (Materialisierungstrat.)
⇒ nur bei Spaltenorientierung
* **Frühe** Materialisierung
* **Späte** Materialisierung
Im Gegensatz zum Online Transaction Processing (OLTP) steht hier die Durchführung komplexer Analysevorhaben im Vordergrund, welche ein sehr hohes Datenaufkommen verursachen
**Transaktionale Workloads (OLTP)**
* Typisches Zugriffsmuster
* Wenige **Tupel**
* **Tupel** im Ganzen
* ****Bsp ⇒ Neuen Kunden/Artikel eifügen
* **Mischung** aus Lese- und Schreiboperationen
⇒ Zeilenorientiertes Layout bietet sich an
* + Schreiboperationen
* + Tupelzugriff mehrere Attr.
79
Nenne und Beschreibe die Kompressionsverfahren von OLAP!
**Ordnungserhaltende Wörterbuchcodierung**
* Wörterbuch aus original Wert und Ersetzungswert
* Komprimierung **O(log card(n))**, Dekomprimierung in **O(1)**
* + Verarbeitung auf komprimierten Werten
* + gut für Strings
**Bit Packing**
* Ausnutzung von **Slacks**: Ungenutzte Bits eines Datentyps
* - Verarbeitung auf komprimierten Werten nicht trivial
**Lauflängenkodierung**
* Reduktion von Sequenzen des gleichen Wertes
* Speichert 2-Tupel (Häufigkeit, Code)
* - Funktioniert nur bei Spaltenorientierung
* + Sortierung kann Kompressionsfaktor erhöhen
80
Was sind die Einzeleffekte und Anforderungen an Kompressionsverfahren von OLAP?
**Einzeleffekte**
* Reduktion der Gesamtgröße der Daten
* Mehr Daten pro Cache-Level
* + Ausnutzung der Speicherbandbreite
**Anforderungen**
* Verlustlos, sonst Datenfehler
* Leichtgewichtige (De-)Kompression, sonst Verlust des Performanz- Gewinns auf CPU Seite
* Idealziel: Anfrageverarbeitung auf komprimierten Daten
81
Welche Materialisierungsstrategien gibt es (OLAP)? Beschreibe sie!
**Materialisierungsstrategien**
**Frühe Materialisierung**
* zum frühest-möglichen Zeitpunkt
* ganzer Teile der Relation
* Reduziert die Kosten, wenn ein Attribut in einem Plan mehrfach benötigt wird
**Späte Materialisierung**
* zum spätest-möglichen Zeitpunkt
* Reduziert Rekonstruktionsaufwand auf tatsächliche Tupel im Resultat
* Erhält Vorteile aus Kompression und Speicher-Layout so lange wie möglich
82
Was ist, wenn wir nur die Vorteile wollen? (in-memory)
Dann nehmen wir **Vektorwertige Ausführung**.
* Dabei Trade-off **Vektorgröße** zwischen **Kompensation des call-overheads** und Größe der resultierenden Zwischenergebnisse
* (Wollte noch ungefähre Vektorgröße wissen - 1k Tupels)
83
Wie Speichern wir denn in OLAP und OLTP?
Protokoll: ausführlicher Monolog zu Spalten und Zeilenorientierter Speicherung mit allen Vor und Nachteilen und was für welche Queries gut ist.
2 Ansätze (Speicherlayouts)
1. Zeilenorientierte Speicherung (**row store**)Alle Tupel (mit ihren Attributen) sequentiell auf Seiten gespeichert
* + Gut: **Schreib**operationen / Tupelzugriff (**mehrere Attribute**)
* - Schwierig: cold data bei Attributzugriffen (Aggregationen etc.)
2. Spaltenorientierte Speicherung (**column store**) Alle Werte eines Attributs sequentiell auf Seiten gespeichert
* + Gut: **Lesender** Attributzugriff auf **einzelne** Attribute (Aggregationen etc.)
* - Schwierig: Schreiboperationen / Tupelzugriff (mehrere Attribute)
84
1. Wie kombiniert man OLAP und OLTP?
2. Suchen sie sich mal eine aus!
Protokoll: Hybride Datenbank, die mit beiden Workloads auskommen
**Hyper gewählt**
von mir:
Grundprinzip: OLAP benötigt nicht die allerneuesten Daten
* OLAP Anfragen auf Snapshot der Daten
**Copy on Write Mechanismus**
* Jedes Mal wenn OLTP Anfrage ein Datenobjekt ändern will, erschafft der Linux Kernel erst eine neue Seite mit den alten Daten für OLAP
* OLAP Anfragen
* fast aktuelle und konsistente Daten
* Danach kann OLTP ungefährdet die Seite modifizieren
Bei OLAP gibt es copy on write, sodass OLAP Anfragen auf den alten Daten weiterlaufen, während die OLTP-Query auf der ursprünglichen Seite arbeitet. Dabei werden Seiten syscalls dupliziert
85
Was ist bei 2 OLTP-Anfragen und warum überhaupt alte Daten?
Protokoll: Entweder nochmal page copy mit anschließendem merge oder einfach sequenziell
--\> Dann illustriert warum OLAPs nur auf den älteren Daten arbeiten können.
86
Chache profitiert vom Prinzip der Lokalität. Was ist damit gemeint und welche Lokatlitäten gibt es?
Häufig benötigte Daten (hot data) passt oft vollständig in Cache 90% der Ausführungszeit resultiert von nur 10 % des Codes
**Räumliche Lokalität**
* Nach einem Zugriff auf einen Adressbereich erfolgt nächster Zugriff mit hoher Wahrscheinlichkeit auf eine Adresse in **unmittelbarer Nachbarschaft** *Beispiel: Scan einer Spalte*
**Zeitliche Lokalität**
* Adressbereiche, auf die zugegriffen wird, werden auch in naher Zukunft mit hoher Wahrscheinlichkeit wieder benutzt werden *Beispiel: Selektionsprädikate*
⇒ DB-Systeme profitieren von der Lokalität von Daten und Code
87
Was kann man über das Speicherlayout in in-memory Systemen sagen?
Welche 2 Varianten gibt es? Vor- und Nachteile?
Wie sieht beide Varianten es mit folgender Anfrage aus?
Grundsätzlich gibt es **zwei Ansätze**
1. Zeilenorientierte Speicherung (row store)
1. **Alle Tupel** (mit ihren Attributen) **sequentiell auf Seiten** gespeichert
* **+** Gut: Schreiboperationen / Tupelzugriff (mehrere Attribute)
* **-** Schwierig: cold data bei Attributzugriffen (Aggregationen etc.)
2. Spaltenorientierte Speicherung (column store)
1. **Alle Werte** eines Attributs **sequentiell auf Seiten** gespeichert
* **+** Gut: Lesender Attributzugriff auf einzelne Attribute (Aggregationen etc.)
* **-** Schwierig: Schreiboperationen / Tupelzugriff (mehrere Attribute)
**Anfrage:**
1. Jeder Zugriff auf l\_shipdate Attribut eines Tupel resultiert in **großer Menge nicht benötigter** Daten im Cache
2. Jeder Zugriff auf l\_shipdate ist **entweder bereits gecached** oder die nächsten Werte werden **gleich mitgeladen**
**Fazit**
**⇒ Keine Standardlösung: Workload-basierte Entscheidung nötig** *Grundsätzlich zwei Arten von Workloads***:**
* **Analytisch (OLAP): read**-mostly / append only
* **Transaktional** **(OLTP): mixed** workloads, read and write
88
Schreiben sie mal einen flexiblen **komplexen** Graphen auf (**Motif**), der aus 2 Knoten als externes Interface besteht! (**Disjunktion**)
Bild!
89
Was ist MapReduce?
* kommerziell Verfügbarer **Konzeptioneller Rahmen** für die **Parallelisierung** von Datenverarbeitung/Berechnungen
* **Zwei Funktionen** (map und reduce), die **anwendungsspezifisch zu implementieren** sind.
* **Framework** kümmert sich um die Ausführung.
⇒ Grund **große Datenbestände**! : Bisherige Technologie an ihre Grenzen gestoßen
**Vorteil:** Zusätzlicher reduce-Schritt nach reduce. Oft besser, um möglichst wenige Daten zu transportieren.
BILD!
90
Was ist Gremlin
Was für Bestandteile gibt es?
(A)Warum komplizierter als XPath?
(B)Inwieweit ist Navigation anders/ausgefeilter als in semistrukturierten Datenbeständen?
Gremlin – Sprache für **Graph-Traversierung.**
Schritte heißen**: Pipes** (in XPath waren es Location-steps), dessen Teilergebnisse mit **next() weiterverarbeitet** werden können
* ⇒ **Pipes werden zeilenweise abgearbeitet** (ähnl. Datalog) **siehe Bild**
**Benutzt HTTP Post Methode**
* g.V #gibt alle Knoten zurück
* g.E #gibt alle Kanten zurück
* g.v(0) #auf einzelne Knoten zugreifen (mit entsprechender ID)
* g.v(0).map() #gibt alle name-wert Paare zurück
* g.v(0).name #gibt name aus
* Konvention: Jeder Knoten muss ein name-Attribut haben.
* g.V.**filter**{it.**name == 'riesling'**} #it. für Iteration und filter=selektion
Außerdem:
* .inE, .outE #gib mir die eingehenden**/**ausgehenden Kanten zurück
* .bothE #quasi **ungerichtet!** egal, ob ein- oder ausgehend Kanten
* .inV, .outV #**Knoten** an denen die Kante beginnt bzw. endet
* .out = outE.inV, #Kanteübersprungen, **direkter weg Knoten-\>Knoten**
* .in =inE.outV #Same here
* .exept([alice]) #Alle Knoten außer alice
* .filter{!it.equals(alice)} #Same here
Beispiel: g.V.filter{...}.out #**alle per ausgehender Kante erreichbare Nachbarknoten**, die die filterbedingung überstehen
(A)Komplizierter als in XPath, da hier Kanten explizit modelliert
(B)D. h. man muss Alice explizit ausschließen, obwohl Navigation bei ihr begonnen hat.
91
Füge den Knoten mit **ID** **pwolf** und **namen**"Prancing Wolf Winery" hinzu, der mit **v(0)** über **Kante "produced"** verbunden ist! [GREMLIN]
Bild
92
Gib mir alle Weine der des gleichen Traubentyps zurück wie ice\_wine, außer ice\_wine selbst!
* Kante "grape\_type"
* Ausgangsknoten ice\_wine = g.v(0)
Bild!
93
Was kann ich mit .next() machen?
Und was mit .class?
Liefert die Elemente die in der **aktuellen Pipe (Zeile) berechnet wurden**!
**.class** gibt aus von welchem **Typ** das **bis hierhin** berechnete **Ergebnis** ist
⇒nur .class --\> dass es sich um eine Pipe handelt, also eine Menge von Knoten, Kanten oder irgendwas
⇒.next().class #erst Element, dann fragen von welchem Typ
Also: **Teilergebnisse von Pipes können weiterverarbeitet werden!**
94
Gib mir alle indirekte Freunde von alice. Also: Freundesfreunde von alice!
Kante "friends" mit loop! ohne Duplikate!
(B)Kann man sich auch die Pfade bis zum Ergebnis ausgeben lasen? Wenn ja wie?
**Erklärung**
* .loop (**3**) #**vorangegangene Schritte, die** wiederholt werden sollen! Also sollen die 3 Schritte zuvor wiederholt werden!
* .loop(3) {**it.loops \<= 2**} #diese 3 vorang. Schritte sollen **2 mal angehängt** werden!
* .dedup.name #deduplicate, bitte Ausgabe **ohne Duplikate**
**⇒** alice.bothE('friends').bothV.except([alice]).loop(3){ it.loops \<= 2 }.dedup.name
(B) ja das geht mit einem **angehängten .paths!**
95
Wie kann man kleine Funktionen mit Gremlin definieren?
* Kanten "friend" gerichtet
* Kanten "likes" gerichtet
Wir möchten jemandem **Freunde empfehlen**. Die Personen, die als Frfeunde empfohlen werden, **sollen Personen sein**, **die** jetzt **Freunde von uns liken!**
**Definiere eine Funktion!**
⇒ Mit **Gremlin.defineStep( "",[Vertex, Pipe]), {})** #"" **{**name der Fuktion**}**
**[Vertex, Pipe] #**anwendbar auf Knoten und Pipe muss explizit angegeben werden
* Zudem **\_().sideEffect{} #**Seiteneffekt wird ausgelöst Variable "start" wird mit "it" (dem aktuellen Knoten, den wir in de rHnad halten) instanziiert! **Diese** können wir **innerhalb** des Ausrucks **wieder verwenden!**
96
Definieren Sie eine Pipe ‚costars‘. Stellen Sie sicher, dass niemand ‚gemeinsam mit sich selbst‘ auftritt, und dass jeder Co-Star nur einmal genannt wird. **siehe Bild**
Bild!
.exept geht auch!
97
Diskutiere die Verwendung von Single-Treaded vs. Multi-Threaded auch in Bezug auf traditionelle Systeme! (OLTP)
Ausführungszeit einer Transaktion meist deutlich \< 1s
**Bei serieller Ausführung (single-Threading)**
* 1)Locking: **nicht benötigt**, weil serielle Ausführung
* #Sicherstellung der Serialisierbarkeit von Transaktionen
* 2)Latches: **nicht benötigt**, weil kein gleichzeitiger Zugriff
* #Schutz von Datenstrukturen vor Problematischen Modifikationen durch verschränkte Verarbeitung
* 3)(optional) MVCC – Multi Version Concurrency Control – erlaubt teilweise das Ignorieren von Locks =\> mehr Parallelisierung möglich
⇒Zusätzlich Mechanismen erzeugen signifikanten Mehraufwand
!!**Traditionelle System nutzen Multi-Threading** um den Durchsatz zu erhöhen
* ⇒Traditionelle Systeme profitieren nicht wirklich von Hauptspeichertechnik aufgrund von Mehraufwand
* loggin,
* locking,
* latchin,
* Pufferverwaltung
98
Wir sind interessiert an dem kürzesten Pfad zwischen Elvis und Bacon. Benutze die im Vorherigen definierte Funktion "costars"
Kürzester Pfad ist in dieser Liste vorne; nur diesen ausgeben.
(elvis. costars.loop(1){
it. loops \< 4 & !it.object.equals(bacon)
}.filter{it.equals(bacon)}.paths \>\> 1)
* **\>\> 1** bedeutet gib mit den ersten Pfad aus(das erste Element), also den kürzesten. Denn die mit .path werden die Pfaden in aufsteigender länge nacheinander ausgegeben
* !it.object.equals(bacon) bedeutet, das das Object bacon im loop selbst nicht auftreten soll!
*
⇒**Problem:** diese Art der Anfrage setzt implizites Wissen voraus.⇒ nämlich, dass die Pfade in geordneter Reihenfolge ausgegeben werden!
99
Gib alle Paare von Freunden aus [Gremlin] mit hilfe von .transform als Array
Beispiel: Alle Paare von Freunden
g.V.outE('friends').transform{[it.outV.name.next(), it.inV.name.next()]}
==\> [Patty, Tom]
==\> [Patty, Alice]
**Erläuterung:** mit g.V.outE('friends') haben wir alle freundes Kanten aller Knoten in der Hand
Nun nehmen wir diese Kante und erstellen folgendes Array**[**name des Knoten von dem die Kante ausgeht, name des Knoten bei dem die Kante eingeht**]**
100
„Alle Personen zusammen mit den Weinen, die sie mögen.“ Also z. B.
[Klemens, [Falanghina]]
[Jean-Luc, [Beaujolais, Bordeaux]]
Hinweis: Benutze .toList()
[Gremlin]
In der Welt stellen anscheinend alle Knoten, die mit einer 'friends' Kante verbunden sind Personen dar
, daher wird mit g.V.both('friends') gearbeitet
⇒ entspricht allen Personen
Lösung:
g.V.both('friends').dedup.transform{ [it.name, it.out('likes').name.toList()]
