VL 3.2 Graph-Datenbestände – Anfragesprachen Flashcards
[mP] Motifs für bestimmte Sachverhalte formulieren können.
da
[mP] Was ist der Unterschied zwischen Patterns und Templates in der vorgestellten Graph Algebra?
Die Spezifikation der Zusammensetzung erfolgt mittels sogenannter Graphvorlagen (Templates).
Aus einem Pattern (quasi Graph QL Abfrage)
wird ein strukturell neuer Graph erzeugt, den man spezifizieren oder erweitern kann
Siehe Beispiel F38
Temlpate= Aufbau mit 2 Bestandteilen / Gibt vor wie ein Graph aus einem Pattern konstruiert werden soll
Template: == Die Festlegung was passieren soll wenn wir jetzt auf eine zulässige Instanz unseres Musters in einem Graph treffen!!
Parameters:
1#Graph Pattern,
2#Körper: gibt an, wie genau die Zusammensetzung aussieht; nutzt Variablen aus Graph Pattern.
Die Vorgabe wie der auszugebende Graph strukturell beschaffen ist
Pattern wird um Variablen ergänzt und so können wir den Ausgabegraph flexibel konstruieren!
Bild das ich gemacht habe einfügen (wo alles zu sehen ist)
Unterschied deklarative und nicht deklarative Anfrage?
Alle Knotenpaare A und B die innerhalb eines gewissen Abstands von einander liegen ist eine deklarative Anfrage
Ich sage was mich interessiert mache aber keine Aussage darüber wie das Ergebnis konstruiert werden soll
hier: 2 Möglichkeiten –> von A nach B wie unten oder andersrum von B nach A vorgehen!
nicht deklarativ wäre:
Gehe zu Knoten A, mache von dort eine Tiefensuche bis Tiefe=4 und gib alle Koten B die du findest zurück
–> nicht deklarativ weil ich Aussage mache wie das von statten gehen soll
//Vorgehensweise hängt von der Beschaffenheit der Graphen ab:
Bsp. A hat hohen OutDegree –> dann doch liber von B nach A durchhangeln!
Was ist ein Motif?
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
Diese orientieren sich an einer herkömmlichen Grammatik
–> Composition by means of concatenation, disjunction, repetition.
Welche 2 Möglichkeiten gibt es Motifs zusammenzusetzte?
(1) Motif A und Motif B über Kanten verbinden
(2) Knoten und Kanten von Motifs zusammenfallen lassen (mit unify unter Angabe welche Knoten zusammenfallen)
Bsp Bild
Unterschied simple Motif und zusammengesetztes Motif und was ist der Vorteil von zusammeng. Motifs?
Simple Motif nehmen keinen Bezug auf andere Motifs
Zusammeng. Motif nehmnen auf andere Motivs Bezug
–> Vorteil: Übersichtlichkeit, aber noch keine Flexibilität
Wie bekommen wir Flexibilität? Und was ist das external interface?
Siehe Bild!
Wichtig ist die Unterscheidung zwischen dem Teil der immer vorhanden ist und dem Teil der variabel ist!
Wenn wir ein Motif in ein größerers Motif einbauen wollen können wir nur Bezug auf den “blauen” statischen Teil nehmen!
–> das sog. “external interface”
Was könnten Beschränkungen sein?
Cliquen –> Das sind Graphen wo alle Knoten miteinander verbunden sind! Wie spezifizier ich das?
Ich nehme eine bestehende Clique und nehme einen neuen Knoten hinzu –> ich verbinde den neuen Knoten mit allen Knoten der bestehenden Clique
Das wäre eine rekursive Definition von Clique und auf den 1. Blick sieht es so aus als würde es hier auch gehen
Aber: Es muss ein Interface geben, also eine fixe Struktur, auf die ich mich immer beziehen kann.
–> Das ist hier nicht der Fall: Die Menge der Knoten, mit der ich mich verbinden will wächst mit jedem Schritt != kein fixes Interface (kommt immer neue Menge von Knoten hinzu)
D.h das externe Interface hängt davon ab wie groß die bestehende Clique ist
Punkt 1: es geht nicht mit der Motifs allein
Gib ein Beispiel für eine simples Pattern für eine Graph QL Anfrage!
Wie sieht es mit dem Benennung/Verwendung von Variablen im Pattern und im abzufragenden Graph aus?
Verwendung von Variablen im Graph unabhängig ist von der Verwendung von den Variablen im Pattern (so wie in SPAQL)
Aus was besteht ein Pattern in Graph QL?
Ein Pattern besteht (Zusammensetzung) aus einem Motif und einer Menge von Bedingungen P(M, F) M=Motif, F=predicates(Bedingungen)
Wie bildet Fi das Matching ab?
Durch Mapping
Graph Pattern (2) Graph-pattern matching:
A graph pattern P(M, F) is matched with graph G if there is an injection f:V(M) → V(G) s. t.
i. For all e(u, v) E(M): (f(u), f(v)) is an edge in G, and
ii. Predicate Ff(G) holds.
**Formale Def. nicht nötig
Mapping reicht (easy)
Beispiel Bild macht es deutlicher!
Was ist neu zu Graph QL an Graph Algebra?
Graph Algebra
Selektion ist komplizierter: Select Operator brauch als Argument : Motif Pattern und Predicades (Bedingunge)
Neuer Operator, der Bestehende Graphen miteinaner verknüpft
Selection sP(C)
C – Kollektion von Graphen
P – Graph Pattern
Was ist der Kern der Anfragesprache GraphQL?
Wir haben als Teil unserer Anfragemöglichkeit einen Operator den sog. Composition Operator der genau mit diesem Template Tp(G) (Welches die Ausgabestruktur und das Muster(Pattern) enthält) instanziiert sein muss!!
Also im wesentlichen 2 Parameter:
(1) C –> Menge der Graphen, auf die er angewendet werden soll
(2) Tp(G) –> Template, das das Pattern P beinhaltet
Dieser Operator beinhaltet die ganze bis hier hin vorgestellte Funktionalität (Motifs Patterns, Template, Mapping, Ausgabe)
Bild vom Operator Formel einfügen
** Es gibt noch einen weiteren Composition Operator der auf mehrere Graphen angewendet werden kann
Welche Operatoren gibt es noch in GraphQL?
Wir haben eine Algebra bestehend aus mehreren Operatoren
Composition (Kern des Ganzen), Projection, Renaming (Brauch man eig nicht. Das kann auch der Composition Operator), set Operator (Vereinigung von Mengen von Graphen oder Schnittmenge)
Wie sieht es mit der Ausdrucksmächtigkeit der Graph Algebra im Vergleich zu der relationalen Algebra und Datalog aus?
Die Algebra Operatoren der Graph Algebra leisten im Prinzip das Gleiche wie die, der relationalen Algebra wenn wir Rekursion außen vor lassen
bzw. Datalog, wenn wir Rekursion zulassen.
Well known: nonrecursive Datalog == RA
Thus: nonrecursive GraphQL == RA
Wenn sie das kann was die relationale Algebra auch kann:
Selektion Projektion Join Mengenoperationen (Diff=Schnittmenge/Union) und Umbenennung
Dann ist die Anfragesprache relationell vollständig
