Eine Abfragesprache – Gremlin

Zurzeit gibt es keine standardisierten Graphanfragesprachen, die alle Bereiche und Projekte in diesem Bereich abdecken. Jedoch gibt es im RDF- Bereich SPARQL, eine an SQL angelehnte Abfragesprache, die sich vor allem auf die Beschreibung von Beispielteilgraphen konzentriert, um dann passende Mengen von Statements herauszufiltern. Es gibt aber eine ganze Menge von Graphen die nicht RDF-kompatibel sind und eigene, nicht standardisierte Strukturen benutzen, wie z.B. unser Matrix-Graph und andere domänenspezifische Datenmengen. Andere Initiativen setzen auf JSON-basierte Varianten, wie zum Beispiel MQL, die Anfragesprache für Freebase. All diese Sprachen funktionieren nur auf ihren eigenen Datenmengen und bieten keinen oder sehr wenig Unterstützung für die wirklich interessanten Graphalgorithmen und heuristischen Analysemethoden, die für heutige große Graphen erforderlich sind.

Für die komplexeren und interessanteren Fragen, die direkt auf einem Netzwerk aufsetzen (ohne und mit RDF), ist zurzeit die XPath-orientierte Graphenprogrammiersprache Gremlin in der Entwicklung. Über die Schaffung eines generellen Graphenmodells, das alle Features der bestehenden Modelle und Theorien vereinigt, wurde eine Plattform geschaffen, um darunter unterschiedliche Datenmodellierungen einzuhängen. Zurzeit gibt es schon einige von diesen Implementierungen. Sie reichen vom einfachen in-memory TinkerGraph, über die RDF-SAIL-Schnittstelle für AllegroGraph, Sesame und das ThinkerPop LinkedData SAIL (ursprünglich von Josh Shinavier für die Ripple-Programmiersparche) bis hin zu Neo4j.

Gremlins Syntax basiert auf XPath, um auch tiefe Wegbeschreibungen durch den Graphen gut ausdrücken zu können. Viele einfache Fälle sehen damit im Prinzip wie normales XPath aus.

Für das verwendete Matrix-Beispiel könnte eine Gremlin-Sitzung ungefähr so aussehen (nachdem Gremlin installiert und gremlin.sh gestartet wurde):

1. peterneubauer$ ~/code/gremlin/gremlin.sh
3. \,,,/
4. (o o)
5. -----oOOo-(_)-oOOo-----
6. gremlin> #öffne einen Neo4j Graphen als default ($_g)
7. gremlin> $_g := neo4j:open('tmp/matrix')
8. ==>neo4jgraph[tmp/matrix]
9. gremlin> #Die Knoten mit Eigenschaften
10. gremlin> $neo := g:add-v(g:map('name','Neo'))
11. ==>v[1]
12. gremlin> $morpheus := g:add-v(g:map('name','Morpheus'))
13. ==>v[2]
14. gremlin> $trinity := g:add-v(g:map('name','Trinity'))
15. ==>v[3]
16. gremlin> $cypher := g:add-v(g:map('name','Cypher'))
17. ==>v[4]
18. gremlin> $smith := g:add-v(g:map('name','Agent Smith'))
19. ==>v[5]
20. gremlin> $architect := g:add-v(g:map('name','The Architect'))
21. ==>v[6]
22. gremlin> #Die Kanten
23. gremlin> g:list($cypher,$neo,$trinity)[g:add-e($morpheus,'KNOWS',.)]
24. ==>v[4]
25. ==>v[1]
26. ==>v[3]
27. gremlin> g:add-e($cypher,'KNOWS',$smith)
28. ==>e[3][4-KNOWS->5]
29. gremlin> g:add-e($trinity,'LOVES',$neo)
30. ==>e[4][3-LOVES->1]
31. gremlin> g:add-e($architect,'HAS_CODED',$smith)
32. ==>e[5][6-HAS_CODED->5]
33. gremlin> #Setze Neo als Startknoten ($_) über eine Volltextsuche
34. gremlin> $_ := g:key('name','Neo')
35. ==>v[1]
36. gremlin> #ist das auch Neo?
37. gremlin> ./@name
38. ==>Neo
39. gremlin> #Wie sehen die Kanten aus?
40. gremlin> ./bothE
41. ==>e[0][1-KNOWS->2]
42. ==>e[4][3-LOVES->1]
43. gremlin> #Nimm nur die KNOWS-Kanten
44. gremlin> ./bothE[@label='KNOWS']
45. ==>e[0][1-KNOWS->2]
46. gremlin> #Die Namen von Neo's Freunden
47. gremlin> ./bothE[@label='KNOWS']/inV/@name
48. ==>Morpheus
49. gremlin>
50. gremlin> #Die Freunde der Freunde, 2 Schritte
51. gremlin> repeat 2
52. $_ := ./outE[@label='KNOWS']/inV
53. end
54. ==>v[4]
55. ==>v[3]
56. gremlin> #Und deren Namen?
57. gremlin> ./@name
58. ==>Cypher
59. ==>Trinity
60. gremlin> #Alle Knoten im Graphen mit einer ausgehenden LOVES Kante
61. gremlin> $_g/V/outE[@label='LOVES']/../@name
62. ==>Trinity

Tiefe Algorithmen – Value in Relationships

Das vorstehende Beispiel ist ein sehr naives Szenario. Interessanter wird es bei Algorithmen über große Graphen. Algorithmen wie Eigenvector Centrality und Dijkstra sind hier nicht brauchbar, da sie jeden Knoten im Graphen berücksichtigen müssen. Hier kommen heuristische Konzepte wie Grammar-based Random Walkers und Spreading Activation ins Spiel (Ein guter Artikel dazu von Marko Rodriguez, dem Author von Gremlin, hier). Der Google-PageRank-Algorithmus ist eine solche Heuristik und wird in Gremlin ungefähr so modelliert (hier als Beispiel über den Graphen aller Lieder, Konzerte und Platten der Gruppe Greatful Dead, mit 2500 Schleifen und einem Energieverlust von 15 % in jeder Schleife):

1. $_g := tg:open()
2. g:load('data/graph-example-2.xml')
3. $m := g:map()
4. $_ := g:key('type', 'song')[g:rand-nat()]
5. repeat 2500
6. $_ := ./outE[@label='followed_by'][g:rand-nat()]/inV
7. if count($_) > 0
8. g:op-value('+',$m,$_[1]/@name, 1.0)
9. end
10. if g:rand-real() > 0.85 or count($_) = 0
11. $_ := g:key('type', 'song')[g:rand-nat()]
12. end
13. end
14. g:sort($m,'value',true())

Was uns die folgenden gewichteten Songs gibt:

1. ==>DRUMS=44.0
2. ==>PLAYING IN THE BAND=38.0
3. ==>ME AND MY UNCLE=32.0
4. ==>TRUCKING=31.0
5. ==>CUMBERLAND BLUES=29.0
6. ==>PROMISED LAND=29.0
7. ==>THE MUSIC NEVER STOPPED=29.0
8. ==>CASSIDY=26.0
9. ==>DARK STAR=26.0
10. ==>NOT FADE AWAY=26.0
11. ==>CHINA CAT SUNFLOWER=25.0
12. ==>JACK STRAW=25.0
13. ==>TOUCH OF GREY=24.0
14. ==>BEAT IT ON DOWN THE LINE=23.0
15. ==>BERTHA=23.0

Wie man sieht, spielt Gremlin seine Stärken bei tieferen Analysen aus. Ein anderes interessantes Beispiel, bei dem die unterliegenden Daten direkt aus dem Internet als alleinige Datenquelle gezogen werden, ist ein Empfehlungsalgorithmus für Musik über LinkedData und DBPedia.

Fazit und Ausblick

Sollte dies nicht reichen, kann man natürlich immer der Domäne angepasste Sharding-Grenzen anwenden, ohne deshalb die harten Konzepte von Key Values oder Dokumenten einführen zu müssen. Ob das in einem z. B. Dokumentenmodell resultiert oder man eine "Objektdatenbank" für seine Domäne baut, richtet sich nach dem Anwendungsfall.

Der Code für diesen Artikel liegt hier

Für das ausgezeichnete Feedback und die hilfreichen Hinweise während des Entstehens dieses Artikels möchte ich mich besonders bei Michael Hunger bedanken.