Zurück zur Artikelliste Artikel
5 Leseminuten

Lange SQL-Abfrage vs. rekursive SQL-Abfrage

Inhaltsverzeichnis

Die Rekursion ist eine der zentralen Ideen in der Computerwissenschaft. Wir können sie als eine Methode zur Lösung von Problemen definieren, bei der die Lösung des Problems von der Lösung einer kleineren Instanz eines Problems abhängt. In diesem Artikel werden wir uns mit der Rekursion in SQL beschäftigen, die Sie in der Vertabelo Academy üben und vertiefen können.

Rekursion ist eine Möglichkeit, hierarchische Probleme, die wir in Daten finden, mit gewöhnlichem SQL zu lösen. Diese Arten von Abfragen werden auch als hierarchische Abfragen bezeichnet. Die Fähigkeit zur Rekursion ist in Standard-SQL seit SQL:1999 in Form von rekursiven CTEs oder gemeinsamen Tabellenausdrücken zu finden.

Einige RDMBS-Systeme haben ihre eigene Art, Rekursion zu implementieren, vor allem die Oracle-Datenbanken mit der CONNECT BY -Anweisung. Da rekursive CTE im SQL-Standard enthalten sind und von allen großen RDBMS-Anbietern verwendet werden, werden wir diese Art der Rekursion untersuchen.

REKURSION MIT CTE

Die Rekursion lässt sich am besten beherrschen, wenn man eine hierarchische Struktur betrachtet. Es gibt kein besseres Beispiel für hierarchische Daten als die Organisationsstruktur eines großen Unternehmens. Wir werden also eine typische employees Tabelle, die Daten über Mitarbeiter und deren direkte Vorgesetzte enthält.

Die Tabelle enthält die Bezeichner des aktuellen Mitarbeiters und seines direkten Vorgesetzten als Verweis auf dieselbe Tabelle. Neben den Bezeichnern haben wir in der Tabelle auch den Namen und den Nachnamen des Mitarbeiters.

Wir werden eine Abfrage konstruieren, die alle Zeilen der Tabelle durchsucht, beginnend mit der ersten Zeile, die gewöhnlich als Ankerzeile bezeichnet wird. In unserer Tabelle ist die Ankerzeile der oberste Manager, der in der Hierarchie über ihm keinen berichterstattenden Manager hat, so dass sein manager_id -Attribut null ist.

  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
ID MANAGER_ID FIRST_NAME LAST_NAME
1 John McGee

Angenommen, wir wollen sehen, wer John verwaltet, wie würde dann die Abfrage aussehen? Etwa so:

SELECT id,
         manager_id,
         first_name,
         last_name
  FROM   employees cur
  WHERE  manager_id in (
    SELECT id
    FROM   employees
    WHERE  manager_id IS NULL
  )

Und für die Manager dieser Manager:

SELECT id,
  manager_id,
  first_name,
  last_name
FROM employees
WHERE manager_id IN
  (SELECT id
  FROM employees
  WHERE manager_id IN
    ( SELECT id FROM employees WHERE manager_id IS NULL
    )
  ) 

Wie Sie sehen, entsteht hier ein Muster, für jede neue Managementebene konstruieren wir eine neue Unterabfrage. Dieser Ansatz ist schlecht, da er von einer festen Anzahl von Ebenen ausgeht.

Die Rekursion ist eine Möglichkeit, diese Unterabfragen zu nehmen und sie so umzuwandeln, dass sie so allgemein sind, dass sie das vorherige Ergebnis der Abfrage darstellen.

In unserem Verwaltungsbeispiel ist der allgemeine Teil so konstruiert, dass wir den vorherigen Ergebnissatz auf der Grundlage der Verwaltungs-ID mit dem aktuellen verknüpfen.

  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id

Dieser vorherige Datensatz ist als CTE definiert.

Die vollständige rekursive Funktion sieht also wie folgt aus:

WITH previous(id, manager_id,first_name,last_name) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT *
FROM   previous;

Die Rekursion beginnt mit dem obersten Manager und wird durch jede neue Ebene in der Managementhierarchie ergänzt. Das abschließende SELECT gibt den gesamten Datensatz zurück.

ID MANAGER_ID FIRST_NAME LAST_NAME
1 John McGee
2 1 Kate Doe
7 1 Ethan Lee
9 1 Emily McPers
3 2 Ethan Smith
4 2 Alexander Lam
8 7 Sophia Wilson
10 9 Jacob Gagnon
12 9 Madison Morin
5 4 Ava Marin
6 4 Olivia Roy
11 10 Logan Tremblay

Wir können diese Abfrage erweitern, um sie nützlicher zu machen, sagen wir, wir wollen die Hierarchieebenen sehen. Dazu konstruieren wir einen neuen Parameter, den wir inkrementieren, nennen wir ihn depth_level. Für jede Ebene der Hierarchie wird die Zahl um 1 erhöht.

WITH previous(id, manager_id,first_name,last_name,depth_level) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name,
         previous.depth_level+1 depth_level
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT previous.*
FROM   previous;

Wir erhalten also die Ebenen der Hierarchie.

ID MANAGER_ID FIRST_NAME LAST_NAME DEPTH_LEVEL
1 John McGee 0
2 1 Kate Doe 1
7 1 Ethan Lee 1
9 1 Emily McPers 1
3 2 Ethan Smith 2
4 2 Alexander Lam 2
8 7 Sophia Wilson 2
10 9 Jacob Gagnon 2
12 9 Madison Morin 2
5 4 Ava Marin 3
6 4 Olivia Roy 3
11 10 Logan Tremblay 3

Wir können diese depth_level verwenden, um die Daten auf eine grafischere Weise mit der Abfrage

WITH previous(id, manager_id,first_name,last_name,depth_level) AS (
  SELECT id,
         manager_id,
         first_name,
         last_name,
         0 depth_level
  FROM   employees
  WHERE  manager_id IS NULL
  UNION ALL
  SELECT cur.id,
         cur.manager_id,
         cur.first_name,
         cur.last_name,
         previous.depth_level+1 depth_level
  FROM   employees cur, previous
  WHERE  cur.manager_id = previous.id
)
SELECT previous.*,
RPAD('.', (depth_level)*2, '.') || id AS tree
FROM   previous;

und der Ergebnismenge:

ID MANAGER_ID FIRST_NAME LAST_NAME DEPTH_LEVEL TREE
1 John McGee 0 1
2 1 Kate Doe 1 ..2
7 1 Ethan Lee 1 ..7
9 1 Emily McPers 1 ..9
3 2 Ethan Smith 2 ....3
4 2 Alexander Lam 2 ....4
8 7 Sophia Wilson 2 ....8
10 9 Jacob Gagnon 2 ....10
12 9 Madison Morin 2 ....12
5 4 Ava Marin 3 ......5
6 4 Olivia Roy 3 ......6
11 10 Logan Tremblay 3 ......11

Die Rekursion ist nicht der intuitivste Teil der Informatik, aber sie ist unerlässlich. Der beste Weg, die Rekursion zu erlernen, ist fleißiges und ausdauerndes Üben. Es gibt keinen besseren Ort zum Üben von SQL als LearnSQL.de. Öffnen Sie also Ihren Browser und gehen Sie die Beispiele in diesem Rekursive Abfragen und Sie werden auf dem Weg zur SQL-Meisterschaft sein.