MariaDB-Kurs / Hierarchien mit rekursiven CTEs abfragen und Kreise begrenzen

Ein rekursiver gemeinsamer Tabellenausdruck, englisch Common Table Expression (CTE), beginnt mit einer Anfangsmenge und folgt Beziehungen wiederholt zu weiteren Zeilen. Eine verlässliche Hierarchieabfrage benötigt einen Startpunkt, eine Abbruchregel, ausreichend breite Pfadspalten, Schutz vor erneuten Besuchen und eine ausdrückliche Ergebnissortierung.

Den Nutzen einer rekursiven Abfrage erkennen

Ein gewöhnlicher CTE benennt einen Abfrageschritt. Ein rekursiver CTE verwendet diesen Namen zusätzlich innerhalb seiner eigenen Definition. Der Anker erzeugt die Anfangszeilen; der rekursive Teil findet aus dem vorherigen Schritt die nächsten Zeilen. Dieses Beispiel verbindet beide Teile mit UNION ALL.

Kategorienbäume und Organigramme können unterschiedlich tief sein. Bei einer festen Beziehung mit zwei Ebenen kann ein JOIN ausreichen. Große Hierarchien benötigen außerdem einen geeigneten Zugriff auf Kindzeilen und eine bewusste Tiefengrenze. Die Indexübung hilft bei der Zugriffsprüfung. Die offizielle Übersicht zu rekursiven CTEs erläutert Berechnung und Typen der Ankerspalten.

Einen Baum mit sechs Kategorien vorbereiten

Verwenden Sie appops_lab mit einer Verwaltungsverbindung oder einem Lernkonto, das Datenbank und Tabellen erstellen darf. Prüfen Sie zuerst SELECT VERSION(), DATABASE(); sowie vorhandene Datenbanken und Tabellen. Wird appops_lab bereits in der Docker-Übung verwendet, erhalten Sie dessen Inhalte. CREATE DATABASE IF NOT EXISTS ersetzt diese Prüfung nicht. Besteht category_tree schon, untersuchen Sie den vorhandenen Aufbau vor einer Wiederholung.

Der Fremdschlüssel prüft, ob ein angegebener Elternknoten existiert. Er belegt nicht, dass die gesamte Hierarchie kreisfrei ist.

CREATE DATABASE IF NOT EXISTS appops_lab
  CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;
USE appops_lab;
CREATE TABLE category_tree (
  category_id INT NOT NULL PRIMARY KEY,
  parent_id INT NULL,
  category_name VARCHAR(40) NOT NULL,
  INDEX ix_parent (parent_id),
  CONSTRAINT fk_category_parent FOREIGN KEY (parent_id)
    REFERENCES category_tree(category_id)
) ENGINE=InnoDB;
INSERT INTO category_tree VALUES
  (1, NULL, 'Catalog'), (2, 1, 'Books'), (3, 1, 'Tools'),
  (4, 2, 'SQL'), (5, 2, 'Python'), (6, 3, 'Editors');

Die englischen Kategorienamen sind Literale des Datenbestands. Catalog ist der Wurzelkatalog mit Books, also Büchern, und Tools, also Werkzeugen. Books enthält SQL und Python; Tools enthält Editors, also Editoren. Der Index auf parent_id unterstützt die Suche nach Kindknoten. Die sechs Zeilen dienen dem Verständnis der Beziehungen und Ergebnisse, ohne einen allgemeinen Geschwindigkeitsvorteil zu belegen.

Baum des SQL-Beispiels: Catalog (1) in Tiefe null, Books (2) und Tools (3) in Tiefe eins sowie SQL (4), Python (5) und Editors (6) in Tiefe zwei

Die vollständige Abfrage mit Tiefe und Pfaden ausführen

WITH RECURSIVE tree AS (
  SELECT category_id, parent_id, category_name, 0 AS depth,
         CAST(CONCAT('/', category_id, '/') AS CHAR(1000)) AS visited,
         CAST(category_name AS CHAR(1000)) AS name_path
  FROM category_tree WHERE category_id = 1
  UNION ALL
  SELECT c.category_id, c.parent_id, c.category_name, t.depth + 1,
         CONCAT(t.visited, c.category_id, '/'),
         CONCAT(t.name_path, ' > ', c.category_name)
  FROM category_tree c JOIN tree t ON c.parent_id = t.category_id
  WHERE t.depth < 8
    AND LOCATE(CONCAT('/', c.category_id, '/'), t.visited) = 0
)
SELECT category_id, parent_id, depth, name_path
FROM tree ORDER BY depth, category_id;

Das erste SELECT liefert Kategorie 1 in Tiefe null. Das rekursive SELECT findet Kategorien, deren parent_id zur aktuellen Kategorie passt, und erhöht die Tiefe. Der Pfad visited umschließt numerische Kennungen mit Schrägstrichen. Dadurch verwechselt die Suche nach Kennung 1 diese nicht mit Kennung 11.

Der Anker wandelt beide Pfade ausdrücklich in CHAR(1000) um. Würde eine kurze Anfangszeichenfolge einen zu schmalen Typ vorgeben, könnten spätere Verkettungen dessen Kapazität überschreiten. Hier gelten ganzzahlige Kennungen, kurze Namen und eine maximale Tiefe von acht. Berechnen Sie Kapazität und Grenzen für andere Pfade erneut; 1000 ist kein universell ausreichender Wert.

ID Elternknoten Tiefe Pfad
1 NULL 0 Catalog
2 1 1 Catalog > Books
3 1 1 Catalog > Tools
4 2 2 Catalog > Books > SQL
5 2 2 Catalog > Books > Python
6 3 2 Catalog > Tools > Editors

Das abschließende ORDER BY nach Tiefe und Kennung legt diese Darstellung fest. Leiten Sie die Ausgabeordnung nicht aus der rekursiven Berechnung ab. Eine Sortierung nach Textpfaden verwendet lexikografische Reihenfolge und kann von der numerischen Reihenfolge der Kennungen abweichen.

Eine Bedingung ändern und den Umfang beobachten

Ersetzen Sie ausschließlich t.depth < 8 durch t.depth < 1 und führen Sie die Abfrage erneut aus. Es erscheinen der Anker in Tiefe null und seine direkten Kinder: Kennungen 1, 2 und 3. Die Bedingung vergleicht die Tiefe des Elternknotens; der Knoten in Tiefe null kann deshalb noch Kinder in Tiefe eins erzeugen. Stellen Sie danach die Grenze acht wieder her.

Ändern Sie für einen gesonderten Vergleich nur den Anker auf category_id = 2. Das Ergebnis enthält den Books-Teilbaum mit 2, 4 und 5; Books beginnt nun in Tiefe null. Stellen Sie den Anker vor dem anschließenden Kreistest wieder auf 1 zurück.

Ein durch die Tiefengrenze abgeschnittenes Ergebnis ist nicht zwingend die vollständige Hierarchie. Prüfen Sie vor einer Erhöhung, ob weitere Ebenen existieren. Die Servervariable max_recursive_iterations begrenzt zusätzlich die Wiederholungen. Sie ersetzt weder eine fachliche Abbruchregel noch eine Prüfung der Elternbeziehungen.

Einen Kreis erzeugen und wieder zurücknehmen

Führen Sie die folgenden Anweisungen in derselben Verbindung aus und wiederholen Sie anschließend die vollständige rekursive Abfrage. Eine andere Verbindung sieht die noch nicht bestätigte Elternänderung möglicherweise nicht.

START TRANSACTION;
UPDATE category_tree SET parent_id = 4 WHERE category_id = 1;

Der Elternknoten 4 für Kategorie 1 erzeugt beim Verfolgen der Kinder den Kreis 1 → 2 → 4 → 1. Die Abfrage beginnt ausdrücklich bei Kategorie 1. Ihre Liste besuchter Kennungen verhindert den erneuten Besuch und lässt sie weiterhin mit sechs Zeilen enden. Die Wurzelzeile zeigt vorübergehend Elternknoten 4. Nehmen Sie die Änderung nach der Beobachtung sofort zurück:

ROLLBACK;
SELECT category_id, parent_id FROM category_tree WHERE category_id = 1;

Der Elternwert von Kategorie 1 muss wieder NULL sein. Ein Anker mit parent_id IS NULL kann den gesamten kreisförmigen Teil auslassen, sobald dessen elternlose Wurzel verschwindet. Wiederbesuche bei einem Durchlauf zu vermeiden belegt deshalb weder globale Kreisfreiheit noch die Erreichbarkeit aller Komponenten. MariaDB bietet auch CYCLE ... RESTRICT. Der ausdrückliche Pfad macht die Regel dieses Beispiels nachvollziehbar.

Die Hierarchie vor dem Anwendungseinsatz prüfen

  • Kontrollieren Sie die durch den Anker ausgewählten Wurzeln.
  • Unterscheiden Sie fehlende Eltern, Selbstreferenzen, Kreise und unerreichbare Komponenten.
  • Wählen Sie eine maximale Tiefe und eine dazu passende Pfadkapazität.
  • Untersuchen Sie Kindzugriffsindex und EXPLAIN und gleichen Sie die Zeilenzahl mit den erwarteten Beziehungen ab.

Beenden Sie zur Bereinigung offene Transaktionen und prüfen Sie, dass die Tabelle ausschließlich entbehrlichen Übungsdaten dient. Entfernen Sie sie gegebenenfalls mit DROP TABLE appops_lab.category_tree;. Die Anweisung löscht Struktur und Zeilen und ist nicht durch ein gewöhnliches ROLLBACK rückgängig zu machen. Ersetzen Sie den Namen nicht durch eine Geschäftstabelle und entfernen Sie nicht die mit anderen Übungen geteilte Datenbank.