Effiziente Datenbankabfrage für Vorfahren auf einem azyklischen gerichteten Graphen

Question

Lassen Sie uns sagen, ich habe einen azyklischen gerichteten Graphen wie eine Familie „Baum“ (nicht wirklich einen Baum, da ein Kind 2 Eltern hat). Ich möchte eine Darstellung dieses Diagramms platzieren in einer relationalen Datenbank, so dass es schnell ist, alle Vorfahren eines Knotens zu berechnen, und alle Nachkommen eines Knotens. Wie würden Sie dieses Diagramm darstellen? Wie würden Sie für alle Nachkommen abfragen? Wie würden Sie Knoten und Beziehungen einzusetzen und entfernen? Welche Annahmen machen Sie über die Daten?

Die beste Lösung die beste große O für die Anzahl der select/insert/delete Aussagen haben Sie zu Abfrage Vorfahren und Nachkommen laufen, mit Bindungen gebrochen durch beste Big O für die Gesamtlaufzeit, mit Bindungen gebrochen durch den Platzbedarf.

Mein Kollege stellte diese Frage an mich. Ich habe eine Lösung, aber es ist exponentielle Größe im schlimmsten Fall so ich, wie andere Leute es lösen würde sehen wollte.

Bearbeiten

Geklärte relationale Datenbank. Diese Frage ist trivial (und langweilig), wenn Sie in transitiv Schließungen Graph-Datenbanken mit integrierten verwenden.

Answer 1

Wenn selects> manipulations und vor allem Unterbaum wählt (alle Vorfahren, alle Nachkommen) ich gehen würde, für einen Closure -table Ansatz. Ja, eine Explosion von Pfaden in Ihrer Pfad-Tabelle, aber es schnell Ergebnisse liefern (wie zum adjacency Modell entgegengesetzt), und hält Updates zu relevanten Abschnitten begrenzt (wie mit verschachtelten Sätzen zu 50% Update gegenüber).

Bill Karwin hat einige schöne Präsentation Online über Vor- und Nachteile der verschiedenen Modelle finden Sie unter http://www.slideshare.net/billkarwin/models-for-hierarchical-data (Folie 48 ist eine Übersicht).

Answer 2

Für DAGs in SQL-Datenbanken erschienen nur zwei Lösungen zu sein:

1. rekursive MIT-Klausel.

2. Transitive Schließung

Ich bin mir nicht bekannt, dass praktisch Graph Kennzeichnungssystem (wie verschachtelte Sätze, Intervalle oder materialisierte Pfad)

Answer 3

"Wie würden Sie dieses Diagramm darstellen?"

• VAR NODES BEZUG {node: sometype} KEY {node};
• VAR KANTEN BEZUG {parentNode: sometype childNode: sometype} {KEY parentNode childNode};
• CONSTRAINT NO_CYCLES IS_EMPTY (Tclose (Kanten) WHERE parentNode = childNode);

"Wie würden Sie für alle Nachkommen abfragen?"

Tclose (Kanten) WHERE parentNode = somevalue;

„Wie würden Sie Knoten und Beziehungen einzusetzen und entfernen?“

• INSERT INTO KANTEN BEZUG {TUPLE {parentNode somevalue chlidNode somevalue}};
• DELETE Kanten, wo deleteCondition;

„Welche Annahmen werden Sie über die Daten zu machen?“

Welche Annahmen gibt es zu machen? Sie haben alles dort angegebenen mit den Worten „gerichteter azyklischer Graph“ angeben ist.

Answer 4

RDBMS: s sind nicht wirklich entwickelt, um diese Art von Daten zu verarbeiten. Die offensichtliche Wahl, anstatt ein Graph-Datenbank zu verwenden ist, dann gibt es keine Notwendigkeit, um die Grafik zu übersetzen in eine andere Darstellung, verwenden Sie ein Diagramm API den ganzen Weg. Es gibt eine gute Präsentation von Marko Rodriguez erklärt, die Auswirkungen des Modells zugrunde liegenden Daten, wenn sie mit Graph Traversierungen tun haben, finden Sie unter der Graph Traversal Programmierung Muster wenn Sie tiefer in das aussehen soll.

Ich schrieb ein einfaches Beispiel bis DAGs mit der Datenbank Neo4j Graph Handhabung eine Weile vor die Ihnen nützlich sein können.

Answer 5

In einer relationalen Datenbank würde ich für jeden Knoten gespeichert werden:

• Vater
• Childs
• Vorfahren

Mit Index für alles und Voll Index auf Vorfahren

Antrag auf:

• alle Vorfahren:
  • O (log n) (Finden Sie den Knoten dann sind Sie fertig)
• alle Nachkommen:
  • O (Vollindexsuche auf Vorfahren) (abhängig von der Datenbank)
• Hinzufügen neuer Knoten / löschen Knoten (ohne Kinder):
  • O (1) für Vater + Vorfahren
  • O (log n) Vater finden
  • update Vaters Childs O (| Vaters Childs |)
• Bewegung Knoten (schwer) :
  • O (1) zu aktualisieren Vater
  • O (log n) finden alte / neue Väter
  • Childs von update Vater zweimal O (| Vaters Childs |)
  • update Vorfahren aller Nachkommen (einfach ersetzen): O (| Nachkommen | * | Tiefe max Baum |) (Tiefe-max: ersetzen und große Reihe von max-Länge (Tiefe-max) erstellen)

Insgesamt Komplexität willdepends von:

• Tiefe des Baumes
• ausgewogen Baum?
• Anzahl der Childs? (In der mittleren, max ...)
• Komplexität des Betriebes in einer gegebenen relationalen Datenbank

Für SELECT nur, effizient, aber schwierig für Updates.

In der Praxis: Arbeiten an RAM-Größe Baum (mit zum Beispiel memchaed, alles im RAM halten), und wenn nicht posssible kauft mehr RAM, des "Köters" Sie Baumes in kleineren Bäumen

.

All-Nachkomme werden viel sowieso kosten, mit Teilbäumen Sie Nachkomme von max-Tiefe D haben können, ohne alle von ihnen zu haben.

Sie „springt“ Form Teilbaum Unterbaum: mehr Anfrage aber schnelle Einsen und bewegt Knoten Art und Weise schneller (nur einen Teilbaum aktualisieren)

.