reading

1 Einführung: Die Welt ist ein Graph

Wir sind umgeben von einem Netz aus Informationen

Von all den Informationen, die tagtäglich verarbeitet werden, ist ein beträchtlicher Anteil nicht wegen ihres Umfangs interessant, sondern wegen der inhärenten Verknüpfungen, die darin enthalten sind. Denn diese machen den eigentlichen Wert solcher Daten aus.

Verknüpfungen reichen von historischen Ereignissen, die zu Orten, Personen und anderen Ereignissen in Beziehung stehen (und selbst in der heutigen Politik ihre Auswirkungen zeigen), bis hin zu Genstrukturen, die unter konkreten Umwelteinflüssen auf Proteinnetzwerke abgebildet werden.

In der IT-Branche sind es Netzwerke, Computer, Anwendungen und Nutzer, die weitreichende Netze bilden, in denen Informationen ausgetauscht und verarbeitet werden. Und nicht zuletzt stellen soziale Netzwerke (ja, neben den virtuellen gibt es auch noch reale) aus Familien, Kollegen, Freunden, Nachbarn bis hin zu ganzen Kommunen einen wichtigen Aspekt unseres Lebens dar.

Jeder Teil unseres Lebens wird von zahlreichen Verbindungen zwischen Informationen, Dingen, Personen, Ereignissen oder Orten bestimmt. Große Internetfirmen versuchen natürlich, sich diese Informationen zunutze zu machen. Beispiele für großangelegte Projekte in dem Zusammenhang sind der Google Knowledge Graph1 oder Facebook Graph Search2.

Abbildung 1.1: Die Welt ist ein Graph

Vernetzte Informationen und Datenbanken

Wenn diese vernetzten Informationen in Datenbanken abgespeichert werden sollen, müssen wir uns Gedanken darüber machen, wie wir mit den Verbindungen umgehen. Normalerweise werden sie ignoriert, denormalisiert oder zusammengefasst, um in das Datenmodell der Datenbank zu passen und auch Abfragen schnell genug zu machen. Was dabei jedoch verloren geht, ist die Informationsfülle, die in anderen Datenbanken und Datenmodellen erhalten geblieben wäre. Genau in dieser Situation spielen Graphdatenbanken und das Graphdatenmodell ihre Stärken aus. Stark vernetzte Daten fallen in einer relationalen Datenbank sofort durch die schiere Menge an JOIN-Tabellen und JOIN-Klauseln in Abfragen auf (und durch die daraus resultierende schlechtere Abfragegeschwindigkeit).

Abbildung 1.2: Relationale JOIN-Tabelle

Graphdatenmodell

Die mathematische Theorie zu Graphen ist viel älter als man denkt. Leonard Euler begründete sie, als er einen Weg über die sieben Brücken des damaligen Königsbergs finden wollte, ohne eine doppelt überqueren zu müssen.3 Die Mathematik hat sich seitdem sehr ausführlich mit Graphtheorie und Graphalgorithmen befasst. Diese sollen aber nicht der Gegenstand dieses Buchs sein. Hier soll stattdessen praktisches Wissen für den pragmatischen und effektiven Umgang mit vernetzten Daten vermittelt werden.

Graphdatenbanken

Die Kombination aus Management von Graphstrukturen (und damit von vernetzten Daten) und Datenbankeneigenschaften wie Transaktionalität und ACID ist eine neuere Erscheinung. Graphdatenbanken, die dies leisten, sind Teil der NoSQL-Bewegung, die zumeist nicht relationale Datenbanken umfasst. Diese Datenbanken sind größtenteils quelloffen, entwicklerorientiert und mit einem Datenmodell versehen, das bestimmte Anwendungsfälle besonders gut unterstützt.

Graphdatenbanken sind dafür prädestiniert, relevante Informationsnetzwerke transaktional zu speichern und besonders schnell und effizient abzufragen. Das Datenmodell besteht aus Knoten, die mittels gerichteter, getypter Verbindungen miteinander verknüpft sind. Beide können beliebige Mengen von Attribut-Wert-Paaren (Properties) enthalten. Daher wird dieses Datenmodell auch als „Property-Graph“ bezeichnet (Abbildung 1.3).

Jeder hat definitiv schon einmal mit Graphen gearbeitet. Sei es bei der Modellierung für eine relationale Datenbank (ER-Diagramm), beim Skizzieren von Domänenaspekten auf einem Whiteboard/Tafel (Symbole und Linien) oder einfach während der kreativen Sammlung von Informationen (Mindmaps). Graphen sind aufgrund der Einfachheit des Datenmodells und einer besonders leichten Visualisierung gut verständlich und leicht zu handhaben.

Abbildung 1.3: Property-Graph

Aber was ist nun so besonders an Graphdatenbanken? Dieses Kapitel geht näher auf dieses Thema anhand von Neo4j, einer Open-Source-Graphdatenbank ein. Sie ist nativ und in Java implementiert. Nativ bedeutet, dass Knoten und Beziehungen direkt in den internen Datenbankstrukturen als Records in den Datenbankdateien repräsentiert sind. Neo4j nutzt keine andere Datenbank als Persistenzmechanismus, sondern baut auf einer eigenen Infrastruktur auf, die speziell dafür entwickelt wurde, vernetzte Daten effizient zu speichern.

Wie schafft es eine Graphdatenbank, die hochperformante Navigation im Graphen zu realisieren? Das ist ganz einfach: mit einem Trick. Statt bei jeder Abfrage rechen- und speicherintensiv Entitäten immer wieder zu korrelieren, werden die Verbindungen beim Einfügen in die Datenbank als persistente Strukturen abgelegt. So wird zwar beim Speichern ein Zusatzaufwand in Kauf genommen, aber beim viel häufigeren Abfragen der Informationen können die direkt gespeicherten Verknüpfungsinformationen zur schnellen Navigation in konstanter Zeit genutzt werden.

Neo4j repräsentiert Knoten und Beziehungen in seinem Java-API als Java-Objekte (Node, Relationship) und im HTTP-API als JSON-Objekte. In der eigens für Graphen entwickelten Abfragesprache Cypher hingegen wird „ASCII-Art“ verwendet.

Neo4js Abfragesprache Cypher

Was? ASCII-Art? Wie soll das denn funktionieren? Man denke einfach an Kreise und Pfeile auf einer Tafel oder einem Whiteboard, die man zum Diskutieren von Modellen schnell aufzeichnen kann. Das klappt, solange die Datenmengen, die es zu visualisieren gilt, klein genug oder nur konzeptionell sind, richtig gut. Bei größeren Graphen kann es schnell passieren, dass man den Wald vor Bäumen (oder Subgraphen) nicht mehr sehen kann. Aber wir wissen eigentlich, wonach wir suchen. Wir sind an ganz bestimmten Mustern im Graphen interessiert und ausgehend von diesen Strukturen wollen wir Daten aggregieren und projizieren, sodass unsere Fragen beantwortet und Anwendungsfälle abgebildet werden können. In einer Visualisierung können wir diese Muster z.B. mit anderen Farben hervorheben (Abbildung 1.4).

Abbildung 1.4: Graph-Muster im Graph

Aber wie würden wir diese Muster in einer textuellen Abfragesprache beschreiben? Dort kommt die ASCII-Art ins Spiel. Wir „zeichnen“ einfach Knoten als geklammerte Bezeichner und Beziehungen als Pfeile aus Bindestrichen (ggf. mit Zusatzinformationen wie Richtung oder Typ). Attribute werden in einer JSON-ähnlichen Syntax in geschweiften Klammern dargestellt (Abbildung 1.5).

Abbildung 1.5: Graph-Muster als ASCII-Art

Viel klarer wird das mit einem Beispiel, hier aus der Domäne der Filmdatenbanken:

(m:Movie {title: "The Matrix"})
<-[:ACTED_IN {role:"Neo"}]-
(a:Actor {name:"Keanu Reeves"})

Der Schauspieler (Actor) "Keanu Reeves" spielte im Film (Movie) "The Matrix" die Rolle "Neo".

Mit dem Inhalt dieses Buchs wird es ganz leicht sein, die ersten Schritte mit Cypher zu machen. Weiterführende Informationen sind in der Referenz verlinkt.

Wir verstehen Cypher als eine „menschenfreundliche“ Abfragesprache, die auf Lesbarkeit und Verständlichkeit optimiert ist. Man stellt dar, an welchen Mustern/Strukturen man im Graphen interessiert ist und welche Operationen, Filter, Aggregationen, Sortierungen usw. man anwenden möchte.

In Cypher wird, ähnlich wie in SQL, deklarativ die Frage dargestellt, die man beantworten möchte, und keine imperative, programmatische Anweisungsabfolge vorgegeben. Trotzdem ist Cypher viel mächtiger als SQL, wenn es um die Darstellung komplexer Beziehungen, Pfade oder Graphalgorithmen geht. Weitere Highlights sind die angenehme Arbeit mit Listen (filter, extract, reduce, Quantoren), das Verketten von mehreren Teilabfragen und die Weiterleitung von (Teil-)Ergebnissen bzw. Projektionen an nachfolgende Abfragen. Dazu später mehr.

Cypher kann nicht nur komplexe Anfragen einfach darstellen und schnell ausführen, sondern auch Daten und Strukturen im Graphen erzeugen, modifizieren und korrigieren (Listing 1.1).

// Erzeugt einen Film mit der gesamten Besetzung in 
// einem Zug
// Benutzt Parameter wie in Prepared-Statements
CREATE (movie:Movie {title:{movie_title}})
FOREACH (a in {actors} : 
  CREATE (:Actor {name:a.name})
         -[:ACTS_IN {role:a.role}]->(movie))

// Findet die Top-10-Schauspielerkollegen von Keanu Reeves
MATCH (keanu:Actor)-[:ACTS_IN]->()<-[:ACTS_IN]-
(co:Actor)
WHERE keanu.name="Keanu Reeves"
RETURN co.name, count(*) as times
ORDER BY times DESC
LIMIT 10

Listing 1.1

Cypher ist der schnellste Weg, um mit Neo4j produktiv zu werden und funktioniert in allen angebotenen APIs: sowohl dem HTTP-API des Servers und dem eingebetteten Java-API sowie natürlich auch mit der interaktiven Entwicklungsumgebung im Neo4j-Browser und der Neo4j Shell.

Um mit Neo4j zu interagieren, kann man sich einfach einen Treiber in der Lieblingsprogrammiersprache4 aussuchen und benutzen.

1 http://www.google.com/insidesearch/features/search/knowledge.html

2 http://www.facebook.com/about/graphsearch

3 http://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem

4 http://neo4j.org/drivers