Subsections

• 1 zufällige Daten auswählen
• 2 Nutzer in MySQL
• 3 PHPMyAdmin
• 4 Bäume in SQL
  • 1 Was ist ein Baum?
  • 2 Beispieldaten
  • 3 Baumdarstellung mit Vater-Zeiger
  • 4 Nested Set Modell
    • 1 Löschen
    • 2 Einfügen
  • 5 Übungen
    • 1 Vater-Zeiger
    • 2 Nested Set

6 Tips & Tricks

1 zufällige Daten auswählen

Häufig benötigt man ein paar zufällige Datensätze aus einer Tabelle, oder will die vorhandenen Datensätze zufällig sortiert anzeigen.

Es gibt verschiedene Lösungen. Ab MySQL-Version 3.23 ist das etwas einfacher geworden. Ab dieser Version ist es nämlich möglich, ORDER BY RAND() zu nutzen. RAND() ist eine MySQL-Funktion, die zufällige Werte produziert. Wenn nach der Ausgabe dieser Funktion sortiert wird, ergeben sich folglich zufällige Reihenfolgen.

Bei älteren Versionen funktioniert das nicht: wir müssen etwas in die Trickkiste greifen. Der Trick besteht darin, der ausgegebenen Tabelle eine Spalte mit den zufälligen Werten anzufügen. Das nächste Beispiel zeigt die Idee.

mysql> SELECT MNr,Name,RAND() AS sort
    -> FROM Mitarbeiter
    -> ORDER BY sort;
+-----+----------------+--------+
| MNr | Name           | sort   |
+-----+----------------+--------+
|   1 | Christoph Reeg | 0.8742 |
|   2 | junetz.de      | 0.5510 |
|   3 | Uli            | 0.1324 |
|   4 | JCP            | 0.0092 |
|   5 | Maier          | 0.6487 |
|   6 | Meier          | 0.2160 |
+-----+----------------+--------+
6 rows in set (0.00 sec)

Die Spalte sort enthält schon die Zufallswerte, aber noch wird nicht richtig danach sortiert. Sobald jedoch eine Spalte mit in die Berechnung von sort einbezogen wird, funktioniert das Ganze, wie im folgenden Beispiel zu sehen ist.

mysql> SELECT MNr,Name,0*MNr+RAND() AS sort
    -> FROM Mitarbeiter
    -> ORDER BY sort;
+-----+----------------+--------+
| MNr | Name           | sort   |
+-----+----------------+--------+
|   3 | Uli            | 0.8871 |
|   6 | Meier          | 0.0881 |
|   1 | Christoph Reeg | 0.7790 |
|   5 | Maier          | 0.6311 |
|   4 | JCP            | 0.8183 |
|   2 | junetz.de      | 0.1982 |
+-----+----------------+--------+
6 rows in set (0.00 sec)

Der Summand $0*MNr$ beeinflußt das Endergebnis nicht, trotzdem funktioniert das Sortieren.

Die Reihenfolge ist zufällig, auch wenn (komischerweise) nicht nach sort sortiert wurde.

Nachdem wir nun die zufällige Reihenfolge erhalten haben, können wir uns auch mit Hilfe von LIMIT (siehe auch 5.6.3) einen Datensatz ausgeben lassen.

Eine andere Möglichkeit, genau einen zufälligen Datensatz auszuwählen, wäre z.B. mit Hilfe von PHP: erst mit Hilfe von COUNT (siehe auch 5.7.5) bestimmen, wie viele Datensätze es gibt, dann mit PHP eine Zufallszahl bestimmen und genau den korrespondierenden Eintrag ausgeben. Funktioniert im Endeffekt genauso, ist nur etwas mehr Programmieraufwand. Was im Endeffekt schneller läuft, hängt von dem jeweiligen Datenbankdesign ab.

2 Nutzer in MySQL

Bei der Installation von MySQL wird standardmäßig ein Nutzer eingerichtet, der kein Paßwort, aber alle Rechte hat: Sein Name ist root. Mit diesem Nutzer solltest Du also, wenn Du einen eigenen (Offline-) Server betreibst, auf eine neu erstellte Datenbank problemlos zugreifen können.
Um die Datenbank effizient nutzen zu können, sollten allerdings später geeignete Nutzer angelegt werden, z.B. ein Abfragenutzer, der nur Leserechte hat und ein Adminnutzer, der vollen Zugriff auf die Datenbank hat. Generell müssen solche Nutzer dem MySQL-Ansatz der Rechtevergabe folgend in mysql.user (Datenbank mysql, Tabelle user) eingetragen werden. Aufgrund der Komplexität dieses Themas verweise ich aber an dieser Stelle nur auf das (englische) MySQL-Manual: Dort findest Du durch Suche nach dem Begriff privileges eine ausführliche Beschreibung, wie man entsprechende Anpassungen vornimmt.

3 PHPMyAdmin

PHPMyAdmin ist ein PHP-basiertes MySQL-Administrierungssystem, d.h. es stellt eine Möglichkeit dar, über einen gewöhnlichen Internet-Browser eine MySQL-Datenbank zu verwalten (Benutzer, Datenbanken, Tabellen und Datensätze anlegen, ändern und löschen). Dabei besteht die Möglichkeit, das System so einzurichten, daß alle MySQL-Nutzer eines Systems sich einloggen und dabei natürlich nur ihre eigenen Datenbanken (genauer: die, für die sie Rechte besitzen) sehen und bearbeiten können. Auch für den Systemverwalter gibt es einige Einstellungsmöglichkeiten wie das Anlegen neuer Nutzer inklusive dem obligatorischen MySQL-Neustart oder Rechtevergabe.

Richtig eingesetzt, kann PHPMyAdmin fast vollständig das mysql Kommandozeilenprogramm ersetzen, denn sogar Im- und Export von fertigen SQL-Dateien ist möglich. Von Vorteil ist natürlich die Umsetzung des Systems in HTML: Während beim Kommandozeilenprogramm schnell die Übersichtlichkeit verloren geht, wenn große Tabellen ausgegeben werden sollen, macht PHPMyAdmin von gewöhnlichen HTML-Tabellen Gebrauch und bietet dabei direkt sinnvolle Editiermöglichkeiten und Vereinfachungen.

Für Nutzer von Billig-Webhosting Angeboten ist ein Zugriff auf die mysql-Kommandozeile gar nicht möglich und dadurch PHPMyAdmin eine sehr einfache Alternative, trotzdem entsprechende Möglichkeit zu bekommen.

Auf der PHPMyAdmin-Homepage http://www.phpmyadmin.net/ finden sich immer die aktuellen Versionen des Pakets. Zu beachten ist, daß es Versionen für zwei verschiedene Endungen (.php und .php3) gibt. Dies ist dann von besonderem Interesse, wenn, wie beim Jugendnetz Frankfurt/Offenbach, verschiedene Endungen verschiedenen PHP-Interpreter-Versionen zugeordnet sind. Dem Paket liegt zwar ein Script zum Ändern der Endungen in frei wählbare bei, dieses funktioniert aber leider nur mit der Bash, also i.A. nicht unter Windows. Ist also z.B. die Verwendung der Endung .php4 gewünscht, so ist Zugang zu einem Unix-basierten System von Vorteil. ;-)

Wenn man nachfragt, ist bei Anbietern von serverseitiger PHP- und MySQL-Unterstützung oftmals PHPMyAdmin schon deshalb installiert, damit die Administratoren selbst effizienter arbeiten können - so auch bei uns. Im Zweifelsfall lohnt es sich, einfach mal zu fragen, ob dieses System angeboten wird und für Mitglieder auch frei verfügbar ist. Für letzteres ist nämlich nicht viel zu machen, lediglich ein Nutzer mit Leserechten auf die mysql-Datenbank muß angelegt werden, was auch kein Sicherheitsrisiko darstellt angesichts der Tatsache, daß die dort abgelegten Paßworte durch den verwendeten Verschlüsselungs-Algorithmus praktisch unknackbar sind.

Sollten noch Fragen offen bleiben, die auch die PHPMyAdmin-eigene Dokumentation nicht beantworten kann und die von allgemeinem Interesse sind, kannst Du diese gerne an die vorne angegebene eMail-Adresse schicken. Auf diese Weise halten häufig gestellte Fragen (FAQ) sicher Einzug in spätere DSP-Versionen.

4 Bäume in SQL

An der ein oder anderen Stelle hat man das Problem, daß man eine Baumstruktur in einer SQL-Datenbank speichern will. Jeder kennt mindestens eine Baumstruktur von seinem Computer, nämlich den Verzeichnisbaum. Die eine oder andere Datenbank bietet dazu proprietäre Funktionen (z.B. Oracle), andere nicht (z.B. MySQL). Im Laufe der Zeit wurden hier entsprechende Varianten entworfen, um trotzdem Bäume abspeichern zu können. Ich werde hier einige vorstellen und die jeweiligen Vor- und Nachteile aufzuzeigen versuchen.

1 Was ist ein Baum?

Jeder kennt sicher die natürliche Variante (die mit den komischen grünen Blättern). Der Informatiker dagegen versteht i.A. etwas anderes unter einem Baum. Es gibt natürlich auch verschiedene Definitionen, was ein Baum ist.

Ein Baum ist ein ungerichteter, zyklenfreier, zusammenhängender Graph.

Ein Baum ist ein azyklischer Graph, in dem genau ein Knoten keinen Vorgänger hat und alle anderen Knoten mindestens einen Vorgänger haben.

Die letzte Definition kann man sogar fast verstehen, trotzdem versuche ich es anders zu erklären.

Bei dem guten alten DOS gab es ein Laufwerk C:, auf dem verschiedene Verzeichnisse (z.B. DOS und WIN) existierten, die wieder Unterverzeichnisse hatten (z.B. SYSTEM im WIN-Verzeichnis). Wenn man nun C: als Wurzel bezeichnet und DOS und WIN als Nachfolger von C:, sowie SYSTEM als Nachfolger von WIN hat man einen Baum.

An Stelle von Nachfolger und Vorgänger wird auch häufig Sohn und Vater gesagt. Die Elemente in der Mitte des Baumes werden Knoten genannt und die Elemente ohne Nachfolger heißen Blätter.

2 Beispieldaten

In diesem Kapitel werde ich von einem Beispielbaum ausgehen, wo ich die Elemente so benannt habe, daß eigentlich klar sein sollte, wo sie sich im Baum befinden sollten. In Abbildung 6.1 habe ich den Baum einmal grafisch dargestellt.

Figure 6.1: Unser Baum-Beispiel

3 Baumdarstellung mit Vater-Zeiger

Eine sehr beliebte Variante zur Baumdarstellung ist, die einzelnen Knoten mit einer eindeutigen ID zu versehen und dann bei jedem Knoten die jeweilige Vater-ID zu speichern. Da über die Vater-ID auf den Vater (übergeordneter Knoten) gezeigt wird, ergibt sich die Bezeichnung Baumdarstellung mit Vater-Zeiger. Konkret ergeben sich daraus die Werte in Tabelle 6.1, wobei eine Vater-ID mit 0 bedeutet, daß es die Wurzel ist.

Table 6.1: Baumdarstellung mit Vater-Zeiger

ID	Name	Vater-ID
1	Root	0
2	A	1
3	B	1
4	C	1
5	A1	2
6	B1	3
7	B2	3
8	C1	4
9	A1I	5
10	C1I	8
11	C1II	8

Der Vorteil dieser Variante ist das relativ einfache Erstellen des Baumes. Auch ist er relativ robust gegen falsche Daten; eine falsche Vater-ID führt nur zu einem falsch angehängten Ast, aber ansonsten ist noch alles OK. Auch das Umhängen von einzelnen Ästen ist relativ einfach. Das große Problem kommt allerdings z.B. bei der Ausgabe des Gesamtbaumes, bei der Bestimmung der maximalen Tiefe, oder beim Festellen, ob ein Knoten noch Söhne hat. Siehe dazu auch die Übung

4 Nested Set Modell

Eine andere sehr elegante Methode für Baumstrukturen ist das Nested Set Model, das den Baum als Summe von Menge betrachtet. Dies hat den Vorteil, daß mit relationalen Datenbanken sehr effizient damit gearbeitet werden kann, da Mengen Relationen sind.

Diese Variante habe ich auf der Homepage von Kristian Köhntopp (http://www.koehntopp.de/ kennen gelernt. Die dort liegenden Folien sind jedoch zum Verstehen etwas knapp gehalten, so daß ich hier versuche, das etwas ausführlicher zu zeigen.

Wie aber funktioniert das nun? Wir betrachten den Baum als Summe sich überlappender Mengen, wobei immer ein Knoten mit allen Nachfolgern eine Menge bildet. D.h. das Element Root bildet eine Menge, in der alle anderen Elemente enthalten sind; bei A sind nur die Elemente A1 und A1I enthalten usw.

Das Ganze ist in Abbildung 6.2 grafisch dargestellt.

Figure 6.2: Baumdarstellung als Summe von Mengen

Jetzt stellt sich nur noch die Frage, wie man dieses Mengenkonstrukt optimal in die Datenbank bringt. Nichts leichter als das: Jedes Element bekommt zwei zusätzliche Felder; ich nenne sie einfach mal l und r. Dann nehme ich wieder die Abbildung 6.1, fange bei der Wurzel an und schreibe in das Feld l eine 1, gehe dann zu dem linken Nachfolger und schreibe dort in das Feld l eine 2 usw. bis ich unten angekommen bin. Dort schreibe ich in das Feld r eine 5 und gehe wieder zählend hoch. Wer dem jetzt nicht folgen konnte: Keine Angst, in Abbildung 6.3 ist das Ganze grafisch dargestellt und dann sollte es eigentlich klar werden.

Figure 6.3: Baumdarstellung im Nested Set Modell

Die an dieser Stelle wichtigste Abfrage, ob ein Element Nachfolger eines anderen ist (gleichbedeutend mit in der Menge enthalten), läßt sich mit BETWEEN erledigen.

Aber nun genug der Theorie, setzen wir das Ganze in SQL um. Dazu als erstes unser CRETE TABLE mit den INSERT Anweisungen:

CREATE TABLE NestedSet (
  ID    int not null primary key,
  Name  varchar(100),
  l     int,
  r     int
);

INSERT INTO NestedSet VALUES (1,'Root',1,22);
INSERT INTO NestedSet VALUES (2,'A',2,7);
INSERT INTO NestedSet VALUES (3,'B',8,13);
INSERT INTO NestedSet VALUES (4,'C',14,21);
INSERT INTO NestedSet VALUES (5,'A1',3,6);
INSERT INTO NestedSet VALUES (6,'B1',9,10);
INSERT INTO NestedSet VALUES (7,'B2',11,12);
INSERT INTO NestedSet VALUES (8,'C1',15,20);
INSERT INTO NestedSet VALUES (9,'A1I',4,5);
INSERT INTO NestedSet VALUES (10,'C1I',16,17);
INSERT INTO NestedSet VALUES (11,'C1II',18,19);

Wie schön diese Struktur ist, zeigt folgende Abfrage:

mysql> SELECT v.Name AS Vater, s.Name AS Nachfolger
    ->   FROM NestedSet v, NestedSet s
    ->  WHERE s.l BETWEEN v.l AND v.r
    ->   ORDER BY s.l, v.l;
+-------+------------+
| Vater | Nachfolger |
+-------+------------+
| Root  | Root       |
| Root  | A          |
| A     | A          |
| Root  | A1         |
| A     | A1         |
| A1    | A1         |
| Root  | A1I        |
| A     | A1I        |
| A1    | A1I        |
| A1I   | A1I        |
| Root  | B          |
| B     | B          |
| Root  | B1         |
| B     | B1         |
| B1    | B1         |
| Root  | B2         |
| B     | B2         |
| B2    | B2         |
| Root  | C          |
| C     | C          |
| Root  | C1         |
| C     | C1         |
| C1    | C1         |
| Root  | C1I        |
| C     | C1I        |
| C1    | C1I        |
| C1I   | C1I        |
| Root  | C1II       |
| C     | C1II       |
| C1    | C1II       |
| C1II  | C1II       |
+-------+------------+
31 rows in set (0.01 sec)

Ich bekomme mit einer Abfrage das Ergebnis, wer alles Vorgänger zu einem bestimmten Knoten ist.

Durch eine entsprechende Eingrenzung kann man sich auch alle Vorgänger zu genau einem Knoten ausgeben lassen:

mysql> SELECT v.Name AS Vater, s.Name AS Nachfolger
    ->   FROM NestedSet v, NestedSet s
    ->  WHERE s.l BETWEEN v.l AND v.r
    ->    AND s.Name = 'C1I'
    ->   ORDER BY v.l;
+-------+------------+
| Vater | Nachfolger |
+-------+------------+
| Root  | C1I        |
| C     | C1I        |
| C1    | C1I        |
| C1I   | C1I        |
+-------+------------+
4 rows in set (0.00 sec)

Die Abfrage, wie viele Nachfolger ein Knoten hat, läßt sich ganz einfach über die Differenz von l und r feststellen.

mysql> SELECT (r-l-1)/2 AS Nachfolger, Name
    -> FROM NestedSet
    -> ORDER BY l;
+------------+------+
| Nachfolger | Name |
+------------+------+
|      10.00 | Root |
|       2.00 | A    |
|       1.00 | A1   |
|       0.00 | A1I  |
|       2.00 | B    |
|       0.00 | B1   |
|       0.00 | B2   |
|       3.00 | C    |
|       2.00 | C1   |
|       0.00 | C1I  |
|       0.00 | C1II |
+------------+------+
11 rows in set (0.00 sec)

Auch sehr interessant: alle Knoten, mit ihrer Tiefe:

mysql> SELECT s.Name, count(*) AS Level
    ->   FROM NestedSet v, NestedSet s
    ->  WHERE s.l BETWEEN v.l AND v.r
    ->  GROUP BY s.l;
+------+-------+
| Name | Level |
+------+-------+
| Root |     1 |
| A    |     2 |
| A1   |     3 |
| A1I  |     4 |
| B    |     2 |
| B1   |     3 |
| B2   |     3 |
| C    |     2 |
| C1   |     3 |
| C1I  |     4 |
| C1II |     4 |
+------+-------+
11 rows in set (0.00 sec)

Bevor wir den Baum gleich durch Löschen & Co verändern, gibt es auch hier Übungen ( zum Vertiefen. Keine Angst, falls das Ganze noch nicht klar geworden ist; mit der Zeit kommt das Verständnis für diese Struktur.

1 Löschen

So schön diese Methode auch zum Abfragen ist, so schwierig ist sie beim Ändern der Datenstruktur. Man muß immer aufpassen, keinen der Zeiger falsch zu belegen, weil sonst der ganze Baum durcheinander kommt.

Vom Prinzip sind folgende Schritte notwendig:

• Sperren der Tabelle
• l und r von dem zu löschenden Element auslesen
• Element löschen
• l und r der Nachfolger um 1 reduzieren
• l und r des rechten Nachbarbaums um 2 reduzieren ( r im Vaterknoten nicht vergessen!)
• Tabelle wieder freigeben

Um das zu verstehen, ist es hilfreich, sich einfach mal ein Blatt Papier und einen Stift zu nehmen und das exemplarisch durchzugehen.

Wir machen das jetzt hier in SQL, indem wir aus dem Beispiel den Knoten B löschen. Die beiden Nachfolger B1 und B2 sollen dann direkt unter Root hängen.

Als erstes verhindern wir, daß durch einen evtl. parallelen Löschvorgang die Tabelle durcheinander kommt, indem wir sie sperren.

mysql> LOCK TABLE NestedSet WRITE;
Query OK, 0 rows affected (0.00 sec)

Nun brauchen wir l und r von unserem Element:

mysql> SELECT l,r
    ->   FROM NestedSet
    ->  WHERE Name = 'B';
+------+------+
| l    | r    |
+------+------+
|    8 |   13 |
+------+------+
1 row in set (0.00 sec)

Diese müssen wir uns nun merken.

Den Knoten zu löschen, sollte kein großes Problem sein:

mysql> DELETE FROM NestedSet         
    ->  WHERE Name = 'B';
Query OK, 1 row affected (0.01 sec)

Kommen wir nun zu den Nachfolgern (hier B1 und B2), zu erkennen an deren l bzw. r, die zwischen 8 und 13 (siehe letzte Abfrage) liegen.

mysql> UPDATE NestedSet
    ->    SET l=l-1, r=r-1
    ->  WHERE l BETWEEN 8 AND 13;
Query OK, 2 rows affected (0.00 sec)
Rows matched: 2  Changed: 2  Warnings: 0

Nicht zu vergessen der rechte Nachbarbaum (in diesem Fall alle C* Elemente).

mysql> UPDATE NestedSet
    ->    SET l=l-2       
    ->  WHERE l > 13;
Query OK, 4 rows affected (0.00 sec)
Rows matched: 4  Changed: 4  Warnings: 0

mysql> UPDATE NestedSet
    ->    SET r=r-2
    ->  WHERE r > 13;
Query OK, 5 rows affected (0.00 sec)
Rows matched: 5  Changed: 5  Warnings: 0

Und als letzter wichtiger Schritt muß natürlich noch die Tabelle wieder freigegeben werden.

mysql> UNLOCK TABLES;
Query OK, 0 rows affected (0.00 sec)

Das war jetzt das Löschen eines Elements. Wer das Prinzip des Baumaufbaus verstanden hat, kann sich auch noch davon überzeugen, daß es tatsächlich funktioniert hat.

mysql> SELECT * 
    ->   FROM NestedSet 
    ->  ORDER BY l;
+----+------+------+------+
| ID | Name | l    | r    |
+----+------+------+------+
|  1 | Root |    1 |   20 |
|  2 | A    |    2 |    7 |
|  5 | A1   |    3 |    6 |
|  9 | A1I  |    4 |    5 |
|  6 | B1   |    8 |    9 |
|  7 | B2   |   10 |   11 |
|  4 | C    |   12 |   19 |
|  8 | C1   |   13 |   18 |
| 10 | C1I  |   14 |   15 |
| 11 | C1II |   16 |   17 |
+----+------+------+------+
10 rows in set (0.00 sec)

Löschen von ganzen Teilbäumen funktioniert analog. Schritt 3 kann dabei allerdings entfallen (es gibt ja keinen Nachfolger mehr) und bei Schritt 4 muß man nicht 2, sondern entsprechend der entfernten Elemente subtrahieren.

2 Einfügen

Das Einfügen funktioniert im Prinzip analog zum Löschen, man muß die Schritte nur in der umgekehrten Reihenfolge durchlaufen.

5 Übungen

1 Vater-Zeiger

Um den Rest machen zu können, muß erstmal die Tabelle 6.1 angelegt werden.

Nachdem die Tabelle nun existiert, kommen wir zu den häufigsten Abfragen (Lösung im Anhang B.1.1):

• Gib die Wurzel aus
• Wie viele Söhne hat die Wurzel?
• Welches sind die Söhne der Wurzel?
• Gib die Wurzel mit den Söhnen aus
• Gib den kompletten Baum aus, so daß etwa das Folgende herauskommt:

  +-------+------+
  | Tiefe | Name |
  +-------+------+
  |     0 | Root |
  |     1 | A    |
  |     2 | A1   |
  |     3 | A1I  |
  |     1 | B    |
  

  Also immer der Vaterknoten, gefolgt von den Söhnen mit Angabe der Tiefe. Die Abfrage soll allgemein sein, also auch bei größeren Tiefen funktionieren.

2 Nested Set

Etliche Abfragen wurden schon gezeigt, von daher kommen hier nur noch ein paar richtig schöne (und damit nicht ganz einfache).

• Um einen Baum sauber in HTML ausgeben zu können, braucht man folgende Informationen: Name des Elements, Anzahl der Nachfolger (bzw. gibt es einen oder keinen), die Tiefe des Elements und ob es auf gleicher Tiefe noch ein Element gibt. Oder andersherum ausgedrückt, folgende Tabelle enthält alle notwendigen Informationen. Wie sieht die dazu passende Abfrage aus?

  +------+------------+-------+--------+
  | Name | Nachfolger | Tiefe | Bruder |
  +------+------------+-------+--------+
  | Root |      10.00 |     1 |      0 |
  | A    |       2.00 |     2 |      1 |
  | A1   |       1.00 |     3 |      0 |
  | A1I  |       0.00 |     4 |      0 |
  | B    |       2.00 |     2 |      1 |
  | B1   |       0.00 |     3 |      1 |
  | B2   |       0.00 |     3 |      0 |
  | C    |       3.00 |     2 |      0 |
  | C1   |       2.00 |     3 |      0 |
  | C1I  |       0.00 |     4 |      1 |
  | C1II |       0.00 |     4 |      0 |
  +------+------------+-------+--------+