Wie man einen Eltern-Kind-Baum in SQL abfragt

Was sind Eltern-Kind-Baumstrukturen in SQL? In diesem Artikel beantworten wir diese Frage, sprechen über die Abfragehierarchie und zeigen die fünf häufigsten SQL-Abfragen, die Sie für diese Datenstrukturen benötigen.

Ja, Sie können SQL auf eine Eltern-Kind-Baumstruktur anwenden. Ich zeige Ihnen in diesem Artikel, wie das geht. Dabei führe ich Sie durch fünf Abfragebeispiele, beginnend mit der einfachsten und endend mit der komplexesten. Dabei werden rekursive Common Table Expressions (CTEs) verwendet.

Wenn Sie mit CTEs nicht vertraut sind, empfehle ich Ihnen unseren interaktiven Rekursive Abfragen Kurs. Er enthält über 100 Übungen, in denen Sie lernen, wie man CTEs in SQL verwendet, angefangen bei den Grundlagen bis hin zu fortgeschrittenen Themen wie rekursiven CTEs.

Bevor wir uns mit dem Code befassen, wollen wir uns einen Überblick über die Eltern-Kind-Baumstruktur verschaffen und darüber, wie sie in einer relationalen Datenbank gespeichert wird.

Was ist ein Eltern-Kind-Baum?

Wenn Sie sich mit hierarchischen Daten auskennen, wissen Sie wahrscheinlich, dass dies ein Synonym für eine Eltern-Kind-Struktur ist. Beide Namen sind sehr logisch; eine Eltern-Kind-Baumstruktur ist eine hierarchisch strukturierte Datenmenge. Mit anderen Worten, es bestehen hierarchische Beziehungen zwischen Datenelementen. Das bedeutet, dass ein Datenelement das Elternteil eines anderen Datenelements sein kann, das dann als Kind bezeichnet wird. Die Elemente werden auch als Baumebenen oder Knoten bezeichnet, und sie können drei Hauptformen annehmen:

• Wurzelknoten - Der erste Knoten, an dem der Eltern-Kind-Baum beginnt.
• Elternknoten - Jeder Knoten, der einen oder mehrere Nachkommen (oder Kindknoten) hat.
• Kindknoten - Jeder Knoten, der einen Vorgänger- oder Elternknoten hat.

Reale Beispiele für Eltern-Kind-Strukturen sind die Organisationsstrukturen von Unternehmen (ein Unternehmen besteht aus Abteilungen, die Abteilungen aus Teams und die Teams aus Mitarbeitern), Familienstammbäume (es gibt Eltern, Kinder, Enkel, Urenkel usw.) und natürliche Taxonomien (Lebewesen gehören zu einer Domäne, einem Königreich, Stamm, einer Klasse, Ordnung, Familie, Gattung und Art). Auch Computerordner (Festplatte C, Programmdateien, Microsoft SQL Server...), Speisekarten (Getränke, alkoholfreie Getränke, Tee...), Kunst- und Musikgenres (z. B. gab es den Blues, aus dem sich der Rhythm and Blues entwickelte, der zu Soul, Funk usw. führte) und Projekte (ein Projekt hat Unterprojekte, die wiederum Aufgaben, Unteraufgaben usw. haben) können als hierarchische Datenstrukturen betrachtet werden.

Eltern-Kind-Baumstruktur in relationalen Datenbanken

Damit SQL etwas damit anfangen kann, muss eine Eltern-Kind-Baumstruktur in einer relationalen Datenbank gespeichert sein.

Diese Strukturen werden normalerweise in einer Tabelle mit zwei ID-Spalten gespeichert, von denen eine auf eine übergeordnete Objekt-ID verweist. Damit lässt sich die Hierarchie zwischen den Daten bestimmen. Mit anderen Worten: Wir wissen, welcher Knoten ein übergeordneter Knoten zu welchem untergeordneten Knoten ist und umgekehrt.

Das mag etwas abstrakt klingen, deshalb zeige ich Ihnen anhand eines einfachen Beispiels, wie es funktioniert. Und ich werde es wörtlich nehmen! Meine Eltern-Kind-Baumstruktur wird Daten über Eltern und deren Kinder anzeigen. Sehen Sie sich das an:

Hier zeigt die Spalte id die ID des Kindes an. Um herauszufinden, wer der Elternteil dieses Kindes ist, müssen Sie in der Spalte parent_id die gleiche ID-Nummer in der Spalte id finden und in dieser Zeile nach dem Namen des Elternteils suchen.

Mit anderen Worten: Jim Cliffy hat keine Eltern in dieser Tabelle; der Wert in seiner Spalte parent_id ist NULL. Das bedeutet, dass er der Wurzelknoten in dieser Baumstruktur ist.

Mark Cliffy ist der Sohn von Jim Cliffy. Woher weiß ich das? Weil Marks parent_id = 1 die ID von Jim Cliffy ist. Mark Cliffy ist ein Kindknoten, aber er ist auch ein Elternknoten. Und warum? Weil Veronica Cliffy die Tochter von Mark Cliffy ist. Ich weiß das, weil ihr Elternteil parent_id = 2 hat, und die Tabelle sagt mir, dass das Mark Cliffy ist. Veronica Cliffy ist ein reiner Kindknoten; sie hat einen Elternknoten, aber es gibt keine Kindknoten, die von ihr abzweigen.

Typische Abfragen in einer Eltern-Kind-Baumstruktur

Ich verwende dieselbe Tabelle für jede dieser Abfragen. Sie hat dieselben Spalten wie oben gezeigt, nur mit mehr Zeilen und anderen Werten darin.

Einführung in die Beispieldaten

Die Tabelle hat den Namen parent_child und hat die folgenden Spalten:

• id - Die ID des Kindes und der Primärschlüssel (PK) der Tabelle.
• first_name - Den Vornamen des Kindes.
• last_name - Der Nachname des Kindes.
• parent_id - Die ID des Elternteils des Kindes.

Hier ist die gesamte Tabelle:

Sie können diese Tabelle verwenden, um zu überprüfen, ob die Abfragen, die ich gleich zeigen werde, die richtige Ausgabe liefern.

Beispiel 1: Alle Kinder von 1 Elternteil auflisten

Dies ist die einfachste Abfrage, daher werde ich sie verwenden, um Ihnen die Baumstruktur näher zu bringen. Hier möchte ich alle Kinder eines bestimmten Elternteils finden. In diesem Fall bin ich daran interessiert, alle Kinder einer Person namens Marge Wellington zu finden, deren ID 4 ist.

Hier ist die kleine Abfrage:

SELECT first_name,
	 last_name
FROM parent_child
WHERE parent_id = 4;

Ich habe einfach den Vor- und den Nachnamen aus der Tabelle ausgewählt und die WHERE Klausel verwendet, um nur Zeilen anzuzeigen, in denen eine 4 in der Spalte parent_id steht.

Das Ergebnis zeigt drei Zeilen an:

Es sagt mir, dass Bobby, Sammy und Sarah Wellington alle Kinder von Marge Wellington sind. Schauen Sie sich die Originaltabelle an, und Sie werden sehen, dass das stimmt.

Das war nur eine Aufwärmübung! Gehen wir zum nächsten Beispiel über.

Beispiel 2: Auflisten eines Elternknotens für einen Kindknoten

Die Ausgabe im vorherigen Beispiel war ein wenig, nun ja, einfach. Ich habe nur die Namen der Kinder aufgelistet. Es könnte wirklich hilfreich sein, auch den Namen des Elternteils anzuzeigen. Und genau das werde ich jetzt tun. Ich werde sowohl den Vornamen als auch den Nachnamen des Kindes und der Eltern anzeigen.

Anstatt nach den Kindern eines Elternteils zu suchen, werde ich nun nach den Eltern des Kindes suchen. Ich möchte herausfinden, wer der Elternteil von Sam Francis Dijkstra ist. Neben den Namen möchte ich auch die IDs sehen.

Die Abfrage dafür lautet:

SELECT child.id AS child_id,
	 child.first_name AS child_first_name,
	 child.last_name AS child_last_name,
	 parent.first_name AS parent_first_name,
	 parent.last_name AS parent_last_name,
	 parent.id AS parent_id
FROM parent_child child 
JOIN parent_child parent
  ON child.parent_id = parent.id
WHERE child.id = 11;

Das Hauptkonzept, das ich hier einführe, ist der Self-Join. Ich habe den Alias child für die parent_child Tabelle gegeben und sie mit sich selbst verbunden, indem ich den parent Alias. Auf diese Weise tue ich so, als ob ich mit zwei verschiedenen Tabellen arbeiten würde. Die eine enthält die Daten über die Kinder; deshalb habe ich ihr den Namen child. Die andere enthält Daten über die Eltern, deshalb habe ich ihr den Namen parent.

Die ausgewählten Spalten spiegeln dies wider. Die Namen und IDs der Kinder werden aus der "ersten" Tabelle ausgewählt. Die Namen und IDs der Eltern werden aus der "zweiten" Tabelle ausgewählt. Die "Tabellen" werden verbunden, wobei parent_id gleich id ist.

Die Originaltabelle sagt mir, dass die ID von Sam Francis Dijkstra 11 ist. Ich habe die WHERE Klausel verwendet, um die Daten zu filtern und nur die Eltern von Sam Francis anzuzeigen. Sie können auch die WHERE -Klausel für die Spalten child.first_name und child.last_name verwenden. Ich habe mich dafür entschieden, die Daten anhand der ID zu filtern, weil die Abfrage auf diese Weise ein wenig kürzer ist.

Hier ist die Ausgabe:

Sie zeigt, dass die Mutter von Sam Francis Mary Dijkstra ist, was auch stimmt.

Alles klar bis jetzt? Sehr gut. Weiter geht's!

Beispiel 3: Eine Generationsnummer (oder Baumebene) für jeden Knoten ermitteln

In diesem Beispiel möchte ich jede Person aus der Tabelle auflisten und anzeigen, zu welcher Generation sie gehört. Was ist der Zweck davon? Wenn ich diese Daten erhalte, kann ich leicht erkennen, wer zu welcher Generation gehört: Eltern, Kinder, Enkelkinder, usw.

Dazu verwende ich eine CTE - keine gewöhnliche CTE, sondern eine rekursive CTE. Wenn Sie Ihre CTE-Kenntnisse auffrischen möchten, finden Sie hier einen Artikel, der erklärt, was eine CTE ist.

Hier ist meine Abfrage:

WITH RECURSIVE generation AS (
	SELECT id,
		first_name,
		last_name,
		parent_id,
		0 AS generation_number
	FROM parent_child
	WHERE parent_id IS NULL

UNION ALL 

	SELECT child.id,
		child.first_name,
		child.last_name,
		child.parent_id,
		generation_number+1 AS generation_number
	FROM parent_child child
	JOIN generation g
	  ON g.id = child.parent_id
)

SELECT first_name,
	 last_name,
	 generation_number
FROM generation;

Wie jede rekursive CTE beginnt auch meine mit zwei Schlüsselwörtern: WITH RECURSIVE. Ich habe die CTE-Generation benannt. In der ersten SELECT Anweisung wähle ich IDs und Namen aus. Zusätzlich gibt es eine neue Spalte namens generation_number mit einer 0 für alle Zeilen, in denen parent_id = NULL steht. Warum NULL? Weil ich weiß, dass die Person, die der Vorgänger aller anderen Personen ist, kein Elternteil in der Tabelle hat. Daher muss der Wert NULL sein.

Ich verwende UNION ALL um das Ergebnis dieser Anweisung SELECT mit der zweiten Anweisung zusammenzuführen, die für die Rekursion zuständig ist. Damit UNION ALL funktioniert, müssen die Anzahl der Spalten und die Datentypen in beiden SELECT -Anweisungen gleich sein.

Das rekursive Mitglied wählt wiederum IDs und Namen aus. Außerdem gibt es die Spalte generation_number mit dem Wert generation_number+1. Bei jeder Rekursion wird 1 zum vorherigen Wert dieser Spalte hinzugefügt. Da die Abfrage mit 0 beginnt, ergibt die erste Rekursion eine 1 in der Spalte generation_number, die zweite eine 2 und so weiter.

Damit das alles funktioniert, habe ich die Tabelle parent_child mit der CTE selbst verbunden, wobei id = parent_id. Es gilt das gleiche Prinzip wie bei selbstverknüpfenden Tabellen: Die Tabelle dient als Daten über die Kinder, die CTE als Daten über die Eltern.

Nachdem ich die CTE geschrieben habe, muss ich ihre Daten verwenden. Dazu habe ich eine einfache SELECT -Anweisung geschrieben, die Namen und Generationsnummern aus der CTE zurückgibt. Gut gemacht, nicht wahr?

So sieht das Ergebnis aus:

Mit diesem Ergebnis sehe ich, dass Rosa Wellington der Wurzelknoten ist, weil ihre Generationsnummer 0 ist. Alle Personen mit dem Wert 1 sind ihre Kinder, Wert 2 sind Enkel und Wert 3 sind Urenkel. Wenn Sie dies in der Quelltabelle überprüfen, werden Sie feststellen, dass alles, was ich gesagt habe, wahr ist.

Beispiel 4: Alle Nachkommen auflisten

Dieses Beispiel ist eine Erweiterung des vorherigen. Ich möchte Ihnen zeigen, wie Sie alle Nachkommen eines Elternteils auflisten und sowohl die Namen der Eltern als auch die der Kinder anzeigen können.

Dies ist die Abfrage:

WITH RECURSIVE generation AS (
	SELECT id,
		 first_name,
		 last_name,
		 parent_id,
		 0 AS generation_number
	FROM parent_child
	WHERE parent_id IS NULL

UNION ALL 

	SELECT child.id,
		 child.first_name,
		 child.last_name,
		 child.parent_id,
		 generation_number+1 AS generation_number
	FROM parent_child child
	JOIN generation g
	  ON g.id = child.parent_id

)

SELECT	g.first_name AS child_first_name,
		g.last_name AS child_last_name,
		g.generation_number,
		parent.first_name AS parent_first_name,
		parent.last_name AS parent_last_name
FROM generation g
JOIN parent_child parent
ON g.parent_id = parent.id
ORDER BY generation_number; 

Wenn Sie diese Abfrage mit der vorherigen vergleichen, werden Sie feststellen, dass der CTE-Teil identisch ist. Ich brauche ihn nicht noch einmal durchzugehen.

Was anders ist, ist die SELECT Anweisung, die auf die CTE verweist. Aber auch hier gibt es keine neuen SQL-Konzepte. Die Abfrage wählt die Namen der Kinder und der Eltern und ihre Generationsnummer aus. Dazu habe ich wieder die CTE mit der Tabelle parent_child. Die CTE enthält Daten für Kinder, während die Tabelle Daten über Eltern enthält. Die letzte Codezeile ordnet das Ergebnis nach der Generationsnummer.

Die Abfrage liefert genau das, was ich wollte:

Oder doch nicht? Sicher, sie zeigt jedes Kind und den Namen des Elternteils an. Aber Rosa Wellington, der Stammknoten und die Matriarchin dieser Familie, fehlt. Und ich habe keine Filter angewandt, um sie auszuschließen.

Was ist passiert? Ich habe tatsächlich einen Filter angewendet, indem ich JOIN in der letzten Anweisung SELECT verwendet habe. Denken Sie daran, dass JOIN nur die übereinstimmenden Zeilen aus verbundenen Tabellen zurückgibt. Rosa Wellington fehlt, weil sie keine Daten über ihre Eltern hat; in ihrem Fall gibt es keine Daten, bei denen id mit parent_id übereinstimmen kann. Wenn Sie auch sie einbeziehen wollen, verwenden Sie LEFT JOIN in der letzten SELECT:

…
FROM generation g LEFT JOIN parent_child parent ON g.parent_id = parent.id
…

Und das vollständige Ergebnis finden Sie hier:

Wenn Sie mehr über diese komplexe Abfrage erfahren möchten, finden Sie hier einen Artikel zu diesem Beispiel.

Beispiel 5: Erzeugen einer Baumansicht von hierarchischen Daten

Das letzte Beispiel ist das komplexeste, aber es macht auch am meisten Spaß. Zumindest, was die Ausgabe betrifft. Es wäre eine Schande, Baumstrukturen abzufragen, ohne die Daten in einer Art Baumform darstellen zu können.

Die Aufgabe hier ist es, jede Person aus der Tabelle anzuzeigen. Außerdem muss jeder Nachkomme so dargestellt werden, dass grafisch ersichtlich ist, wessen Kind er ist und zu welcher Generation er gehört. Dies ist eine Baumansicht. Ich denke, es ist am besten, wenn Sie warten, bis ich zur Abfrageausgabe komme, um zu sehen, was ich damit meine.

Gehen wir an die Arbeit! Wieder rettet die rekursive CTE den Tag:

WITH RECURSIVE tree_view AS (
	SELECT id,
		 parent_id,
		 first_name,
		 last_name,
		 0 AS level,
		 CAST(id AS varchar(50)) AS order_sequence
	FROM parent_child
	WHERE parent_id IS NULL
	
UNION ALL

	SELECT parent.id,
		 parent.parent_id,
		 parent.first_name,
		 parent.last_name,
		 level + 1 AS level,
		 CAST(order_sequence || '_' || CAST(parent.id AS VARCHAR (50)) AS VARCHAR(50)) AS order_sequence
	FROM parent_child parent
	JOIN tree_view tv
	  ON parent.parent_id = tv.id
)

SELECT 
   RIGHT('------------',level*3) || first_name || ' ' || last_name 
     AS parent_child_tree
FROM tree_view
ORDER BY order_sequence;

Sie wissen bereits, wie rekursive Abfragen funktionieren. Diesmal heißt die CTE tree_view. Die erste Anweisung SELECT wählt einige Daten aus der Tabelle aus, in der parent_id NULL ist. Dort gibt es die Spalte level mit dem Wert 0. Und ich habe die Funktion CAST() verwendet, um den Datentyp id in VARCHAR zu ändern; Sie werden sehen, warum ich das brauche.

Wir verwenden erneut UNION ALL, um die Ergebnisse von zwei Abfragen zusammenzuführen. Die zweite SELECT Anweisung wählt wieder einige Daten aus, wobei die Tabelle parent_child verbunden mit der CTE selbst. Wichtig ist, dass bei jeder Rekursion 1 zur vorherigen Ebene hinzugefügt wird. Außerdem werden der Unterstrich und der Wert der Spalte id bei jeder Rekursion hinzugefügt. Ich brauche diesen kleinen Trick, weil ich diese Spalte später zum Sortieren der Ausgabe verwenden werde. Auf diese Weise kann ich die Baumansicht richtig darstellen. Damit Sie es verstehen, hier eine Zeile aus der Tabelle:

Der Spaltenwert für Frank Wellington wird 1_2_6 sein. Warum? Weil Rosa, als erste Ebene, den Wert 1 erhält. Jon Wellington ist ihr Sohn; seine ID geht an die order_sequence, die nun 1_2 wird. Dann wird Franks ID hinzugefügt und erhält den Wert 1_2_6. Wenn ich dies in der gesamten hierarchischen Struktur tue, erhalte ich die Spalte, die ich verwenden kann, um die Ausgabe auf die gewünschte Weise anzuzeigen.

Zurück zur Abfrage. Um das Ergebnis zu erhalten, benötigen Sie eine SELECT, die die CTE-Daten verwendet. Ich verwende hier die Funktion RIGHT(). Sie extrahiert eine bestimmte Anzahl von Zeichen aus der rechten Seite. In meinem Fall entfernt sie die Anzahl der Bindestriche der Ebene*3 für jede Ebene. Außerdem habe ich diese Bindestriche mit dem Vor- und Nachnamen verkettet. Das Ergebnis ist nach order_sequence sortiert.

Sind Sie bereit, die Baumansicht zu sehen? Hier ist sie:

Diese einfache grafische Darstellung zeigt ganz offensichtlich die Generationsstufen und wer wer in diesem Stammbaum ist. Anhand der Anzahl der Striche können Sie leicht erkennen, dass Jon, Joni und Marge Wellington die Kinder von Rosa sind. Mary Dijkstra, Frank, Jason, Sarah, Bobby und Sammy Wellington sind die Enkelkinder von Rosa. Es ist auch leicht zu erkennen, wer ihre Eltern sind. Sie können auch sehen, wer die Urenkel sind, aber das überlasse ich Ihnen.

Bevor ich zum Schluss komme, möchte ich Ihnen noch diesen Artikel empfehlen, in dem es um die Abfrage von Baumstrukturen in Oracle geht.

Die Abfrage von Eltern-Kind-Bäumen wird immer interessanter

Eltern-Kind-Baumstrukturen sind ziemlich spannend. Sie sind eine völlig andere Art von Daten als die, die man normalerweise in relationalen Datenbanken abfragt. Ich habe Ihnen gezeigt, was diese hierarchischen Strukturen sind und wie sie in einer Tabelle dargestellt werden.

Vor allem aber habe ich Ihnen fünf Abfragen gezeigt, mit denen Sie einige der häufigsten Probleme im Zusammenhang mit hierarchischen Daten lösen können. Wie Sie gesehen haben, sind CTEs und rekursive CTEs für die Abfrage von Eltern-Kind-Bäumen unerlässlich.

Ich bin sicher, dass Sie bei Ihrer Arbeit schon mit hierarchischen Daten zu tun hatten. Wahrscheinlich haben Sie erkannt, dass Sie sich mit detaillierten Kenntnissen über rekursive Abfragen ausstatten müssen, um mit solchen Daten umgehen zu können. Wir haben einen Rekursive Abfragen Kurs, der Sie systematisch durch CTEs im Allgemeinen, rekursive Abfragen und das Abfragen von hierarchischen Daten und Graphen in SQL führen wird.

Viel Erfolg beim Lernen! Und Sie können alle Abfragen, die ich Ihnen gezeigt habe, verwenden und an Ihre geschäftlichen Anforderungen anpassen.