Bäume in SQL (MySQL)

Bäume

Um große Datenstrukturen in einzelne Zeilen einer Tabelle zu zerlegen, halte man Ausschau nach wiederkehrenden Strukturen gleicher Art.

Manchmal sollen Informationen einer sogenannte Baumstruktur gespeichert werden. Eine Baumstruktur wird auch kurz als Baum  bezeichnet. (Man denke beispielsweise an einen Stammbaum.)

Bei einem Baum haben Punkte verschiedene Unterpunkte. Beispielsweise können wir Tiere betrachten:

                                   Tier
                                    ^
                                    |
                .-------------------'-------------------.
                |                                       |
              Hund                                    Katze
                ^                                       ^
                |                                       |
       .--------'--------.                     .--------'--------.
       |                 |                     |                 |
  Terrier            Retriever               Siam             Burmilla

Es gibt verschiedene Möglichkeiten, wie solche Bäume in Tabellen gespeichert werden können. Eine einfache Möglichkeit besteht darin, zu jedem Tier seinen Oberbegriff zu erfassen.

DROP SCHEMA S; CREATE SCHEMA S; USE S;
CREATE TABLE TIER ( NAME VARCHAR ( 255 ), OBERBEGRIFF VARCHAR ( 255 )); 
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Terrier',   'Hund'  );
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Retriever', 'Hund'  );
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Siam',      'Katze' );
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Burmilla',  'Katze' );
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Hund',      'Tier'  );
INSERT INTO TIER ( NAME, OBERBEGRIFF ) VALUES ( 'Katze',     'Tier'  );
SELECT * FROM TIER;

+-----------+-------------+
| NAME      | OBERBEGRIFF |
+-----------+-------------+
| Terrier   | Hund        |
| Retriever | Hund        |
| Siam      | Katze       |
| Burmilla  | Katze       |
| Hund      | Tier        |
| Katze     | Tier        |
+-----------+-------------+

Die folgenden Abfrage gibt nun alle direkten Unterbegriffe zu »TIER« aus:

SELECT NAME AS NAME1 FROM TIER WHERE OBERBEGRIFF = 'TIER';

+--------+
| NAME1  |
+--------+
| Hund   |
| Katze  |
+--------+

Die folgenden Abfrage gibt alle direkten Unterbegriffe zu allen direkten Unterbegriffe von »TIER« aus.

In den Klammern steht die oben gezeigte Abfrage.

SELECT NAME 
FROM 
  TIER,
  ( SELECT NAME AS NAME1 FROM TIER WHERE OBERBEGRIFF = 'TIER' ) AS TIER1
WHERE OBERBEGRIFF = NAME1;

+-----------+
| NAME      |
+-----------+
| Terrier   |
| Retriever |
| Siam      |
| Burmilla  |
+-----------+

Für die nächste verschachtelte Abfrage zeigen wir zunächst das Ergebnis der Unterabfrage.

SELECT NAME AS NAME1, OBERBEGRIFF AS OBEROBERBEGRIFF FROM TIER WHERE OBERBEGRIFF = 'TIER';

+-------+-----------------+
| NAME1 | OBEROBERBEGRIFF |
+-------+-----------------+
| Hund  | Tier            |
| Katze | Tier            |
+-------+-----------------+

Die folgenden Abfrage zeigt, daß man den Baum in diesem Fall aus der Tabelle rekonstruieren kann. Der Pfeil der Abbildung entspricht dabei der WHERE-Klausel.

  TIER                         TIER1
.-------------------------.   .-------------------------.
| NAME      | OBERBEGRIFF |   | NAME1 | OBEROBERBEGRIFF |
|-------------------------|   |-------------------------|
| Terrier   | Hund     ------>| Hund  | Tier            |
| Retriever | Hund        |   | Katze | Tier            |
| Siam      | Katze       |   '-------------------------'
| Burmilla  | Katze       |
| Hund      | Tier        |
| Katze     | Tier        |
'-------------------------'

SELECT OBEROBERBEGRIFF, OBERBEGRIFF, NAME 
FROM 
  TIER,
  ( SELECT NAME AS NAME1, OBERBEGRIFF AS OBEROBERBEGRIFF FROM TIER WHERE OBERBEGRIFF = 'TIER' ) AS TIER1
WHERE OBERBEGRIFF = NAME1;

+-----------------+-------------+-----------+
| OBEROBERBEGRIFF | OBERBEGRIFF | NAME      |
+-----------------+-------------+-----------+
| Tier            | Hund        | Terrier   |
| Tier            | Hund        | Retriever |
| Tier            | Katze       | Siam      |
| Tier            | Katze       | Burmilla  |
+-----------------+-------------+-----------+

Übungsaufgaben

/   Listen

Unter einer Liste wollen wir eine lineare Abfolge von Einträgen verstehen, bei denen fast jeder einen Vorgänger und einen Nachfolger hat (außer dem ersten und dem letzten).

Das Speichern einer Liste in einer Tabelle ist nicht so einfach, wie man vielleicht denken könnte, denn die einzelnen Zeilen werden ja nicht in einer bestimmten Reihenfolge gespeichert, obwohl sie in einer Reihenfolge ausgegeben werden. Außerdem soll es auch möglich sein, später noch Einträge aus der Liste zu entfernen oder an einer bestimmten Stelle zu der Liste hinzuzufügen.

Die folgende Liste von Wörtern soll in einer Tabelle gespeichert werden:

.----------.    .----------.    .----------.
| Tisch    |--->| Garten   |--->| Haus     |
'----------'    '----------'    '----------'

Es soll dann durch Abfragen möglich sein die folgenden Tabellen daraus zu erhalten:

Eine Tabelle der Nachfolger:

+------------------+--------------------+
| EINTRAG          | NACHFOLGER         |
+------------------+--------------------+
| Tisch            | Garten             |
| Garten           | Haus               |
+------------------+--------------------+

Eine Tabelle der Vorgänger:

+------------------+--------------------+
| EINTRAG          | VORGAENGER         |
+------------------+--------------------+
| Garten           | Tisch              |
| Garten           | Haus               |
+------------------+--------------------+

Die Reihenfolge  der ausgegebenen Zeilen darf – wie bei den meisten Übungsaufgaben – auch anders sein.

Überlegen Sie sich, wie solch eine Liste als Tabelle abgespeichert werden kann, so daß die beiden obigen Abfragen möglich sind und möglichst wenig Information mehrfach abgespeichert wird.

Legen Sie dann eine entsprechende Tabelle an und schreiben Sie Abfragen zur Ausgabe der Tabelle der Nachfolger und der Tabelle der Vorgänger.

(Eine Information ist dabei nicht ein einzelnes Wort, sondern erst die Paarung mehrerer Wörter in einer Zeile.)