Machen Sie es in SQL: Rekursives SQL-Baum-Traversal

Im vorigen Artikel habe ich beschrieben, wie man mit Common Table Expressions den kürzesten Weg in einem gerichteten Graphen findet. Ich gebe zu, dass dieses Beispiel schwer zu verstehen ist. Lassen Sie uns etwas viel Gewöhnlicheres machen, etwas, das auf fast jeder Website implementiert ist - ein Menü. Anstatt den Code zu schreiben, werden wir die Vorteile der SQL-Baumstruktur nutzen und nur eine einzige Abfrage schreiben. Wir werden CTEs für PostgreSQL und die hierarchische Abfrageklausel für Oracle verwenden. Wenn Sie selbst lernen wollen, CTEs zu schreiben, empfehle ich Ihnen unseren interaktiven Kurs Rekursive Abfragen.

Schauen wir uns also an, wie ein einfaches Menü aussieht:

Was haben wir hier? Es gibt ein Hauptmenü und ein Dropdown-Menü, das erscheint, wenn wir auf die Schaltfläche des Hauptmenüs klicken. Natürlich könnte es weitere Untermenüs geben, die mit einer anderen Schaltfläche des Hauptmenüs verbunden sind. Darüber hinaus könnte es auch ein Untermenü geben, das nach dem Anklicken einer Schaltfläche eines Untermenüs erscheint.

Im Allgemeinen kann es eine unbegrenzte Anzahl von Menüebenen geben. Die Datenanordnung eines solchen Menüs ist eine SQL-Baumstruktur:

Wie Sie sehen können, handelt es sich um eine typische SQL-Baumstruktur. Es gibt Menüknoten, die mit übergeordneten Knoten verbunden sind. Der einzige Knoten ohne übergeordnete Knoten ist der Wurzelknoten.

So speichern wir eine solche SQL-Baumstruktur in der Datenbank:

In der SQL-Baumstruktur hat jeder Knoten seine eigene, eindeutige ID. Er hat einen Verweis auf den übergeordneten Knoten. Für jeden Knoten in einem Untermenü benötigen wir seine Sequenznummer zu Ordnungszwecken. Die Spalte name ist nur eine Bezeichnung, die auf der Website angezeigt wird. Die Spalte url_path bedarf vielleicht etwas mehr Erklärung. Jeder Knoten speichert einen Teil des vollständigen URL-Pfads der Ressource. Der gesamte Pfad ist eine Verkettung der url_path aller Knoten von der Wurzel bis zu diesem Knoten.

Zum Beispiel für die folgenden Daten:

> select * from menu_node;
 id | parent_node_id | seq |        name        | url_path  
----+----------------+-----+--------------------+----------- 
  1 |                |   1 | root               | 
  2 |              1 |   1 | Diagram            | diagram 
  3 |              1 |   2 | My models          | my_models 
  4 |              1 |   3 | Share requests     | share 
  5 |              1 |   4 | My account         | account 
  6 |              1 |   5 | Invite people      | invite 
  7 |              1 |   6 | Help               | help 
  8 |              7 |   1 | Documentation      | doc 
  9 |              7 |   2 | FAQ                | faq 
 10 |              7 |   3 | Ask a question     | ask 
 11 |              7 |   4 | Request a feature  | feature 
 12 |              7 |   5 | Report a problem   | problem 
 13 |              7 |   6 | Keyboard shortcuts | shortcuts 
 14 |              8 |   1 | Section 1          | section1 
 15 |              8 |   2 | Section 2          | section2 
 16 |              8 |   3 | Section 3          | section3 
(16 rows) 

Der gesamte Pfad des Knotens "Abschnitt 1" lautet: /help/doc/section1.

Mit einer solchen Struktur wollen wir das Menü auf der Seite darstellen. Wenn wir keine SQL-Abfrage verwenden würden, um hierarchische Baumebenen zu erhalten, müssten wir entweder mehrere Abfragen durchführen (für jeden Knoten, um seine Kinder zu erhalten) oder alle Daten abrufen und die Struktur im Code aufbauen. Ich sage nicht, dass dies ein schlechter Ansatz ist, aber es kann auf eine einfachere und intelligentere Weise geschehen.

PostgreSQL - rekursive WITH-Klausel

Um ein solches Menü zu rendern, müssen wir den vollständigen URL-Pfad jeder Schaltfläche kennen, Informationen über die Ebene des Knotens (um ihn in CSS entsprechend zu gestalten) und wo er angehängt werden soll (natürlich die ID des Elternteils). Beginnen wir also damit, unsere Select-Abfrage mit CTE zu erstellen:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) AS (

Zunächst müssen wir den Wurzelknoten ermitteln:

  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL

Dann gehen wir mit unserer SQL-Abfrage rekursiv tiefer, indem wir den Pfad verketten und die Ebene inkrementieren:

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id

Und am Ende müssen wir alle Zeilen außer dem Wurzelknoten (den wir nicht mehr brauchen) in der richtigen Reihenfolge abrufen. Zuerst sollten sie nach Ebene geordnet werden, dann nach Elternteil"gruppiert" und schließlich in der Reihenfolge seq. Die Abfrage wird also so aussehen:

SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq; 

Die endgültige Abfrage:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) 
AS ( 
  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL 

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id 
) 
SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq;

Sieht ziemlich einfach aus, nicht wahr? Als Ergebnis erhalten wir die Daten:

 id |        name        |        url         | level | parent_node_id | seq 
----+--------------------+--------------------+-------+----------------+----- 
  2 | Diagram            | /diagram           |     1 |              1 |   1 
  3 | My models          | /my_models         |     1 |              1 |   2 
  4 | Share requests     | /share             |     1 |              1 |   3 
  5 | My account         | /account           |     1 |              1 |   4 
  6 | Invite people      | /invite            |     1 |              1 |   5 
  7 | Help               | /help              |     1 |              1 |   6 
  8 | Documentation      | /help/doc          |     2 |              7 |   1 
  9 | FAQ                | /help/faq          |     2 |              7 |   2 
 10 | Ask a question     | /help/ask          |     2 |              7 |   3 
 11 | Request a feature  | /help/feature      |     2 |              7 |   4 
 12 | Report a problem   | /help/problem      |     2 |              7 |   5 
 13 | Keyboard shortcuts | /help/shortcuts    |     2 |              7 |   6 
 14 | Section 1          | /help/doc/section1 |     3 |              8 |   1 
 15 | Section 2          | /help/doc/section2 |     3 |              8 |   2 
 16 | Section 3          | /help/doc/section3 |     3 |              8 |   3 
(15 rows)

Mit dieser einzigen Abfrage erhalten Sie alle Daten, die Sie für die Darstellung eines einfachen mehrstufigen Menüs benötigen. Dank der SQL-Baumstruktur werden Ihre Daten in einer klaren und leicht verständlichen Weise dargestellt.

Um das Schreiben von hierarchischen Abfragen wie dieser zu üben, empfehle ich unseren interaktiven Kurs Rekursive Abfragen.

Oracle - hierarchische Abfragen

In Oracle können Sie entweder die hierarchische Abfrageklausel (auch bekannt als "CONNECT BY-Abfrage") oder das rekursive Subquery-Factoring (eingeführt in Version 11g Release 2) verwenden.

Die Struktur der zweiten ist fast die gleiche wie bei der Abfrage für PostgreSQL. Die einzigen Unterschiede sind:

• das Fehlen des Schlüsselworts RECURSIVE
• "level" ist ein reserviertes Wort, das wir ändern müssen.

Der Rest bleibt unverändert und die Abfrage funktioniert gut.

Was die hierarchische Abfrageklausel betrifft, so ist ihre Syntax völlig anders. Die Abfrage sieht wie folgt aus:

SELECT 
  id, 
  name,
  SYS_CONNECT_BY_PATH(url_path, '/') AS url, 
  LEVEL, 
  parent_node_id, 
  seq 
FROM menu_node 
START WITH id IN 
  (SELECT id FROM menu_node WHERE parent_node_id IS NULL) 
CONNECT BY PRIOR id = parent_node_id;

Zu beachten ist, dass diese Abfrage wirklich rekursiv ist, d. h. in der Reihenfolge der ersten Tiefe. Die "rekursive" WITH-Klausel in PostgreSQL und (standardmäßig) in Oracle durchläuft die Struktur in einer breadth-first-Reihenfolge.

Wie Sie sehen, kann das Verständnis des Konzepts der SQL-Baumstruktur etwas von unserer kostbaren Zeit (und ein paar Zeilen Code) sparen. Es bleibt Ihnen überlassen, ob Sie rekursive Traversalabfragen verwenden oder nicht, aber es lohnt sich auf jeden Fall, die Alternative zu kennen.

Um zu lernen, wie man rekursive Abfragen in SQL schreibt, empfehle ich unseren interaktiven Kurs Rekursive Abfragen. Er enthält 114 praktische Programmierübungen, mit denen Sie Common Table Expressions und rekursive Abfragen wie die in diesem Artikel gezeigten üben können.