Graph-Abfragen in relationalen Datenbanken simulieren

1. Warum man nicht immer eine Graphdatenbank braucht

Graph-Abfragen gelten oft als klassisches Argument fuer den Wechsel zu einer dedizierten Graphdatenbank wie Neo4j. Tatsaechlich brauchen aber viele Anwendungsfaelle keine allgemeine Graph-Engine mit beliebig vielen Kantentypen und komplexen Traversierungsalgorithmen, sondern eine begrenzte Menge klar definierter Beziehungen: Mitarbeiter-Hierarchien, Kategorie-Baeume, einfache Freundesnetzwerke oder Abhaengigkeitsgraphen zwischen Komponenten.

Fuer genau diese Faelle bieten relationale Datenbanken mit rekursiven Common Table Expressions, kurz CTEs, ein maechtiges Werkzeug, um Graph-Abfragen direkt in SQL zu formulieren, ohne ein zweites System einzufuehren. Der Vorteil: Die Daten bleiben in derselben Transaktion, denselben Backups und demselben Betriebsmodell wie der Rest der Anwendung, mit vollen ACID-Garantien fuer die zugrunde liegenden Beziehungen.

Dieser Beitrag zeigt die drei wichtigsten Techniken fuer Graph-Abfragen in SQL: das Adjazenzlisten-Modell mit rekursiven CTEs, die Closure Table als materialisierte Alternative, und die konkreten Performance-Grenzen, an denen eine echte Graphdatenbank tatsaechlich die bessere Wahl wird.

2. Das Adjazenzlisten-Modell als Grundlage

Das Adjazenzlisten-Modell ist die einfachste Form, Beziehungen fuer Graph-Abfragen in einer relationalen Tabelle abzubilden: Jede Zeile referenziert per Fremdschluessel genau einen direkten Nachbarn, etwa einen Mitarbeiter, der auf seinen direkten Vorgesetzten verweist. Diese Struktur ist kompakt, leicht zu pflegen und deckt Einfuegen, Aktualisieren und Loeschen einzelner Kanten mit minimalem Aufwand ab.

Der Nachteil des reinen Adjazenzlisten-Modells: Eine einzelne SQL-Abfrage ohne rekursive Erweiterung kann nur eine feste Anzahl von Ebenen abfragen, etwa mit mehreren aufeinanderfolgenden Self-Joins fuer jede zusaetzliche Ebene. Fuer eine unbekannte oder variable Tiefe, wie sie Graph-Abfragen in Hierarchien typischerweise brauchen, reicht das Modell allein nicht aus und muss mit rekursiven CTEs kombiniert werden.

-- Adjazenzlisten-Modell: jede Zeile kennt nur ihren direkten Vorgesetzten
CREATE TABLE employees (
  employee_id   INT PRIMARY KEY,
  name          VARCHAR(255) NOT NULL,
  manager_id    INT REFERENCES employees(employee_id)
);

INSERT INTO employees (employee_id, name, manager_id) VALUES
  (1, 'Anna Vogel', NULL),        -- CEO, hat keinen Vorgesetzten
  (2, 'Ben Krueger', 1),
  (3, 'Clara Sommer', 2),
  (4, 'David Winter', 2),
  (5, 'Erik Falk', 3);

-- Direkte Nachbarn abfragen ist trivial, ein einzelner Join reicht
SELECT e.name AS mitarbeiter, m.name AS vorgesetzter
FROM employees e LEFT JOIN employees m ON e.manager_id = m.employee_id;

3. Rekursive CTEs fuer Traversierungen und Pfadsuche

Eine rekursive CTE besteht aus einem Anker-Teil, der die Startpunkte der Traversierung definiert, und einem rekursiven Teil, der sich selbst referenziert und schrittweise weitere Ebenen anfuegt, bis keine neuen Zeilen mehr gefunden werden. Fuer Graph-Abfragen in einer Hierarchie bedeutet das: Der Anker waehlt die Wurzel, etwa den CEO ohne Vorgesetzten, und jede rekursive Iteration fuegt die naechste Ebene direkter Untergebener hinzu.

-- Rekursive CTE: komplette Organisationshierarchie ab der Wurzel
WITH RECURSIVE org_chart AS (
  -- Anker: Wurzel der Hierarchie (kein Vorgesetzter)
  SELECT employee_id, name, manager_id, 1 AS level,
         ARRAY[employee_id] AS path
  FROM employees
  WHERE manager_id IS NULL

  UNION ALL

  -- Rekursion: naechste Ebene direkter Untergebener
  SELECT e.employee_id, e.name, e.manager_id, oc.level + 1,
         oc.path || e.employee_id
  FROM employees e
  JOIN org_chart oc ON e.manager_id = oc.employee_id
  WHERE NOT e.employee_id = ANY(oc.path)  -- Zyklenschutz
)
SELECT level, name, path FROM org_chart ORDER BY path;

-- Ergebnis zeigt jede Ebene der Hierarchie mit vollstaendigem Pfad
-- von der Wurzel bis zum jeweiligen Mitarbeiter

Der Array-Pfad in dieser Abfrage dient zwei Zwecken: Er dokumentiert den vollstaendigen Traversierungsweg fuer jede Zeile, und er verhindert Endlosschleifen bei zyklischen Daten, was bei Graph-Abfragen ueber fehlerhafte oder unvorhergesehene Datenkonstellationen ein reales Risiko ist. Ohne diese Zyklenpruefung wuerde eine rekursive CTE bei einem versehentlichen Zyklus in den Daten nie terminieren.

4. Transitive Huelle und Erreichbarkeitsabfragen

Eine haeufige Form von Graph-Abfragen ist die Erreichbarkeitsfrage: Ist Knoten B von Knoten A aus ueber eine beliebige Anzahl von Kanten erreichbar? Diese sogenannte transitive Huelle laesst sich mit derselben rekursiven CTE-Technik beantworten, indem man statt einer Baumstruktur einen allgemeinen gerichteten Graphen zulaesst, bei dem ein Knoten mehrere Vorgaenger haben kann.

-- Allgemeiner gerichteter Graph statt Baum: Abhaengigkeiten zwischen Modulen
CREATE TABLE module_dependencies (
  module_id      INT NOT NULL,
  depends_on_id  INT NOT NULL,
  PRIMARY KEY (module_id, depends_on_id)
);

-- Erreichbarkeitsabfrage: welche Module haengen transitiv von "core" ab?
WITH RECURSIVE reachable AS (
  SELECT module_id, depends_on_id
  FROM module_dependencies
  WHERE depends_on_id = (SELECT module_id FROM modules WHERE name = 'core')

  UNION

  SELECT md.module_id, md.depends_on_id
  FROM module_dependencies md
  JOIN reachable r ON md.depends_on_id = r.module_id
)
SELECT DISTINCT module_id FROM reachable;
-- UNION statt UNION ALL dedupliziert automatisch, wichtig bei
-- Graphen mit mehreren Pfaden zwischen denselben zwei Knoten

5. Kuerzesten Pfad mit gewichteten Kanten simulieren

Fuer gewichtete Graph-Abfragen, etwa den kuerzesten Weg zwischen zwei Staedten in einem Streckennetz, erweitert man die rekursive CTE um eine kumulierte Gewichtssumme und sortiert das Endergebnis danach. Diese Technik implementiert im Kern eine vereinfachte Breitensuche, ist aber nicht so effizient wie ein dedizierter Dijkstra- oder A-Stern-Algorithmus einer echten Graph-Engine, weil SQL keine Prioritaetswarteschlange kennt und jede moegliche Route bis zu einer Abbruchbedingung vollstaendig durchsucht.

-- Gewichtete Kanten: kuerzester Pfad zwischen zwei Staedten
CREATE TABLE routes (
  from_city  VARCHAR(50) NOT NULL,
  to_city    VARCHAR(50) NOT NULL,
  distance_km INT NOT NULL
);

WITH RECURSIVE path_search AS (
  SELECT from_city, to_city, distance_km AS total_distance,
         ARRAY[from_city, to_city] AS route
  FROM routes
  WHERE from_city = 'Hamburg'

  UNION ALL

  SELECT ps.from_city, r.to_city, ps.total_distance + r.distance_km,
         ps.route || r.to_city
  FROM routes r
  JOIN path_search ps ON r.from_city = ps.to_city
  WHERE NOT r.to_city = ANY(ps.route)     -- Zyklenschutz
    AND ps.total_distance < 2000          -- Abbruchbedingung gegen Explosion
)
SELECT route, total_distance
FROM path_search
WHERE to_city = 'Muenchen'
ORDER BY total_distance
LIMIT 1;

6. Closure Table als Alternative zur rekursiven Abfrage

Eine Closure Table materialisiert alle Vorfahren-Nachfahre-Beziehungen einer Hierarchie explizit in einer eigenen Tabelle, statt sie bei jeder Abfrage neu zu berechnen. Fuer Graph-Abfragen, die haeufig gelesen, aber selten geschrieben werden, ist dieser Ansatz oft schneller als eine rekursive CTE, weil die teure Traversierung einmalig beim Schreiben stattfindet, nicht bei jedem Lesevorgang.

-- Closure Table: jede Vorfahre-Nachfahre-Beziehung als eigene Zeile,
-- inklusive der Distanz zwischen den Knoten (depth = 0 fuer sich selbst)
CREATE TABLE employee_hierarchy (
  ancestor_id    INT NOT NULL REFERENCES employees(employee_id),
  descendant_id  INT NOT NULL REFERENCES employees(employee_id),
  depth          INT NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

-- Alle Untergebenen von Ben Krueger (employee_id = 2), beliebiger Tiefe
SELECT e.name, eh.depth
FROM employee_hierarchy eh
JOIN employees e ON e.employee_id = eh.descendant_id
WHERE eh.ancestor_id = 2 AND eh.depth > 0
ORDER BY eh.depth;

-- Diese Abfrage braucht keine Rekursion mehr zur Laufzeit,
-- die Traversierung ist bereits beim Einfuegen einer neuen
-- Mitarbeiter-Beziehung in der Closure Table materialisiert worden

7. Performance-Grenzen rekursiver SQL-Abfragen

Rekursive Graph-Abfragen mit CTEs stossen an klare Grenzen: Jede rekursive Iteration ist im Kern ein zusaetzlicher Join, und bei sehr tiefen Hierarchien mit vielen Ebenen oder bei dichten Graphen mit vielen Kanten pro Knoten waechst die Anzahl der zu verarbeitenden Zwischenzeilen schnell exponentiell. PostgreSQL und MySQL optimieren rekursive CTEs nicht mit denselben Graph-spezifischen Indexstrukturen, die eine dedizierte Graphdatenbank fuer Traversierungen nutzt.

Als Faustregel gilt: Bis zu einigen tausend Knoten und einer Traversierungstiefe von zehn bis zwanzig Ebenen bleiben rekursive Graph-Abfragen performant genug fuer die meisten Anwendungsfaelle. Bei Millionen von Knoten, dichten Netzwerken mit vielen Kanten pro Knoten, oder Abfragen wie kuerzestem Pfad ueber tausende moegliche Routen wird eine dedizierte Graphdatenbank wie Neo4j mit ihren nativen Adjazenz-Indizes und spezialisierten Traversierungsalgorithmen deutlich effizienter.

-- EXPLAIN ANALYZE zeigt die tatsaechliche Kostenexplosion
-- bei zunehmender Rekursionstiefe
EXPLAIN ANALYZE
WITH RECURSIVE org_chart AS (
  SELECT employee_id, manager_id, 1 AS level FROM employees WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.manager_id, oc.level + 1
  FROM employees e JOIN org_chart oc ON e.manager_id = oc.employee_id
)
SELECT * FROM org_chart;

-- Bei flachen Hierarchien (unter 20 Ebenen, wenige tausend Zeilen):
-- CTE Scan mit vertretbarer Laufzeit im Millisekundenbereich
-- Bei tiefen, dichten Graphen: Laufzeit waechst ueberproportional,
-- Signal fuer eine Migration zu einer dedizierten Graphdatenbank

8. Praxisbeispiel: Organisationshierarchie und Freundesnetzwerk

Eine Organisationshierarchie mit wenigen tausend Mitarbeitern und einer Tiefe von selten mehr als acht bis zehn Ebenen ist ein Lehrbuchbeispiel fuer erfolgreiche Graph-Abfragen per rekursiver CTE direkt in der bestehenden relationalen Datenbank. Berichtsketten, Genehmigungsworkflows und Zustaendigkeitsabfragen laufen performant, ohne ein zweites System zu betreiben, und profitieren von denselben Transaktionsgarantien wie die restlichen Mitarbeiterdaten.

Ein soziales Netzwerk mit Millionen Nutzern und der Anforderung, Freunde zweiten und dritten Grades in Echtzeit zu berechnen, ist dagegen das klassische Gegenbeispiel: Die Anzahl moeglicher Pfade waechst hier so schnell, dass rekursive SQL-Graph-Abfragen selbst mit guter Indizierung an Grenzen stossen. Genau in diesem Bereich liefert eine dedizierte Graphdatenbank mit nativen Traversierungsalgorithmen spuerbar bessere Antwortzeiten.

9. SQL-Graphsimulation versus native Graphdatenbank

Die folgende Tabelle fasst zusammen, wann SQL-basierte Graph-Abfragen ausreichen und wann eine dedizierte Graphdatenbank die bessere Wahl ist.

Solange Knotenanzahl und Traversierungstiefe moderat bleiben, sind Graph-Abfragen mit rekursiven CTEs die pragmatischere Wahl, weil sie kein zweites System erfordern. Erst bei echten Big-Graph-Anforderungen mit Millionen Knoten und komplexen Traversierungsalgorithmen wird eine dedizierte Graphdatenbank zur besseren Investition.

10. Zusammenfassung

Graph-Abfragen lassen sich mit dem Adjazenzlisten-Modell und rekursiven CTEs direkt in PostgreSQL oder MySQL abbilden, fuer Hierarchien, Erreichbarkeitsfragen und sogar einfache kuerzeste-Pfad-Berechnungen ueber gewichtete Kanten. Eine Closure Table materialisiert diese Beziehungen fuer leseintensive Anwendungsfaelle vorab und spart damit teure Rekursion zur Laufzeit. Beide Techniken bleiben innerhalb derselben Transaktionsgrenzen wie der Rest der Anwendungsdaten, ohne ein zweites System zu benoetigen.

Die Grenze liegt bei Knotenanzahl, Traversierungstiefe und Kantendichte: Solange diese moderat bleiben, sind SQL-basierte Graph-Abfragen die pragmatischste Loesung. Wachsen Knotenanzahl in den Millionenbereich oder wird komplexe Pfadsuche zum Kernfeature der Anwendung, liefert eine dedizierte Graphdatenbank mit nativen Traversierungsalgorithmen die bessere Performance, zum Preis eines zusaetzlichen Systems im Betrieb.

11. FAQ: Graph-Abfragen in relationalen Datenbanken simulieren