Beste Datenbankstruktur zum Implementieren eines Graphenbaums

Question

Ich versuche eine Datenbank mit pyramidalen Beziehungen zu entwerfen. Zum Beispiel ist dies meine Daten:

Nun, wie kann ich diese beiden Nummern speichern und ihre Beziehung halten?

---

Zur Zeit habe ich, dass dies wie:

// myTree 
+----+------+--------+ 
| id | node | parent | 
+----+------+--------+ 
| 1 | 8 | Null | 
| 2 | 10 | 8  | 
| 3 | 3 | 8  | 
| 4 | 14 | 10  | 
| 5 | 6 | 3  | 
| 7 | 1 | 3  | 
| 8 | 13 | 14  | 
| 9 | 7 | 6  | 
| 10 | 4 | 6  | 
+----+------+--------+ 

Aber in diesem Fall kann ich nur eine Ebene wählen des Graphen durch eine Abfrage. Während ich den gesamten Zweig für einen Knoten auswählen muss. Foe examle:

$node = 14; 

Erwartetes Ergebnis:

[8, 10, 14, 13] 

Hinweis: Knoten sind einzigartig.

Wie auch immer, wie kann ich die Datenbank so gestalten, dass sie Zugriff auf alle Ebenen nach einer Abfrage hat?

Answer 1

Wenn Sie MÜSSEN in MySQL tun, @philipxy stellte Ihnen einen guten Link zur Verfügung, aber Sie sollten wissen, dass MySQL eine schlechte Wahl für hierarchische/Baumdaten ist.
Andere DBMS wie Oracle, SQL Server und PostgreSQL sind für den Adjazenzlistenansatz etwas besser, da sie zumindest iterative ("rekursive") Abfragen unterstützen.
Für eine gute Passform, empfehle ich Ihnen bei neo4j

Answer 2

Ihre Datenbank-Design einen Blick werden korrekt ist, ist nur Herausforderung, wie aus einzelnen Abfrage Sie alle untergeordneten Knoten erhalten. Dazu können Sie eine benutzerdefinierte Funktion schreiben und diese Funktion aus der Abfrage aufrufen. Inside-Funktion kann eine hierarchische Abfrage oder einen datenbankspezifischen Code schreiben, macht keinen großen Unterschied, da diese Funktion nur aus der Abfrage aufgerufen wird.

Answer 3

Sie möchten vielleicht nested sets betrachten. Ich wusste lange über diese Technik Bescheid, bevor ich sie tatsächlich auf einem funktionierenden System ausprobierte, hauptsächlich weil es sehr wenig darüber geschrieben ist, was positiv ist. Ich war angenehm überrascht über die Leichtigkeit der Abfrage grafischer Informationen, die mit Adjazenzlisten oder anderen Methoden extrem kompliziert sind.

Es hat jedoch Nachteile, die es in einer sehr spezifischen Umgebung nützlich machen: Die Liste muss statisch sein. Das heißt, nach der Erstellung wird die Liste selbst nur sehr wenig gewartet - Bewegung der Knoten zueinander, neue Knoten hinzugefügt oder vorhandene Knoten gelöscht. Dies liegt daran, dass jede Zeile von anderen Zeilen abhängig ist (die von anderen Zeilen abhängig sind usw.). Eine Änderung in der Liste könnte das Aktualisieren aller Einträge umfassen, die in der Liste folgen. Dies ist eine Menge Aufwand für eine kleine Veränderung.

Ich hatte den perfekten Anwendungsfall: die Bildungsstandards aller Staaten, District of Columbia und Territorien der USA. Bildungsstandards ändern sich höchstens einmal im Jahr und die meisten Staaten ändern sie viel seltener. Sobald die Schuljahre beginnen, bleiben jedenfalls die zu diesem Zeitpunkt gültigen Standards für die Dauer gültig. Wenn die Listen zu Beginn des Jahres erstellt werden, ändern sie sich daher erst Anfang des nächsten Jahres.

Stellen Sie sich vor, Sie könnten nach Informationen suchen, die nur im Teilbaum eines beliebigen Knotens des Baums enthalten sind. Absolutes Powah!

Es gab andere gute Verwendungen, die ich nie umgesetzt habe, wie zum Beispiel Schulkataloge, die sich auch zu Beginn des Semesters nur wenig verändern.

Mit "Änderungen" beachte ich, dass ich auf Änderungen verweise, die die Struktur des Baumes manipulieren: Einfügen eines neuen Knotens, Verschieben eines Knotens von einem Ort zum anderen, Entfernen eines Knotens usw. Aktualisierung des Inhalts eines Knotens sind nicht ein Problem.

Beachten Sie auch, dass ich mehrere Wochen hatte, um sich mit der Struktur vertraut zu machen. Sie können einige radikale Abfragen schreiben, aber es dauert eine Weile, um die Vertrautheit mit dem System dazu zu bekommen.

Es mag jetzt nicht Ihren Bedürfnissen entsprechen, aber es würde nicht schaden, ein grundlegendes Verständnis dafür zu bekommen, wann es nützlich werden könnte. Es ist einfach zu mächtig, um es zu ignorieren.