Baumtiefe in SQL

Question

Angenommen, es gibt eine Tabelle namens tree_node, die den Primärschlüssel mit der Bezeichnung id und eine Nullable-Spalte namens parent_id hat und die Tabelle eine Baumstruktur (oder eine Gesamtstruktur) einbettet, wie kann man die Tiefe eines berechnen Knoten in der Struktur/Gesamtstruktur in einer effizienten Art und Weise in SQL?

Answer 1

Sie benötigen Rekursionsfähigkeit. Mit rekursive Abfragen wird dies:

WITH RECURSIVE node_ancestors(node_id, parent_id) AS (
     SELECT id, id FROM tree_node WHERE id IN (1, 2, 3) 
    UNION ALL 
     SELECT na.node_id, tree_node.parent_id 
      FROM node_ancestors AS na, tree_node 
      WHERE tree_node.id = na.parent_id AND tree_node.parent_id IS NOT NULL 
) 
SELECT node_id, COUNT(parent_id) AS depth FROM node_ancestors GROUP BY node_id; 

Die anderen Optionen, um die Rekursion in gespeicherten Prozeduren tun, die Rekursion in der Anwendung tun, und die Menge der Rekursion zu begrenzen und mit viel verbindet. (Die letzte Option ist nicht wirklich effizient für nicht-triviale Tiefen)

Answer 2

Wenn die Tiefe unbegrenzt ist, dann ist das Problem rekursiv, und es gibt nicht wirklich eine einfache und effiziente Lösung. (Es kann einfache xor effiziente Lösungen geben.) Wenn Sie die Kontrolle über das Schema haben und regelmäßig auf diese Art von Daten zugreifen müssen, können Sie die Tabelle als verschachtelte Menge mit linken und rechten Begrenzungsgrenzen für jedes Element umgestalten. Dies würde ermöglichen es Ihnen, die Tiefe eines Knotens in einer einzigen Abfrage mit elementaren Bedingungen zu berechnen, etwa:

select count(*) from tree_node 
    where left < myLeft 
    and right > myRight 

Answer 3

Ein üblicher Weg, Bäume zu handhaben ist, zusätzlich zu den regulären Spalten von KEY und ELTERN, Sie haben Ein PATH-Typ von Spalten, der einen Zeichenfolgenwert enthält, der die Schlüssel der Knoten enthält, aus denen der Pfad besteht, vom Stamm bis zu und einschließlich des Knotens selbst, begrenzt durch ein Zeichen, das nicht Teil eines Schlüssels sein darf selbst.

Lassen Sie mich Ihnen ein Beispiel geben:

KEY  PARENT   PATH 
1   -    *1* 
    2  1    *1*2* 
    3  1    *1*3* 
    4  3    *1*3*4* 
    5  1    *1*5* 
    6  5    *1*5*6* 

Dies ist vor allem mit Bäumen verwendet, die auch nicht viel ändern, wie Abteilungshierarchien oder ähnlichem.

Ich weiß, dass eine solche Zeichenfolge nicht genau die Normalisierung Theorien folgt, da es mehrere Regeln (Multi-Tasten, mehrwertige Felder, etc.) ungültig scheint, aber es ist sehr nützlich in vielen Szenarien, einschließlich der nach dem du fragst.

In Ihrem Fall müssen Sie einfach den TREE-Wert für den fraglichen Knoten abrufen, und abhängig davon, was am einfachsten ist, entweder die Anzahl der Trennzeichen zählen oder sie mit einer Replace-Funktion entfernen und die Differenz berechnen Längen.

Hier SQL Sie die obige Liste der Knoten zu geben, mit ihren Tiefen:

select KEY, PARENT, LEN(PATH)-LEN(REPLACE(PATH, '*', ''))-1 as DEPTH 
from NODES 

Beachten Sie, dass dieser Ansatz keine spezielle Syntax oder Unterstützung benötigt von der Datenbank-Engine für rekursive SQL, und eignet sich sehr schön zum Indexieren auch.