Wie viele SQL-Abfragen brauche ich?

Question

Ich habe eine Datenbanktabelle (sqlite) mit Elementen, die eine Baumhierarchie bilden. Jeder Artikel hat ein Feld id (für sich selbst) und ein parentId für seine Eltern. Wenn ich nun einen Gegenstand bekomme, muss ich die gesamte Kette von der Wurzel zum Gegenstand zurückholen.

Grundsätzlich ist der Algorithmus in Pseudo-Code wie folgt aussieht:

1. Cursor Artikel ist
2. parentItem von parentId für Cursor abrufen
3. wenn parentItem nicht rootItem ist, dann Cursor = parentItem und gehe zu 2.

Also muss ich eine SQL SELECT-Abfrage für jedes Element durchführen.

Kann die gesamte Kette rootItem -> ... -> item abgerufen werden, indem nur eine SQL-Abfrage ausgeführt wird?

Answer 1

Nicht mit ANSI-Standard SQL ist es nicht, nein. Nun, das stimmt nicht ganz. Sie können linke Outer-Joins ausführen und genug einbringen, um die wahrscheinliche maximale Tiefe abzudecken. Wenn Sie jedoch die maximale Tiefe nicht beschränken und so viele Joins einbeziehen, wird dies nicht immer funktionieren.

Wenn Ihre Reihe von Zeilen ausreichend klein ist (sagen Sie weniger als 1000), rufen Sie sie alle nur ab und dann herausfinden. Es wird aller Wahrscheinlichkeit nach schneller als Single-Read-Traversal sein.

Sie könnten die Parent Traversal parsen. Haben Sie eine Abfrage wie:

SELECT t1.id id1, t1.parent parent1, 
     t2.id id2, t2.parent parent2, 
     t3.id id3, t3.parent parent3, 
     t4.id id4, t4.parent parent4, 
     t5.id id5, t5.parent parent5 
FROM mytable t1 
LEFT OUTER JOIN mytable t2 ON t1.parent = t2.id 
LEFT OUTER JOIN mytable t3 ON t2.parent = t3.id 
LEFT OUTER JOIN mytable t4 ON t3.parent = t4.id 
LEFT OUTER JOIN mytable t5 ON t4.parent = t5.id 
WHERE t1.id = 1234 

und erweitern Sie es auf welche Nummer Sie wollen. Wenn das zuletzt abgerufene übergeordnete Element nicht null ist, befinden Sie sich noch nicht an der Spitze der Struktur. Führen Sie die Abfrage daher erneut aus. Auf diese Weise sollten Sie es hoffentlich auf 1-2 Runden reduzieren.

Darüber hinaus könnten Sie Möglichkeiten zur Codierung dieser Daten in der ID suchen. Dies wird nicht empfohlen, aber wenn Sie beispielsweise jeden Knoten auf 100 Kinder beschränken, können Sie sagen, dass der Knoten mit der ID 10030711 den Pfad 10 -> 03 -> 07 -> 11 hat. Das hat natürlich andere Probleme (wie max ID Länge) und natürlich ist es hacky.

Es ist auch erwähnenswert, dass es zwei grundlegende Modelle für hierarchische Daten in SQL gibt. Adjazenzlisten und verschachtelte Sets. Dein Weg (der ziemlich häufig ist) ist ein Adjacency-Set. Verschachtelte Mengen würden in dieser Situation nicht wirklich helfen und sie sind kompliziert, um Einfügungen auszuführen.

Answer 2

Es gibt viele kreative Möglichkeiten, hierarchische Daten in einer Datenbank zu organisieren, aber ich finde es am einfachsten, die Daten in einem nicht-hierarchischen Format zurück zu bringen und Eltern- und Kinddatensätze programmatisch abzugleichen.

Gesamtaufwand: 1 Query + 1 programmatic Durchlauf durch Ihre Datenmenge, um die Hierarchie zu erstellen.

---

Alternative Ansatz:

Ich habe diese Methode in der Vergangenheit mit begrenztem Erfolg eingesetzt.Sie können speichern den Pfad jedes Element in Ihrem Baum eine varchar (max) Spalte wie folgt:

ID ParentID Path 
-- -------- ---- 
1  null  1/ 
2  1   1/2/ 
3  null  3/ 
4  2   1/2/4/ 
5  4   1/2/4/5/ 
6  null  6/ 
7  5   1/2/4/5/7/ 
9  5   1/2/4/5/9/ 

Von diesem Punkt alle Knoten unter ID bekommen = 5 ist ein sehr einfach:

SELECT * 
FROM table 
WHERE Path like (SELECT Path FROM Table WHERE ID = 5) + '%' 

Answer 3

können Sie die Tabellenstruktur ändern? Sieht so aus, als wäre es einfacher, mit linken und rechten Knoten zu arbeiten, als mit nur einem Elternteil, denn dann ist eine einzige Auswahl möglich. Siehe die folgenden Links:

http://www.mail-archive.com/sqlite-users@sqlite.org/msg23867.html

http://weblogs.asp.net/aghausman/archive/2009/03/16/storing-retrieving-hierarchical-data-in-sql-server-database.aspx (diese SQLServer ist, aber sie haben ein Diagramm, das helfen könnte.)