Bereits Kunde? Jetzt einloggen.
Lesezeit ca. 17 Min.

Wie Graph-Datenbanken funktionieren und was sie leisten: Beziehungsfragen


Linux Magazin - epaper ⋅ Ausgabe 7/2020 vom 04.06.2020

One size fits all - das stimmt auch bei der Datenhaltung nicht. Wo der Wert der Daten in den zwischen ihnen bestehenden Beziehungen liegt, da stechen Graph-Datenbanken alle Konkurrenten aus.


Artikelbild für den Artikel "Wie Graph-Datenbanken funktionieren und was sie leisten: Beziehungsfragen" aus der Ausgabe 7/2020 von Linux Magazin. Dieses epaper sofort kaufen oder online lesen mit der Zeitschriften-Flatrate United Kiosk NEWS.

Bildquelle: Linux Magazin, Ausgabe 7/2020

Steuerbetrug, Geldwäsche, Verstöße gegen Sanktionen und noch etliche weitere Straftaten werden den Kunden des panamaischen Offshore-Dienstleisters Mossack Fonseca zur Last gelegt. Die Verbrechen aufgedeckt haben im Jahr 2016 Investigativ-Journalisten von 109 Zeitungen, Fernsehstationen und Online-Medien aus 76 Ländern. Dafür analysierten sie gemeinsam rund 11,5 Millionen geleakte E-Mails, Briefe, Fax-Nachrichten, ...

Weiterlesen
epaper-Einzelheft 5,99€
NEWS 14 Tage gratis testen
Bereits gekauft?Anmelden & Lesen
Leseprobe: Abdruck mit freundlicher Genehmigung von Linux Magazin. Alle Rechte vorbehalten.

Mehr aus dieser Ausgabe

Titelbild der Ausgabe 7/2020 von News. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
News
Titelbild der Ausgabe 7/2020 von Zahlen & Trends. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Zahlen & Trends
Titelbild der Ausgabe 7/2020 von Graph-Datenbank Neo4j enttarnt gefälschte Bewertungen auf Amazon: Digitale Detektei. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Graph-Datenbank Neo4j enttarnt gefälschte Bewertungen auf Amazon: Digitale Detektei
Titelbild der Ausgabe 7/2020 von Einfüheung: In eigener Sache: DELUG-DVD: Fedora 32 und mehr. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Einfüheung: In eigener Sache: DELUG-DVD: Fedora 32 und mehr
Titelbild der Ausgabe 7/2020 von RHEL 8.2: Red Hat Enterprise Linux 8.2 mit umfassenden Neuerungen in allen Bereichen: Auf ins nächste Level. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
RHEL 8.2: Red Hat Enterprise Linux 8.2 mit umfassenden Neuerungen in allen Bereichen: Auf ins nächste Level
Titelbild der Ausgabe 7/2020 von Tooltipps. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
Tooltipps
Vorheriger Artikel
Zahlen & Trends
aus dieser Ausgabe
Nächster Artikel Graph-Datenbank Neo4j enttarnt gefälschte Bewertungen auf Am…
aus dieser Ausgabe

... Gründungsurkunden, Kreditverträge, Rechnungen und Bankauszüge, die später unter dem Namen Panama Papers berühmt wurden. Wichtigstes Werkzeug dieser monumentalen Auswertung war ein Tool der Art, die dieser Beitrag vorstellt: eine Graph-Datenbank. Auf die Details dieses Falls kommt der Text noch einmal zurück.

Beziehungen

Alice mag Bob, der Carol und Dave auf Twitter folgt. Die Straßenbahnlinie 15 fährt vom Max-Weber-Platz über Giesing nach Grünwald. Herr Huber ist der Vorgesetzte von Herrn Meyer und Frau Schulze. Theresa liked das Video, das Mike ihr neulich empfohlen hat. Fahrzeug ist der Oberbegriff von Auto, Motorrad und Lkw. Der Mensch stammt von verschiedenen Frühmenschen und diese letztlich von Menschenaffen ab.

Alle diese Aussagen haben eins gemeinsam: Sie handeln von Relationen, von Verbindungen zwischen Personen oder Sachen, von Beziehungen, von Dingen, für die man intuitiv auf einem Blatt Papier etwas Baumartiges skizzieren könnte. Solche Beziehungen werden in einer Welt, die sich zunehmend vernetzt, in der alles mit jedem zusammenhängt, immer bedeutsamer. Damit ist es sicher auch kein Zufall, dass Beziehungen der Kern der Geschäftsideen von Konzernen sind, die heute zu den teuersten und mächtigsten der Welt gehören - zum Beispiel Facebook oder Google. Im ersten Fall geht es um Relationen zwischen Menschen, die einander kennen, im zweiten um solche zwischen Webseiten, die aufeinander verlinken. Der viel zitierte Page Rank ist das Maß dieser Verbindungen. Vernetzung ist der gemeinsame Nenner dieser Modelle, und Beziehungen sind seine Grundlage. Das gilt im übrigen noch für unzählige andere Anwendungen, in denen Beziehungen die Hauptrolle spielen, sei es bei Kaufempfehlungen, bei Dating-Portalen, beim Erkennen betrügerischer Transaktionen, in der Genetik oder der Logistik und so weiter und so fort.

Unter allen Datenstrukturen eignet sich nun gerade eine für die Darstellung von Beziehungen besonders gut: Graphen. Graph-Datenbanken wiederum können Graphen speichern, erweitern oder verkleinern, updaten und umstellen sowie Fragen zu ihrem Inhalt beantworten. Andere Entwicklungen haben sicherlich mehr öffentliche Aufmerksamkeit auf sich gezogen, aber ein wenig außerhalb des Scheinwerferlichts ist die Trendkurve des Suchbegriffs Graph Database bei Google seit zehn Jahren kontinuierlich gestiegen. Parallel dazu ist eine große Vielfalt solcher Datenbanken entstanden. Dazu gehören originäre wie Neo4j •, verteilte wie Titan •, freie wie Janus-Graph • und proprietäre wie Amazon Neptune • oder solche, die eingeführte relationale oder NoSQL-Datenbanken um die Fähigkeit erweitern, mit Graphen zu hantieren. Ein Beispiel für den letztgenannten Fall ist die Datenbank Datastax Enterprise Graph •, die die Open-SourceDatenbank Cassandra • mit dem ebenfalls freien Graph Computing Framework Apache TinkerPop • zu einem erfolgreichen Produkt kombiniert. Graph-Datenbanken sind heute in weltweit führenden Konzernen so gut wie aller Branchen im produktiven Einsatz, darunter - um nur ein paar Namen aus den Kundenlisten zu zitieren - bei der NASA oder Walmart, bei Siemens oder Google, bei Samsung oder Ebay, bei IBM, Airbnb, Novartis oder Volvo und bei vielen, vielen mehr.

Was sind Graphen?

Wer sich mit Graph-Datenbanken beschäftigen will, dem schadet ein kurzer Crashkurs in Graphentheorie sicher nicht. Diesen Zweig der Mathematik begründete bereits vor fast 300 Jahren der Schweizer Mathematiker Leonhard Euler. Er fand eine Lösung für das sogenannte Königsberger Brückenproblem, das in der Frage mündet, ob es einen Rundgang durch die Stadt Königsberg gibt, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Euler bewies, dass das unmöglich ist. Die möglichen Wege durch die Stadt bilden einen Graphen - auch wenn Euler ihn damals noch nicht so nannte 1.

1 Das Königsberger Brückenproblem: Kann man bei einem Spaziergang alle Brücken genau einmal und nicht öfter überqueren?


Allgemein ist ein Graph ein Gebilde aus Ecken oder Knoten (Vertices) und Kanten (Edges), die die Knoten verbinden. Angewendet auf die Informationsverarbeitung stehen die Knoten immer für ein Element (Person, Sache, Ort, Datum, Organisation, Kategorie und so weiter), und die Kanten repräsentieren die Beziehungen zwischen zwei Knoten. Die Kanten können Pfeile sein, dann heißen sie Bogen, und der Graph ist ein gerichteter Graph oder Digraph (für Directed Graph). Den Kanten können auch Attribute zugeordnet sein -Weglängen etwa oder Kosten - dann spricht man von einem gewichteten Graphen. Ein und derselbe Graph kann oft auf verschiedene Weise dargestellt werden, die äquivalenten Darstellungen heißen dann isomorph 2.

Gibt es eine Darstellung, bei der sich die Kanten nur in den Knoten kreuzen, ist der Graph planar. Das hat beispielsweise eine Anwendung in der Architektur: Bilden die Laufwege zwischen Zimmern einen planaren Graphen, können die Räume in einer Etage liegen - andernfalls müssten sie über mehrere Stockwerke verteilt werden und man bräuchte Treppen.

2 Auf den ersten Blick fällt es nicht ins Auge, aber das ist ein und derselbe Graph in verschiedenen Darstellungen.


Die Anzahl der Kanten, die sich in einem Knoten treffen, nennt man den Grad des Knotens. Der schon erwähnte Euler fand heraus, dass es dann und nur dann einen Weg durch alle Knoten gibt, bei dem sich keine Kante wiederholt (Euler-Kreis), wenn der Grad jedes Knotens eine gerade Zahl ist. Das ist beim Graphen des Königsberger Brückenproblems nicht der Fall 1. Der Mittelwert aller Grade der Knoten eines Graphen ist der sogenannte Branching Faktor. Stellt man alle legalen Zugmöglichkeiten, die sich im Verlauf einer Schachpartie ergeben, als Graphen dar, liegt der Branching Faktor zwischen 31 und 35. Der Schachspieler kann also an jedem Punkt des Spiels im Durchschnitt aus 31 bis 35 möglichen, regelgerechten Zügen wählen. Der Branching Faktor beim Go beträgt 250, weshalb es zum Beispiel wesentlich länger gedauert hat, bis Computer den Menschen im Go übertrafen.

Ein gängiges Optimierungsproblem ist die Veränderung eines Graphen mit möglichst minimalen Eingriffen so, dass ein Euler-Kreis entsteht, die Eulerisierung. Ein Weg, bei dem zwar die Kanten, nicht aber die Eckpunkte mehrfach durchlaufen werden dürfen, heißt Hamilton-Kreis. Ob ein Hamilton-Kreis existiert, ist beispielsweise für alle Abhol- oder Auslieferfahrten von Belang.

3 Ein mögliches Schema eines Twitter-Tweets-Graphen mit LPG.


Eine endliche Folge vom Typ Knoten-Kante-Knoten-… ist ein Pfad. Ist der Startpunkt gleich dem Endpunkt, heißt der Pfad geschlossen, andernfalls offen. Einen geschlossenen Pfad mit verschiedenen Eckpunkten und Kanten nennt man auch Zyklus. Ein einfacher Graph ohne Zyklen ist ein Baum. Ein Verfahren, das eine Route bestimmt, die an jedem Knoten und jeder Kante eines baumförmigen Graphen genau einmal vorbeiführt, ist das sogenannte Traversieren.

Ein Anwendungsbeispiel für das Konzept der Pfade findet sich beispielsweise im Projektmanagement, dessen Abläufe sich als gerichteter Graph darstellen lassen, wobei die Kanten meist mit einer Zeitdauer gewichtet sind. Dann ist es von Bedeutung, denjenigen Pfad zu erkennen, der die Mindestprojektdauer bestimmt, indem er über die längste Kette voneinander abhängiger Schritte führt. Man nennt ihn den kritischen Pfad und die entsprechende Terminplanungsmethode dazu CPM (Critical Path Method). Alle Verzögerungen auf diesem Weg wirken sich unmittelbar auf die Gesamtlaufzeit des Projekts aus.

RDF und LPG

Graphen können für die verschiedensten Dinge stehen: Computernetze, Landkarten, U-Bahn-Pläne, Organigramme, Ablaufdiagramme, Molekularstrukturen, Entscheidungswege, Leiterbahnen, soziale Netzwerke, Stammbäume, Wissensinhalte, Lieferketten und vieles, vieles mehr. Für ihre Kodierung kennt die Informatik mehrere Modelle, darunter das Resource Description Framework (RDF) . und das Labeled Property Graph Model (LPG), das vor einiger Zeit die Datenbank Neo4j einführte.

RDF stammt aus dem Umfeld des Semantic Web, das Daten mit Kontextinformationen anreichern will. RDF beschreibt Graphen als Triple, wobei der erste Teil jedes Tripels, der Ausgangsknoten, das Subjekt ist. Es schließt sich das Prädikat an, das die Kante repräsentiert und die Art der Beziehung näher beschreibt. Am Ende steht das Objekt oder der Endknoten beziehungsweise an seiner Stelle ein einfacher Literalwert. Ein Beispiel, das einen stark vereinfachten Ausschnitt aus einem Beziehungsnetz bei Twitter zeigen könnte, mag so aussehen:

Hans ‑‑folgt Werner
Werner ‑‑folgt Hans
Thomas ‑‑folgt Hans

In Wirklichkeit sind Subjekt, Prädikat und Objekt in RDF allerdings eindeutige URIs (Unified Resource Identifier), die man benötigt, um Informationen aus verschiedenen Quellen mischen zu können. (Die allseits bekannten URLs sind übrigens eine Spezialform der URIs zur eindeutigen Bezeichnung von Internet-Seiten.) Die Elemente eines RDF-Triples, also die URIs, sind reine Verweise - oder einfache Literale im Fall mancher Objekte. Sie haben keine interne Struktur. Ein Vorteil ist ihre Eindeutigkeit.

Eine bibliografische Angabe zur Webseitehttp://www.example. org/ index. html mit Autor, Erstellungsdatum und Sprache könnte damit in RDF zum Beispiel so aussehen wie in Listing 1. Das Beispiel verweist mit dem URIhttp://purl.org/dc … übrigens auf den Metadaten-Standard Dublin Core.

Etwas anders liegen die Dinge bei LPG, hier haben die Knoten und Kanten eine interne Struktur, jeder Knoten (und jede Kante) ist ein eigener kleiner Key-Value-Store und speichert dessen Attribute. Verschiedene Arten von Knoten oder Kanten können eine unterschiedliche Anzahl solcher Schlüssel-Wert-Paare enthalten. Weil die Attribute im Unterschied zu RDF keine Extra-Knoten sind, ist die Darstellung kompakter. Außerdem ist die Abbildung individueller Eigenschaften von Beziehungen und mehrfachen Beziehungen derselben Art zwischen Subjekt und Objekt in LPG einfacher zu beschreiben. Allerdings ist die Bedeutung der frei definierbaren Key-Value-Paare, die an den Knoten und Kanten hängen, nicht in derselben Weise eindeutig definiert, wie das bei RDF mit den URIs der Fall ist. Das beispielhafte Schema für die Speicherung von Twitter-Tweets in LPG könnte so aussehen wie in Abbildung 3.

Graph-Datenbanken

Es gibt sowohl Graph-Datenbanken, die RDF, als auch solche, die Labeled Property Graphs verwenden können. Außerdem kann man die Datenbanken danach unterscheiden, ob es native Graph-Datenbanken sind, die eine speziell für Graphen konstruierte Storage-Engine verwenden, oder nicht native, die die Graphen in irgendeiner Form serialisieren und dann mit einer bewährten relationalen oder NoSQL-Storage-Engine speichern. Beides hat Vor- und Nachteile. So sind native Datenbanken meist schneller, wogegen sich nicht native auf eine lange bekannte, gut verstandene und optimierte Technik stützen.

Ein weiteres Unterscheidungsmerkmal sind die Abfragesprachen. Da sich dafür bislang im Unterschied zur relationalen Welt kein einzelner Standard wie SQL als Favorit etabliert hat, konnte sich eine Anzahl verschiedener Query Languages herausbilden, darunter das weitverbreitete Cypher, das in diesem Artikel verwendete Gremlin, SPARQL, GraphQL und andere. Während Graph-Datenbanken hauptsächlich für die Verarbeitung von Online-Transaktionen zum Einsatz kommen (OLTP, Online Transaction Processing), verarbeiten sogenannte Graph Compute Engines große Batch-Jobs mit GraphDaten (OLAP, Online Analytical Processing).

Beide Techniken eignen sich am besten für Szenarien, in denen es weniger um das Abrufen diskreter Fakten geht als um verbundene Dinge, um Beziehungen. Alles, was sich als Netzwerk oder Baum darstellen lässt, ist ein dankbarer Gegenstand für Graph-Datenbanken. Dazu alles, was mit der Suche nach Mustern oder Hotspots in der Vernetzung zu tun hat. Das sind zugleich die Fälle, die sich im relationalen Modell nur ineffizient und wenig performant abbilden lassen, weil die Beziehungen dort etwa über Joins und besondere Tabellen abgebildet werden müssen und keine speziellen Eigenschaften haben können.

4 Struktur der Beispieldatenbank Modern, die zusammen mit der Gremlin Console ausgeliefert wird.


Erste Schritte

Eine unkomplizierte Möglichkeit für erste Experimente mit einer Graph-Datenbank bietet die Gremlin Console. Gremlin ist die Abfragesprache von Apache TinkerPop, einer Abstraktionsschicht für mehrere Graph-Datenbanken und ‑prozessoren, die mit dem oben beschriebenen Property-Graph-Modell arbeitet.

Gremlin ist deklarativ, was bedeutet, dass das Was beschrieben wird, das Problem, und nicht das Wie oder der Lösungsweg. Außerdem ist es pfadbasiert, was heißt, dass die Abfragen einer Kette von Knoten folgen. Unter anderen können Neo4j, OrientDB, Datastax Enterprise, Hadoop oder Amazons Neptune die Abfragesprache Gremlin verwenden. Manchmal geschieht das parallel zu anderen Abfragesprachen, die sich zuweilen zudem - wie etwa SPARQL - auch in Gremlin-Code übersetzen lassen.

Die Installation der Console ist schnell erledigt, der Anwender braucht auf einem Linux-Rechner nur die aktuelle Version unter • herunterzuladen und zu entpacken. Ist außerdem bereits Java 8 installiert, ist er sofort startklar. Auch eine Datenbank - nämlich das In-Memory-Modell Apache TinkerGraph - ist als Plugin bereits dabei. Und sogar eine Auswahl an Beispieldaten gehört zum Paket.

Die Console startet man aus dem beim Entpacken angelegten Verzeichnis mit bin/gremlin.sh. Eine sehr kleine Beispieldatenbank 4 lässt sich mit dem Befehl aus der ersten Zeile von Listing 2 erzeugen. Er lädt aus dem Unterverzeichnis data/ die Datenbank Modern, die so heißt, weil sie eine modernere Version eines älteren Beispiels mit sechs Knoten und sechs Kanten ist.

Die Datenbank enthält Angaben zu einer kleinen Gruppe von Software-Entwicklern und deren Produkten. Die Entwickler kennen sich teilweise untereinander und trugen teilweise zu denselben Projekten bei. Zusätzlich braucht Gremlin eine sogenannte Traversal Source, die beschreibt, wie es sich durch den Graphen bewegen soll. Am einfachsten benutzt man hier den Standardweg (Listing 2, Zeile 4).

Nun kann man sich schon alle Knoten (g.V()) und alle Kanten (g.E()) ausgeben lassen. Die Abfragen sind generell in Schritten (Steps) organisiert, die durch Punkte getrennt sind. Dabei ist g, wie schon erwähnt, die Traversal Source, und V() ist ein Iterator, der schrittweise alle Knoten durchläuft. Weitere Steps können nun beispielsweise Properties des jeweiligen Knotens ausgeben (.values()) oder ihn auf bestimmte Bedingungen prüfen (.has()).

5 Das River-Crossing-Rätsel als Ablaufdiagramm. Die Kästchen zeigen die Zustände am Ende einer Überfahrt. Ein Weg vom Start- zum Zielpunkt ist eine Lösung.


Zudem lassen sich auch Filterergebnisse aggregieren, was etwa passiert, wenn der Anwender die Datenbank fragt, wie viele Knoten sie von welchem Typ jeweils hat (Listing 2, Zeile 7). Weitere Beispiele für einfache Abfragen demonstrieren die Zeilen 10 bis 28 von Listing 2. Prinzipiell hangelt sich jede Abfrage den Baum entlang. Das lässt sich auf verschiedene Weise beobachten. Zum einen kann man sich die Treffer schrittweise anzeigen lassen - zum Beispiel den ersten Knoten, auf den eine Created-Kante weist (Zeile 31), die ersten beiden (Zeile 34 bis 36) und so weiter.

Alle Treffer auf einmal liefert .to‑ List(), alle Treffer ohne Duplikate .to‑ Set(). Daneben ist es möglich, sich den Pfad ausgeben zu lassen, der durchlaufen wurde, um zum Suchtreffer zu gelangen. Der Aufruf aus der ersten Zeile von Listing 3 beantwortet beispielsweise die Frage, an welchen Software-Projekten der Entwickler Josh beteiligt war.

Bei der folgenden Ermittlung des Pfads (Zeile 5) wird also zunächst der Knoten 4 gefunden, der das Label Person und die Namenseigenschaft Josh hat, und dann werden von da aus die abgehenden Kanten 10 und 11 verfolgt, die beide mit der Property created gekennzeichnet sind, also auf eine Software verweisen müssen. Dabei werden die Knoten 3 und 5 gefunden, die für lop und ripple stehen.

Die nächste Frage lau: „Welches Softwareprodukt hat jemand ganz allein entwickelt?“ In diesem Fall müsste die Gewichtung der Kante created den Wert 1.0 erhalten haben. Der Aufruf aus Zeile 9 liefert die Lösung. Und wer waren der oder die Programmierer, die ein Projekte allein gestemmt haben? In diesem Fall interessieren die Knoten, von denen eine created-Kante mit Gewichtung 1 abgeht (Zeile 12).

Das waren alles einfache Abfragen. Die sogenannten Traversals können aber auch Verzweigungen im Graphen folgen (Branching Traversals), rekursiv abgearbeitet werden (Recursive Traversals), Pfaden folgen (Path Traversals) oder sich auf Teilgraphen beziehen (Subgraph Traversals) und noch einiges mehr. Der schrittweise Aufbau bleibt allerdings immer gleich, und auch die Anzahl der nötigen Kommandos für die Steps artet nicht aus. Dieser Artikel soll sich dennoch mit einfachen Abfragen zufrieden geben.

Nebenbei, wer die Sprache Gremlin auf eigene Faust weiter erkunden möchte: Die Gremlin Console kommt noch mit anderen Beispieldatensätzen, die teils wesentlich umfangreicher sind, wie die Datenbank Grateful Dead. Sie enthält Songs der amerikanischen Rockgruppe Grateful Dead nebst Informationen darüber, wer sie gesungen und komponiert hat und in welcher Reihenfolge sie auf Konzerten und LPs vorkamen. Das macht viele Hundert Knoten und etliche Tausend Kanten und lässt sich zur Gänze kaum mehr übersichtlich visualisieren.

(K)ein Rätsel

Ein Bauer kommt mit einem Wolf, einer Ziege und einem Kohlkopf an einen Fluss. In seinem Boot kann er immer nur entweder ein Tier oder den Kohl mitnehmen. Außerdem darf er weder Wolf und Ziege noch Ziege und Kohl allein an einem Ufer zurücklassen, weil Erstere Letztere fressen würden. Wie bekommt er sein gesamtes Hab und Gut unbeschadet über den Fluss?

Wer das River-Crossing-Rätsel noch nicht kennt und ein wenig knobeln will, der lese nicht sofort weiter. Den anderen sei verraten: Der Bauer schafft zuerst die Ziege auf die andere Seite und fährt leer zurück. Danach holt er den Wolf, nimmt die Ziege aber wieder mit zurück. Nun kann er erst den Kohl und schließlich die Ziege über den Fluss schaffen.

Dieses Prozedere lässt sich als Graph darstellen, bei dem die Knoten die jeweiligen Endzustände einer Überfahrt sind 5. Die Buchstaben BKWZ stehen für Bauer, Kohl, Wolf und Ziege. Der Unterstrich symbolisiert den Fluss. Unerlaubte Zustände sind grün eingefärbt. In jedem Schritt gibt es eine Aktion, mit der der Bauer den soeben erfolgten Transport wieder rückgängig machen würde - die führt ihn allerdings nicht weiter und ist der Übersichtlichkeit halber hier auch nicht mit dargestellt.

Intelligente Zwillinge

Auf den ersten Blick wirkt das befremdlich: Wie soll ein Haus intelligent sein können? Gemeint sind aber weniger seine Mauern als die verbaute Klimatechnik, Heizung oder Beleuchtung, die durch ein Netz vielfältiger Geräte, Sensoren, Service-Protokolle oder Verträge verknüpft ist, ständig überwacht und analysiert wird und kostensparend wie ressourcenschonend bewirtschaftet werden muss.
Wäre es im Licht der Belegungsstatistik günstig, aus dem großen Besprechungsraum A.22 zwei kleine zu machen? In welchen Räumen über 20 Quadratmeter Fläche in Gebäuden ohne Klimaanlage lag die Durchschnittstemperatur im Juli 2019 über 30 Grad? Solche Fragen untersuchen wir bei Siemens unter dem Stichwort Smart Infrastructure. Unser Ziel ist es, über eine halbe Million kommerziell genutzter Gebäude mit Hilfe von cloudbasierten, digitalen Dienstleistungen und Produkten zu smarten Gebäuden zu machen. Dabei dient ein sogenannter digitaler Zwilling als Sammelpunkt für alle Pläne, Verträge, Modelle, Service-Reports oder Sensordaten. Diese Daten stehen auch für Simulationen zur Verfügung oder werden für Fernwartung oder Energieoptimierung verwendet oder fließen in Apps für die Raumbuchung und Navigation im Gebäude ein. Diese Datenflut in einem Modell zusammenzufassen, erfordert eine hoch flexible Datenstruktur. Schon kurz nach Projektbeginn war uns bei Siemens klar, dass eine herkömmliche relationale Datenbank das wegen der Vielfalt an Beziehungen zwischen den Daten nur schwer leisten kann. Auch verschiedene NoSQL-Datenbanken kamen hier an ihre Grenzen, weil sie die Daten nur schwach strukturierten. Die Lösung brachte uns schließlich die Einführung einer Graph-Datenbank. Sie ermöglichte es, die Time-to-Data um gute 30 bis 50 Prozent zu verkürzen. Sie erlaubte dem Kernteam für die Modellierung, sich wieder ganz auf die Weiterentwicklung des Modells zu konzentrieren, statt unnötig lange über der Formulierung übermäßig komplexer Abfragen zu brüten.
In unserem Fall fiel die Wahl auf Amazon Neptune, weil wir mit AWS auf das breiteste Angebot an Services zugreifen und es jederzeit entsprechend unseren Bedürfnissen skalieren können. Zudem können wir bei AWS darauf vertrauen, dass weitere Services, die wir brauchen, kontinuierlich entwickelt werden. Unsere operativen Kosten reduzierten sich ebenfalls.
Welche Erfahrungen haben wir sammeln können? Zum einen eignen sich nicht alle Daten gleich gut für die Graph-Datenbank. Deshalb kann es sinnvoll sein, beispielsweise Zeitreihendaten in einer Spezialdatenbank zu belassen. Zum anderen löst die Graph-Datenbank das Problem allein noch nicht, wenn nicht auch das Datenmodell und die Abfragen angepasst werden. Das wie auch die Formulierung der Abfragen brauchen geschultes Personal. Und schließlich erzielt man den höchsten Nutzen oft erst durch eine geeignete Visualisierung der Abfrageergebnisse. Markus Winterholer
Global Head of Digital Buildings, Siemens

Will man den Graphen in der Datenbank speichern, kann man ihn zur Vorbe- reitung noch etwas vereinfachen, indem man die Rückschritte und die Übergänge zu den unerlaubten Zuständen im Graphen weglässt. Was übrig bleibt, lässt sich direkt in der Datenbank ablegen, und zwar ohne dass man - anders etwa als beim relationalen Modell - zuerst ein Schema entwerfen oder Tabellen definieren müsste. Man könnte nun alle Knoten und alle Kanten interaktiv nacheinander eingeben. Einfacher und weniger fehleranfällig ist es allerdings, den Datenbankinhalt zunächst in einem XML-Format (GraphML) in einem File anzulegen (Listing 4) und dieses File dann in der Gremlin- Konsole mit den Kommandos aus Listing 5 einzulesen.

6 Das Ergebnis einer Suchanfrage in der Datenbank der Panama Papers.


Nun kann man eine Abfrage an dem Knoten beginnen lassen, der die Startposition enthält (BZKW_). Von da an sind alle abgehenden Kanten und eingehenden Knoten so lange zu verfolgen, bis die Abfrage auf den Knoten trifft, der den Endzustand nach der Flussüberquerung darstellt (_BZKW). An dieser Stelle soll die Datenbank den beschrittenen Weg (.path()) ausgeben (im Beispiel sind es zwei gleichwertige Wege). Das ist die Lösung des Rätsels. Die Rückgabe der Datenbank führt die ID des Knotens auf (etwa [1]), gefolgt von der ID der abgehenden Kante (etwa [e11]), gefolgt von einer Beschreibung der Kante mit Startund Zielknoten sowie transportiertem Gut (etwa 1‑mit_Ziege‑>2). Mit dem so erreichten Knoten geht es genauso weiter, bis die Abfrage am Zielknoten angekommen ist.

Das Ergebnis ist in diesem Fall offensichtlich und ließe sich auf den ersten Blick aus dem Graphen ablesen. Würden wir als Graphen aber beispielsweise das Netz des öffentlichen Nahverkehrs in München hinterlegen und nach einer Verbindung zwischen Neuried und Nordbad suchen (mindestens dreimal umsteigen), ist die Aufgabe nicht mehr trivial. Erst recht nicht, wenn die Kanten noch mit Entfernung, Fahrzeit oder Fahrtkosten gewichtet sind und man nach der kürzesten, schnellsten oder billigsten Route forscht. Auch funktioniert die Methode selbst dann, wenn der Graph zu groß ist, um visualisiert und überblickt zu werden.

Aus der Praxis

Jenseits solcher Fingerübungen: Welche Anwendung haben Graph-Datenbanken denn nun in der Praxis? Gibt es plakative Beispiele für ihren vorteilhaften Einsatz? Dieser Beitrag stellt im Folgenden ein paar überzeugende Einsatzmöglichkeiten anhand einiger realer Fallbeispiele vor.

Sagen wir, Frau X ist Angestellte einer Firma Y und wohnt in Z. Sie hat ein unverdächtiges Girokonto bei einer lokalen Sparkasse. Herr A wohnt an genau derselben Adresse und ist bei B als Manager beschäftigt. B hat eine Tochterfirma C, und die unterhält ein Offshore-Konto auf den Cayman Islands. Die Verbindung von Frau X zu diesem Konto ist nur indirekt, doch gerade für das Aufspüren solcher Verbindungen über mehrere Ecken eignen sich Graph-Datenbanken.

Und tatsächlich verwendeten die Reporter des International Consortium of Investigative Journalists (ICIJ) dieses Werkzeug für die monatelange Auswertung der 2,6 Terabyte geleakter Steuerdaten der Panama Papers - wie eingangs erwähnt. Die weit bekannte Open-Source-Graph-Datenbank Neo4j stellt die Daten heute in ihrer online erreichbaren, via Browser bedienbaren Sandbox 6 jedermann kostenlos zum Ausprobieren zur Verfügung •.

Bei der Wissensdarstellung beispielsweise in Gestalt einer Ontologie, also einer formal geordneten Begriffshierarchie, ergeben sich baumartige Graphen. Auch ein sogenanntes semantisches Netz, das ebenfalls Begriffe und ihre Beziehungen untereinander repräsentiert, ist ein Graph.

Innerhalb von Einzelwissenschaften bieten sich unter anderem Abstammungsoder Verwandschaftsverhältnisse in Biologie oder Geschichte als Graphen an. So speichert etwa das Forschungsprojekt Nomen et Gens (NeG) • mehr als 21 500 Einzelbelege über schriftlich belegte Namen und Personen im Kontinentaleuropa der Zeit zwischen 400 und 800 n.Chr. nebst ihrer Verwandschaftsverhältnisse in einer Graph-Datenbank.

Ein anderes Beispiel aus dem wissenschaftlichen Umfeld ist die Standort-, Disziplin-, und Spezies-übergreifende Vernetzung von Forschungsdaten zu Diabetes am Deutschen Zentrum für Diabetesforschung (DZD) im Anfang des Jahres ausgezeichneten Projekt Graphs to Fight Diabetes •. Die Datenbank verknüpft zahlreiche heterogene Daten - unter anderem Messwerte, Daten aus der Grundlagenforschung, aus klinischen Studien oder aus Tierversuchen, Mikroskopaufnahmen, Informationen zu Stoffwechselwegen, Genen oder Proteinen, aber auch Nebenwirkungen und schließlich Publikationsnachweise. Daraus entsteht eine Art Meta-Datenbank. Die Forscher erhoffen sich davon unter anderem, neue Sub-Typen der Erkrankung identifizieren und neue, individualisierte Schritte für Prävention oder Therapie finden zu können.

7 Autoren, Institutionen, Veröffentlichungen und wie sie zusammenhängen: Das zeigt dieser kleine Ausschnitt aus der Graph-Datenbank des DZD.


© Deutsches Zentrum für Diabetesforschung

Die Datenbank umfasst gegenwärtig etwa 2,1 Milliarden Knoten und 3,8 Milliarden Kanten und belegt ungefähr 480 GByte. Derzeit wird sie von rund 450 Wissenschaftlern des DZD genutzt, soll aber noch in diesem Jahr auf andere Zentren der Gesundheitsforschung ausgeweitet werden.

Hilfreich ist dabei in vielen Fällen, dass sich die Beziehungen zwischen den Inhalten visuell darstellen lassen 7. Auf diese Weise lassen sich auch Abfragen zusammenklicken, ohne dass man dafür unbedingt eine der möglichenAbfragesprachen erlernen muss. Im einfachsten Fall genügt es, zwei Knoten zu markieren und mit der rechten Maustaste Find Shortest Path aus dem Kontextmenü zu wählen. Daneben lassen sich aber natürlich auch Abfragen in Cypher oder einer Skriptsprache wie Python oder R programmieren.

Fazit

Wo es vor allem darum geht, Aussagen über Beziehungen zwischen Personen, Sachen, Ereignissen, Zeitpunkten oder Orten zu verarbeiten, sind Graph-Datenbanken ihren relationalen Geschwistern gleich aus mehreren Gründen deutlich überlegen. Der erste Vorteil ist: Sie können die Beziehungen direkt abbilden, statt nur indirekt überJoins.

Ganz besonders Abfragen nach Beziehungsketten, etwa den Freunden meiner Freunde, brauchen in der relationalen Welt rekursive Joins, die sehr komplex und langsam sind. Das gilt um so mehr, je tiefer die Verkettung reicht. Eine Handvoll Ebenen ist genug und eine relationale Datenbank kann eine solche Abfrage nicht mehr performant beantworten. Bei solchen Problemen sind Graph-Datenbanken um Größenordnungen leistungsfähiger.

Ähnliche Nachteile haben übrigens NoSQL-Datenbanken wie Key-Value-Stores oder dokumentenorientierte Datenbanken. Bei ihnen verlagert sich die Datenverarbeitung bei der Abfrage von Beziehungen dann allerdings oft in die Applikation.

Der zweite nennswerte Vorteil entsteht dadurch, dass sich Graph-Datenbanken im Unterschied zu relationalen Datenbanken jederzeit um neue Beziehungen und Knoten erweitern lassen. Dafür muss vorher auch kein starres Schema festgelegt worden sein. Dieser Umstand macht Graph-Datenbanken zudem agiler: Sie passen sich besser einem schrittweisen Ausbau der Programmlogik an. Darüber hinaus erlauben relationale Schemata, wie man sie zum Beispiel im bekannten Entity-Relationship-Modell entwerfen könnte, ausschließlich einfache und unidirektionale Beziehungen, wogegen sie für eine Graph-Datenbank sowohl spezifische Eigenschaften haben dürfen als auch bidirektional ausfallen können.

Die Möglichkeiten, aus diesen Vor-teilen der Graph-Datenbanken Kapital zu schlagen, wachsen in der Gegenwart beständig - aus einem ganz einfachen Grund: Weil sich die Welt immer stärker vernetzt. Der Wert von Daten liegt dadurch häufig nicht mehr allein in ihrer schieren Masse, sondern vor allem in ihren Verbindungen. Graph-Datenbanken sind genau das Mittel der Wahl, um ebendiese Verbindungen darzustellen, um sie abzuspeichern und um sie zuabzufragen. (jlu)

Weitere Infos und interessante Links

www.lm-online.de/qr/44517