Das Problem

Ich möchte zu einem bestimmten Beitrag in einem Online-Forum alle Antworten ermitteln. Die entsprechende Beispieltabelle liegt auf einem PostgreSQL-Server und hat folgenden Aufbau:

CREATE TABLE beitrag (
 beitrag_id       SERIAL,
 account_id       INT NOT NULL,
 antwort_auf_id   INT NOT NULL DEFAULT 1,
 zeitstempel      TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
 nachricht        TEXT,
 deleted          SMALLINT NOT NULL DEFAULT 0,
 PRIMARY KEY(beitrag_id),
 FOREIGN KEY(antwort_auf_id) REFERENCES beitrag(beitrag_id)
);

Sie erkennen sicherlich, dass die Spalte antwort_auf_id ein Fremdschlüssel auf die eigene Tabelle ist und markiert, auf welchen Beitrag sich der Datensatz bezieht. Die Spalte account_id ist auch ein Fremdschlüssel auf die account-Tabelle, aber ich habe die entsprechende Spezifikation der Übersichtlichkeit hier weggelassen.

Der Inhalt der Tabelle ist beispielhaft wie folgt:

Der inhaltliche Zusammenhang wird so dargestellt — glaube ich — besser deutlich:

  • Leere Wurzelnachricht
    • Der Lieferservice ist super
      • Das finde ich auch
      • Aber ein wenig langsam
        • Finde ich nicht
    • Das Angebot könnte besser sein

Die Tabelle wird durch einen entsprechende INSERTs gefüllt:

INSERT INTO
 beitrag (beitrag_id, account_id, antwort_auf_id, zeitstempel, nachricht)
  VALUES
   (1, 1, 1, NULL, NULL)
  ,(2, 2, 1, '2016-05-01 14:13:00', 'Der Lieferservice ist super')
  ,(3, 3, 2, '2016-05-02 11:45:00', 'Das finde ich auch')
  ,(4, 5, 2, '2016-05-01 17:01:00', 'Aber ein wenig langsam')
  ,(5, 2, 4, '2016-05-01 17:15:00', 'Finde ich nicht')
  ,(6, 5, 1, '2016-06-12 09:07:00', 'Angebot könnte besser sein');

Der Beitrag mit der beitrag_id=1 ist mein leerer Wurzelbeitrag. So verhindere ich NULL-Werte im Fremdschlüssel und kann trotzdem ermitteln, welche Beiträge keine Antworten auf andere Beiträge sind. Die Beiträge 3, 4 und 5 sind direkte oder indirekt Antworten auf Beitrag 2 und Beitrag 6 hat keine Antworten. Wir wollen nun alle Antworten auf Beitrag 2. Ein erster naiver Ansatz ist die Verwendung eines einfachen INNER JOINs:

oshop=# SELECT a.beitrag_id, a.antwort_auf_id, a.nachricht
oshop-#  FROM beitrag a INNER JOIN beitrag b ON a.antwort_auf_id=b.beitrag_id
oshop-#  WHERE b.beitrag_id=2
oshop-# ;

 beitrag_id | antwort_auf_id   |        nachricht
------------+------------------+-------------------------
          3 |                2 | Das finde ich auch.
          4 |                2 | Aber ein wenig langsam.

Das Ergebnis ist unbefriedigend. Zunächst fällt auf, dass der Beitrag 2 selbst nicht aufgelistet wird und dann, dass die indirekten Antworten fehlen. Das erste Problem ließe sich noch durch ein UNION lösen, aber für das zweite Problem ist eine Rekursion nötig.

Exkurs: Was ist eine Rekursion?

Der Rekursionsbegriff ist in der Informatik, besonders in der theoretischen Informatik sehr stark ausformuliert worden (z.B. primitive Rekursion, μ-Rekursion). In der Programmierung ist damit eine Funktion gemeint, die sich selbst aufruft. Das klassische Beispiel einer Rekursion ist die Berechnung der Fakultät der Zahl n (mathematische Schreibweise: n!). Die Fakultät einer Zahl n ist definiert als das Produkt aller natürlichen Zahlen ohne 0 kleiner oder gleich der Zahl n, also

n! = 1 * 2 * 3 * … * n;
4! = 1 * 2 * 3 * 4 = 24,  für n=4.

Rekursiv lässt sich das – hier als Python-Funktion – wie folgt formulieren:

 def fakultaet(n):
     if n == 1:
         return 1
     else:
         return n * fakultaet(n-1)

Anhand dieses Beispiels können Sie gut die Elemente einer Rekursion erkennen:

  1. Rekursionsfuß: Der Rekursionsfuß ist der Teil der Rekursion, welcher die Rekursion beendet oder begründet. Im Beispiel ist dies der grün hinterlegte Teil. Meist kann man diesen Teil daran erkennen, dass der Übergabeparameter überprüft wird und im if- oder else-Teil einer Berechnung ohne Selbstaufruf vorkommt und im anderen Teil eine Berechnung mit dem Selbstaufruf.
  2. Berechnungsvorschrift: Die eigentliche Verarbeitung der Daten. Im Beispiel der gelb hinterlegte Teil.
  3. Selbstaufruf: Die eigene Funktion wird mit verändertem Funktionsparameter aufgerufen. Im Beispiel der rot hinterlegte Teil.

Eine wichtige Frage ist, ob die Funktion irgendwann aufhört, sich selbst aufzurufen. Tut die rekursive Funktion dies nicht, läuft sie potentiell unendlich lange bzw. wird in der Realität irgendwann einen Stackoverflow erzeugen (dieser kann übrigens auch bei korrekter Rekursion ausgelöst werden, wenn die Anzahl der Selbstaufrufe eine technische Grenze überschreitet). In unserem Fall ist die Frage leicht zu beantworten: Da sich der Übergabeparameter jeweils um 1 verringert, kommt er irgendwann bei 1 an. Dann wird aber der Rekursionsfuß ausgeführt, der keinen Selbstaufruf enthält und die Rekursion endet.

Hinweis: Die Frage, ob eine Rekursion endet, ist auch schon bei einfachen Aufgabenstellungen nicht mehr trivial. Einige Beispiele sind bis heute sogar ungelöst. Ich verweise auf das Collatz-Problem (unbedingt lesen: Collatz-Problem).

Zurück zum Problem

Wie können Sie aber nun die Beiträge mit Hilfe der Rekursion ermitteln? Hier ein Ansatz in Pseudo Code, damit ich mich und Sie sich nicht mit Sprachdetails herumplagen müssen:

alle_beiträge(such_beitrag_id)
  begin
   print beitrag mit beitrag_id=such_beitrag_id;
   für alle beiträge x mit der antwort_auf_id=such_beitrag_id
    begin
     alle_beiträge(x.beitrag_id);
    end;
  end;

Die Rekursion endet, wenn kein Beitrag mehr gefunden wird, der als antwort_auf_id die such_beitrag_id enthält. Dazu muss sichergestellt sein, dass die Daten keine Zyklen aufweisen. Würde beispielsweise der Beitrag 2 auf Beitrag 5 zeigen, terminiert die Rekursion nicht.

Wie können Sie das jetzt aber in SQL umsetzen? Werden wir eine Prozedur oder sowas ähnliches schreiben? Nun, eine Prozedur, die das Ergebnis in eine temporäre Tabelle wegschreibt, ist nicht die schlechteste Lösung. Aber in einigen DBMSen (MySQL/MariaDB: 🙁 nein, PostgreSQL: 🙂 ja) gibt es die Möglichkeit, einen SELECT rekursiv aufzurufen.

Dazu werden common table expressions verwendet. Die funktionieren ungefähr so wie temporären Tabellen, die aus einem SELECT abgeleitet werden. Ich verwende mal kurz ein anderes Beispiel aus meinem Buch ([1]), da hier der Einsatz von temporären Tabellen besser nachvollzogen werden kann, als bei dem Forum-Beispiel oben. Es wird eine temporäre Tabelle aufgebaut, welche alle Kunden und die Anzahl ihrer Bestellungen enthält. Dabei werden auch Kunden erfasst, welche gar keine Bestellung aufgegeben haben; diese haben dann eine Anzahl von 0 Bestellungen:

 oshop=# CREATE TEMPORARY TABLE t_anz AS
 oshop-#  SELECT kunde_id, COUNT(bestellung_id) AS anzahl
 oshop-#   FROM
 oshop-#    bestellung RIGHT JOIN kunde USING(kunde_id)
 oshop-#   GROUP BY kunde_id
 oshop-#   HAVING COUNT(bestellung_id) > 0;
 oshop=#
 oshop=# SELECT kunde_id, iban
 oshop-#  FROM bankverbindung RIGHT JOIN t_anz USING(kunde_id);

  kunde_id |                iban
 ----------+------------------------------------
         1 | 100100101111111111
         2 |

Die temporäre Tabelle heißt t_anz und enthält die Spalten kunde_id und anzahl. Im zweiten SELECT wird diese temporäre Tabelle für einen OUTER JOIN mit der Tabelle bankverbindung genutzt und könnte auch noch für weitere Auswertungen in der selben Session genutzt werden.

So sähe das Beispiel unter Verwendung einer common table expression (CTE) aus:

 oshop=# WITH cte_anz AS
 oshop-# (
 oshop(#  SELECT kunde_id, COUNT(bestellung_id) AS anzahl
 oshop(#   FROM
 oshop(#    bestellung RIGHT JOIN kunde USING(kunde_id)
 oshop(#   GROUP BY kunde_id
 oshop(#   HAVING COUNT(bestellung_id) > 0
 oshop(# )
 oshop-# SELECT kunde_id, iban
 oshop-#  FROM bankverbindung RIGHT JOIN cte_anz USING(kunde_id);

 kunde_id |                iban
----------+------------------------------------
        1 | 100100101111111111
        2 |

In der ersten Zeile wird die Definition der CTE eingeleitet. Hinter dem Namen cte_anz könnte man in Klammern den zwei Spalten dieser Tabelle noch neue Namen vergeben. Erfolgt dies nicht, haben die Spalten die Namen, die sich aus dem nachfolgenden SELECT ergeben (hier: kunde_id und anzahl). In den runden Klammern wird nun der SELECT angegeben, der die Tabellen definiert. Bitte beachten Sie, dass hinter der schließenden runden Klammer in Zeile 8 kein Semikolon steht, da die Anweisung noch nicht abgeschlossen ist, schließlich ist die Definition der CTE Teil der Anweisung und nicht eine eigene Anweisung.

Nach der schließenden runden Klammer erfolgt nun die eigentliche Anweisung in Zeile 9, hier ein SELECT. In dieser kann die CTE wie eine vorhandene Tabelle verwendet werden. Anders als bei temporären Tabellen steht die CTE aber nur dieser Anweisung zur Verfügung und nicht noch weiteren nachfolgenden der Session.

Bauen wir den obigen naiven Ansatz vom Forum-Beispiel mithilfe der CTE um, ergibt sich folgendes:

 oshop=# WITH ant_auf AS
 oshop-# (
 oshop(#  SELECT * FROM beitrag WHERE antwort_auf_id = 2
 oshop(# )
 oshop-# SELECT beitrag_id, antwort_auf_id, nachricht
 oshop-#  FROM ant_auf;
 
  beitrag_id | antwort_auf_id   |        nachricht
 ------------+------------------+-------------------------
           3 |                2 | Das finde ich auch.
           4 |                2 | Aber ein wenig langsam.

Das ist alles nicht sehr überraschend, aber jetzt kommt der Clou: Innerhalb einer CTE kann der SELECT die CTE wieder aufrufen; es erfolgt also ein rekursiver Aufruf! Und genau dieses Feature können Sie anwenden, endlich 🙂

 oshop=# WITH RECURSIVE ant_auf AS
 oshop-# (
 oshop(#  SELECT * FROM beitrag WHERE beitrag_id = 2
 oshop(#  UNION ALL
 oshop(#  SELECT beitrag.*
 oshop(#   FROM
 oshop(#    beitrag INNER JOIN ant_auf orig
 oshop(#       ON beitrag.antwort_auf_id = orig.beitrag_id
 oshop(# )
 oshop-# SELECT beitrag_id, antwort_auf_id, nachricht FROM ant_auf;

  beitrag_id | antwort_auf_id   |          nachricht
 ------------+------------------+------------------------------
           2 |                1 | Der Lieferservice ist super.
           3 |                2 | Das finde ich auch.
           4 |                2 | Aber ein wenig langsam.
           5 |                4 | Finde ich nicht.

Syntaktisch lassen sich die einzelnen Elemente der Rekursion nicht einfach ablesen, da SQL eine deklarative Programmiersprache ist, aber sie sind natürlich im SELECT-Befehl irgendwo versteckt erkennbar. Der Rekursionsfuß besteht aus zwei Teilen. Einmal der SELECT auf Beitrag 2 und zum zweiten die Bedingung des INNER JOINs. Falls diese nämlich keine passenden Primär-/Fremdschlüsselpaare mehr findet, werden keine neuen Zeilen in der CTE mehr generiert.

Doch der Reihe nach: In Zeile 1 steht das Schlüsselwort RECURSIVE. Dieses kündigt dem SQL-Interpreter einen rekursiven Aufruf an; fehlt es, gibt’s eine hässliche Fehlermeldung, da dann die Tabelle ant_auf innerhalb der CTE unbekannt ist. In Zeile 3 wird die erste Zeile der CTE-Tabelle ant_auf erzeugt; es ist der Beitrag 2 aus der Tabelle beitrag. In Zeile 5 steht nun ein weiterer SELECT und der UNION in Zeile 4 sorgt dafür, dass die Ergebnisse beider SELECTs als eine Ergebnismenge betrachtet werden. Der SELECT in Zeile 5 beinhaltet in Zeile 7 einen JOIN auf die CTE selbst, sie ruft sich somit wieder auf. Nun enthält die CTE beim ersten Durchgang ja nur die eine Zeile vom Beitrag 2. Durch den INNER JOIN in Zeile 5 werden nun alle Beiträge verknüpft, die im Fremdschlüssel antwort_auf_id eine 2 stehen haben. Dadurch enthält die CTE jetzt 3 Beiträge, nämlich 2, 3, und 4. Nun ruft der INNER JOIN wieder ant_auf auf, so dass er die CTE mit allen Beiträgen in der Tabelle beitrag verknüpft, die im Fremdschlüssel den Wert 2, 3 oder 4 haben; es kommt der Beitrag 5 hinzu. Jetzt findet der INNER JOIN keine weiteren neuen Beiträge, die die Werte 2, 3, 4 oder 5 als Fremdschlüsselwert enthalten, und der rekursive Aufruf stoppt.

Zusammenfassung

In bestimmten Situationen sind Daten nicht nur einfach über eine Primär-/Fremdschlüsselpaarung miteinander verknüpft, sondern auch indirekt. Beispiele sind Forenbeiträge, Familienbeziehungen, Mitarbeiterorganisation, Nachbarschaftsverhältnisse etc. In solchen Fällen liefert ein einfacher JOIN immer nur die direkten Antworten auf einen Forenbeitrag, die direkten Nachfahren einer Person, die unmittelbaren Mitarbeiter eines Vorgesetzten, die direkte Nachbarschaft etc. Durch eine Rekursion können diese Verhältnisse vollständig ermittelt werden. Die Rekursion kann durch entsprechende Prozeduren, client-seitige Programmierung oder eben einer common table expression gelöst werden.

Dabei ist darauf zu achten, dass die Daten zyklenfrei sind, ein Tiefenzähler verwendet wird, der die Rekursion ab einer bestimmten Tiefe abbricht, oder besuchte Einträge markiert werden.

Quellen

[1] Adams, Ralf; SQL: Der Grundkurs für Ausbildung und Praxis. Mit Beispielen in MySQL/MariaDB; September 2016; Hanser Verlag; ISBN 978-3-4464-5074-5

[2] https://msdn.microsoft.com/de-de/library/ms175972.aspx

[3] https://en.wikipedia.org/wiki/Hierarchical_and_recursive_queries_in_SQL

[4] http://www.essentialsql.com/introduction-common-table-expressions-ctes/