Rekursive Abfragen (WITH RECURSIVE): Hierarchien und Graphen

Durchlaufe Bäume und Graphen mit WITH RECURSIVE und meistere Tiefe und Zyklenerkennung.

11 Min. · 3 Fragen

Eine rekursive CTE besteht aus zwei durch UNION ALL verbundenen Teilen: einem Anker-Term, der die Startzeilen liefert, und einem rekursiven Term, der die CTE selbst referenziert. SQLite führt den Anker einmal aus und wendet dann den rekursiven Term in einer Schleife auf die neuen Zeilen an, bis keine mehr entstehen. Erstellen wir eine Hierarchie von Vorgesetzten, um das zu veranschaulichen.

SQL

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

Ada führt Grace, die Alan und Edsger führt.

Um das Organigramm unter Ada zu entfalten, wählt der Anker die Wurzel mit einer Tiefe von 0, und der rekursive Term verbindet jeden Mitarbeiter mit seinem bereits in der CTE vorhandenen Vorgesetzten und erhöht dabei die Tiefe. Die Spalte depth, die du selbst berechnest, ist der einfachste Weg, die Ebenen einer Hierarchie zu messen.

SQL

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

Ada 0, Grace 1, Alan 2, Edsger 2.

Ein Graph wird durch eine Kantentabelle (src, dst) modelliert. Das Durchlaufen folgt derselben Mechanik, aber ein Graph kann Zyklen enthalten: 1 -> 2 -> 3 -> 1 zu folgen, dreht sich endlos im Kreis. Das Gegenmittel ist, sich den durchlaufenen Pfad in einer Textspalte zu merken und jeden bereits besuchten Knoten abzulehnen. Die Funktion instr sucht einen Knoten zwischen zwei Punkten innerhalb dieses Pfads.

SQL

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

Der Pfad '.1.2.3.' blockiert die Rückkehr zu 1.

Mit UNION ALL erzeugt ein ungesicherter Zyklus eine unendliche Rekursion: Jeder erneut besuchte Knoten wird ohne Deduplizierung wieder eingespeist. Der Wechsel zu UNION beseitigt *ganze* identische Zeilen, was manchmal hilft, aber nicht ausreicht, sobald sich eine Spalte wie path bei jedem Durchlauf unterscheidet. SQLite kennt die Standard-Klausel CYCLE nicht (in PostgreSQL 14+ vorhanden): Die Zyklenerkennung liegt daher bei dir.

Eine rekursive CTE erzeugt auch Zahlenreihen: WITH RECURSIVE seq(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM seq LIMIT 10) liefert 1 bis 10, wobei ein externes LIMIT genügt, um die Schleife zu begrenzen. Einschränkung von SQLite: Der rekursive Term darf die CTE nur einmal referenzieren und erlaubt weder eine Aggregatfunktion noch ein internes ORDER BY.

Wissenscheck

Stelle sicher, dass du die wichtigsten Punkte dieser Lektion behalten hast.

Welcher Operator verbindet in einer rekursiven CTE den Anker-Term mit dem rekursiven Term?
- UNION ALL (oder UNION)
- JOIN
- INTERSECT
- CROSS APPLY
Warum riskiert ein zyklischer Graph mit UNION ALL eine unendliche Rekursion?
- Weil UNION ALL die Ergebnisse systematisch sortiert
- Weil dieselben Knoten ohne Deduplizierung erneut besucht werden
- Weil SQLite den Index während der Rekursion deaktiviert
- Weil der Anker bei jedem Durchlauf neu ausgewertet wird
Wie vermeidest du eine unendliche Schleife beim Durchlaufen eines zyklischen Graphen in SQLite?
- Ein ORDER BY im rekursiven Term hinzufügen
- Sich den durchlaufenen Pfad merken und bereits besuchte Knoten ausschließen
- Die Standard-Klausel CYCLE verwenden
- Die Größe des Speicher-Caches erhöhen