PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-Graph-Datenbank
Ralf Hartmut Guting, Thomas Behr, Holger Helmut Hennings,Fabio Valdes
Fachpraktikum Erweiterbare Datenbanksysteme(WS 2018/19)
Lehrgebiet Datenbanksysteme fur neue Anwendungen
FernUniversitat in Hagen
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 1/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Literatur: https://neo4j.com/
Graph Databases, 2nd EditionNew Opportunities for Connected DataBy Ian Robinson, Jim Webber, Emil EifremPublisher: O’Reilly Media [1]
Graph Databases for Beginners,By Bryce Merkl Sasaki, Joy Chao, Rachel HowardPublisher: neo4j.com [2]
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 2/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Motivation und Einfuhrung
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 3/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Motivation
(native) Graphendatenbanken: Wozu? und Warum?
Nachteil relationaler Datenbanken:
festgelegt auf ein SchemaModellierung und Handling von Beziehungen zwischen DatenDarstellung und Speicherung vernetzter Daten
Vorteil von Graphdatenbanken:
Darstellung und Speicherung vernetzter Datenexplizite Darstellung der Entitaten und Beziehungeneinfachere Modellierung und Wartbarkeit:
”if you can
whiteboard it, you can graph it“vielfaltige Anwendungen: Soziale Netzwerke,Empfehlungssysteme, Verwaltung von Rechenzentren und
Netzwerke, Bioinformatik usw.
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 4/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Property-Graph
gerichteter, markierter, attributierter Multigraph
Knoten stehen fur Entitatengerichtete Kanten beschreiben Beziehungen zwischen KnotenLabel geben Rolle der Knoten bzw. der Kanten an(Knotentypen und Kantentypen)Mehrfachkanten zwischen Knoten nur mit unterschiedlichemBeziehungstypAttribute (Properties) erweitern Knoten und KantenProperties sind bzgl. des Knoten- bzw Kantentyps eindeutig
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 5/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Beispiel Property-Graph Quelle: [1]
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 6/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Anfragesprachen
Gremlin
graph traversal language
imperativ 7→ beschreibt konkreten Weg zur Traversierung desProperty-Graphen
hier: Cypher
deklarativ 7→ beschreibt nur was gefunden werden soll
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 7/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
deklarative Anfragen und deren Auswertung
Eine Anfrage ist eine Beschreibung eines potentiellenTeilgraphen des Property-Graphen der Datenbank
Auswertung der Anfrage: Alle moglichen Matchingszwischen Anfragegraph und Teilgraphen der Graphdatenbankfinden
Ein Matching ist also ein Subgraph des Property-Graphen derDatenbank
Hilfreich zum Auffinden der Matchings: Ankerpunkte
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 8/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Cypher Beispiel
MATCH
(theater: Venue {Name: "Theatre Royal"}),
(newcastle: City {Name: "Newcastle"}),
(bard: Author {Lastname: "Shakespeare"}),
(newcastle)<-[:CITY]-(s)<-[:STREET]-(theater)<-[:VENUE]-(performance)-
[:PERFORMANCE_OF]->(production)-[:PRODUCTION_OF]->(play)<-
[w:WROTE_PLAY]-(bard)
WHERE w.year > 1608
RETURN DISTINCT play.title AS play
Citynewcastle: StreetCITY
VenueSTREET
theater:
ProductionPerfor-mance
Play
VENUE
PERFOR-MANCE_OF
PRODUC-TION_OF
Author
w: WROTE_PLAY
bard:
Name: „Theatre Royal“
Name: „Newcastle“
Lastname: „Shakespeare“
play:
prod: perf:
s:
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 9/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Was wird gesucht ?
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 10/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Cypher Beispiel
MATCH
(theater: Venue {Name: "Theatre Royal"}),
(newcastle: City {Name: "Newcastle"}),
(bard: Author {Lastname: "Shakespeare"}),
(newcastle)<-[:CITY]-(s)<-[:STREET]-(theater)<-[:VENUE]-(performance)-
[:PERFORMANCE_OF]->(production)-[:PRODUCTION_OF]->(play)<-
[w:WROTE_PLAY]-(bard)
WHERE w.year > 1608
RETURN DISTINCT play.title AS play
Citynewcastle: StreetCITY
VenueSTREET
theater:
ProductionPerfor-mance
Play
VENUE
PERFOR-MANCE_OF
PRODUC-TION_OF
Author
w: WROTE_PLAY
bard:
Name: „Theatre Royal“
Name: „Newcastle“
Lastname: „Shakespeare“
play:
prod: perf:
s:
Variable theater kann mit Knoten Venue
mit Name: “Theatre Royal“ gematchtwerden
Variable newcastle kann mit Knoten City
mit Name: “Newcastle” gematcht werden
Variable bard kann mit Knoten Author mitLastname: “Shakespeare” gematcht werden
Anfragegraphbeschreibung
WHERE Klausel: Stucke mussen nach 1608geschrieben worden sein
RETURN Klausel: Name der Stucke (title)
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 11/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Nochmal der Property-Graph Quelle: [1]
ERGEBNIS:play“The Tempest”
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 12/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Property-GraphAnfragesprachen und Auswertung von Anfragen
Aufgabenbeschreibung
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 13/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Ubersicht Aufgabenbeschreibung
Realisierung eines Graphdatenbankprototyp in Secondo mitProperty-Graphen
Darstellung des Property-GraphenVerschiedene Varianten des match-Operators (berechnetMatchings und Ergebnisse der Anfrage)Unterschied der Varianten: Behandlung bzw. Vorgabe vonAnkerpunkten, Eingabeformat des Anfragegraphen
Fernziel: Unterstutzung von Cypher-Anfragen
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 14/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Darstellung des Property-Graphen der Datenbank
Speicherung von Knoten und Kanten in Relationen
Pro Knoten bzw. Kantentyp eine Relation mit Bezeichnungdes entsprechenden Typs
Properties sind abhangig vom Typ eindeutig und bilden dieAttribute der Tupel
Knoten erhalten zusatzlich: NodeId zur Identifizierung
Knoten erhalten zusatzlich: EdgeId zur Identifizierung,Identifier von Start- und Zielknoten
Knoten und Kanten werden relationsubergreifend durchgezahltund die jeweiligen IDs werden eindeutig vergeben
Property-Graph: Relation, die die Namen aller Knoten- undKantenrelationen enthalt
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 15/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
loadprop-Operator
Anfragen sollen aber im Hauptspeicher erfolgen
Main-Memory-Algebra2:let memtestrel = memload(testrel)
Alle Relationen werden in den Hauptspeicher geladen
Realisierung: loadprop-Operator → erzeugt zusatzlich:
Successors: indiziert mit Knotennummern, enthalt fur jedenKnoten Zeiger auf die ausgehenden Kantentupel und derenZielknotentupel, also eine Liste von Paaren (ei , ti), sowie denKanten- und Knotentyp.Predecessors: analog fur eingehende Kanten und derenStartknoten, also eine Liste von Paaren (sj , ej ), sowie dieTypen.Edges: indiziert mit Kantennummern, enthalt fur jede Kantedrei Zeiger auf Startknotentupel, Kantentupel undZielknotentupel, sowie deren Typen
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 16/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Cypher vs. Listendarstellung des Anfragegraphen
MATCH
(theater: Venue {Name: "Theatre Royal"}),
(newcastle: City {Name: "Newcastle"}),
(bard: Author {Lastname: "Shakespeare"}),
(newcastle)<-[:CITY]-(s)<-[:STREET]-(theater)<-[:VENUE]-(performance)-
[:PERFORMANCE_OF]->(production)-[:PRODUCTION_OF]->(play)<-
[w:WROTE_PLAY]-(bard)
WHERE w.year > 1608
RETURN DISTINCT play.title AS play
(
(theater Venue ( (Name "Theatre Royal") ))
(newcastle City ( (Name "Newcastle") ))
(bard Author ( (Lastname "Shakespeare") ))
(theater STREET s)
(s CITY newcastle)
(perf VENUE theatre)
(perf PERFORMANCE_OF prod)
(prod PRODUCTION_OF play)
(bard w WROTE_PLAY play)
)
Citynewcastle: StreetCITY
VenueSTREET
theater:
ProductionPerfor-mance
Play
VENUE
PERFOR-MANCE_OF
PRODUC-TION_OF
Author
w: WROTE_PLAY
bard:
Name: „Theatre Royal“
Name: „Newcastle“
Lastname: „Shakespeare“
play:
prod: perf:
s:
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 17/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Anfragegraph −→ Anfragebaum
Expansion X (v) des Graphen im Knoten v :
Falls v keine Nachfolger hat, ist X (v) der Baum, welcher nuraus v bestehtSeien v1, . . . , vk Nachfolger von v , so ist X (v) der Baum mitder Wurzel v und den Nachfolgern X (v1), . . . .X (vk )Das Verfahren brechen wir ab, wenn Knoten erneut besuchtwerden. Der Baum wird also an diesen Knoten abgeschnitten.
Beobachtung: Ein Tiefendurchlauf durch den Graphenentspricht einem Preorder-Durchlauf durch die Expansion desGraphen, der jeweils in einem bereits besuchten Knoten desGraphen abgebrochen wird.
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 18/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Anfragebaum
Idee:
Wahle Knoten v als Ankerknoten
Berechne X (v)
Tiefendurchlauf des Baums → Matching der Knoten undKanten mit dem DatenbankgraphenDarstellung des Baumes: geschachtelte Liste (v e1 T1 . . . enTn)
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 19/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Anfragegraph vs. Listendarstellung des Anfragebaums
( (theater Venue ( (Name "Theatre Royal") ))
STREET
(s CITY ( (newcastle City ( (Name "Newcastle") )) )
)
VENUE <-
( perf
PERFORMANCE_OF
( prod
PRODUCTION_OF
( play
w WROTE_PLAY <-
(bard Author ( (Lastname "Shakespeare") ))
)
)
)
)
Citynewcastle: StreetCITY
VenueSTREET
theater:
ProductionPerfor-mance
Play
VENUE
PERFOR-MANCE_OF
PRODUC-TION_OF
Author
w: WROTE_PLAY
bard:
Name: „Theatre Royal“
Name: „Newcastle“
Lastname: „Shakespeare“
play:
prod: perf:
s:
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 20/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Der match1-Operator
DBGraph Venue feed filter[.Name = "Theatre Royal"]
match1[
’( (theater Venue ( (Name "Theatre Royal") ))
STREET
(s CITY ( (newcastle City ( (Name "Newcastle") )) )
)
VENUE <-
( perf
PERFORMANCE_OF
( prod
PRODUCTION_OF
( play
w WROTE_PLAY <-
(bard Author ( (Lastname "Shakespeare") ))
)
)
)
)’,
’( ((w Year) > 1608) )’,
’( ((play Title) Play) )’ ]
consume
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 21/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Verbesserung: match2-Operator
Findet Ankerpunkte selbst
Verwendet Listendarstellung des Anfragegraphen
Zwischenschritt: propconvlist2tree-Operator
→ Anwendung des match1-Operators
Hilfreich: In Secondo ist es moglich, dass Operatoren selbstAnfragen durchfuhren und verarbeiten konnen
ExecuteQuery -Methode aus dem QueryProcessor -Modul
Beispiel: relcount2 aus der StandardAlgebra
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 22/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Der match2-Operator
Problem: Wie konnen Ankerpunkte gefunden werden?
Was ist ein guter Ankerpunkt?
Spielt der Ankerpunkt uberhaupt eine Rolle?
→ Dazu ein weiteres Beispiel...
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 23/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Beispiel
DBGraph match2[
’( (author AUTHOR ((Name "Alfons Kemper")) )
(journal JOURNAL ((Name "ACM Transactions on Database Systems")) )
(author WROTE doc)
(doc a APPEARED journal)
)’,
’( ((a Year) > 2015) )’,
’( ((doc Title) Title) ((a Year) Year) )’]
consume
Document
Title
Author
Name
Journal
Name
Keyword
Word
APPEARED
WROTE
KEYWORD
Year
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 24/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Beispiel
Knotentyp Anzahl
AUTHOR 886000
DOCUMENT 3287416
JOURNAL 1640
Kanten −→ ←−
WROTE 22.4 3.6
APPEARED 1.0 7293.3
Document
Title
Author
Name
Journal
Name
Keyword
Word
APPEARED
WROTE
KEYWORD
Year
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 25/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Beispiel
Schatzung der Graphengroße
Beginn bei author (nach Identifizierung des Autorknotens):1.0 ∗ 22.4 ∗ 1.0 = 22.4Beginn bei journal (nach Identifizierung des Journalknotens):1.0 ∗ 7293.3 ∗ 3.6 = 26255.9Beginn bei doc: 3287416 ∗ 3.6 ∗ 1.0 = 11834697.6
→ author ist geigneter Ankerpunkt
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 26/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Verbesserung: match2-Operator
Findet Ankerpunkte selbst
Verwendet Listendarstellung des Anfragegraphen
Zwischenschritt: propconvlist2tree-Operator
ermittelt Statistiken und benutzt diese fur die Wahl derAnkerpunkte
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 27/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Der match2-Operator
DBGraph match2[
’(
(theater Venue ( (Name "Theatre Royal") ))
(newcastle City ( (Name "Newcastle") ))
(bard Author ( (Lastname "Shakespeare) ))
(theater STREET s)
(s CITY newcastle)
(perf VENUE theatre)
(perf PERFORMANCE_OF prod)
(prod PRODUCTION_OF play)
(bard w WROTE_PLAY play)
’),
’( ((w Year) > 1608) )’,
’( ((play Title) Play) )’ ]
consume
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 28/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Der match3-Operator (optional)
DBGraph match3 [
’MATCH
(theater: Venue {Name: "Theatre Royal"}),
(newcastle: City {Name: "Newcastle"}),
(bard: Author {Lastname: "Shakespeare"}),
(newcastle)<-[:CITY]-(s)<-[:STREET]-(theater)<-[:VENUE]-(performance)-
[:PERFORMANCE_OF]->(production)-[:PRODUCTION_OF]->(play)<-
[w:WROTE_PLAY]-(bard)
WHERE w.year > 1608
RETURN DISTINCT play.title AS play’
consume
Compiler: Cypher-Anfrage 7→ geschachteltes Listenformat
Dann: match3 kann auf match2 zuruckgreifen
Cypher-Anfragen mit anonymen Knoten unterstutzen
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 29/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
UbersichtDarstellung des Property-Graphen der DatenbankDarstellungen des Anfragegraphenmatch-Operator Varianten
Ausblicke (optional):
Eingabe eines Graphen im einem zu definierendenListenformat analog zu Cypher-Create Darstellung ([1] S.45),automatische Vergabe von Knoten- und Kantenidentifikatoren
Eingabe des Graphen in Cypher wie in [1] S.45, also Schreibeneines Compilers, der die Listenform erzeugt.
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 30/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Zusammenfassung
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 31/33
PreludeMotivation und Einfuhrung
AufgabenbeschreibungZusammenfassung
Zusammenfassung
Realisierung eines Graphdatenbankprototyp in Secondo mitProperty-Graphen
Darstellung des Property-Graphenloadprop-Operatormatch1-Operatormatch2-Operatorpropconvlist2tree-Operatormatch3-Operator (optional)Ausblicke (optional)
Guting, Behr, Hennings, Valdes Property-Graph Datenbank 32/33