Teil 10: NOT-Tore und Negationen in Graphdatenbanken

In diesem Artikel möchte ich klären, wie NOT-Logiken in den Logikgraph implementiert werden können und warum diese eigentlich ein logisches Problem für Graph Traversal darstellen.

Die nächste Grafik zeigt einen OR-, AND- und einen NOT-Knoten jeweils in Gelb.

Den ODER-Knoten habe ich dir in einem früheren Artikel bereits erklärt. Hier spielt es nämlich keine Rolle von welcher Richtung der Traversal-Prozess auf den Knoten trifft. Sobald dieser Knoten gefunden wird, darf einfach allen ausgehenden Verbindungen weiter gefolgt werden.

Auch den UND-Knoten habe ich bereits näher erläutert. Trifft der Wanderer auf einen UND-Knoten, muss er zunächst prüfen, ob er vorher schonmal auf diesen Knoten getroffen ist und ob alle anderen eingehenden Wege bereits genutzt wurden.

NOT-Knoten allerdings, stellen auf den ersten Blick ein Problem für den Wanderer dar. Denn die Verbindungen, die von dem in der Grafik gezeigten NOT-Knoten ausgehen, dürfen eigentlich nur genutzt werden, wenn der Traverser den Knoten nicht erreicht hat. Das wiederum bedeutet, dass der Wanderer den ausgehenden Edges nur folgen darf, wenn der Knoten nicht gefunden wurde. Er muss also unbekannt bleiben. Hier liegt also ein logisches Problem vor.

Im vorherigen Artikel habe ich beschrieben, warum es besser ist die Logik in Edges und nicht in Nodes zu speichern. An dieser Stelle kommt ein weiterer Nachteil der Logik-Nodes hinzu. Der Versuch NOT-Tore mit Knoten abzubilden ist logisch nicht möglich.

NOT-Logik in Edges

NOT-Logiken lassen sich aber sehr gut mit Edges beschreiben. Zur Erinnerung: Wir wollen beschreiben, dass den Verbindungen eins bestimmten Nodes nur gefolgt werden darf, wenn ein anderer Node nicht besucht wurde.

Ganz links haben wir eine Conclusion, also eine Schlussfolgerung, die gültig ist, egal welcher eingehende Weg benutzt wird. Die eingehenden Edges sind also ODER-Edges. Die Schlussfolgerung in der Mitte beschreibt durch die beiden roten eingehenden UND-Edges ein UND-Tor. Hier muss der Traversal-Prozess bereits beide eingehenden Edges durchquert haben, damit die Conclusion gültig ist. Die Schlussfolgerung ganz rechts beschreibt nun durch die schwarz markierte NICHT-Edge eine Negation. Nur, wenn diese beim Erreichen des Knotens noch nicht durchquert wurde, ist der Knoten gültig.

Wie du sicher schon bemerkt hast bedarf es aber dennoch einer eingehenden neutralen Edge, die den Knoten überhaupt erst erreichbar macht.