Hierarchische Strukturen und Bäume in MySQL (Rekursion)

Hierarchische Strukturen werden in Datenbanken oft mithilfe einer parentID umgesetzt. Man hat zu jedem Eintrag einen übergeordneten Eintrag, außer beim Wurzelelement. Diese parentID kommt zum Einsatz, da es sich laut ERM um eine Relation – besser 1:1-Beziehung – eines Eintrages der Tabelle mit einem anderen Eintrag der gleichen Tabelle handelt.
Da sich solche mathematischen Sachverhalte am verständlichsten mit einem Beispiel erklären lassen, wollen wir die Kategorien-Tabelle eines Online-Shops nehmen. Es gibt also zum Beispiel die Oberkategorien Lebensmittel und Kleidung. Als Unterkategorien haben wir Getränke, Gemüse und Obst. Gemüse hat zusätzlich die Unterkategorien Broccoli und Kohlrabi. Unter Obst hängen Pfirsich und Orange. Der gesamte Kategoriebaum wird im Baum-Schema deutlich.
Daraus lässt sich ein DHTML-Menü erstellen, das ähnlich wie das Windows-Startmenü zuerst alle Hauptkategorien auflostet und wenn man mit der Maus über eine Hauptkategorie fährt, klappen die Unterkategorien aus. Ein Script für hierarchische Menüs soll hier allerdings nicht weiter diskutiert werden. Als Beispiel und Verdeutlichung möchte ich noch das Menü auf der linken Seite eines großen Kleinanzeigenmarktes erwähnen – da sieht man recht deutlich, worum es geht: den Aufbau des Menüs.
Mit einfachem HTML verdeutlicht soll in unserer Datenbank-Tabelle folgende Struktur abgebildet werden:

• Lebensmittel
  • Getränke
  • Gemüse
    • Broccoli
    • Kohlrabi
  • Obst
    • Pfirsich
    • Orange
• Kleidung
  • Herrenkleidung
  • Damenkleidung

Die Datenbank sieht nach ERM-Modell mit der Spalte parentID also so aus (Reihenfolge willkürlich gewählt):

Die Hauptkategorien haben die parentID 0. Wir brauchen also eine Funktion, die den Baum komplett aufbaut. Bei genauem Hinsehen sieht man, dass diese rekursiv sein muss, denn wenn wir alle Kinder von einer Hauptkategorie selektieren, brauchen wir ja auch die Kinder von den selektierten Kinder – sozusagen die Kindes-Kinder = Enkel ????

Die PHP-Funktionen dafür sehen so aus:

  
  function getMenu($oberkat) {
    $einlesen = mysql_query("SELECT ID,name FROM kategorien WHERE parentID='".$oberkat."' ORDER BY name");
    $menu = "";
    while($einzeln = @mysql_fetch_assoc($einlesen)) {
      if(hasChildKats($einzeln['ID'])) {
        $menu .= "
".$einzeln['name']."
";
        $menu .= getMenu($einzeln['ID']);
        $menu .= "
";
      } else {
        $menu .= "
".$einzeln['name']."
";
      }
    }
    return $menu;
  }
 
  function hasChildKats($katID) {
    $einlesen = mysql_query("SELECT ID FROM kategorien WHERE parentID='".$katID."'");
    if(mysql_num_rows($einlesen)>0) return true; else return false;
  }

Wir selektieren erst alle Kinder einer Ebene, dann die Kinder der selektierten Einträge usw. Die Verzweigung mit der Prüfung, ob eine selektierte Kategorie noch weitere Kinder hat, ist nötig, da eine leere Liste (UL) nicht html-konform ist.

Funktionieren tut diese Abfrage, sie entspricht auch der Normalformenlehre und trotzdem gibt es an diesem Weg etwas zu kritisieren: Rekursion und SQL-Abfragen innerhalb einer Schleife sollten unbedingt – wenn möglich – vermieden werden. Da bei größeren Datenmenge bzw. einer tieferen Baumstruktur eine Unmenge an Abfragen an die Datenbank abgesetzt werden, wird der ganze Prozess sehr langsam. Wenn Sie schon etwas fortgeschrittener im Umgang mit SQL sind, empfehle ich deshalb das Nested Sets-Modell, das wesentlich besser skaliert.