Teil 5: Von Chatbots und Wanderern - Was ist Graph Traversal?
Ich habe dir bereits gezeigt, warum es sinnvoll ist, geplante Konversationen als Graph zu speichern. Graphdatenbanken funktionieren grundlegend anders als klassische relationale Ansätze. Nicht nur die Speicherung der Daten ist anders. Auch die Art und Weise, wie du die Daten auslesen kannst, ist besonders.
Eine Möglichkeit Daten aus einer Graphdatenbank auszulesen ist der Graph Traversal Algorithmus in seinen verschiedenen Facetten. Das beherrschen die meisten Graphdatenbanken in mehr oder weniger anpassungsfähigen Ausführungen.
Stell dir ein Netzwerk aus Knotenpunkten vor, die durch gerichtete Linien miteinander verbunden sind. Gerichtet bedeutet, dass die Verbindungen immer eine bestimmte Richtung haben. Also ein Anfang und ein Ende, auf das sie zeigen. Innerhalb der Knoten können Daten abgelegt werden. Auch in den Verbindungen selbst können Daten gespeichert sein.
In dem nachfolgenden Beispiel sind einige der Knoten Fragen und andere Antwortvorschläge. Die Herausforderung ist es nun, Informationen aus diesem Netzwerk zu bekommen.
Innerhalb des Netzwerks gibt es einen Startpunkt. Das ist der Einstieg für unsere Konversation. In der Grafik unten ist dieser rot markiert. Von dort können wir einen sogenannten Traversal-Prozess starten, der den ausgehenden Verbindungen nach und nach folgt. Unterwegs sammelt der Prozess dabei Informationen aus unseren Nodes und Verbindungen ein und liefert uns diese als Ergebnis zurück.
Wandern auf verschlungenen Pfaden
Man könnte sich diesen Prozess auch als eine Art Wanderer vorstellen, der Verbindungen in Form von Straßen folgt. Die Fragen und Antworten, also die Knoten, auf die er unterwegs trifft, sind Kreuzungen mit Wegweisern. Diese geben dem Wanderer Auskunft darüber, von wo er kommt und wohin er noch laufen kann. Jede der Straßen ist dabei eine Einbahnstraße. Der Wanderer kann sie nur in eine einzige Richtung durchlaufen. Das bedeutet, dass die Fragen und alle anderen Knotenpunkte im Netzwerk eingehende und ausgehende Verbindungen haben. Erst wenn der Wanderer zu einer Sackgasse kommt, geht er den Weg wieder zurück, bis er einen Weg entdeckt, den er noch nicht gelaufen ist.
Diese Durchquerung der netzwerkartigen Struktur bezeichnet man auch als Graph Traversal, Path Traversal oder Graph Search. Grundlegend kann man dabei in Depth-first search und Breadth-first search unterscheiden. Bei der ersten Variante folgt der Wanderer den Pfaden immer tiefer in das Dickicht hinein. Bei der zweiten Methode folgt er zunächst allen ausgehenden Straßen einer Kreuzung und geht erst danach weiter in die Tiefe.
Wanderkarten und Wegweiser
Das Spannende daran: Alles spielt sich in nur einem einzigen Query ab. Ich muss die Datenbank also nur einmal fragen und bekomme ein Ergebnis zurück, welches alle gefundenen Knoten, Verbindungen und deren Daten enthält. Das Ergebnis lässt sich unter anderem dadurch steuern, dass du dem Wanderer vorher Regeln mit auf den Weg gibst. Zum Beispiel:
- Folge nicht allen Wegen, sondern nur denen eines bestimmten Typs
- Sammle nur Informationen von bestimmten Knoten
- Gehe maximal x Knoten tief
- Gehe erst in die Tiefe und dann in die Breite
- Lasse bestimmte Knoten aus
- Besuche die ausgehenden Verbindungen in einer bestimmten Reihenfolge
- etc...
Auf diese Weise können wir mit einfachen Regeln definieren, welche Informationen aus dem Netzwerk für uns relevant sind. Dabei spielt es keine Rolle, ob wir 10, 100 oder 1000 Items durchqueren müssen. An dieser Stelle zeichnet sich eine unglaubliche Stärke der Graphdatenbank ab: Wir können die Daten nicht nur realitätsnah abbilden, sondern sie dank der Verbindungen auch genauso unkompliziert auslesen, indem wir sie regelrecht durchqueren.
Ich habe dir hier ein vereinfachtes Beispiel gezeigt, denn es gibt in unserem Netzwerk nicht nur Fragen und Antworten. Es gibt einen komplexen Kontext der durchquert werden muss. Er besteht aus Usern, Konversationen, Fragen, Antwortvorschlägen, Antworten und einigen weiteren Items.
In den nächsten Artikeln erfährst du daher, was ein Logikgraph ist und wie der Wanderer durch logisches Graph Traversal die nächste logische Frage ganz von selbst findet, indem er den Kontext der Konversation durchquert.