Prüfungsfragen aus Protkollen [Ausstehend] Flashcards

Question 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?

Question 2

Q

Wie funktioniert die Transformation von horizontal nach vertikal? Was passiert, wenn man eine Zeile hat, die nur NULL-Werte enthält?

Question 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

Answer

A

Siehe Bild

Übrigens Projektion ist das Gleiche wie v2h mit entsprechenden Attributen

Question 4

Q

Was für Probleme gibt es bei der Erzeugung von der horizontalen Sicht aus einer vertikalen Sicht?

Answer

A

**Man muss viele Leftjoins durchführen, wenn man die ganze horizontale Tabelle haben will

Question 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!!

Answer

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

Question 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?

Answer

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
1. Negation ist nicht-monoton: Eine Vergrößerung der Eingabemenge verkleinert die Ausgabemenge und das nicht in Datalog erlaubt ist, da Datalog monoton ist!
2. 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.

Question 7

Q

Was ist Oszillation, Warum taucht sie auf? Was ist ein Abhänigkeitgraph Wie kann man Ozillation beseitigen?

Question 8

Q

Was ist Relationale Algebra? Was ist Relationale Vollständigkeit?

Answer

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

Question 9

Q

Wie unterscheidet sich Datalog von relationalen Kalkülen, relationaler Algebra, Prolog, SQL?

Answer

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.

Question 10

Q

Warum beschäftigen wir uns mit Datalog, gegeben dass wir relationale Anfragesprachen schon kennen?

Answer

A

Rekursion ist möglich!

Question 11

Q

[mP] Was bedeutet modelltheoretische/ beweistheoretische Semantik von Datalog Programmen? Unter welchen Umständen können diese Betrachtungsweisen sich im Ergebnis unterscheiden?

Answer

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.

Question 12

Q

Was ist Stratifikation? Warum ist dieses Konzept im Kontext von Datalog bedeutsam?

Answer

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!!

Question 13

Q

Ist Negation grundsätzlich erlaubt in Datalog? Wie kann es zugelassen werden?

Answer

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.

Question 14

Q

Wozu kann Negation führen? Zeigen sie ein Beispiel!

Answer

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!

Question 15

Q

Wie können wir denn nach Mustern in Graphen suchen? Also zum Beispiel diese Dreieck?

Answer

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

Question 16

Q

Stellen sie mal einen Join mit Datalog dar! Mit Student(MatrNr, Name) und Prüfung(MatrNr, Note) –> Name und Note ausgeben

Answer

A

Einfach mit Komma getrennt !

Ergebnis(Name, Note) :- Student(MatrNr, Name), Prüfung(MatrNr, Note)

Question 17

Q

Stellen sie mal Selektion mit Datalog dar! –> x>100 in R(x,y) (Mit 2 Bedingung AND/OR y=’some string’ )

Answer

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’

Question 18

Q

Stellen sie mal Union mit Datalog dar!

Answer

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)

Question 19

Q

Stellen sie mal Projektion mit Datalog dar! R(A,B.C) und ich möchte das B wegprojezieren!

Answer

A

S(A,C) :- R(A,B,C) .

Question 20

Q

Warum ist ein external Interface bei Motifs nötig?

Answer

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

Question 21

Q

Schreiben Sie mal das Muster für einen Pfad beliebiger Länge auf und mal einen Cycle! Und was beinhaltet diese Muster?

Answer

A

Das Muster beinhaltet Rekursion

Warum muss die Export Klausel dazu?

siehe tonspur

Question 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!

Answer

A

Komplexe Motifs

Concatenation (keine Flexibilität)
1. by edges
2. by unification
Disjunction. (Flexibilität - common part’ – here shown in blue.)
Repetition

Beispiele im Bild

Question 23

Q

Motifs ist keine vollständige Anfragesprache was fehlt noch? Schreibe Beispiele zu den fehlenden Bestandteilen auf!

Answer

A

Ich möchte zum einen noch bestimmte Bedingungen an einzelne Elemente des Graphen stellen (z.b Knoten1.name=”A” oder Knoten2.year > 2000)
1. 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.
1. 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!

Question 24

Q

Was ist denn der Abhänigkeitsgraph und was sind die Knoten und die Kanten?

Male den Abhänigkeitsgraph für dieses Beispiel!

Answer

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.

Question 25

Q

Wie können wir das Beispiel abändern damit es kein Problem mit der Negation gibt?

Answer

A

-Q(X) aus P(X) entfernen!

Ausführung siehe Bild

Question 26

Q

Erkläre die Schritte und Führe Stratifikation an folgendem Beispiel aus!

Answer

A

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:

Abhängigkeitsgraph aufstellen und auf Zykel prüfen/ ggf. Abbruch siehe oben!
Alle Knoten die eine ausgehende Kante mit Negation haben weglassen
Alle Knoten, die von den eben gelöschten Knoten abhängen ebenfalls entfernen
Der Rest, der übrig bleibt ist unser Stratum 0, welches zuerst berechnet werden muss
Stratum 1 sind dann die gelöschen

Lösung im Bild

Question 27

Q

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?

Answer

A

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?“

Question 28

Q

Welche Zentralitätsmaße kenne Sie? Klassifizieren sie diese!

Answer

A

Lösung –> Bild

Question 29

Q

Was ist Betweennes Centrality? Formel angeben und erklären wann ein großer/kleiner Wert angenommen wird!

Answer

A

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!

Question 30

Q

Wann ist Betweenness Centrality maximal/minimal?

Answer

A

(*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

Question 31

Q

Was ist Proximity Prestige? Beschreibe auch wann es minimal/maximal wird (anhand der Formel)

Answer

A

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

Question 32

Q

Wann sind die Ergebnisse von Betweenness und Proximity Prestige unterschiedlich?

Answer

A

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

Question 33

Q

Welche Vorteile hat es Zentralitätsmaße direkt in die Anfragesprache zu integrieren?

Answer

A

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

Question 34

Q

Warum ist in Datalog Negation grunsätzlich nicht erlaubt?

Answer

A

Es ist grundsätzlich nicht erlaubt, auf Grund der nicht-Monotonizität!

s kann zu Oszillation kommen!

Question 35

Q

Kommt es bei Negation in Datalog immer zu Oszillation?

Answer

A

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!

Question 36

Q

Haben wir in relationaler Algebra Negation

Answer

A

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)

Question 37

Q

Vergleichen sie mal Datalog mit relationaler Algebra!

Answer

A

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!

Question 38

Q

[mP] Was ist Zusammenhang zwischen Aggregation und Nicht-Monotonizität?

Answer

A

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).

Question 39

Q

Geht so etwas auch in Datalog -> S(X) :- -R(X) ?

Answer

A

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!

Question 40

Q

Was ist die Monotonie-Eigenschaft?
[grüne Frage] Welcher Operator der relationalen Algebra ist nicht monoton?
Ist Datalog monoton?

Answer

A

monoton := Vergrößerung des Inputs (einer Anfrage/eines Operators) verkleinert nicht den Output.
Mengendifferenz
Ja, Datalog ist monoton. (Keine Negation in Rümpfen von Regeln erlaubt.)

Beispiele siehe Tonspur

Question 41

Q

Wir haben in der Vorlesung 2 verschiedene Graph Frameworks kennen gelernt. Wie unterscheiden die sich?

Answer

A

Vertex-centric (Giraph Framework)⇒ (machen im moment alle (2016))
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 dem 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.

Question 42

Q

Was bleibt bei der Stratifikation übrig, wenn sie nicht funktioniert?

Answer

A

Es können Knoten und Kanten übrig bleiben!

?? Bei Negation in Zykeln würde der Algo eh nicht ausgeführt ??

Question 43

Q

Aus was ist ein Typsystem aufgebaut?
Warum ist ein Schema eigentlich ein Typ?

Answer

A

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
Das nämlich gesagt wird, welche Zustände zulässig sind.

Question 44

Q

Für was kann man Graphen (ganz allgemein) kann man Graphen einsetzten?

Answer

A

Darstellung von z.B.:

#Soziale Netzwerke (SN),
#Web Graphen, 
#Chemische (Struktur-) Formeln, 
#(Schematische) Karten (Netzpläne),
#Prozess- und Programmausführungen.

Question 45

Q

Warum verwenden wir Graphen und nicht ein relationales Modell?

Answer

A

Je eine Relation für Knoten (V) und Kanten (E).

Personen(Person,Attr1, Attr2, …)
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!

Question 46

Q

Was muss Anwendungsentwickler noch tun, wenn er Giraph Giraph++
einsetzt, und was wird ihm abgenommen?

Question 47

Q

Inwieweit ist Giraph++ gegenüber Giraph eine Verbesserung?

Answer

A

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

Question 48

Q

Geben sie mal ein Giraph Beispiel und der Kommunikation der Knoten!

Answer

A

Bild und Ton!

Question 49

Q

Geben sie mal ein Beispiel für einen Partitonierten mit 2 Partitionen und erklären sie das!

Question 50

Q

Schreiben Sie mal die Formel für den PageRank auf und erklären Sie!
Wofür ist der erste Summand der Formel und was ist der Damping-Factor?

Answer

A

(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

Question 51

Q

Welche Schwierigkeiten gibt es bei der Speicherung von E-Commerce Daten im relationalen Modell?

Answer

A

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

Question 52

Q

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?
Was ist das Problem, wenn ich in der horizontalen Repräsentation unterschiedliche Typen habe

Answer

A

Physische Speicherung folgendermaßen! (Logische sicht bleibt Horizontal)

Logische horizontale Sicht auf vertikale Repräsentation (oder Binär = collum store)
Lösung: unterschiedliche vertikale Relationen pro Typ!

Question 53

Q

Was ist wenn ein Tupel nur NULL-Werte besitzt? Wie geht man damit in der vertikalen Repräsentation um?
Von welchem Typ ist das Val Attribut der vertikalen Relation?

Answer

A

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!

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
Wir können es in einer seperaten Relation speichern (nur für diese Fälle)
Das generischste, das es gibt, also das, welches am meisten umfasst!

Question 54

Q

Was versteht man unter Higher Order View?
Was unter Enablement Layer?

Answer

A

High Order View ⇒ Inhalt der vertikalen Relation Bestandteil des Schemas der horizontalen Relation und umgekehrt!!
Enablement Layer ⇒ 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

Question 55

Q

Was ist mit Erweiterung der Algebra, Rewritings gemeint

Question 56

Q

[A] v2h Aufschreiben und kurz Erklären!

[B] Warum Left Outer Join und nich (outer)Join

Answer

A

[A] v2h

Wir gehen Spaltenweise vor!

Anm: Projektion ist Mengenwertig und entfernt Duplikate

Schritt: Dupplikate 1 Spalte in V mit Projektion eliminieren π_{<strong>Oid(V</strong>)}
Schritt: Outer-Left-Join mit Projektion_Oid,Val des 1. Attributs. Also: σ(Key=A1(V))
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

es gibt keinen LOJoin mit Iteration und laufindex K (Phantasie-Operator)
benötigter String-Manipulation um A[1], A[2], A[3]… an A[i] anzuhängen gibt es nicht
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!

Question 57

Q

h2v Aufschreiben und kurz Erklären!

Answer

A

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))
Analog für weitere Attribute A2,A3,…
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!

Question 58

Q

Was ist Rewriting?

Answer

A

Rewritings (1)

Implementierung der Operatoren der relationalen Algebra.

⇒Input in vertikaler Repräsentation, Ergebnis in horizontaler Repräsentation.

Question 59

Q

Was muss ich tun, wenn ich in der horizontale Relation alle Oid Einträge mit A3=4 suchen möchte?

Answer

A

Ich müsste ein Rewriting machen

Horizontale Anfrage wäre ⇒ π_Oid(σ_A3=4(H))

in Vertikal ⇒ π_Oid(σ_Key=A3^Val=3(V))

Question 60

Q

Beschreiben Sie bitte was ein R-Baum ist!

Was bedeuten Überlappungen der Rectangles?

Answer

A

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)

Question 61

Q

Was für ein Problem mit R-Bäumen gibt es in hochdimensionalen Räumen?

Was wäre eine Lösung des Problems?

Answer

A

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

Mehrdimensionale Indexstruktur ist problematisch
1. ⇒ verwende eindimensionale Struktur, z.B. iDistance
Brauchen wir überhaupt immer exakte Ergebnisse?
1. ⇒ Approximate Nearest Neighbour via z.B. Locality Sensitive Hashing

Question 62

Q

Wie führt man eine kNearest Neighbour Anfrage in einem R-Baum durch?

Answer

A

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

Schritt: Priority Queue erzeugen und bei der Wurzel einsteigen. Also erster Zustand der Queue ist die Wurzel und sonst nichts
Schritt: Entnehme das erste Objekt aus der Queue und betrachten statt dessen die Kinder
Schritt: Ordnen die Kinder gemäß ihres geringsten Abstandes in die Queue ein

noch beenden!

Question 63

Q

Wie löst iDistance das beim R-Baum vorliegende Problem? (Viele Überlappungen bei vielen Dimensionen)
Welche Partitionierungs-Ansätze gibt es bei iDistance?

Answer

A

Teil1 Vorgehen des Partitionieren in 3 Steps iDistance

Im ersten Schritt wird der hochdimensionale Datenraum in einen Satz von Partitionen aufgeteilt.
Im zweiten Schritt wird für jede Partition ein Referenzpunkt festgelegt. O0, O1, . . . ,
Im dritten Schritt werden schließlich alle Datenpunkte in einem eindimensionaldargestellt

Teil2 Möglichkeiten

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
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

Question 64

Q

Wie funktioniert eine kNN-Anfrage bei iDistance?

Answer

A

Beobachtung:

alle kNN von q (Query) liegen im
Raumsphere(q; r*) wobei der Abstand zum amweitesten entferntenNearest Neighbourkleiner r* ist!

*Problem**: r* unbekannt
*Idee**: finde r* iterativ

Schritt: Man legt einen Query Punkt in den Raum und startet mit kleinem Radius r an.
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

Answer 59

A

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

Answer 60

A

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

Answer 61

A

Schema hier lediglich Attribute, keine Integritätsbedingungen.

Answer 62

A

Bild Meine Lsg

Answer 63

A

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.

Answer 64

A

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

Answer 65

A

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

Answer 66

A

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.

Answer 67

A

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.

Answer 68

A

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

Answer 69

A

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.

Answer 70

A

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!

Answer 71

A

Kurzübersicht

2 Technologien für das Arbeiten mit Datenbanksystemen

https://www.youtube.com/watch?v=Zd4VK3gHYs0

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

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

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.

Answer 72

A

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

Answer 73

A

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

Answer 74

A

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

Answer 75

A

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)

Answer 76

A

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)

Zeilenorientierte Speicherung (row store)Alle Tupel (mit ihren Attributen) sequentiell auf Seiten gespeichert
- - Gut: Schreiboperationen / Tupelzugriff (mehrere Attribute)
- - Schwierig: cold data bei Attributzugriffen (Aggregationen etc.)
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)

Answer 77

A

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

Answer 78

A

Protokoll: Entweder nochmal page copy mit anschließendem merge oder einfach sequenziell

–> Dann illustriert warum OLAPs nur auf den älteren Daten arbeiten können.

Answer 79

A

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

Answer 80

A

Grundsätzlich gibt es zwei Ansätze

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.)
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:

Jeder Zugriff auf l_shipdate Attribut eines Tupel resultiert in großer Menge nicht benötigter Daten im Cache
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

Answer 81

A

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!

Answer 82

A

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.

Answer 83

A

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!

Answer 84

A

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!

Answer 85

A

⇒ 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!

Answer 86

A

Bild!

.exept geht auch!

Answer 87

A

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

Answer 88

A

Kü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!

Answer 89

A

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]

Answer 90

A

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()]

Brainscape's Knowledge GenomeTM

Prüfungsfragen aus Protkollen [Ausstehend] Flashcards

Brainscape's Knowledge Genome^TM