Ich habe eine Tabelle, die die Kanten von Knoten x zu Knoten y in einem Graphen enthält.
%Vor%Ich möchte eine (materialisierte) Ansicht erstellen, die die kürzeste Anzahl von Knoten / Hops angibt, die ein Pfad enthält, um von x zu Knoten y zu gelangen:
%Vor%Wie sollte ich meine Tabellen und Ansichten modellieren, um dies zu erleichtern? Ich denke, ich brauche eine Art von Rekursion, aber ich glaube, das ist in SQL ziemlich schwierig. Ich möchte zum Beispiel vermeiden, dass die Clients 10 Abfragen auslösen müssen, wenn der Pfad zufällig 10 Knoten / Hops enthält.
Das funktioniert für mich, aber es ist irgendwie hässlich:
%Vor% Ich bin mir auch nicht sicher, wie gut es bei größeren Datensätzen funktionieren wird. Wie von Mark Mann vorgeschlagen, möchten Sie vielleicht stattdessen eine Graphenbibliothek verwenden, z. pygraph .
EDIT: hier ist ein Beispiel mit pygraph
Ohne Berücksichtigung der Zeit für die Erstellung des Diagramms dauert dies 0,3 ms, während die SQL-Version 0,5 ms benötigt.
Wenn wir uns Marks Antwort genauer ansehen, gibt es einige sehr vernünftige Ansätze, um einen Graphen auch in SQL zu untersuchen. In der Tat sind sie schneller als die dedizierten Bibliotheken in Perl oder Python, da DB-Indizes Ihnen die Notwendigkeit ersparen, das Diagramm zu untersuchen.
Der effizienteste Index (wenn sich der Graph nicht ständig ändert) ist eine verschachtelte Baumvariante namens GRIPP-Index . (Das verlinkte Papier erwähnt andere Ansätze.)
Wenn sich Ihr Diagramm ständig ändert, sollten Sie die verschachtelten Intervalle anpassen Ansatz zu Graphen, in ähnlicher Weise, dass GRIPP verschachtelte Mengen erweitert oder einfach Floats anstelle von Ganzzahlen verwendet (vergiss nicht, sie zu normalisieren, indem du auf numerische und zurück zu floatest, wenn du dies tust).
> Anstatt diese Werte direkt zu berechnen, erstellen Sie eine echte Tabelle mit allen interessanten Paaren und dem kürzesten Pfadwert. Wenn Daten in Ihre Datentabelle eingefügt, gelöscht oder aktualisiert werden, können Sie alle Informationen zum kürzesten Pfad neu berechnen. (Perls Modul Graph ist für diese Aufgabe besonders geeignet, und Perls DBI -Schnittstelle macht den Code einfach.)
Durch Verwendung eines externen Prozesses können Sie auch die Anzahl der Neuberechnungen begrenzen. Die Verwendung von PostgreSQL-Triggern würde zu Neuberechnungen bei jedem Einfügen, Aktualisieren und Löschen führen. Wenn Sie jedoch wüssten, dass Sie zwanzig Punktepaare hinzufügen, könnten Sie warten, bis Ihre Einfügungen abgeschlossen sind, bevor Sie die Berechnungen durchführen.
Tags und Links sql postgresql recursion path graph