Verkettete Listen in SQL

Inhaltsverzeichnis

Verkettete Listen sind eine zwar einfache, aber nach wie vor ausgesprochen hilfreiche Datenstruktur für viele Gelegenheiten. Während sie im Arbeitsspeicher leicht mithilfe von Objekten abbildbar sind, wird das in der Datenbank schon schwieriger. Abhilfe schaffen Common Table Expressions (CTE).

Von Zeit zu Zeit ist es erforderlich, Daten als einfach verkettete Listen zu modellieren. Diese gilt es dann häufig auch zu speichern, wofür gerne auf eine Datenbank zurückgegriffen wird. Allerdings stellt sich automatisch die Frage, wie man die Liste auf effizientem Weg wieder ausliest – oder bei Bedarf auch nur einen Teil dieser Liste.

Einfach verkettete Listen

Häufig wird zu dem Zweck auf ein Tabellenschema zurückgegriffen, das neben der ID eines Datensatzes auch noch die ID seines Vorgängers speichert, das sinngemäß also wie folgt aussieht:

ID | PredecessorID | Data
---|---------------|------
1  | null          | <...>
2  | 1             | <...>
3  | 2             | <...>

Natürlich ist das Vorgehen in dem Fall ausgesprochen einfach, da man die ID des Vorgängers praktisch nicht benötigt, da die Datensätze ohnehin bereits anhand der ID in vorsortierter Reihenfolge vorliegen.

Schwieriger wird das ganze allerdings, wenn als ID eine UUID verwendet wird, nach der sich nicht mehr sinnvoll filtern oder sortieren lässt (die UUIDs werden in den folgenden Beispielen aus Gründen der besseren Lesbarkeit gekürzt dargestellt):

ID             | PredecessorID  | Data
---------------|----------------|------
da4d9e6c-<...> | null           | <...>
5f2902be-<...> | da4d9e6c-<...> | <...>
1ec50658-<...> | 5f2902be-<...> | <...>

Der Zugriff darauf erfordert eine rekursive Abfrage, bei der für jeden einzelnen Datensatz die Verknüpfung zu dessen Vorgänger hergestellt wird. Das lässt sich mit sogenannten Common Table Expressions (CTE) umsetzen, die im SQL-Standard seit 1999 vorgesehen und von den meisten gängigen relationalen Datenbanken unterstützt werden.

Common Table Expressions verwenden

Eine CTE ist dabei eine Art temporäre View, ähnelt also einem Sub-Select, die zudem auf sich selbst referenzieren kann. Innerhalb der CTE gilt es dabei zunächst, den Basisfall der Rekursion zu definieren. Im Gegensatz zu der in Programmiersprachen gängigen Rekursion ist dieser Fall jedoch das Start- und nicht das Abbruchkriterium.

Im vorliegenden Fall ist das sehr einfach zu bewerkstelligen, da man den ersten Eintrag der Liste leicht daran erkennt, dass seine PredecessorID den Wert null hat:

SELECT x.ID, x.Data
  FROM MyTable AS x
  WHERE x.PredecessorID IS NULL

Diesen ersten Wert gilt es nun rekursiv mit dem folgenden Wert zu verknüpfen, der dann wiederum als neuer Ausgangswert verwendet wird, und so weiter:

WITH cte (ID, Data)
AS (
  -- base case
  SELECT x.ID, x.Data
    FROM MyTable AS x
    WHERE x.PredecessorID IS NULL

  UNION ALL

  -- other cases
  SELECT x.ID, x.Data
    FROM MyTable AS x
    INNER JOIN cte
      ON x.PredecessorID=cte.ID
)
SELECT * FROM cte

Mit dem Vorgehen erhält man den Inhalt der gesamten einfach verketteten Liste als Ergebnismenge mit den beiden Spalten ID und Data.

Eine Untermenge auswählen

Spannend wird es, wenn man von der Liste nur eine Untermenge benötigt, also sinngemäß alle Datensätze zwischen zwei UUIDs, die den ersten und letzten Eintrag markieren. Da der base case der CTE den Startwert definiert, ist das für die untere Grenze leicht zu bewerkstelligen. An die Stelle von

WHERE x.PredecessorID IS NULL

tritt der Ausdruck:

WHERE x.PredecessorID='5f2902be-<...>'

Für die obere Grenze ist ein bisschen mehr Aufwand erforderlich, aber dennoch ist das Ganze leicht zu bewerkstelligen. Man muss lediglich den Fall für den rekursiven Aufruf (also other cases) um eine WHERE-Bedingung erweitern, die abbricht, sobald die obere UUID erreicht wird:

WHERE cte.id <> '1ec50658-<...>'

Kombiniert man beides, erhält man eine Abfrage, die nur noch die gewünschte Unterliste zurückgibt:

WITH cte (ID, Data)
AS (
  -- base case
  SELECT x.ID, x.Data
    FROM MyTable AS x
    WHERE x.PredecessorID='5f2902be-<...>'

  UNION ALL

  -- other cases
  SELECT x.ID, x.Data
    FROM MyTable AS x
    INNER JOIN cte
      ON x.PredecessorID=cte.ID
    WHERE cte.id <> '1ec50658-<...>'
)
SELECT * FROM cte

tl;dr: Common Table Expressions (CTE) ermöglichen rekursive Abfragen auf SQL-Tabellen. Das ist unter anderem praktisch, um einfach verkettete Listen effizient in relationalen Datenbanken ablegen und abfragen zu können. ()