Nehmen wir an, ich habe einen azyklischen gerichteten Graphen wie einen Familienbaum (nicht wirklich ein Baum, da ein Kind zwei Eltern hat). Ich möchte eine Darstellung dieses Graphen in einer relationalen -Datenbank platzieren, damit alle Vorfahren eines Knotens und alle Nachkommen eines Knotens schnell berechnet werden können. Wie würden Sie diese Grafik darstellen? Wie würden Sie alle Nachkommen abfragen? Wie würden Sie Knoten und Beziehungen einfügen und entfernen? Welche Annahmen treffen Sie bezüglich der Daten?
Die beste Lösung hat das beste große O für die Anzahl der select/insert/delete -Anweisungen, die Sie für die Abfrage von Vorfahren und Nachkommen ausführen, wobei Bindungen durch das beste große O für die gesamte Laufzeit unterbrochen werden, wobei Bindungen durch Platzanforderungen unterbrochen sind.
Mein Kollege hat mir diese Frage gestellt. Ich habe eine Lösung, aber im schlimmsten Fall ist es exponentiell, also wollte ich sehen, wie andere Leute es lösen würden.
Bearbeiten
Geklärte relationale Datenbank. Diese Frage ist trivial (und langweilig), wenn Sie Graph-Datenbanken mit integrierten transitiven Closures verwenden.
Wenn selects & gt; manipulations , und besonders Unterbaum wählt (alle Vorfahren, alle Nachkommen) Ich würde für eine Closure -Tabelle Ansatz gehen. Ja, eine Explosion von Pfaden in Ihrer Pfad-Tabelle, aber es liefert Ergebnisse schnell (im Gegensatz zum Adjazenzmodell) und hält Updates auf relevante Teile beschränkt (im Gegensatz zu 50% Update mit verschachtelten Sets).
Bill Karwin hat eine schöne Präsentation online über Vor- und Nachteile verschiedener Modelle, siehe Ссылка (Folie 48 ist eine Übersicht).
Für DAGs in SQL-Datenbanken schien es nur zwei Lösungen zu geben:
Rekursive WITH-Klausel.
Ich kenne kein praktisches Diagrammbeschriftungsschema (wie verschachtelte Mengen, Intervalle oder materialisierte Pfade)
RDBMS: s sind nicht wirklich dafür ausgelegt, mit dieser Art von Daten umzugehen. Die offensichtliche Wahl ist, stattdessen eine Graphdatenbank zu verwenden, dann ist es nicht nötig, den Graphen in eine andere Repräsentation zu übersetzen, die Sie verwenden eine Graph-API den ganzen Weg. Es gibt eine gute Präsentation von Marko Rodriguez, die die Auswirkungen des zugrundeliegenden Datenmodells im Umgang mit Graphen-Traversalen erklärt, siehe Das Graph Traversal Programming Pattern wenn du tiefer hinein schauen willst.
Ich habe vor einiger Zeit ein einfaches Beispiel für die Behandlung von DAGs mit der Neo4j Graph-Datenbank geschrieben, die für Sie nützlich sein könnte .
"Wie würden Sie diese Grafik darstellen?"
"Wie würden Sie alle Nachkommen abfragen?"
TCLOSE (KANTEN) WHERE parentNode = somevalue;
"Wie würden Sie Knoten und Beziehungen einfügen und entfernen?"
"Welche Annahmen treffen Sie bezüglich der Daten?"
Welche Art von Annahmen gibt es? Sie haben alles spezifiziert, was zu spezifizieren ist, indem Sie "gerichteter azyklischer Graph" sagen.
In einer relationalen Datenbank würde ich für jeden Knoten speichern:
Mit Index für alles und voller Index für Vorfahren
Anfrage für:
Die Gesamtkomplexität hängt ab von:
Nur für SELECT, effizient, aber schwierig für Aktualisierungen.
In der Praxis: Arbeite am RAM-Baum (mit muddaged zum Beispiel alles im RAM) und wenn nicht möglich, kaufe mehr RAM, von "cur" tree in kleineren Bäumen.
Alle Nachkommen werden sowieso viel kosten, mit Unterbäumen können Sie Nachkommen mit der maximalen Tiefe D haben, ohne alle zu haben.
Sie "springen" von Unterbaum zu Unterbaum: mehr Anfragen, aber schnellere UND Knoten viel schneller bewegen (nur einen Unterbaum aktualisieren).
Tags und Links algorithm database graph family-tree